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

Martin R. Albrecht and Nadia Heninger

##### 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 problems. 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.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Keywords
lattice techniqueselliptic curve cryptosystemside-channel attackscryptanalysisimplementation
Contact author(s)
martin albrecht @ royalholloway ac uk
nadiah @ cs ucsd edu
History
2021-03-07: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/1540

CC BY

BibTeX

@misc{cryptoeprint:2020/1540,
author = {Martin R.  Albrecht and Nadia Heninger},
title = {On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem},
howpublished = {Cryptology ePrint Archive, Paper 2020/1540},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1540}},
url = {https://eprint.iacr.org/2020/1540}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.