BIMSA > Cryptography and Its Applications Cryptography and Its Applications A Compact Rank-Metric Signature Scheme from Double-Circulant LRPC Codes
A Compact Rank-Metric Signature Scheme from Double-Circulant LRPC Codes
Organizer
Yingjie Zhang
Speaker
Babindamana Régis Freguin
Time
Wednesday, September 23, 2026 2:00 PM - 3:00 PM
Venue
A7-301
Online
Zoom 442 374 5045 (BIMSA)
Abstract
Stern-Véron identification protocols give code-based signatures with small keys, provided the public generator matrix is random, which is what makes it costly to store. In this work, we show that the systematic generator matrix of a double-circulant LRPC code works just as well and costs a single circulant row. Combined with the rank-metric Véron protocol and the Fiat-Shamir transform, this gives a signature whose public key is that row plus one noisy codeword. The protocol never decodes, so the low-rank trapdoor stays hidden and security reduces to rank syndrome decoding for ideal codes, the assumption behind ROLLO and Durandal. We prove completeness, soundness and zero-knowledge, give size formulas, a worked example over $\mathbb{F}_{2^5}$ and a comparison with Wave, Durandal and rank-metric CVE.