Talk by Martin Albrecht: “On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem”
On 14 May 2021 at 14:00 CET, Martin Albrecht will give a talk titled “On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem”.
You can join the Zoom meeting using the details provided here.
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.
Link:
https://eprint.iacr.org/2020/1540.pdf
Biography:
Martin is Chair of Information Security at Royal Holloway, University of London. He works across the field of cryptography from theoretical to applied. His recent work focuses on post-quantum and lattice-based cryptography, studying the hardness of the underlying assumptions, on the one hand, and the security of cryptographic protocols deployed in the wild, on the other hand. His Erdős–Bacon number is 6.