Paper 2013/766

RankSign : an efficient signature algorithm based on the rank metric

P. Gaborit, O. Ruatta, J. Schrek, and G. Zémor

Abstract

In this paper we propose a new approach to code-based signatures that makes use in particular of rank metric codes. When the classical approach consists in finding the unique preimage of a syndrome through a decoding algorithm, we propose to introduce the notion of mixed decoding of erasures and errors for building signature schemes. In that case the difficult problem becomes, as is the case in lattice-based cryptography, finding a preimage of weight above the Gilbert-Varshamov bound (case where many solutions occur) rather than finding a unique preimage of weight below the Gilbert-Varshamov bound. The paper describes RankSign: a new signature algorithm for the rank metric based on a new mixed algorithm for decoding erasures and errors for the recently introduced Low Rank Parity Check (LRPC) codes. We explain how it is possible (depending on choices of parameters) to obtain a full decoding algorithm which is able to find a preimage of reasonable rank weight for any random syndrome with a very strong probability. We study the semantic security of our signature algorithm and show how it is possible to reduce the unforgeability to direct attacks on the public matrix, so that no information leaks through signatures. Finally, we give several examples of parameters for our scheme, some of which with public key of size $5760$ bits and signature of size $1728$ bits. Moreover the scheme can be very fast for small base fields.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
signature schemecode based cryptorank metric
Contact author(s)
gaborit @ unilim fr
History
2013-11-25: received
Short URL
https://ia.cr/2013/766
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/766,
      author = {P.  Gaborit and O.  Ruatta and J.  Schrek and G.  Zémor},
      title = {RankSign : an efficient signature algorithm based on the rank metric},
      howpublished = {Cryptology ePrint Archive, Paper 2013/766},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/766}},
      url = {https://eprint.iacr.org/2013/766}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.