Cryptographic Protocols from Lattices

Daniele Micciancio

We describe a general technique to simplify as well as to improve several lattice based cryptographic protocols. The technique is rather straightforward and is easily applied to the protocols, and gives both a simpler analysis and better performance than the original protocols. The improvement is global: the modified protocols are simpler, faster, require less storage, use less bandwidth and need less random bits than the originals. Moreover, the improvement is achieved without any loss in security: we formally prove that the modified protocols are at least as secure as the original ones. In fact, the modified protocols might even be more secure as the adversary gets less information. We exemplify our technique on the Goldreich-Goldwasser zero-knowledge proof systems for lattice problems and the GGH public key cryptosystem. Partially supported by DARPA grant DABT63-96-C-0018 and NTT grant 67627-00. 1 1 Introduction Various cryptographic protocols based on the hardness of la...

Oded Regev

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

Daniele Micciancio, Oded Regev

S Zaky Mohamed

Gohin Balakrishnan, Aruna Samudrala, Suresh Chanamala +2 more

The emergence of quantum computers poses a significant threat to classical cryptographic systems. Post-quantum cryptography (PQC) aims to develop cryptographic protocols resistant to quantum attacks. This study explores the enhancement of post-quantum cryptographic protocols by integrating quantum-resistant key exchange mechanisms. We propose the Quantum-Lattice Resilient Exchange Framework (Q-LREF), utilizing lattice dimensions 256, 512, and 1024) with Gaussian noise distribution 3.2. Through experimental evaluation, we demonstrate that our approach outperforms traditional RSA and ECC schemes while achieving comparable efficiency to CRYSTALS-Kyber with robust security margins. By reviewing existing literature, implementing our novel framework, and analyzing results, we demonstrate the efficacy of our approach against both classical and quantum adversaries. We also provide a comprehensive analysis of potential challenges and future directions in PQC, including detailed examination of various quantum-resistant algorithms and their applications.