Analysis of DSTU 8961:2019 in random oracle model
DOI:
https://doi.org/10.30837/rt.2022.4.211.02Keywords:
post-quantum cryptography, algebraic lattices, DSTU 8961:2019 , Random Oracle ModeAbstract
The paper provides a proof in the IND-CCA2 random oracle model of the security of the asymmetric encryption scheme described in the DSTU 8961:2019 standard, and the IND-CCA2 security of the corresponding key encapsulation mechanism. Since the standard contains only a technical description of transformations, a formalized mathematical model was introduced in Chapter 4 without unnecessary technical details that do not affect safety assessments. Since the system-wide parameters in the standard were chosen in such a way that the scheme did not contain decryption errors, it was possible to simplify significantly the proof. Section 5 provides a schematic overview of possible attack vectors on the DSTU 8961:2019, but a detailed analysis is the subject of further research. In addition to safety, the analysis also showed that the DSTU 8961:2019 has a certain disadvantage in terms of safety. The design can be significantly simplified and accelerated without loss of safety. Security, on the contrary, can be significantly increased.
References
ДСТУ 8961:2019. Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів. Чинний від 21.12.2019. Вид. офіц. Київ : УкрНДНЦ, 2019. 72 с.
Горбенко І. Д., Горбенко Ю. І. Прикладна криптологія. Теорія. Практика. Застосування : монографія. Харків : Форт, 2012. 880 с.
Calculation of general parameters for NTRU Prime Ukraine of 6-7 levels of stability / I. D. Gorbenko and other // Telecommunications and Radio Engineering. Vol. 78. P. 327 – 340
Methods of building general parameters and keys for ntru prime Ukraine of 5th-7th levels of stability. product form / I.D. Gorbenko and other // Telecommunications and Radio Engineering. 2018. Vol 78. P. 579 – 594.
NIST Post-Quantum Cryptography Standartization Project [Electronic resource] // Online: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization
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
FrodoKEM. Learning With Errors Key Encapsulation Algorithm Specifications. And Supporting Documentation // [Electronic resource]. Online: https://frodokem.org/files/FrodoKEM-specification-20210604.pdf
Katz J., Lindell Y. Introduction to Modern Cryptography: Principles and Protocols // Chapman and Hall/CRC, 2007. 603 P.
Canetti R., Goldreich O., Halevi S. The random oracle methodology, revisited // 30th symposium on theory of computing. STOC, 1998. P. 209 – 218.
А. Dent. A Designer’s Guide to KEMs // Lecture Notes in Computer Science. Vol. 2898. P. 28 – 44.
Howgrave-Graham N., Silverman J., Singer A. and William Whyte. NAEP: Provable security in the presence of decryption failures // Cryptology ePrint Archive, Report 2003/172. [Electronic resource]. Online: https://eprint.iacr.org/2003/172.
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.
Goldreich O. Foundations of Cryptography/ Vol. 2. Cambridge University Press, 2000. 392 p.
Bellare M., Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols // ACM Conference on Computer and Communications Security. 1993. Vol. 1. P. 62 – 73.
Canetti R., Krawczyk H. Analysis of key-exchange protocols and their use for building secure channels // EUROCRYPT. 2001. Vol. 2045. P. 453 – 474.
Hoffstein J., Pipher J., Silverman H. NTRU: a ring based public key cryptosystem // Algorithmic Nuber Theory. Third International Symposium. 1998. P. 267 – 288.
Hirschhorn P., Hoffstein J., Howgrave-Graham N. Choosing NTRUEncrypt Parameters in Light of Com-bined Lattice Reduction and MITM Approaches // Lecture Notes in Computer Science. Vol. 5536. P. 58 – 78.
Mol, P., Young M. Recovering NTRU Secret Key from Inversion Oracles // PKS. 2008. Vol. 4939.P. 18 – 36.
Micheli G., Heninger N., Shani B. Characterizing overstretched NTRU attacks // Journal of Mathematical Cryptology. 2020. Vol 14, Is 1. P. 110 – 119.
Bernstein D., Lange T. Non-randomness of S-unit lattices // [Electronic resource]. Online: https://s-unit.attacks.cr.yp.to/spherical.html
Eisenträger K., Hallgren S., Kitaev A. and Song F. A quantum algorithm for computing the unit group of an arbitrary degree number field // STOC. 2014. P. 293 – 302.
Fujioka A., Suzuki K., Xagawa K. and Yoneyama K. Strongly secure authenticated key exchange from factoring codes and lattices // PKC. 2012. Vol. 7293. P. 467 – 484.
Boyd C., Cliff Y., Gonzalez J. and Kenneth G. Efficient one-round key exchange in the standard model // ACISP. 2008. Vol. 5107. P. 69 – 83.
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).