Paper 2023/1238 Original: eprint.iacr.org/2023/1238 ↗

On the Independence Heuristic in the Dual Attack

Abstract

Post-quantum cryptography deals with the development and analysis of cryptographic schemes that are assumed to be secure even against attackers with access to a powerful quantum computers. Along the main candidates for quantum-safe solutions are cryptographic schemes, whose security are based on classic lattice problems such as the bounded-distance decoding (BDD) problem or learning with errors (LWE) problem. In this work we contribute to the analysis of an attack category against these problems called dual attack. Our first contributions is to provide theoretical counterarguments against a so-called independence assumption, which was used in earlier works on this attack, and which was shown to be contradicting practical experiments. Then, we provide estimates on the success probability and the cost of the dual attack against the decisional version of the BDD problem. These estimates are derived both rigorously and heuristically. Finally, we also provide experimental evidence that confirms these results.