The Blockwise Rank Syndrome Learning problem and its applications to cryptography

Nicolas Aragon; Pierre Briaud; Victor Dyseryn; Philippe Gaborit; Adrien Vinçotte

Paper 2023/1875

The Blockwise Rank Syndrome Learning problem and its applications to cryptography

Nicolas Aragon, University of Limoges

Pierre Briaud, French Institute for Research in Computer Science and Automation

Victor Dyseryn, University of Limoges

Philippe Gaborit, University of Limoges

Adrien Vinçotte, University of Limoges

Abstract

Recently the notion of blockwise error in a context of rank based cryptography has been introduced by Sont et al. at AsiaCrypt 2023 . This notion of error, very close to the notion sum-rank metric, permits, by decreasing the weight of the decoded error, to greatly improve parameters for the LRPC and RQC cryptographic schemes. A little before the multi-syndromes approach introduced for LRPC and RQC schemes had also allowed to considerably decrease parameters sizes for LRPC and RQC schemes, through in particular the introduction of Augmented Gabidulin codes. In the present paper we show that the two previous approaches (blockwise errors and multi-syndromes) can be combined in a unique approach which leads to very efficient generalized RQC and LRPC schemes. In order to do so, we introduce a new problem, the Blockwise Rank Support Learning problem, which consists of guessing the support of the errors when several syndromes are given in input, with blockwise structured errors. The new schemes we introduce have very interesting features since for 128 bits security they permit to obtain generalized schemes for which the sum of public key and ciphertext is only 1.4 kB for the generalized RQC scheme and 1.7 kB for the generalized LRPC scheme. The new approach proposed in this paper permits to reach a 40 % gain in terms of parameters size when compared to previous results, obtaining even better results in terms of size than for the KYBER scheme whose total sum is 1.5 kB. Besides the description of theses new schemes the paper provides new attacks for the l-RD problem introduced in the paper by Song et al. of AsiaCrypt 2023, in particular these new attacks permit to cryptanalyze all blockwise LRPC parameters they proposed (with an improvement of more than 40bits in the case of structural attacks). We also describe combinatorial attacks and algebraic attacks, for the new Blockwise Rank Support Learning problem we introduce.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: post-quantum cryptography code-based cryptography rank metric cryptanalysis pkc
Contact author(s): nicolas aragon @ unilim fr
pierre briaud @ inria fr
victor dyseryn @ gmail com
gaborit @ unilim fr
adrien vincotte @ etu unilim fr
History: 2024-11-12: last of 2 revisions; 2023-12-06: received; See all versions
Short URL: https://ia.cr/2023/1875
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1875,
      author = {Nicolas Aragon and Pierre Briaud and Victor Dyseryn and Philippe Gaborit and Adrien Vinçotte},
      title = {The Blockwise Rank Syndrome Learning problem and its applications to cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1875},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1875}
}