PhD Candidate
University of Maryland, College Park
Areas of Interest
- Cryptography
Poster
Security of Lattice-Based Cryptography under "Imperfect" Scenarios
Abstract
There is an urgent demand for replacing currently standardized public key cryptosystems, which are quantum-insecure. Lattice-based cryptography is one of the prominent post-quantum candidates, which has been recognized for its versatility of realizing cryptographic applications. One concern that arises is potential security loss in the process of transitioning theoretical work with provable security into practice. Although the best known algorithms for solving LWE problems run in exponential time, faulty parameter instantiation, incorrect implementation, or side-channel attacks may lead to severe security risks, which is often not considered in the scenarios of the original provable security claim.
In this work, we propose a framework for cryptanalysis of lattice-based schemes when certain side information---in the form of "hints"--- about the secret is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information.
Our framework can have many applications in cryptanalysis. We implement a Sage 9.0 toolkit to mount such attacks with hints when computationally feasible, and to predict their performances on larger instances.
Bio
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 lattice-based cryptography.
