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.
Category / Keywords: public-key cryptography / lattice techniques, elliptic curve cryptosystem, side-channel attacks, cryptanalysis, implementation Date: received 10 Dec 2020 Contact author: martin albrecht at royalholloway ac uk, nadiah@cs ucsd edu Available format(s): PDF | BibTeX Citation Version: 20201213:163819 (All versions of this report) Short URL: ia.cr/2020/1540