Communications in Cryptology IACR CiC

Analysis of Layered ROLLO-I: A BII-LRPC code-based KEM

Authors

Seongtaek Chee, Kyung Chul Jeong, Tanja Lange, Nari Lee, Alex Pellegrini, Hansol Ryu
Seongtaek Chee
The Affiliated Institute of ETRI, Daejeon, Republic of Korea
chee at nsr dot re dot kr
Kyung Chul Jeong
The Affiliated Institute of ETRI, Daejeon, Republic of Korea
jeongkc at nsr dot re dot kr
Tanja Lange
Eindhoven University of Technology, The Netherlands
tanja at hyperelliptic dot org
Nari Lee
The Affiliated Institute of ETRI, Daejeon, Republic of Korea
narilee at nsr dot re dot kr
Alex Pellegrini ORCID
Eindhoven University of Technology, The Netherlands
alex dot pellegrini at live dot com
Hansol Ryu
The Affiliated Institute of ETRI, Daejeon, Republic of Korea
hansolryu at nsr dot re dot kr
Keywords: Post-quantum cryptography code-based cryptography rank-metric code BII-LRPC code ROLLO-I

Abstract

We analyze Layered ROLLO-I, a code-based cryptosystem published in IEEE Communications Letters and submitted to the Korean post-quantum cryptography competition. Four versions of Layered ROLLO-I have been proposed in the competition. We show that the first two versions do not provide the claimed security against rank decoding attacks and give reductions to small instances of the original ROLLO-I scheme, which was a candidate in the NIST competition and eliminated there due to rank decoding attacks. As a second contribution, we provide two efficient message recovery attacks, affecting every security level of the first three versions of Layered ROLLO-I and security levels 128 and 192 of the fourth version.

References

[ABD+19]
Nicolas Aragon, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Adrien Hauteville, Olivier Ruatta, Jean-Pierre Tillich, Gilles Zémor, Carlos Aguilar Melchor, Slim Bettaieb, Loic Bidoux, Magali Bardet, and Ayoub Otmani. ROLLO. Technical report, NIST. available at Round 2 page. 2019.
Google Scholar ePrint
[BBB+20]
Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Vincent Neiger, Olivier Ruatta, and Jean-Pierre Tillich. An Algebraic Attack on Rank Metric Code-Based Cryptosystems. In Eurocrypt 2020, volume 12107 of LNCS, pages 64–93. 2020. DOI: 10.1007/978-3-030-45727-3_3
Google Scholar ePrint
[BBB+23]
Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, and Jean-Pierre Tillich. Revisiting algebraic attacks on MinRank and on the rank decoding problem. Designs, Codes and Cryptography, 2023. DOI: 10.1007/s10623-023-01265-x
Google Scholar ePrint
[BBC+20]
Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray A. Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, and Javier A. Verbel. Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. In Asiacrypt 2020, volume 12491 of LNCS, pages 507–536. 2020. DOI: 10.1007/978-3-030-64837-4_17
Google Scholar ePrint
[BBD09]
Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen. Post-Quantum Cryptography. Springer Berlin Heidelberg 2009.
Google Scholar ePrint
[Gop70]
Valery D. Goppa. A new class of linear error correcting codes. Problemy Peredachi Informatsii, 60:24-30, 1970.
Google Scholar ePrint
[GPT91]
Ernst M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. Ideals over a Non-Commutative Ring and thier Applications in Cryptology. In Donald W. Davies, editor, Advances in Cryptology – EUROCRYPT'91, volume 547 of Lecture Notes in Computer Science, pages 482–489, Brighton, UK. April 8–11, 1991. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/3-540-46416-6_41
Google Scholar ePrint
[KKN22]
Chanki Kim, Young-Sik Kim, and Jong-Seon No. Layered ROLLO-I. Submission to KpqC Competition Round 1. 2022.
Google Scholar ePrint
[KKN23a]
Chanki Kim, Young-Sik Kim, and Jong-Seon No. Comments and modification on Layered ROLLO on kPQC-forum. Slides attached to reply on KpqC bulletin, 19 May. 2023.
Google Scholar ePrint
[KKN23b]
Chanki Kim, Young-Sik Kim, and Jong-Seon No. Comments and modification on Layered ROLLO on kPQC-forum. Slides attached on KpqC Bulletin, 22 Sep. 2023.
Google Scholar ePrint
[KKN23c]
Chanki Kim, Young-Sik Kim, and Jong-Seon No. Comments and modification on Layered ROLLO on kPQC-forum. Slides attached to reply on KpqC Bulletin, 20 Oct. 2023.
Google Scholar ePrint
[KKN23d]
Chanki Kim, Young-Sik Kim, and Jong-Seon No. New Design of Blockwise Interleaved Ideal Low-Rank Parity-Check Codes for Fast Post-Quantum Cryptography. IEEE Communications Letters, 27(5):1277–1281, May 2023. DOI: 10.1109/lcomm.2023.3257136
Google Scholar ePrint
[LPR23]
Tanja Lange, Alex Pellegrini, and Alberto Ravagnani. On the security of REDOG. Cryptology ePrint Archive, Paper 2023/1205. 2023.
Google Scholar ePrint
[LPR24]
Tanja Lange, Alex Pellegrini, and Alberto Ravagnani. On the security of REDOG, pages 282–305. Springer Nature Singapore 2024. DOI: 10.1007/978-981-97-1238-0_15
Google Scholar ePrint
[McE78]
Robert J. McEliece. A Public-Key Cryptosystem Based on Algebraic Coding Theory. Jet Propulsion Laboratory DSN Progress Report 42–44. 1978.
Google Scholar ePrint
[Ove08]
R. Overbeck. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes. Journal of Cryptology, 21(2):280–301, April 2008. DOI: 10.1007/s00145-007-9003-9
Google Scholar ePrint
[Pra62]
Eugene Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5-9, 1962. DOI: 10.1109/TIT.1962.1057777
Google Scholar ePrint
[Sho94]
Peter W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In 35th Annual Symposium on Foundations of Computer Science, pages 124–134, Santa Fe, NM, USA. November 20–22, 1994. IEEE Computer Society Press. DOI: 10.1109/SFCS.1994.365700
Google Scholar ePrint
[WGR22]
Violetta Weger, Niklas Gassner, and Joachim Rosenthal. A Survey on Code-Based Cryptography. CoRR, January 2022. DOI: 10.48550/arXiv.2201.07119
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/a6qgy11zn4
History
Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07
How to cite

Seongtaek Chee, Kyung Chul Jeong, Tanja Lange, Nari Lee, Alex Pellegrini, and Hansol Ryu, Analysis of Layered ROLLO-I: A BII-LRPC code-based KEM. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a6qgy11zn4.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.