Paper 2022/1645

The Return of the SDitH

Carlos Aguilar-Melchor, SandboxAQ, Palo Alto, USA
Nicolas Gama, SandboxAQ, Palo Alto, USA
James Howe, SandboxAQ, Palo Alto, USA
Andreas Hülsing, Eindhoven University of Technology, The Netherlands
David Joseph, SandboxAQ, Palo Alto, USA
Dongze Yue, SandboxAQ, Palo Alto, USA
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, Hypercube-MPCitH, 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. Hypercube-MPCitH leads to a protocol with $1/N^D$ soundness error, requiring $N^D$ offline computation, but with only $N\cdot D$ 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 8.1x improvement in global runtime and a 30x improvement in online runtime for their shortest signatures size (8,481 Bytes). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6,784 Bytes for 26 ms offline and 5,689 Bytes for 320 ms offline. For NIST security level 1, online signature cost is around 3 million cycles ($<$1 ms on commodity processors), regardless of signature size.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
Keywords
Code-Based CryptographyMPCitHSDitHSignaturesPost-Quantum CryptographyMPC
Contact author(s)
carlos aguilar @ sandboxaq com
nicolas gama @ sandboxaq com
james howe @ sandboxaq com
andreas @ huelsing net
david joseph @ sandboxaq com
dongze yue @ sandboxaq com
History
2023-02-27: revised
2022-11-25: received
See all versions
Short URL
https://ia.cr/2022/1645
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1645,
      author = {Carlos Aguilar-Melchor and Nicolas Gama and James Howe and Andreas Hülsing and David Joseph and Dongze Yue},
      title = {The Return of the SDitH},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1645},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1645}},
      url = {https://eprint.iacr.org/2022/1645}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.