Perfectly secure message transmission

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 connecti...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 1993-01, Vol.40 (1), p.17-47
Main Authors: DOLEV, D, DWORK, C, WAARTS, O, YUNG, M
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Communication
Communications networks
Computer programming
Computer science
control theory
systems
Computer systems performance. Reliability
Cybersecurity
Exact sciences and technology
Lower bounds
Messages
Networks
Processors
Security management
Software
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0004-5411
1557-735X
DOI:10.1145/138027.138036