On lattice based digital signature schemes

Download

index.pdf

Date

2014

Author

Javani, Farid

Metadata

Show full item record

Item Usage Stats

232
views

124
downloads

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.

Subject Keywords

Public key cryptography., Digital signatures., Lattice theory., Cryptography.

URI

http://etd.lib.metu.edu.tr/upload/12617468/index.pdf
https://hdl.handle.net/11511/23688

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

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...
Faster Montgomery modular multiplication without pre-computational phase for some classes of finite fields Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2010-09-24) In this paper, we give faster versions of Montgomery modular multiplication algorithm without pre-computational phase for GF(p) and GF(2 m ) which can be considered as a generalization of [3], [4] and [5]. We propose sets of moduli different than [3], [4] and [5] which can be used in PKC applications. We show that one can obtain efficient Montgomery modular multiplication architecture in view of the number of AND gates and XOR gates by choosing proposed sets of moduli. We eliminate precomputational phase wi...
NEW TMVP-BASED MULTIPLICATION ALGORITHMS FOR POLYNOMIAL QUOTIENT RINGS AND APPLICATION TO POST-QUANTUM CRYPTOGRAPHY Keskinkurt Paksoy, İrem; Cenk, Murat; Department of Cryptography (2022-7-28) One of the quantum-safe cryptography research areas is lattice-based cryptography. Most lattice-based schemes need efficient algorithms for multiplication in polynomial quotient rings. The fastest algorithm known for multiplication is the Number Theoretic Transform (NTT), which requires certain restrictions on the parameters of the ring, such as prime modulus. Direct NTT application is not an option for some schemes that do not comply with these restrictions, e.g., the two finalists of the PQC standardizati...
Radix-3 NTT-Based Polynomial Multiplication for Lattice-Based Cryptography Hassan, Chenar Abdulla; Yayla, Oğuz; Department of Cryptography (2022-5-31) The lattice-based cryptography is considered as a strong candidate amongst many other proposed quantum-safe schemes for the currently deployed asymmetric cryptosystems that do not seem to stay secure when quantum computers come into play. Lattice-based algorithms possesses a time consuming operation of polynomial multiplication. As it is relatively the highest time consuming operation in lattice-based cryptosystems, one can obtain fast polynomial multiplication by using number theoretic transform (NTT). In ...
Design and performance evaluation of a flexible and efficient server assisted signature protocol Bicakci, K; Baykal, Nazife (2003-07-03) One method to reduce the computational costs of generating public key signatures on constrained devices is to get help from a verifiable server In this paper, we propose a (verifiable) server assisted signature protocol which is the first one that totally elliminates public key operations for the ordinary user Our protocol is also more efficient and flexible in terms of storage since unlike previous ones the user does not need to save the server's signatures to prove its cheating.

Citation Formats

F. Javani, “On lattice based digital signature schemes,” M.S. - Master of Science, Middle East Technical University, 2014.