IMPROVING CRYPTANALYSIS OF LATTICE-BASED CRYPTOGRAPHY USING GPU

Abstract

For the last few decades, the public-key cryptosystems based on the inte- ger factorization problem, the discrete logarithm problem and the elliptic curve problem have been considered among the most secure public key cryptosystems. Recently, the emergence of the quantum computing [40] has posed a major threat to these types of cryptosystems. In fact, there is no physical implementation of the quantum computing due to no exis- tence of quantum computers until now. The wide evolution of the tech- nology increases the feeling that the emerging of the quantum computers is not far off. As precautionary measures, the researchers started seek- ing alternatives for unsecure cryptosystems in quantum computing. The most promising cryptosystems are those based on lattice problems such as GGH [34], NTRU [39] and recently Regev cryptosystems [49, 62]. The lattice problems are known to be post-quantum problems [63]. Up to now, there is no quantum algorithm that can solve the lattice problems in polynomial time. GPU as a new promising technology with high com- putation power, opens a new trend for the researchers in the domain of parallel computation, it even enforces them to reconsider the method of treating the problem in parallelism. We investigate the high computation power of GPU to improve algorithms that solves some lattice problems. We present a GPU-based parallel algorithm for LWE problem using a lattice-based BDD approach. In addition, we proposed three strategies for improving shortest vector enumeration using GPU. Finally, we show the scalability of our improvements by using multi-GPUs.