On lattice based digital signature schemes

Abstract

Kafes tabanlı s¸ifreleme, kuantum sonrası c¸a˘gda g¨uvenli ac¸ık anahtar algoritmalarınıolus¸turmak ic¸in gerekli olan az sayıdaki arac¸lardan birisidir. Bunun nedeni ise zorkafes problemlerini c¸¨ozebilecek polinomiyal zamanlı kuantum algoritmalarının hen¨uzmevcut olmamasıdır. Zor kafes problemlerine dayanan kriptografik yapılar, bu ¨onemli¨ozelli˘gine ra˘gmen zaman ve kapladı˘gı alan ac¸ısından c¸ok verimli de˘gildir. Bu durumdaha az zaman ve yer gerektiren yapılı kafeslerin olus¸turulmasına yol ac¸mıs¸tır. Kafestabanlı s¸ifreleme sistemlerindeki var olan tek standart, bu yapılı kafesler ¨uzerindetanımlanan zor problemlere dayanmaktadır. NTRU olarak adlandırılan bu standart,verimlilik ac¸ısından sayılar teorisine dayanan s¸ifreleme sistemleriyle kıyaslanabilir.Kriptografik ac¸ıdan b¨uy¨uk ¨oneme sahip olan dijital imzalama algoritmaları kafes ta-banlı zor problemler kullanılarak da olus¸turulabilir. Bu tezde, kafes tabanlı zor prob-lemlere dayanan ¨uc¸ farklı dijital imzalama algoritması c¸alıs¸ılmıs¸tır. Bu algoritmalarsırasıyla ispatlanabilir g¨uvenli˘gi olan bir imzalama algoritması, GGH imzalama algo-ritması ve NTRUSign imzalama algoritmasıdır. Bunlara ek olarak, GGH ve NTRUSignalgoritmalarının kriptoanalizi de incelenmis¸tir.

Lattice based cryptography is one of the few hopes for secure public key cryptographyin post quantum era since there is no known polynomial time quantum algorithm thatcan solve hard lattice problems. But despite this precious property, for a cryptographicconstruction which is designed based on a hard lattice problem, to be secure, requiredtime and space is not efficient. This has led to introduction of structured lattices thatneed less time and space; indeed the only existing standard on lattice based cryptogra-phy 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 thisstandardized cryptographic system can be compared to cryptographic constructionswhich are based on Integer Factorization Problem or Discrete Logarithm Problem.Digital signatures are important cryptographic primitives that can naturally be designedusing hard lattice problems. In this thesis we have studied three signature schemes thatare based on hardness of solving certain lattice problems; first scheme is an efficientsignature scheme with provable security, the second scheme is GGH signature and thethird one is NTRUSign. We also have studied a brilliant cryptanalysis technic whichis applicable on GGH signature and NTRUSign and implemented it on a lattice ofdimension 15.