Paper 2023/1652
On SigmaProtocols and (packed) BlackBox Secret Sharing Schemes
Abstract
$\Sigma$protocols are a widely utilized, relatively simple and well understood type of zeroknowledge proofs. However, the well known Schnorr $\Sigma$protocol for proving knowledge of discrete logarithm in a cyclic group of known prime order, and similar protocols working over this type of groups, are hard to generalize to dealing with other groups. In particular with hidden order groups, due to the inability of the knowledge extractor to invert elements modulo the order. In this paper, we introduce a universal construction of $\Sigma$protocols designed to prove knowledge of preimages of group homomorphisms for any abelian finite group. In order to do this, we first establish a general construction of a $\Sigma$protocol for $\mathfrak{R}$module homomorphism given only a linear secret sharing scheme over the ring $\mathfrak{R}$, where zero knowledge and special soundness can be related to the privacy and reconstruction properties of the secret sharing scheme. Then, we introduce a new construction of 2outof$n$ packed blackbox secret sharing scheme capable of sharing $k$ elements of an arbitrary (abelian, finite) group where each share consists of $k+\log n3$ group elements. From these two elements we obtain a generic ``batch'' $\Sigma$protocol for proving knowledge of $k$ preimages of elements via the same group homomorphism, which communicates $k+\lambda3$ elements of the group to achieve $2^{\lambda}$ knowledge error. For the case of class groups, we show that our $\Sigma$protocol improves in several aspects on existing proofs for knowledge of discrete logarithm and other related statements that have been used in a number of works. Finally, we extend our constructions from group homomorphisms to the case of ZKready functions, introduced by Cramer and Damg\aa rd in Crypto 09, which in particular include the case of proofs of knowledge of plaintext (and randomness) for some linearly homomorphic encryption schemes such as JoyeLibert encryption. However, in the case of JoyeLibert, we show an even better alternative, using Shamir secret sharing over Galois rings, which achieves $2^{k}$ knowledge soundness by communicating $k$ ciphertexts to prove $k$ statements.
Note: Accidentally, the most recent version incorporated a few examples that we are currently drafting. They will be reintegrated in a later update.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in PKC 2024
 Keywords
 Sigma ProtocolsBlackBox Secret SharingBatch Proofs
 Contact author(s)

claudia bartoli @ imdea org
ignacio cascudo @ imdea org  History
 20240611: last of 3 revisions
 20231025: received
 See all versions
 Short URL
 https://ia.cr/2023/1652
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1652, author = {Claudia Bartoli and Ignacio Cascudo}, title = {On SigmaProtocols and (packed) BlackBox Secret Sharing Schemes}, howpublished = {Cryptology ePrint Archive, Paper 2023/1652}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1652}}, url = {https://eprint.iacr.org/2023/1652} }