Confidential gossip

Epidemic gossip has proven a reliable and efficient technique for sharing information in a distributed network. Much of this reliability and efficiency derives from processes collaborating, sharing the work of distributing information. As a result of this collaboration, processes may receive information that was not originally intended for them. For example, some process may act as an intermediary, aggregating and forwarding messages from some set of sources to some set of destinations. But what if rumors are confidential? In that case, only processes that were originally intended to receive the rumor should be allowed to learn the rumor. This blatantly contradicts the basic premise of epidemic gossip, which assumes that processes can collaborate. In fact, if only processes in a rumor’s “destination set” participate in gossiping that rumor, we show that high message complexity is unavoidable. A natural approach is to rely on cryptography, for example, assuming that each process has a well-known public-key that can be used to encrypt the rumor. In a dynamic system, with changing sets of destinations, such a process seems potentially expensive. In this paper, we propose a scheme in which each rumor is broken into multiple fragments using a very simple coding scheme; any given fragment provides no information about the rumor, while together, the fragments can be reassembled into the original rumor. The processes collaborate in disseminating the rumor fragments in such a way that no process outside of a rumor’s destination set ever receives all the fragments of a rumor, while every process in the destination set eventually learns all the fragments. Notably, our solution operates in an environment where rumors are dynamically and continuously injected into the system and processes are subject to crashes and restarts. In addition, the presented scheme can tolerate a moderate amount of collusions among curious processes without a substantial increase in cost; curious processes are non-malicious processes that are not in a rumor’s destination set, and still want to learn the rumor (that is, collect all fragments of the rumor).