2018/04/07 by Thomas Debris-Alazard, Debris-Alazard, Thomas, Jean–Pierre Tillich +1 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1804.02556
openalex publication_date 2018/04/07 · openalex created_date 2022/09/05 · openalex updated_date 2026/07/28
RankSign [GRSZ14a] is a code-based signature scheme proposed to the NIST\ncompetition for quantum-safe cryptography [AGHRZ17] and, moreover, is a\nfundamental building block of a new Identity-Based-Encryption (IBE) [GHPT17a].\nThis signature scheme is based on the rank metric and enjoys remarkably small\nkey sizes, about 10KBytes for an intended level of security of 128 bits.\nUnfortunately we will show that all the parameters proposed for this scheme in\n[AGHRZ17] can be broken by an algebraic attack that exploits the fact that the\naugmented LRPC codes used in this scheme have very low weight codewords.\nTherefore, without RankSign the IBE cannot be instantiated at this time. As a\nsecond contribution we will show that the problem is deeper than finding a new\nsignature in rank-based cryptography, we also found an attack on the generic\nproblem upon which its security reduction relies. However, contrarily to the\nRankSign scheme, it seems that the parameters of the IBE scheme could be chosen\nin order to avoid our attack. Finally, we have also shown that if one replaces\nthe rank metric in the [GHPT17a] IBE scheme by the Hamming metric, then a\ndevastating attack can be found.\n