On the Independence Heuristic in the Dual Attack

Andreas Wiemers; Kaveh Bashiri

Paper 2023/1238

On the Independence Heuristic in the Dual Attack

Andreas Wiemers

, Federal Office for Information Security

Kaveh Bashiri, Federal Office for Information Security

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: lattices dual attack Learning with Errors Lattices Cryptanalysis
Contact author(s): andreas wiemers @ bsi bund de
kaveh bashiri @ bsi bund de
History: 2025-06-11: last of 2 revisions; 2023-08-16: received; See all versions
Short URL: https://ia.cr/2023/1238
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1238,
      author = {Andreas Wiemers and Kaveh Bashiri},
      title = {On the Independence Heuristic in the Dual Attack},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1238},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1238}
}