Norbert Obiekwe
M.Sc. Candidate
Supervisor: Dr. Antonina Kolokolova

Lattice-based Digital Signature Schemes

Department of Computer Science
Friday, August 2, 2013, 1:00 p.m., Room EN 2022

---

Astract

The introduction of quantum computers is considered a challenge to the most common public cryptosystems such as RSA and ECC. The existing public signature schemes are based on the hardness of integer factoring problem and discrete logarithm problems. These schemes do fine against classical computers, for the time being, but they are provably not resistant to quantum computer attacks. In quantum computations, Shor’s algorithm, a quantum algorithm, solves the factoring and discrete logarithm problem in polynomial time. The fastest classical algorithms have runtime that is at best sub-exponential in the main security parameter. On a quantum computer, Shor’s algorithm is able to solve both problems in polynomial time. Thus the construction of powerful quantum computers which can use Shor’s algorithm will threaten modern cryptography. When quantum computers become common place, they would obsolete the existing public signature schemes which in effect would render digital communications vulnerable to various security attacks, communications devoid of authentication and lack of integrity.

However, there are hopes of constructing suitable cryptosystems and digital signature schemes that could be resistant to quantum computer algorithms. In this project, I explore signature lattice-based cryptosystem, the best candidate for a secure public signature scheme which is resistant to quantum attacks based on Shor’s algorithm. As such, I present an overview of the most recent cryptographic scheme with hardness based on lattice problems. Lattice cryptography schemes use easy and few operations in order to compute signatures. Such operations include products of matrices with vectors, sums of vectors or multiplication of polynomials. These operations are faster than exponentiation used in current classical systems like RSA. The fundamental security assumptions behind lattice based cryptosystems are based on NP-hard problems for which no quantum computer algorithms are known or believed to exists, in particular the closest vector problem.