High performance number theoretic transforms in cryptography

Thesis Type: Doctorate

Institution Of The Thesis: Middle East Technical University, Turkey

Approval Date: 2020

Student: Metin Evrim Ulu

Supervisor: MURAT CENK


Theoretical advances in physics opened up a new window into quantum computation. This window rendered a number of mathematically hard problems unusable for cryptographic applications. For instance, Shor showed that it is possible factor integers by a quantum algorithm efficiently thus rendering the standard public-key encryption scheme RSA insecure. In February 2016, NIST launched a standardization process for post-quantum cryptography algorithms to study the effect of quantum computing on the current generation of cryptographic algorithms and to build the next generation cryptosystems that are resistant to quantum attacks. One type of quantum safe cryptographic systems is based on lattices. In order to improve the performance in lattice based systems, Number Theoretic Transforms (NTT) are used. In this thesis, the performance of NTT in cryptography is studied. First, Peikert’s Scheme and its realization BCNS Algorithm and NewHope key encapsulation method is discussed. Next, SWIFFTX hash function that uses NTT as a building block is presented. Finally, an efficient GPU implementation of SWIFFTX hash function is provided. Experimental results indicate almost 10x improvement in speed and 5 Watts decrease in power consumption per 2^16 hashes.