Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
2 results
Search Results
Item Improved Robustness and Versatility of Lattice-Based Cryptography(2021) Gong, Huijing; Dachman-Soled, Dana DD; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Current public key cryptosystems that are based on the hardness of integer factorization and discrete logarithm are insecure in the presence of large-scale quantum computers. Much effort has been devoted to replacing the quantum-insecure cryptosystems with newly developed "post-quantum" cryptosystem candidates, conjectured to be secure against quantum attack. Lattice-based cryptography has been widely recognized as a prominent candidate for practical post-quantum security.This dissertation improves the robustness and versatility of lattice-based cryptography through the following three contributions: 1. Chapter 3 introduces a constant-round protocol for unauthenticated group key exchange (i.e., with security against a passive eavesdropper). Group key exchange protocols allow a set of N parties to agree on a shared, secret key by communicating over a public network. Our protocol is based on the hardness of a lattice problem, which hence yields (plausible) post-quantum security. 2. In Chapter 4, we propose a framework for cryptanalysis of lattice-based schemes when certain types of information about the secret are leaked. Our framework generalizes the primal lattice reduction attack. The generalization allows for integrating the leaked information progressively before running a final lattice reduction step. Our framework can estimate the amount of security loss caused by the leaked information, and perform lattice reduction attacks with leaked information when computationally feasible. 3. Chapter 5 introduces an approach towards a ring analogue of the Leftover Hash Lemma (LHL). The LHL is a mathematical tool often used in the analysis of various lattice-based cryptosystems, as well as their leakage-resilient counterparts. However, it does not hold in the ring setting, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt '13) proved a "regularity lemma," which is used in the ring setting instead of the LHL; however, this applies only for centered, spherical Gaussian inputs, while the LHL applies when the input is drawn from any high min-entropy distribution. Our approach generalizes the "regularity lemma" of Lyubashevsky et al. to certain conditional distributions. A number of Ring-Learning with Errors based cryptosystems can achieve certain leakage resilience properties using our results.Item Algorithms for Solving Linear and Polynomial Systems of Equations over Finite Fields with Applications to Cryptanalysis(2007-06-07) Bard, Gregory Van; Washington, Lawrence C; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation contains algorithms for solving linear and polynomial systems of equations over GF(2). The objective is to provide fast and exact tools for algebraic cryptanalysis and other applications. Accordingly, it is divided into two parts. The first part deals with polynomial systems. Chapter 2 contains a successful cryptanalysis of Keeloq, the block cipher used in nearly all luxury automobiles. The attack is more than 16,000 times faster than brute force, but queries 0.62 × 2^32 plaintexts. The polynomial systems of equations arising from that cryptanalysis were solved via SAT-solvers. Therefore, Chapter 3 introduces a new method of solving polynomial systems of equations by converting them into CNF-SAT problems and using a SAT-solver. Finally, Chapter 4 contains a discussion on how SAT-solvers work internally. The second part deals with linear systems over GF(2), and other small fields (and rings). These occur in cryptanalysis when using the XL algorithm, which converts polynomial systems into larger linear systems. We introduce a new complexity model and data structures for GF(2)-matrix operations. This is discussed in Appendix B but applies to all of Part II. Chapter 5 contains an analysis of "the Method of Four Russians" for multiplication and a variant for matrix inversion, which is log n faster than Gaussian Elimination, and can be combined with Strassen-like algorithms. Chapter 6 contains an algorithm for accelerating matrix multiplication over small finite fields. It is feasible but the memory cost is so high that it is mostly of theoretical interest. Appendix A contains some discussion of GF(2)-linear algebra and how it differs from linear algebra in R and C. Appendix C discusses algorithms faster than Strassen's algorithm, and contains proofs that matrix multiplication, matrix squaring, triangular matrix inversion, LUP-factorization, general matrix in- version and the taking of determinants, are equicomplex. These proofs are already known, but are here gathered into one place in the same notation.