Perfectly secure message transmission
- 2 January 1993
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 40 (1) , 17-47
- https://doi.org/10.1145/138027.138036
Abstract
This paper studies the problem of perfectly secure communication in general network in which processors and communication lines may be faulty. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms are obtained that operate with this connectivity and rely on no complexity-theoretic assumptions. These are the first algorithms for secure communication in a general network to simultaneously achieve the three goals of perfect secrecy, perfect resiliency, and worst-case time linear in the diameter of the network.Keywords
This publication has 4 references indexed in Scilit:
- Fault Tolerance in Networks of Bounded DegreeSIAM Journal on Computing, 1988
- Easy impossibility proofs for distributed consensus problemsDistributed Computing, 1986
- On sharing secrets and Reed-Solomon codesCommunications of the ACM, 1981
- How to share a secretCommunications of the ACM, 1979