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 paradigm known as ``Sigma protocol with helper'', 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 is competitive with respect to existing solutions of similar type.

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

Date: received 3 Aug 2021, last revised 8 Nov 2021

Contact author: epersichetti at fau edu

Available format(s): PDF | BibTeX Citation

Version: 20211108:135843 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]