Advanced functionalities and post-quantum security through the lens of lattice-based cryptography
Willy Quach
Over the last twenty years, lattice-based cryptography has quickly become a central component of modern cryptography. Its most prominent characteristics are (1) its capacity to build cryptographic primitives with powerful functionalities, famously including fully-homomorphic encryption, and (2) its widely-believed resilience against quantum attacks, leading to the currently most prevalent family of candidates for post-quantum cryptography. In this thesis, we further study these two fundamental features of lattice-based cryptography. First, we introduce a new advanced cryptographic primitive, that we call laconic function evaluation, which captures general sender-optimized two-party computation. We build laconic function evaluation from lattice-based assumptions, and show applications to efficient secure multi-party computation. Second, we take a systematic approach to studying post-quantum security of cryptographic protocols. We show that, perhaps surprisingly, post-quantum resilience of a computational assumption does not automatically imply post-quantum security of cryptographic primitives built upon it, including encryption and signature schemes. We do so by exhibiting counter-examples based on lattices. Last, we show that natural interactive protocols from lattices shed light on cryptographic arguments systems, and more specifically the so-called Fiat-Shamir transform. As a byproduct, we uncover a conceptual connection between two families of practical lattice-based signatures.--Author's abstract
•Jan 1, 2023•0 citations