Paper 2026/1290

A Compact Signature Scheme Based on QC-MDGM Codes

Abstract

Constructing a post-quantum signature scheme that is simultaneously compact and efficient remains a central challenge in code based cryptography. Existing schemes based on turning a zero-knowledge identification scheme into a signature exhibit either large signatures or slow verification procedures, while the design of hash-and-sign schemes has led to constructions such as Wave and MIRANDA, having small signatures at the cost of massive public key sizes and time-consuming signature algorithms. In this work, we present ASTRA-Sign: a quASi cyclic code-based full-distance decoding TRApdoor Signature Scheme, combining the hash-and-sign paradigm with quasi-cyclic moderate density generator matrix codes to obtain small signatures and small public keys. The security of our scheme is based on the hardness of finding low weight codewords in quasi-cyclic codes, and on the hardness of finding a codeword that has full Hamming distance from a given random vector. We analyse key recovery and signature forgery attacks against ASTRA, and we propose several parameter sets achieving 128-, 192- and 256-bit security. Our scheme exhibits public keys and signatures below 1 kiB for 128 bits of security, with 40 µs verification times.