
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. [an error occurred while processing this directive] 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. [an error occurred while processing this directive] Personal home page [an error occurred while processing this directive] [an error occurred while processing this directive]