Paper 2023/994
A proposal for quantum GRS algorithm and the cryptanalysis for ROLLO and RQC
Abstract
Code-Based Cryptosystem, CBC, is one of the candidates for Post-Quantum Cryptosystems, PQCs. Its security primarily bases on the Syndrome Decoding Problem, SDP. In this paper, we focus on the rank CBC whose security relies on the rank SDP. The GRS (Gaborit-Ruatta-Schrek) algorithm is well known as the current best decoding algorithm for the rank SDP. We propose the quantum version of the GRS algorithm. Then, we introduce the attack strategy using that quantum algorithm for previous rank CBCs remained at the 2nd Round of the NIST's PQC standardization project, and consider the quantum security for those cryptosystems. We present a result that is effective for RQC by our attack method, so give new RQC's instances which is secure against that attack.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Rank code-based cryptographyGRS algorithmGrover's algorithmROLLORQC
- Contact author(s)
-
a_wakasugi @ eaglys co jp
m tada @ faculty chiba-u jp - History
- 2023-06-27: approved
- 2023-06-26: received
- See all versions
- Short URL
- https://ia.cr/2023/994
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/994,
author = {Asuka Wakasugi and Mitsuru Tada},
title = {A proposal for quantum {GRS} algorithm and the cryptanalysis for {ROLLO} and {RQC}},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/994},
year = {2023},
url = {https://eprint.iacr.org/2023/994}
}
