Multiparty computation with faulty majority
- 1 January 1989
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 468-473
- https://doi.org/10.1109/sfcs.1989.63520
Abstract
The problem of performing a multiparty computation when more than half of the processors are cooperating Byzantine faults is addressed. It is shown how to compute any Boolean function of n inputs distributively, preserving the privacy of inputs held by nonfaulty processors and ensuring that faulty processors obtain the function value if and only if the nonfaulty processors do. If the nonfaulty processors do not obtain the correct function value, they detect cheating with high probability. The solution is based on a new type of verifiable secret sharing in which the secret is revealed not all at once but in small increments. This process ensures that all processors discover the secret at roughly the same time. The solution assumes the existence of an oblivious transfer protocol and uses broadcast channels. The processors are not required to have equal computing power.Keywords
This publication has 13 references indexed in Scilit:
- Limits on the provable consequences of one-way permutationsPublished by Association for Computing Machinery (ACM) ,1989
- Completeness theorems for non-cryptographic fault-tolerant distributed computationPublished by Association for Computing Machinery (ACM) ,1988
- On the cunning power of cheating verifiers: Some observations about zero knowledge proofsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- How to generate and exchange secretsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Limits on the security of coin flips when half the processors are faultyPublished by Association for Computing Machinery (ACM) ,1986
- A randomized protocol for signing contractsCommunications of the ACM, 1985
- Verifiable secret sharing and achieving simultaneity in the presence of faultsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- A robust and verifiable cryptographically secure election schemePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- How to simultaneously exchange a secret bit by flipping a symmetrically-biased coinPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- How to share a secretCommunications of the ACM, 1979