Security analysis of promising key encapsulation mechanisms in the core-SVP model
DOI:
https://doi.org/10.30837/rt.2023.1.212.06Keywords:
post-quantum cryptography, algebraic lattices, DSTU 8961:2019 , CRYSTALS-Kyber, BKZ, SVP, core-SVPAbstract
The study of key encapsulation mechanisms on structured lattices is one of the important directions in modern post-quantum cryptography, as many mechanisms are either already standardized (DSTU 8961:2019 "Skelya") or are promising candidates for standardization (CRYSTALS-Kyber). Estimating the complexity of lattice reduction for cryptographic schemes is an old problem. Asymptotic estimates differ greatly from experimental values, therefore, a number of heuristic methods were developed to solve practical problems. The coreSVP model is a standard means of assessing the security of cryptographic schemes on lattices. The purpose of the work is to analyze the encapsulation mechanisms of DSTU 8961:2019 "Skelya" and CRYSTALS-Kyber keys in the coreSVP model. The analysis was performed using two popular heuristics – GSA (Geometric Series Assumption) and the Chen-Nguyen simulator. The analysis showed that the Chen-Nguyen simulator gives slightly lower estimates than the GSA heuristic. As a result of the analysis, it was found that 8961:2019 The “Skelya” and CRYSTALS-Kyber in the coreSVP model for classical computers have slightly lower than declared security values, but for quantum computers the key encapsulation mechanisms provide the declared security levels. Note that during the analysis, the accuracy of the GSA heuristics and the Chen-Nguyen simulator were analyzed separately. Examples of parameters for which heuristics do not give sufficiently accurate results are given. The performed analysis does not take into account the algebraic structure of lattices used in 8961:2019 "Skelya" and CRYSTALS-Kyber. The inclusion of an algebraic structure in the analysis is a further direction of work. The use of simulators is a promising direction, however, more accurate simulators that take into account the structuring of LWE and NTRU arrays are needed.
References
ДСТУ 8961:2019. Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів. Чинний від 21.12.2019. Вид. офіц. Київ : УкрНДНЦ, 2019. 72 с.
CRYSTALS – Kyber: a CCA-secure module-lattice-based KEM // Cryptology ePrint Archive, Report 2017/634. [Electronic resource]. Online: https://eprint.iacr.org/2017/634.pdf
Lyubachevsky V., Ducas L., Kiltz E. CRYSTALS-Kyber Techn. rep. NIST, 2017. [Electronic resource]. Access mode: https://pq-crystals.org/kyber/ (дата звернення: 21.03.2023)
Albrecht M., Deo A. Large Modulus Ring-LWE ≥ Module-LWE // URL: https://eprint.iacr.org/2017/612.pdf (дата звернення: 21.03.2023)
Hoffstein J., Pipher J., Silverman H. NTRU: a ring based public key cryptosystem // Algorithmic Nuber Theory. Third International Symposium. 1998. P. 267 – 288.
Alkim E., Ducas L., Pöppelmann T., Schwabe P. Post-quantum key exchange – a new hope // URL: https://eprint.iacr.org/2015/1092.pdf (дата звернення: 21.03.2023)
Li J., Nguyen P. A Complete Analysis of the BKZ Lattice Reduction Algorithm // URL: https://eprint.iacr.org/2020/1237 (дата звернення: 21.03.2023)
Chen Y., Nguyen P. BKZ 2.0: Better Lattice Security Estimates // ASIACRYPT, 2011.
Lyubashevsky V., Peikert C., Regev O. On ideal lattices and learning with errors over rings // EUROCRYPT, 2010. P. 1 – 23.
Eisenträger K., Hallgren S., Kitaev A., Song F. A quantum algorithm for computing the unit group of an arbitrary degree number field // Proceedings of the forty-sixth annual ACM symposium on Theory of computing. P 293 – 302. ACM, 2014.
Campbell P., Groves M., Shepherd D. Soliloquy: A cautionary tale. // ETSI 2nd Quantum-Safe Crypto Workshop. P. 1 – 9.
Biasse J., Song F. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields // ACM-SIAM symposium on Discrete Algorithms, 2017. P. 893 – 902.
Bernstein D., Lange T. Non-randomness of S-unit lattices // [Electronic resource]. Online: https://s-unit.attacks.cr.yp.to/spherical.html
Gamma N., Nguyen P. Finding short lattice vectors within Mordell’s inequality // STOC, 2008. P. 3 – 13.
Micciancio D., Walter M. Practical, predictable lattice basis reduction // EUROCRYPT, 2016. P. 56 – 73.
Albrecht M., Ducas L., Herold G., Kirshanova E., Postlethwaite E., Stevens M. The General Sieve Kernel and New Records in Lattice Reduction. // URL: https://eprint.iacr.org/2019/089 (дата звернення: 21.03.2023)
Dent A. A Designer’s Guide to KEMs. Cryptography and Coding // Cryptography and Coding, 2003. Vol 28. P. 29 – 56.
Hofheinz D., Hovelmanns K., Kiltz E. A modular analysis of the fujisaki-okamoto transformation // Lecture Notes in Computer Science. 2017. Vol. 10677. P. 341 – 371.
Cheon J., Jeong J., Lee C. An algorithm for ntru problems and cryptanalysis of the ggh multilinear map without a low-level encoding of zero // LMS Journal of Computation and Mathematics, 2016. Vol. 19 P. 255 – 266.
Kirchner P., Fouque P. Revisiting lattice attacks on overstretched NTRU parameters // STOC, 2017. P. 3 – 26.
Albrecht M., Göpfert F., Virdia F., Wunderer T. Revisiting the expected cost of solving uSVP and applications to LWE // ASIACRYPT. 2017. Vol. 10624. P.297 – 322.
Bernstein D., Chuengsatiansup C., Lange T., Vredendaal C. NTRU Prime: reducing attack surface at low cost // URL: https://eprint.iacr.org/2016/461 (дата звернення: 21.03.2023)
Laarhoven T., Mariano A. Progressive lattice sieving // URL: https://eprint.iacr.org/2018/079.pdf (дата звернення: 21.03.2023)
Gama N., Nguyen P., Regev O. Lattice Enumeration Using Extreme Pruning // URL: https://hal.science/hal-01083526/document (дата звернення: 21.03.2023)
Albrecht M., Göpfert F., Virdia F., Wunderer T. Revisiting the expected cost of solving uSVP and applications to LWE // ASIACRYPT. 2017. Vol. 10624. P.297 – 322.
Bai S., Stehle D., Wen W. Measuring, simulating and exploiting the head concavity phenomenon in BKZ // ASIACRYPT, 2018. P. 389 – 404.
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).
