Paper 2024/592
Asymptotics for the standard block size in primal lattice attacks: second order, formally verified
Abstract
Many proposals of latticebased cryptosystems estimate security levels by following a recipe introduced in the New Hope proposal. This recipe, given a lattice dimension n, modulus q, and standard deviation s, outputs a "primal block size" β and a security level growing linearly with β. This β is minimal such that some κ satisfies ((n+κ)s^2+1)^{1/2} < (d/β)^{1/2} δ^{2β−d−1} q^{κ/d}, where d = n + κ + 1 and δ = (β(πβ)^{1/β}/(2π exp 1))^{1/2(β−1)}. This paper identifies how β grows with n, with enough precision to show the impact of adjusting q and s by constant factors. Specifically, this paper shows that if lg q grows as Q_0 lg n + Q_1 + o(1) and lg s grows as S_0 lg n + S_1 + o(1), where 0 <= S_0 <= 1/2 < Q_0 − S_0, then β/n grows as z_0 + (z_1+o(1))/lg n, where z_0 = 2Q_0/(Q_0−S_0+1/2)^2 and z_1 has a formula given in the paper. The paper provides a traditionalformat proof and a proof verified by the HOL Light proof assistant.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Contact author(s)
 authorcontactlatticeasymp @ box cr yp to
 History
 20240727: last of 2 revisions
 20240416: received
 See all versions
 Short URL
 https://ia.cr/2024/592
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/592, author = {Daniel J. Bernstein}, title = {Asymptotics for the standard block size in primal lattice attacks: second order, formally verified}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/592}, year = {2024}, url = {https://eprint.iacr.org/2024/592} }