Secure Hypergraphs: Privacy from Partial Broadcast
Authors:
- Matthew FranklinMFMatthew Franklin
- Moti YungMYMoti Yung
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 18 (3) , 437-450
Abstract
A "partial broadcast channel" enables one processor to send the same message---simultaneously and privately---to a fixed subset of processors. Suppose that a collection of processors are connected by an arbitrary network of partial broadcast channels (a hypergraph). We initiate the study of necessary and sufficient conditions, complexity bounds, and protocols for individual processors to exchange private messages across this network. Private message exchange, in turn, enables the realization of general secure computation primitives. The model (motivated by various environments such as multicast network architectures and group communication in distributed systems) is an intermediate setting between the private channels model and the full information model, both of which have been investigated extensively in the last few years. We assume a computationally unlimited adversary (i.e., the information theoretic notion of security), and our techniques are combinatorial. Both the possibility and the polynomial-time feasibility of private message exchange are investigated.Keywords
This publication has 17 references indexed in Scilit:
- Broadcast Encryption2001
- Secure Communication in Minimal Connectivity ModelsJournal of Cryptology, 2000
- Fault-tolerant Computation in the Full Information ModelSIAM Journal on Computing, 1998
- A secure and efficient conference key distribution system1995
- Perfectly secure message transmissionJournal of the ACM, 1993
- The Varieties of Secure Distributed Computation1993
- A lower bound for radio broadcastJournal of Computer and System Sciences, 1991
- Point-To-Multipoint Communication Over Broadcast LinksIEEE Transactions on Communications, 1984
- Key exchange using ‘keyless cryptography’Information Processing Letters, 1983
- Communication Theory of Secrecy Systems*Bell System Technical Journal, 1949