Welcome to the resource topic for 2022/1345
Title:
Refined Security Estimation for LWE with Hints via a Geometric Approach
Authors: Dana Dachman-Soled, Huijing Gong, Tom Hanson, Hunter Kippen
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 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 introduce a variant of DBDD which we coin Ellipsoidal Bounded Distance Decoding (EBDD), and view an EBDD instance as providing the promise that the correct solution is the unique lattice
point contained in an ellipsoid. We then view “hints” as geometric operations on the EBDD ellipsoid. Our approach allows us to introduce 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 approximations. We also consider compatibility of our approach with “perfect,” “approximate,” “modular,” and “short vector” hints from the prior work.
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, resulting in reduced hardness of the resulting uSVP instance, compared to a naive combination of the information. 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.
ePrint: https://eprint.iacr.org/2022/1345
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .