Paper 2020/1308

On the Success Probability of Solving Unique SVP via BKZ

Eamonn W. Postlethwaite and Fernando Virdia

Abstract

As lattice-based key encapsulation, digital signature, and fully homomorphic encryption schemes near standardisation, ever more focus is being directed to the precise estimation of the security of these schemes. The primal attack reduces key recovery against such schemes to instances of the unique Shortest Vector Problem (uSVP). Dachman-Soled et al. (Crypto 2020) recently proposed a new approach for fine-grained estimation of the cost of the primal attack when using Progressive BKZ for lattice reduction. In this paper we review and extend their technique to BKZ 2.0 and provide extensive experimental evidence of its accuracy. Using this technique we also explain results from previous primal attack experiments by Albrecht et al. (Asiacrypt 2017) where attacks succeeded with smaller than expected block sizes. Finally, we use our simulators to reestimate the cost of attacking the three lattice KEM finalists of the NIST Post Quantum Standardisation Process.

Note: Minor differences in body, includes appendices that are missing in the published version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Pkc 2021
Keywords
cryptanalysislattice-based cryptographylattice reduction
Contact author(s)
eamonn postlethwaite 2016 @ rhul ac uk
fernando virdia 2016 @ rhul ac uk
History
2021-05-01: revised
2020-10-20: received
See all versions
Short URL
https://ia.cr/2020/1308
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1308,
      author = {Eamonn W.  Postlethwaite and Fernando Virdia},
      title = {On the Success Probability of Solving Unique SVP via BKZ},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1308},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1308}},
      url = {https://eprint.iacr.org/2020/1308}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.