1987 · 1.1K citations · 14 references
ComputingComputer ScienceComputer NetworksCryptographyDistributed SystemsCryptographic Protocol DesignCryptographic ProtocolsDistributed ComputingLeader ElectionNetwork ProtocolsSecret SharingBroadcastByzantine AgreementConstant-round Secure ComputationReductionsVerifiable Secret Sharing
Verifiable secret sharing (VSS) is a cryptographic primitive that distributes a secret among processors so that only a quorum can reconstruct it, enabling reductions for problems such as fair voting, leader election, and Byzantine agreement, and serving as a bottleneck in fault‑tolerant protocols. This paper presents an extremely efficient, non‑interactive protocol for verifiable secret sharing. The authors design a non‑interactive protocol that achieves verifiable secret sharing with extreme efficiency, reducing communication and round complexity compared to prior schemes.
This paper presents an extremely efficient, non-interactive protocol for verifiable secret sharing. Verifiable secret sharing (VSS) is a way of bequeathing information to a set of processors such that a quorum of processors is needed to access the information. VSS is a fundamental tool of cryptography and distributed computing. Seemingly difficult problems such as secret bidding, fair voting, leader election, and flipping a fair coin have simple one-round reductions to VSS. There is a constant-round reduction from Byzantine Agreement to non-interactive VSS. Non-interactive VSS provides asynchronous networks with a constant-round simulation of simultaneous broadcast networks whenever even a bare majority of processors are good. VSS is constantly repeated in the simulation of fault-free protocols by faulty systems. As verifiable secret sharing is a bottleneck for so many results, it is essential to find efficient solutions.
14
Adi Shamir · Communications of the ACM · 1979 · 13.5K citations · Full text
Shafi Goldwasser, Silvio Micali · Journal of Computer and System Sciences · 1984 · 2.6K citations
Theory and application of trapdoor functions
Andrew Chi-Chih Yao · 1982 · 1K citations