Accelerating Lattice-based Cryptography with GPUs
Lattice-based cryptography has received a growing interest due to the threat of quantum computers. Unlike more widely adopted and known public-key cryptosystems based on RSA and Elliptic-Curves, many of lattice-based constructions are resistant to both classical and quantum attacks. Over last decades, many cryptosystems are built with security based on well-studied lattice problems. One plausible instance is fully homomorphic encryption that was for the first time proposed in 2009. Fully homomorphic encryption, despite being powerful as it is, magnified the common problem of lattice-based cryptographic constructions - inefficiency.
In this dissertation we make efforts to tackle the efficiency problems of several lattice-based cryptography schemes by exploiting CUDA-enabled GPUs. Since most efficient lattice-based schemes rely on polynomial arithmetic. We investigated existing optimizations for fast polynomial arithmetic, chose and customized a combination of them to implement on GPUs, and built core arithmetic libraries from the scratch. This became the fundamental acceleration engine of more complex cryptography schemes. For homomorphic encryption schemes where efficiency is a major roadblock of its practicality, we designed software libraries to accelerate homomorphic evaluation, and have achieved 1--2 orders of magnitude of speedup compared to previous implementations on CPUs.
We experimented with a more practical lattice-based signature scheme and proposed an alternative solution for CUDA-enabled GPUs.
The performance gain we presented shows the great potential of hardware acceleration and provides an advantageous starting point for future research on accelerating lattice-based cryptography with alternative hardware platforms such as GPUs, FPGAs and ASICs.
Professor Berk Sunar
Professor Reinhold Ludwig
Dr. Kristin Lauter
Dr. Tancrède Lepoint