Post quantum cryptographic constructions

• Main Author: Li, Zhe
• Other Authors: Ling San
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Science::Mathematics
• Online Access: https://hdl.handle.net/10356/146200
• Institution: Nanyang Technological University

With the past and ongoing developments of quantum computers, the existing asymmetric schemes are no longer secure. In a report of 2006, the National Institute of Standards and Technology (NIST) predicts that large scale quantum computers will be built within three decades. Thus, we need to actively find quantum resistant cryptographic constructions. To date, there are many proposals based on different hard mathematical problems. This thesis seeks to enrich the diversity of the quantum resistant schemes and improve the efficiency of existing schemes. We present constructions from coding theory, lattices and subset sum problems. Concretely, our quantum-safe contributions are listed as follows. For the code-based construction, we propose a new general construction to reduce the public key size of McEliece cryptosystems constructed from automorphism-induced Goppa codes. In particular, we generalize the ideas of automorphism-induced Goppa codes by considering nontrivial subsets of automorphism groups to construct Goppa codes with a nice block structure. By considering additive and multiplicative automorphism subgroups, we provide explicit constructions to demonstrate our technique. We show that our technique can be applied to automorphism-induced Goppa codes based cryptosystems to further reduce their key sizes. For the lattice-based construction, we propose new classes of trapdoor functions to solve the bounded distance decoding problem in lattices. Specifically, we construct lattices based on properties of polynomials for which the bounded distance decoding problem is hard to solve unless some trapdoor information is revealed. We thoroughly analyze the security of our proposed functions using state-of-the-art attacks and results on lattice reductions. Then, we describe how our functions can be used to design quantum-safe encryption schemes with reasonable public key sizes. Our encryption schemes are efficient with respect to key generation, encryption and decryption. For the subset sum problem, we propose a variant of the subset sum problem which we name the \emph{rounded subset sum problem}. We prove that this problem is as hard as the subset sum problem. We then present a public key cryptosystem that achieves semantic security based on the rounded subset sum problem. Next we show the robustness of the rounded subset sum assumption in the presence of auxiliary input of the secret. Based on the robustness result, we present a public key encryption that is resilient to adaptive leakage of the secret key, and this solves an open problem in the work of Lyubashevsky, Palacio, and Segev (TCC 2010). The subset sum assumption we used to construct adaptive leakage-resilient scheme is weaker than the assumption underlying existing lattice-based leakage-resilient schemes such as Dodis et al.(TCC 2010). We also present other applications of the rounded subset sum problem.