Post-Quantum Cryptography beyond Encryption: Design and Cryptanalysis

Abstract

We explore the design and analysis of post-quantum cryptographic primitives with an emphasis on two angles. First, diversity of assumptions, by building and analysing cryptography that does not rely on structured lattices. Second, diversity of functionalities, focusing on various primitives that extend beyond standard encryption. Motivated by the rapid development of quantum computing and the consequent threat to classical public-key cryptography, we therefore consider two families of post-quantum assumptions: isogeny-based and code-equivalence problems from which we build and analyse various primitives. In the first part, we focus on isogeny-based cryptography. We start our study with digital signatures derived from SIDH squares and investigate their security by analysing a range of attack vectors, including higher-dimensional attack strategies (known as SIDH attacks), and consequently propose suitable parameters. Building on the powerful constructive tools that the SIDH attacks became, we design an updatable public-key encryption scheme from a variant of FESTA, a public-key encryption scheme by Basso, Maino and Pope, enabling an efficient instantiation of this primitive that allows an unbounded number of updates. Finally, we investigate isogeny-based group actions and propose a framework for general-purpose zero-knowledge proofs. The second part focuses on code-based cryptography, particularly tensor group actions and code-equivalence problems. We first analyze and break a commitment scheme based on a structured tensor isomorphism problem, and we propose a secure fix. Then, we study variants of code-equivalence problems that underlie the security of two blind signature schemes. For one variant, we provide a reduction to a standard problem, whilst for another one we show that its security has been largely over-estimated. Overall, this thesis contributes to the development of a diverse suite of post-quantum primitives by providing new constructions, security analyses, and insights into the use of alternative assumptions beyond lattice-based systems.