Danny Dolev
Moti Yung
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.
- 11 ~DWORK, C., PELEG, D., PIPPENGER, N., AND UPFAL, E. Fault tolerance in networks of ~bounded degree. SIAMJ. Comput. 17, 5 (1988), 975-988. Google Scholar
- 12 ~FELDMAN, P. Optimal algorithms for Byzantine agreement. Ph.D. dissertation, Department ~of mathematics, MIT, Cambridge, Mass., 1988.Google Scholar
- 13 ~ELDMAN, P., AND MICAL1, S. Optimal algorithms for Byzantine agreement. Proceedings of ~the 20th Annual ACM Symposium on Theory of Computing (Chicago, II1., May 2-4). ACM, New ~York, 1988, pp. 148-161. Google Scholar
- 14 ~FISCHER, M., LYNCH, N., AND MERRITT, M. Easy impossibility proofs for distributed consen- ~sus problems. J. Distrib. Compttt. } (1986), 26-39. Google Scholar
- 15 ~GALIL, Z., HABER, S., AND YUNG, M. Primitives for designing multiparty protocols from ~specifications. Manuscript, 1989.Google Scholar
- 16 ~OLDREICH, O., MICALI, S., AND WIGDERSON, A. How to play ANY mental game. In ~Proceedings of 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May ~25-27). ACM, New York, 1987, pp. 218-229. Google Scholar
- 17 ~KARL1N, A., AND YAO, h. Probabilistic lower bounds for Byzantine agreement. Manuscript.Google Scholar
- 18 ~McELIECE, R., AND SARWATE, D. On sharing secrets and Reed-Solomon codes. Commztn. ~ACM 24, 9 (Sept. 1981), 583-584. Google Scholar
- 19 ~RABIN, M., AND LEHMANN, D. On the advantages of free choice: A symmetric and fully ~distributed solution to the dining philosophers problem. In Proceedings' of the Symposium on ~Principles' of Programming Languages. 1981, pp. 133-138. Google Scholar
- 20 ~RABIN, T., AND BEN-OR, M. Verifiable secret sharing and multiparty protocols with honest ~majority. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing. (Seattle, ~Wash., May 15 17). ACM, New York, 1989, pp. 73-85. Google Scholar
- 21 ~SHAMIR, A. How to share a secret. Commtm. ACM 22, 6 (June 1979), 612-613. Google Scholar
- 22 ~YAO, A. How to generate and exchange secrets. In Proceedings of the 29th Sympostum on ~Foundations of Computer Science. IEEE, New York, 1986, pp. 162-167.Google Scholar
Index Terms
- Perfectly secure message transmission
Recommendations
Perfectly secure message transmission
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer ScienceThe problem of perfectly secure communication in a general network in which processors and communication lines may be faulty is studied. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms ...
Perfectly secure message transmission in asynchronous networks
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed ProcessingWe study the problem of perfectly secure communication in general asynchronous networks where processors and communication lines may be Byzantine faulty. To our knowledge, this is the first work that solves the secure message transmission (SMT) problem ...
Perfectly Secure Message Transmission Revisited
EUROCRYPT '02: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in CryptologyAchieving secure communications in networks has been one of the most important problems in information technology. Dolev, Dwork, Waarts, and Yung have studied secure message transmission in one-way or two-way channels. They only consider the case when ...
Reviews
Morrie Gasser
Perfect security of communications as defined here refers to both secrecy and integrity of communications. In an environment with perfect security where a sender and receiver have some number n of wires with which to communicate, no adversary can learn anything about the data by observing any possible subset of s of those wires, and likewise no adversary can successfully disrupt communications by controlling any possibly unrelated subset of r of those wires. The authors claim to be the first to achieve perfect secrecy and integrity using an algorithm with a worst-case time linear in the diameter of the network. Past work has always resulted in a low-probability loss of integrity or secrecy. The paper explores the necessary relationships between s , r , and n , and then continues with a lengthy and highly mathematical discussion of the issues and the proposed algorithms, with a number of fairly complex proofs. While it is not clear whether the method has any practical benefit over others (considerations of practicability are well outside the scope of this paper), it appears to be an important theoretical result that should be mandatory reading for researchers in this field.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments