TY - GEN
T1 - Two attacks on rank metric code-based schemes
T2 - 24th Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2018
AU - Debris-Alazard, Thomas
AU - Tillich, Jean Pierre
N1 - Publisher Copyright:
© 2018, International Association for Cryptologic Research.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - RankSign [30] is a code-based signature scheme proposed to the NIST competition for quantum-safe cryptography [5] and, moreover, is a fundamental building block of a new Identity-Based-Encryption (IBE) [26]. This signature scheme is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. Unfortunately we will show that all the parameters proposed for this scheme in [5] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords. Therefore, without RankSign the IBE cannot be instantiated at this time. As a second contribution we will show that the problem is deeper than finding a new signature in rank-based cryptography, we also found an attack on the generic problem upon which its security reduction relies. However, contrarily to the RankSign scheme, it seems that the parameters of the IBE scheme could be chosen in order to avoid our attack. Finally, we have also shown that if one replaces the rank metric in the [26] IBE scheme by the Hamming metric, then a devastating attack can be found.
AB - RankSign [30] is a code-based signature scheme proposed to the NIST competition for quantum-safe cryptography [5] and, moreover, is a fundamental building block of a new Identity-Based-Encryption (IBE) [26]. This signature scheme is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. Unfortunately we will show that all the parameters proposed for this scheme in [5] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords. Therefore, without RankSign the IBE cannot be instantiated at this time. As a second contribution we will show that the problem is deeper than finding a new signature in rank-based cryptography, we also found an attack on the generic problem upon which its security reduction relies. However, contrarily to the RankSign scheme, it seems that the parameters of the IBE scheme could be chosen in order to avoid our attack. Finally, we have also shown that if one replaces the rank metric in the [26] IBE scheme by the Hamming metric, then a devastating attack can be found.
KW - Code-based cryptography
KW - Cryptanalysis
KW - Identity based encryption
KW - Rank metric
KW - Signature scheme
U2 - 10.1007/978-3-030-03326-2_3
DO - 10.1007/978-3-030-03326-2_3
M3 - Conference contribution
AN - SCOPUS:85057581751
SN - 9783030033255
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 62
EP - 92
BT - Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Peyrin, Thomas
A2 - Galbraith, Steven
PB - Springer Verlag
Y2 - 2 December 2018 through 6 December 2018
ER -