Paper 2022/1345

Revisiting Security Estimation for LWE with Hints from a Geometric Perspective

Dana Dachman-Soled, University of Maryland
Huijing Gong, Intel Labs
Tom Hanson, University of Maryland
Hunter Kippen, University of Maryland
Abstract

The Distorted Bounded Distance Decoding Problem (DBDD) was introduced by Dachman-Soled et al. [Crypto ’20] as an intermediate problem between LWE and unique-SVP (uSVP). They presented an approach that reduces an LWE instance to a DBDD instance, integrates side information (or “hints”) into the DBDD instance, and finally reduces it to a uSVP instance, which can be solved via lattice reduction. They showed that this principled approach can lead to algorithms for side-channel attacks that perform better than ad-hoc algorithms that do not rely on lattice reduction. The current work focuses on new methods for integrating hints into a DBDD instance. We view hints from a geometric perspective, as opposed to the distributional perspective from the prior work. Our approach provides the rigorous promise that, as hints are integrated into the DBDD instance, the correct solution remains a lattice point contained in the specified ellipsoid. We instantiate our approach with two new types of hints: (1) Inequality hints, corresponding to the region of intersection of an ellipsoid and a halfspace; (2) Combined hints, corresponding to the region of intersection of two ellipsoids. Since the regions in (1) and (2) are not necessarily ellipsoids, we replace them with ellipsoidal approximations that circumscribe the region of intersection. Perfect hints are reconsidered as the region of intersection of an ellipsoid and a hyperplane, which is itself an ellipsoid. The compatibility of “approximate,” “modular,” and “short vector” hints from the prior work is examined. We apply our techniques to the decryption failure and side-channel attack settings. We show that “inequality hints” can be used to model decryption failures, and that our new approach yields a geometric analogue of the “failure boosting” technique of D’anvers et al. [ePrint, ’18]. We also show that “combined hints” can be used to fuse information from a decryption failure and a side-channel attack, and provide rigorous guarantees despite the data being non-Gaussian. We provide experimental data for both applications. The code that we have developed to implement the integration of hints and hardness estimates extends the Toolkit from prior work and has been released publicly.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Keywords
lattice reductionellipsoidLWE
Contact author(s)
danadach @ umd edu
huijing gong @ intel com
thanson @ umd edu
hkippen @ umd edu
History
2023-07-07: last of 3 revisions
2022-10-09: received
See all versions
Short URL
https://ia.cr/2022/1345
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1345,
      author = {Dana Dachman-Soled and Huijing Gong and Tom Hanson and Hunter Kippen},
      title = {Revisiting Security Estimation for {LWE} with Hints from a Geometric Perspective},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1345},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1345}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.