Visible to the public Improved Veron Identification and Signature Schemes in the Rank Metric

TitleImproved Veron Identification and Signature Schemes in the Rank Metric
Publication TypeConference Paper
Year of Publication2019
AuthorsBellini, Emanuele, Caullery, Florian, Gaborit, Philippe, Manzano, Marc, Mateu, Victor
Conference Name2019 IEEE International Symposium on Information Theory (ISIT)
Date PublishedJuly 2019
ISBN Number978-1-5386-9291-2
Keywordscheating probability, code-based signature schemes, Computing Theory, cryptography, Decoding, digital signatures, double circulant codes, error correction codes, error-correcting codes, Fiat-Shamir transform, identification protocol, linear codes, Measurement, Metrics, probability, Protocols, pubcrawl, public key cryptography, public key size, quantum computing, quantum cryptography, random oracle model, rank metric, secure signature scheme, security metrics, signature size, smallest signature, Transforms, veron identification

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.

Citation Keybellini_improved_2019