Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

Gadgets and Gaussians in Lattice-Based Cryptography

  • Author(s): Genise, Nicholas James
  • Advisor(s): Micciancio, Daniele
  • Kim, Young-Han
  • et al.
Abstract

This dissertation explores optimal algorithms employed in lattice-based cryptographic schemes. Chapter 2 focuses on optimizing discrete gaussian sampling on "gadget" and algebraic lattices. These gaussian sampling algorithms are used in lattice-cryptography's most efficient trapdoor mechanism for the SIS and LWE problems: "MP12" trapdoors. However, this trapdoor mechanism was previously not optimized and inefficient (or not proven to be statistically correct) for structured lattices (ring-SIS/LWE), lattice-cryptography's most efficient form, where the modulus is often a prime. The algorithms in this chapter achieve optimality in this regime and have (already) resulted in drastic efficiency improvement in independent implementations.

Chapter 3 digs deeper into the gadget lattice's associated algorithms. Specifically, we explore efficiently sampling a simple subgaussian distribution on gadget lattices, and we optimize LWE decoding on gadget lattices. These subgaussian sampling algorithms correspond to a randomized bit-decomposition needed in lattice-based schemes with homomorphic properties like fully homomorphic encryption (FHE). Next, we introduce a general class of "Chinese Remainder Theorem" (CRT) gadgets. These gadgets allow advanced lattice-based schemes to avoid multi-precision arithmetic when the applications modulus is larger than 64 bits.

The algorithms presented in the first two chapters improve the efficiency of many lattice-based cryptosystems: digital signature schemes, identity-based encryption schemes, as well as more advanced schemes like fully-homomorphic encryption and attribute-based encryption.

In the final chapter, we take a closer look at the random matrices used in trapdoor lattices. First, we revisit the constants in the concentration bounds of subgaussian random matrices. Then, we provide experimental evidence for a simple heuristic regarding the singular values of matrices with entries drawn from commonly used distributions in cryptography. Though the proofs in this chapter are

dense, cryptographers need a strong understanding of the singular values of these matrices since their maximum singular value determines the concrete security of the trapdoor scheme's underlying SIS problem.

Main Content
Current View