Security analysis of promising key encapsulation mechanisms in the core-SVP model

Authors

  • S.О. Kandiy Харківський національний університет імені В. Н. Каразіна, АТ «Інститут Інформаційних Технологій», Ukraine

DOI:

https://doi.org/10.30837/rt.2023.1.212.06

Keywords:

post-quantum cryptography, algebraic lattices, DSTU 8961:2019 , CRYSTALS-Kyber, BKZ, SVP, core-SVP

Abstract

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.

Published

2023-03-28

How to Cite

Kandiy, S. (2023). Security analysis of promising key encapsulation mechanisms in the core-SVP model. Radiotekhnika, 1(212), 66–84. https://doi.org/10.30837/rt.2023.1.212.06

Issue

Section

Articles