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

Paper 2021/1020

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

Shay Gueron, 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Code-based Signature Zero-Knowledge Syndrome Decoding
Contact author(s): epersichetti @ fau edu
History: 2021-11-08: revised; 2021-08-06: received; See all versions
Short URL: https://ia.cr/2021/1020
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1020,
      author = {Shay Gueron and Edoardo Persichetti and Paolo Santini},
      title = {Designing a Practical Code-based Signature Scheme from Zero-Knowledge Proofs with Trusted Setup},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1020},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1020}
}