On lattice based digital signature schemes

Download
2014
Javani, Farid
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.

Suggestions

On the efficient implementation of RSA
Güner, Hatice Kübra; Cenk, Murat; Department of Cryptography (2015)
Modular exponentiation is an essential operation for many asymmetric key cryptosystems such as RSA in which encryption and decryption are based on modular exponentiation. Therefore, efficiency of the system is effected with running time of the modular exponentiation algorithm. At the same time, key sizes also influence the efficiency of the algorithm. Over the years key sizes had to be increased to provide security. To make RSA practical, one of usable choices is acceleration of the modular exponentiation a...
ON THE k-TH ORDER LFSR SEQUENCE WITH PUBLIC KEY CRYPTOSYSTEMS
KIRLAR, Barış Bülent; Cil, Melek (Walter de Gruyter GmbH, 2017-06-01)
In this paper, we propose a novel encryption scheme based on the concepts of the commutative law of the k-th order linear recurrences over the finite field F-q for k > 2. The proposed encryption scheme is an ephemeral-static, which is useful in situations like email where the recipient may not be online. The security of the proposed encryption scheme depends on the difficulty of solving some Linear Feedback Shift Register (LFSR) problems. It has also the property of semantic security. For k = 2, we propose ...
On the efficiency of lattice-based cryptographic schemes on graphical processing unit
Yüce Tok, Zaliha; Akyıldız, Ersan; Akleylek, Sedat; Department of Cryptography (2016)
Lattice-based cryptography, a quantum-resistant public key alternative, has received a lot of attention due to the asymptotic efficiency. However, there is a bottleneck to get this advantage on practice: scheme-based arithmetic operations and platform-based implementations. In this thesis, we discuss computational aspects of lattice-based cryptographic schemes focused on NTRU and GLP in view of the time complexity on both CPUs and Graphical Processing Units (GPU). We focus on the optimization of polynomial ...
Message transmission for GH-public key cryptosystem
Ashraf, Muhammad; KIRLAR, Barış Bülent (2014-03-15)
In this paper we propose an ElGamal type encryption scheme based on the concepts of public key cryptosystem over cubic finite field extension proposed by Gong and Ham (GH). The proposed encryption scheme is an ephemeral-static, which is useful in situations like email where the recipient may not be online. The security of the proposed encryption scheme depends on the difficulty of solving 3-LFSR-DLP, 3-LFSR-DHP and 3-LFSR-DDHP. It then provides secure message transmission by having also the property of sema...
On the trace based public key cryptosystems over finite fields
Ashraf, Muhammad; Akyıldız, Ersan; Kırlar, Barış Bülent; Department of Cryptography (2013)
In this thesis, the trace based Public Key Cryptosystems (PKC) are explored from theoretical and implementation point of view. We will introduce cryptographic protocols for the ones they are not discussed yet. We introduce improved trace based exponentiation algorithm for fifth degree recursive relation. The Discrete Log Problem (DLP), that is computing $x$, given $y=\alpha^x$ and $<\alpha>=G\subset \F_q^*$, based Public Key Cryptosystems (PKC) are being studied since late 1970's. Such development of PKC wa...
Citation Formats
F. Javani, “On lattice based digital signature schemes,” M.S. - Master of Science, Middle East Technical University, 2014.