Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/89452
Title: Contributions to post-quantum cryptographic techniques
Authors: Lu, Xingye
Degree: Ph.D.
Issue Date: 2020
Abstract: In recent decades, public-key cryptographic techniques have been widely employed to secure digital communication infrastructure. Their security mainly relies on mathematical assumptions that integer factorization problem and discrete logarithm problem are hard. In 1994, Shor's algorithm was proposed. It allows people to solve integer factorization and discrete log problem using a quantum computer efficiently. As such, a quantum computer will make the deployed public-key cryptographic techniques insecure. Facing the rapid development of quantum computing, post-quantum cryptography, the study of cryptographic techniques resilient to attacks from the quantum computer is now receiving growing attention. Upgrading the modern public-key cryptography infrastructure as soon as possible become the best approach to protect individual's privacy under the threats from quantum computers. In this thesis, we focus on designing practical and efficient cryptosystems that are post-quantum secure based on lattice-based and hash-based cryptography, two common approaches in the post-quantum cryptography. Specifically, this thesis develops quantum-safe solutions for three cryptographic primitives. Firstly, we propose a hash-based ad hoc anonymous identification scheme. Such a scheme allows a participant to identify himself as a member of a group of users in a way that his actual identity is not revealed. We demonstrate a highly efficient construction in the symmetric-key setting based on the idea of program obfuscation. The salient feature of our scheme is that only hash evaluations are needed. Consequently, our scheme outperforms all previous constructions for a reasonably large ad hoc group size (of around 50000 users) since no exponentiation nor pairing operation is involved.
We also present a new signature scheme, PASSG, relying on lattice-based cryptography. It is based on signatures from the partial Fourier recovery problem PASSRS introduced by Hoffstein et al. in 2014. Same as PASSRS, security of our construction is based on the hardness of a special kind of Short Integer Solution problem and the hardness of partial Fourier recovery problem. PASSG improves PASSRS in two aspects. Firstly, it comes with a reduction proof and is thus provably secure. Secondly, we adopt rejection sampling technique introduced by Lyubashevsky in 2012 to reduce the signature size and improve the efficiency. We also present another security parameter set based on best known attack using BKZ 2.0 algorithm introduced by Chen and Nguyen in 2011. Furthermore, we design two new lattice-based (linkable) ring signature schemes. The first scheme, Raptor, is the first practical construction of its kind that comes with an implementation. We develop a generic construction of (linkable) ring signatures based on the well-known generic construction from Rivest et al., which is not fully compatible with lattices. We give instantiations from both standard lattice, as a proof of concept, and NTRU lattice, as an efficient instantiation. We show that the latter construction, Raptor, is almost as efficient as the classical RST ring signatures and thus may be of practical interest. We also revisit the generic framework of ring signatures based on hash-then-one-way type (Type-H) signatures presented by Abe et al. (AOS) in 2004 and made the following contributions. First, we give a proof for the generic construction, in a strengthened security model. Secondly, we also extend AOS's framework to generically construct one-time linkable ring signatures from Type-H signatures and one-time signatures. Lastly, we instantiate the generic construction with an NTRU-based Type-H signature: FALCON and obtain a post-quantum linkable ring signature scheme. Our analysis suggests that the resulting linkable signature outperforms Raptor.
Subjects: Cryptography
Quantum computing
Computer security
Data encryption (Computer science)
Hong Kong Polytechnic University -- Dissertations
Pages: iv, xiv, 136 pages
Appears in Collections:Thesis

Show full item record

Page views

5
Citations as of Jul 3, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.