Secretive Birds: Privacy in Population Protocols
We study private computations in a system of tiny mobile agents. We consider the mobile population protocol model of Angluin et al.  and ask what can be computed without ever revealing any input to a curious adversary. We show that any computable predicate of the original population model can be made private through an obfuscation procedure that exploits the inherent non-determinism of the mobility pattern. In short, the idea is for every mobile agent to generate, besides its actual input value, a set of wrong input values to confuse the curious adversary. To converge to the correct result, the procedure has the agents eventually eliminate the wrong values; however, the moment when this happens is hidden from the adversary. This is achieved without jeopardizing the tiny nature of the agents: they still have very small storage size that is independent of the cardinality of the system. We present three variants of this obfuscation procedure that help compute respectively, remainder, threshold, and or predicates which, when composed, cover all those that can be computed in the population protocol model.
Record created on 2007-10-02, modified on 2016-08-08