A remark on the Independence Heuristic in the Dual Attack

Andreas Wiemers; Stephan Ehlen

Paper 2023/1238

A remark on the Independence Heuristic in the Dual Attack

Andreas Wiemers

, Federal Office for Information Security

Stephan Ehlen, Federal Office for Information Security

Abstract

Ducas and Pulles in "Does the Dual-Sieve Attack on Learning with Errors even Work?" especially report on experiments they made comparing the distributions of scores for random targets and BDD targets. They discovered that the distribution of scores for BDD targets deviate from the predictions made under the independence heuristic. Here, we want to derive approximations for the distributions which take into account the dependency that occur in the scores. These approximations lead to new formulas that seem to describe the result in Table 1 of the article quite accurately.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: lattices dual attack
Contact author(s): andreas wiemers @ bsi bund de
stephan ehlen @ bsi bund de
History: 2023-08-21: approved; 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 Stephan Ehlen},
      title = {A remark on the Independence Heuristic in the Dual Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1238},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1238}},
      url = {https://eprint.iacr.org/2023/1238}
}