As an important authentication technology, digital signature enables people to carry out convenient digital office in the digital information age. It is widely used in information security, identity authentication, data integrity, non-repudiation and so on. As the extensions of digital signature, multi-signature and aggregate signature integrate digital signature compression technology and batch processing technology, which greatly saves the consumption of storage space and transmission bandwidth. And they are widely used in blockchain bitcoin transactions, electronic voting, certificate chains authentication and so on. With the rapid development of quantum computers, the security of many traditional cryptosystems has been seriously threatened. Fortunately, lattice-based cryptography is a type of public-key cryptosystem that can withstand quantum computing attacks, because the hard problem on lattice is considered to be resistant to the attacks of quantum computers. Therefore, research
Post–quantum cryptography (PQC) is a new and fast–growing part of Cryptography. It focuses on developing cryptographic algorithms and protocols that resist quantum adversaries (i.e., the adversaries who have access to quantum computers). To construct a new PQC primitive, a designer must use a mathematical problem intractable for the quantum adversary. Many intractability assumptions are being used in PQC. There seems to be a consensus in the research community that the most promising are intractable/hard problems in lattices. However, lattice–based cryptography still needs more research to make it more efficient and practical. The thesis contributes toward achieving either the novelty or the practicality of lattice– based cryptographic systems.
NewHope Key Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alkim et al. and was one of the lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence, we propose a set of alternative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed-up of 17%
This thesis is a compilation of the main published works I did during my studies in Australia. My research area was lattice-based cryptography, which focuses mainly on a family of mathematical primitives that are supposed to be “quantum-resistant”. The direction of my research was mostly targeted towards constructions that lie out- side of the mainly researched lattice forms to provide an alternative direction in the case common constructions were discovered to be insecure. We do have, however, some work that makes use of common constructions in which we expand the design space for better efficiency or security.
At PKC 2008, Plantard et al. published a theoretical framework for a lattice-based signature scheme, namely Plantard-Susilo-Win (PSW). Recently, after ten years, we proposed a new signature scheme dubbed the Diagonal Reduction Signature (DRS) scheme was presented in the National Institute of Standards and Technology (NIST) PQC Standardization as a concrete instantiation of