It is notably challenging to design an efficient and

secure signature scheme based on error-correcting codes. An

approach to build such signature schemes is to derive it from

an identification protocol through the Fiat-Shamir transform.

All such protocols based on codes must be run several rounds,

since each run of the protocol allows a cheating probability of

either 2/3 or 1/2. The resulting signature size is proportional to

the number of rounds, thus making the 1/2 cheating probability

version more attractive. We present a signature scheme based

on double circulant codes in the rank metric, derived from

an identification protocol with cheating probability of 2/3. We

reduced this probability to almost 1/2 to obtain the smallest

signature among code-based signature schemes based on the

Fiat-Shamir paradigm, around 22 KBytes for 128 bit security

level. Furthermore, among all code-based signature schemes,

our proposal has the lowest value of signature plus public key

size, and the smallest secret and public key sizes. We provide

a security proof in the Random Oracle Model, implementation

performances, and a comparison with the parameters of similar

signature schemes.

Cryptographie [1]

Florian Caullery

Darkmatter