International Association
for Cryptologic Research

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.