Paper 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.