Paper Info
Title
Secure hypergraphs: privacy from partial broadcast (Extended Abstract)
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 an all-powerful 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.
Year
DOI
Venue
1995
10.1145/225058.225077
STOC
Keywords
Field
DocType
secure computation,distributed system,information model,group communication,polynomial time
Discrete mathematics,Broadcasting,Atomic broadcast,Computer science,Constraint graph,Theoretical computer science,Secure two-party computation
Conference
Citations 
PageRank 
References 
7
0.58
7
Authors
2
Name
Order
Citations
PageRank
Matthew K. Franklin1959119.11
Moti Yung2120801152.41