log in  |  register  |  feedback?  |  help  |  web accessibility
PhD Defense: Improved Robustness and Versatility of Lattice-Based Cryptography
Huijing Gong
Wednesday, April 14, 2021, 10:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
All the 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.  A large 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. The first part of the dissertation 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 the second part of the dissertation, we propose a framework for cryptanalysis of lattice-based schemes, when certain types of information about the secret is leaked.  Our framework generalizes the primal lattice reduction attack.  The generalization allows 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. The third part of the dissertation introduces an approach towards a ring analogue of 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 can be used instead of the LHL, but 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-LWE cryptosystems can achieve certain leakage resilience properties using our results.

Examining Committee: 
                           Chair:              Dr. Dana Dachman-Soled                                    
                          Dean's rep:      Dr. Lawrence C. Washington
                          Members:         Dr. Michelle Mazurek
                                                Dr.  William Gasarch
                                                Dr.  Gorjan Alagic 
Huijing Gong is a Ph.D. candidate in Computer Science at the University of Maryland, advised by Prof. Dana Dachman-Soled. Her research interests lie primarily in the area of cryptography. In particular, she has worked on designing and cryptanalyzing post-quantum cryptography.


This talk is organized by Tom Hurst