Communications in Cryptology IACR CiC

Feldman's Verifiable Secret Sharing for a Dishonest Majority

Authors

Yi-Hsiu Chen, Yehuda Lindell
Yi-Hsiu Chen ORCID
Coinbase, USA
yihsiuc at pm dot me
Yehuda Lindell ORCID
Coinbase, USA
yehuda dot lindell at gmail dot com

Abstract

Verifiable secret sharing (VSS) protocols enable parties to share secrets while guaranteeing security (in particular, that all parties hold valid and consistent shares) even if the dealer or some of the participants are malicious. Most work on VSS focuses on the honest majority case, primarily since it enables one to guarantee output delivery (e.g., a corrupted recipient cannot prevent an honest dealer from sharing their value). Feldman's VSS is a well known and popular protocol for this task and relies on the discrete log hardness assumption. In this paper, we present a variant of Feldman's VSS for the dishonest majority setting and formally prove its security. Beyond the basic VSS protocol, we present a publicly-verifiable version, as well as show how to securely add participants to the sharing and how to refresh an existing sharing (all secure in the presence of a dishonest majority). We prove that our protocols are UC secure, for appropriately defined ideal functionalities.

References

[Can00]
Ran Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptol., 13(1):143–202, 2000. https://doi.org/10.1007/S001459910006.
Google Scholar ePrint
[Can01]
Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, 136–145. IEEE Computer Society, 2001. https://doi.org/10.1109/SFCS.2001.959888.
Google Scholar ePrint
[CD00]
Jan Camenisch and Ivan Damgård. Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In Tatsuaki Okamoto, editor, Advances in Cryptology - ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3-7, 2000, Proceedings, volume 1976 of Lecture Notes in Computer Science, 331–345. Springer, 2000. https://doi.org/10.1007/3-540-44448-3_25.
Google Scholar ePrint
[Fel87]
Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, 427–437. IEEE Computer Society, 1987. https://doi.org/10.1109/SFCS.1987.4.
Google Scholar ePrint
[Fis05]
Marc Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, 152–168. Springer, 2005. https://doi.org/10.1007/11535218_10.
Google Scholar ePrint
[Gol04]
Oded Goldreich. The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. ISBN 0-521-83084-2. https://doi.org/10.1017/CBO9780511721656.
Google Scholar ePrint
[KLR10]
Eyal Kushilevitz, Yehuda Lindell, and Tal Rabin. Information-theoretically secure protocols and security under composition. SIAM J. Comput., 39(5):2090–2112, 2010. https://doi.org/10.1137/090755886.
Google Scholar ePrint
[Sch89]
Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, 239–252. Springer, 1989. https://doi.org/10.1007/0-387-34805-0_22.
Google Scholar ePrint
[Sch99]
Berry Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic. In Michael J. Wiener, editor, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in Computer Science, 148–164. Springer, 1999. https://doi.org/10.1007/3-540-48405-1_10.
Google Scholar ePrint
[Sta96]
Markus Stadler. Publicly verifiable secret sharing. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, 190–199. Springer, 1996. https://doi.org/10.1007/3-540-68339-9_17.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/ak2isgvtw
History
Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Yi-Hsiu Chen and Yehuda Lindell, Feldman's Verifiable Secret Sharing for a Dishonest Majority. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/ak2isgvtw.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.