On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem.
M. Albrecht, Nadia Heninger · IACR Cryptology ePrint Archive · 2020
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.