Increasing Efficiency and Flexibility in Post-Quantum Cryptography

Abstract

In 1994, Peter Shor (FOCS 1994) discovered a polynomial time quantum algorithm that can be used to break the security of protocols based on the hardness of factoring or computing discrete logarithms. This ignited the study of problems for which no quantum speed-ups are currently known, and a branch of cryptography, called post-quantum cryptography, started, trying to construct cryptographic primitives from the presumed hardness of such problems. However, the deployment of post-quantum cryptosystem is momentarily held back by at least two factors: 1) currently deployed cryptosystems are faster and/or smaller than post-quantum ones, 2) in many modern computing settings, richer functionalities are required from cryptographic protocols, than those that current post-quantum constructions support. In this thesis we make progress on both sides. More concretely: 1.We study the setting of generically transforming PKE schemes with potentially large correctness error to ones having negligible correctness error. In particular, we show that the direct product compiler by Dwork, Naor, and Reingold (EUROCRYPT 2004) can be used in combination with a transformation from Hofheinz, Hövelmanns, and Kiltz (TCC 2017) to generically transform weakly secure deterministic or randomized PKEs into CCA-secure KEMs in the (quantum) random oracle model. Such transformation applies to essentially all candidates to the NIST post-quantum competition based on lattices and codes with non-negligible error for which we provide an extensive analysis, showing that it improves the concrete efficiency of some of the code-based candidates. Moreover, we demonstrate how the same ideas can be applied to obtain a first approach towards post-quantum secure Bloom-Filter KEMs, a primitive introduced by Derler et al. (EUROCRYPT 2018) in connection with puncturable KEMs, generically from lattices and codes. 2. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: (i) is tentatively post-quantum secure, (ii) is publicly-verifiable,(iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive composition. At the heart of this construction is a new lattice-based vector commitment scheme supporting openings to constant-degree multivariate polynomial maps. The security of our constructions is based onix a new family of lattice-based computational assumptions which naturally generalises the standard Short Integer Solution (SIS) assumption. 3. Building on the above construction, we present some further approaches to constructing efficient lattice-based succinct arguments. In particular, we propose a new commitment scheme based on vanishing polynomials, a notion borrowed from algebraic geometry. We analyse the security of such a commitment scheme, and show how to take advantage of the additional algebraic structure to build (i) the first recursive folding (i.e. Bulletproofs-like) protocol for linear relations with poly-logarithmic verifier runtime, and (ii) the first lattice-based linear-time prover succinct argument for NP, in the preprocessing model.