Paper 2022/1407

Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head

Thibauld Feneuil, CryptoExperts (France), Sorbonne University
Matthieu Rivain, CryptoExperts (France)
Abstract

The MPC-in-the-Head paradigm is a popular framework to build zero-knowledge proof systems using techniques from secure multi-party computation (MPC). While this paradigm is not restricted to a particular secret sharing scheme, all the efficient instantiations proposed so far rely on additive secret sharing. In this work, we show how applying a threshold linear secret sharing scheme (threshold LSSS) can be beneficial to the MPC-in-the-Head paradigm. For a general MPC protocol model capturing most of the existing MPCitH schemes, we show that our approach improves the soundness of the underlying proof system from $1/N$ down to $1/\binom{N}{\ell}$, where $N$ is the number of parties and $\ell$ is the threshold of the sharing scheme. While very general, our technique is limited to a number of parties $N \leq |\mathbb{F}|$, where $\mathbb{F}$ is the field underlying the statement, because of the MDS conjecture. Applying our approach with a low-threshold LSSS also boosts the performance of the proof system by making the MPC emulation cost independent of $N$ for both the prover and the verifier. The gain is particularly significant for the verification time which becomes logarithmic in $N$ (while the prover still has to generate and commit the $N$ input shares). We further generalize and improve our framework: we show how homomorphic commitments can get rid of the linear complexity of the prover, we generalize our result to any quasi-threshold LSSS, and we describe an efficient batching technique relying on Shamir's secret sharing. We finally apply our techniques to specific use-cases. We first propose a variant of the recent SDitH signature scheme achieving new interesting trade-offs. In particular, for a signature size of 10 KB, we obtain a verification time lower than $0.5$ ms, which is competitive with SPHINCS+, while achieving much faster signing. We further apply our batching technique to two different contexts: batched SDitH proofs and batched proofs for general arithmetic circuits based on the Limbo proof system. In both cases, we obtain an amortized proof size lower than $1/10$ of the baseline scheme when batching a few dozen statements, while the amortized performances are also significantly improved.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
zero-knowledge proofs MPC-in-the-Head threshold secret sharing post-quantum signatures
Contact author(s)
thibauld feneuil @ cryptoexperts com
matthieu rivain @ cryptoexperts com
History
2022-10-23: approved
2022-10-17: received
See all versions
Short URL
https://ia.cr/2022/1407
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1407,
      author = {Thibauld Feneuil and Matthieu Rivain},
      title = {Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1407},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1407}},
      url = {https://eprint.iacr.org/2022/1407}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.