### Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme

Thomas Debris-Alazard and Jean-Pierre Tillich

##### Abstract

RankSign [GRSZ14a] is a code-based signature scheme proposed to the NIST competition for quantum-safe cryptography [AGHRZ17] and, moreover, is a fundamental building block of a new Identity-Based-Encryption (IBE) [GHPT17a]. 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 [AGHRZ17] 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 [GHPT17a] IBE scheme by the Hamming metric, then a devastating attack can be found.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.https://arxiv.org/pdf/1804.02556.pdf
Contact author(s)
thomas debris @ inria fr
jean-pierre tillich @ inria fr
History
2018-06-07: last of 3 revisions
See all versions
Short URL
https://ia.cr/2018/339

CC BY

BibTeX

@misc{cryptoeprint:2018/339,
author = {Thomas Debris-Alazard and Jean-Pierre Tillich},
title = {Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme},
howpublished = {Cryptology ePrint Archive, Paper 2018/339},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/339}},
url = {https://eprint.iacr.org/2018/339}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.