Assessing the influence of the algebraic structure of q-ary lattices on the complexity of cryptanalysis of problems on lattices
DOI:
https://doi.org/10.30837/rt.2024.2.217.07Keywords:
NTRU, SIS, LWE, cryptanalysis, lattice cryptography, Crystals-DilithiumAbstract
The work is devoted to the influence of the algebraic structure of q-ary lattices on the complexity of cryptanalysis of cryptographic problems on lattices. The root-mean-square errors for existing lattice reduction models are obtained. It is shown that the deterministic Albrecht-Lee simulator shows the smallest mean square deviations on small lattices. Collapsibility estimates for nesting and decoding attacks on the algebraic structure of q-ary lattices have been found. A new method for selecting attack parameters has been proposed for the decoding attack. It is shown that a decoding attack with such a choice of parameters can be at the expense of nesting attacks. To distribute the power of the secret vector in decoding attacks, which differ from the normal one, the approximation method is used by the normal division, which minimizes the Kolmogorov-Smirnov equation and calculates the optimal values for some distributions. There are no parameters for any divisions. For the SIS problem, a new approach to safety assessment has been proposed, which takes into account the possibility of various Euclidean norms. Based on the new approach, estimates of the SIS problem for Crystals-Dilithium electronic signature schemes have been calculated.
References
Post-quantum cryptography: CSRC, CSRC. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography (Accessed: 21 July 2024).
O. Regev. The Learning with Errors Problem. Available: https://cims.nyu.edu/~regev/papers/lwesurvey.pdf
J. Hoffstein, J. Pipher, and J. Silverman. NTRU: A Ring-Based Public Key Cryptosystem. Available: https://www.ntru.org/f/hps98.pdf
C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for Hard Lattices and New Cryptographic Constructions. ePrint IACR, 2007. https://eprint.iacr.org/2007/432
C. Schnorr. Lattice Reduction by Random Sampling and Birthday Methods, 2003. Accessed: Jul. 21, 2024. [Online]. Available: https://d-nb.info/1153616645/34
M. Albrecht and L. Ducas. LATTICE ATTACKS ON NTRU AND LWE: A HISTORY OF REFINEMENTS. Available: https://eprint.iacr.org/2021/799.pdf
Y. Chen and P. Nguyen. BKZ 2.0: Better Lattice Security Estimates. Accessed: Jul. 21, 2024. [Online]. Available: https://www.iacr.org/archive/asiacrypt2011/70730001/70730001.pdf
S. Bai, D. Stehlé, and W. Wen. Measuring, simulating and exploiting the head concavity phenomenon in BKZ // Cryptology ePrint Archive (eprint.iacr.org), 2018. https://eprint.iacr.org/2018/856 (accessed Jul. 21, 2024).
Z. Zhao and G. Xu. On the Measurement and Simulation of the BKZ Behavior for q-ary Lattices // Lecture notes in computer science, pp. 463–482, Jan. 2023, doi: https://doi.org/10.1007/978-3-031-26553-2_25.
I. D. Gorbenko, O. G. Kachko, Y. I. Gorbenko, I. V. Stelnik, S. O. Kandy, and M. V. Yesina. METHODS OF BUILDING GENERAL PARAMETERS AND KEYS FOR NTRU PRIME UKRAINE OF 5TH – 7TH LEVELS OF STABILITY. PRODUCT FORM // Telecommunications and radio engineering, vol. 78, no. 7, pp. 579–594, Jan. 2019, doi: https://doi.org/10.1615/telecomradeng.v78.i7.30.
E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe. Post-quantum key exchange – a new hope // Cryptology ePrint Archive (eprint.iacr.org), 2015. https://eprint.iacr.org/2015/1092
ДСТУ 8961:2019. Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів. Чин. від 21.12.2019. Вид. офіц. Київ: УкрНДНЦ, 2019. 72 с.
C. Peikert. A Decade of Lattice Cryptography // Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 4, pp. 283–424, 2016, doi: https://doi.org/10.1561/0400000074.
M. Albrecht, S. Bai, and L. Ducas. A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes // Cryptology ePrint Archive (eprint.iacr.org), 2016. https://eprint.iacr.org/2016/127 (accessed Jul. 21, 2024).
L. Ducas and W. van Woerden. NTRU Fatigue: How Stretched is Overstretched? // Cryptology ePrint Archive (eprint.iacr.org), 2021. https://eprint.iacr.org/2021/999 (accessed Jul. 21, 2024).
C. van Vredendaal. Reduced memory meet-in-the-middle attack against the NTRU private key // LMS Journal of Computation and Mathematics, vol. 19, no. A, pp. 43–57, 2016, doi: https://doi.org/10.1112/s1461157016000206.
Q. Guo, T. Johansson, and P. Stankovski. Coded-BKW: Solving LWE Using Lattice Codes // Accessed: Jul. 21, 2024. [Online]. Available: https://www.iacr.org/archive/crypto2015/92160189/92160189.pdf
M. Albrecht, C. Cid, J.-C. Faugère, R. Fitzpatrick, and L. Perret. On the complexity of the Arora-Ge Algorithm against LWE On the complexity of the Arora-Ge Algorithm against LWE. 2012 // Accessed: Jul. 21, 2024. [Online]. Available: https://inria.hal.science/hal-00776434/PDF/SCC_AG_2012.pdf
D. Bernstein and T. Lange. Non-randomness of S-unit lattices. Accessed: Jul. 21, 2024. [Online]. Available: https://eprint.iacr.org/2021/1428.pdf
R. Lindner and C. Peikert, “Better Key Sizes (and Attacks) for LWE-Based Encryption, 2010 // Accessed: Jul. 21, 2024. [Online]. Available: https://eprint.iacr.org/2010/613.pdf
N. Alkadri, J. Buchmann, R. Bansarkhani, and J. Krämer. A Framework to Select Parameters for Lattice-Based Cryptography // Accessed: Jul. 21, 2024. [Online]. Available: https://eprint.iacr.org/2017/615.pdf
L. Bi, X. Lu, J. Luo, and K. Wang. Hybrid Dual and Meet-LWE Attack // Cryptology ePrint Archive (eprint.iacr.org), 2022. https://eprint.iacr.org/2022/1330 (accessed Jul. 21, 2024).
S. Bai, S. Miller, and W. Wen. A refined analysis of the cost for solving LWE via uSVP, 2019 // Accessed: Jul. 21, 2024. [Online]. Available: https://hal.science/hal-02886638/document
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
