UC San Diego

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.