## Cryptology ePrint Archive: Report 2021/1020

Designing a Practical Code-based Signature Scheme from Zero-Knowledge Proofs with Trusted Setup

Shay Gueron and Edoardo Persichetti and Paolo Santini

Abstract: This paper defines a new practical construction for a code-based signature scheme. We introduce a new protocol that is designed to follow the recent Sigma protocol with helper'' paradigm, and prove that the protocol's security reduces directly to the Syndrome Decoding Problem. The protocol is then converted to a full-fledged signature scheme via a sequence of generic steps that include: removing the role of the helper; incorporating a variety of protocol optimizations (using e.g., Merkle trees); applying the Fiat-Shamir transformation. The resulting signature scheme is EUF-CMA secure in the QROM, with the following advantages: a) Security relies on only minimal assumptions and is backed by a long-studied NP-complete problem; b) the trusted setup structure allows for obtaining an arbitrarily small soundness error. This minimizes the required number of repetitions, thus alleviating a major bottleneck associated with Fiat-Shamir schemes. We outline an initial performance estimation to confirm that our scheme greatly outpaces existing similar type solutions.

Category / Keywords: Code-based, Signature, Zero-Knowledge, Syndrome Decoding

Date: received 3 Aug 2021

Contact author: epersichetti at fau edu

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2021/1020

[ Cryptology ePrint archive ]