TY - GEN
T1 - Interleaved Prange
T2 - 13th International Conference on Post-Quantum Cryptography, PQCrypto 2022
AU - Porwal, Anmoal
AU - Holzbaur, Lukas
AU - Liu, Hedongliang
AU - Renner, Julian
AU - Wachter-Zeh, Antonia
AU - Weger, Violetta
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - Due to the recent challenges in post-quantum cryptography, several new approaches for code-based cryptography have been proposed. For example, a variant of the McEliece cryptosystem based on interleaved codes was proposed. In order to deem such new settings secure, we first need to understand and analyze the complexity of the underlying problem, in this case the problem of decoding a random interleaved code. A simple approach to decode such codes, would be to randomly choose a vector in the row span of the received matrix and run a classical information set decoding algorithm on this erroneous codeword. In this paper, we propose a new generic decoder for interleaved codes, which is an adaption of the classical idea of information set decoding by Prange and perfectly fits the interleaved setting. We then analyze the cost of the new algorithm and compare it to the other approaches.
AB - Due to the recent challenges in post-quantum cryptography, several new approaches for code-based cryptography have been proposed. For example, a variant of the McEliece cryptosystem based on interleaved codes was proposed. In order to deem such new settings secure, we first need to understand and analyze the complexity of the underlying problem, in this case the problem of decoding a random interleaved code. A simple approach to decode such codes, would be to randomly choose a vector in the row span of the received matrix and run a classical information set decoding algorithm on this erroneous codeword. In this paper, we propose a new generic decoder for interleaved codes, which is an adaption of the classical idea of information set decoding by Prange and perfectly fits the interleaved setting. We then analyze the cost of the new algorithm and compare it to the other approaches.
KW - Code-based cryptography
KW - Information set decoding
KW - Interleaved codes
UR - http://www.scopus.com/inward/record.url?scp=85140456883&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-17234-2_4
DO - 10.1007/978-3-031-17234-2_4
M3 - Conference contribution
AN - SCOPUS:85140456883
SN - 9783031172335
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 69
EP - 88
BT - Post-Quantum Cryptography - 13th International Workshop, PQCrypto 2022, Proceedings
A2 - Cheon, Jung Hee
A2 - Johansson, Thomas
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 28 September 2022 through 30 September 2022
ER -