Welcome to the resource topic for 2022/1645
Title:
The Return of the SDitH
Authors: Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, Dongze Yue
Abstract:This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform.
At the heart of our proposal is a new approach to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with N parties can be repeated D times using parallel composition to reach the same soundness as a protocol run with N^D parties. However, the former comes with D times higher communication costs, often mainly contributed by the usage of D auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating $N^D$ shares, arranged into a $D$-dimensional hypercube of side $N$ containing only one auxiliary’ state. We derive from this hypercube D sharings of size N which are used to run D instances of an N party MPC protocol. This approach leads to an MPCitH protocol with 1/N^D soundness error, requiring N^D offline computation, only ND online computation, and only 1 `auxiliary’. As the, potentially offline, share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition.
Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO’22) on code-based signatures, and obtain a new signature scheme that achieves a 3.3x improvement in global runtime, and a 15x improvement in online runtime for their shortest signatures size (8.5 kB). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6.7 kB for 60 ms offline, or 5.6 kB for 700 ms offline. For NIST security level 1, online signature cost is around 3 million cycles (1 ms on commodity processors), regardless of signature size.
ePrint: https://eprint.iacr.org/2022/1645
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .