COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Gadgets and Gaussians in Lattice-Based Cryptography
by Genise, Nicholas James, Ph.D., University of California, San Diego, 2019, 113; 13857523
Abstract (Summary)

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.

Indexing (document details)
Advisor: Micciancio, Daniele, Kim, Young-Han
Commitee: Bellare, Mihir, Franceschetti, Massimo, Lovett, Shachar, Orlitsky, Alon
School: University of California, San Diego
Department: Electrical and Computer Engineering
School Location: United States -- California
Source: DAI-B 81/3(E), Dissertation Abstracts International
Subjects: Computer science
Keywords: Cryptography, Discrete Gaussian, Lattice
Publication Number: 13857523
ISBN: 9781088326138
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy