International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem

Authors:
Martin R. Albrecht , Information Security Group, Royal Holloway, University of London
Nadia Heninger , University of California, San Diego
Download:
DOI: 10.1007/978-3-030-77870-5_19 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short. We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these prob- lems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.
BibTeX
@inproceedings{eurocrypt-2021-30818,
  title={On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77870-5_19},
  author={Martin R. Albrecht and Nadia Heninger},
  year=2021
}