On lattice based digital signature schemes

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Türkiye

Tezin Onay Tarihi: 2014

Öğrenci: FARİD JAVANİ

Danışman: ERSAN AKYILDIZ

Özet:

Lattice based cryptography is one of the few hopes for secure public key cryptography in post quantum era since there is no known polynomial time quantum algorithm that can solve hard lattice problems. But despite this precious property, for a cryptographic construction which is designed based on a hard lattice problem, to be secure, required time and space is not efficient. This has led to introduction of structured lattices that need less time and space; indeed the only existing standard on lattice based cryptography is based on hardness of solving lattice problems for a class of structured lattices, called NTRU lattices; and though it lacks a security proof, in terms of efficiency this standardized cryptographic system can be compared to cryptographic constructions which are based on Integer Factorization Problem or Discrete Logarithm Problem. Digital signatures are important cryptographic primitives that can naturally be designed using hard lattice problems. In this thesis we have studied three signature schemes that are based on hardness of solving certain lattice problems; first scheme is an efficient signature scheme with provable security, the second scheme is GGH signature and the third one is NTRUSign. We also have studied a brilliant cryptanalysis technic which is applicable on GGH signature and NTRUSign and implemented it on a lattice of dimension 15.