Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography

被引:28
作者
Aragon, Nicolas [1 ,2 ]
Gaborit, Philippe [1 ,2 ]
Hauteville, Adrien [1 ,2 ]
Ruatta, Olivier [1 ,2 ]
Zemor, Gilles [1 ,2 ]
机构
[1] Univ Limoges, XLIM Res Lab, F-87060 Limoges, France
[2] Univ Bordeaux, Inst Math Bordeaux, F-33405 Bordeaux, France
关键词
Error correction codes; Iterative decoding; Cryptography; Encryption; MCELIECE; CRYPTANALYSIS; COMPLEXITY; ATTACKS;
D O I
10.1109/TIT.2019.2933535
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems A la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms-notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC code-based cryptosystem) in a rank metric context, due to the similar form of the public keys. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to 2/3 (n - k) when the previous decoding algorithm only decodes up to n - k/2 errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to n - k/2. This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 5893 bits for public key encryption, both for 128 bits of security.
引用
收藏
页码:7697 / 7717
页数:21
相关论文
共 41 条
[1]  
[Anonymous], 1991, P WORKSH THEOR APPL
[2]  
[Anonymous], ACCT
[3]  
Aragon N., 2017, P 1 ROUND SUBM NIST
[4]  
Aragon N., 2017, IMPROVEMENT GENERIC
[5]  
Aragon N, 2018, IEEE INT SYMP INFO, P2421, DOI 10.1109/ISIT.2018.8437464
[6]  
Baldi M, 2008, LECT NOTES COMPUT SC, V5229, P246, DOI 10.1007/978-3-540-85855-3_17
[7]   Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem [J].
Baldi, Marco ;
Chiaraluce, Franco ;
Garello, Roberto ;
Mininni, Francesco .
2007 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-14, 2007, :951-+
[8]   Security and complexity of the McEliece cryptosystem based on quasi-cyclic low-density parity-check codes [J].
Baldi, Marco ;
Bianchi, Marco ;
Chiaraluce, Franco .
IET INFORMATION SECURITY, 2013, 7 (03) :212-220
[9]  
Barbulescu R, 2014, LECT NOTES COMPUT SC, V8441, P1, DOI 10.1007/978-3-642-55220-5_1
[10]  
Berger T, 2004, LECT NOTES COMPUT SC, V3348, P218