Brief Announcement: Swarming Secrets

We present information-theoretically secure schemes for sharing and modifying secrets among a dynamic swarm of computing devices. The schemes support an unlimited number of changes to the swarm including players joining and leaving the swarm, while swarms may be merged, cloned or split. The schemes securely and distributively maintain a global state for the swarm, and support an unlimited number of changes to the state according to received input. Our schemes are based on a novel construction of a strongly oblivious universal Turing Machine and on a distributed evaluation of this TM that reveals nothing to an adversary beyond a bound on the space complexity of the TM. Categories and Subject Descriptors: C.2.1: Distributed networks General Terms: Security, Theory. Keywords: Swarm, Multi-Party Computation, Strongly Oblivious TM. Introduction. Motivated by swarm computing security [5], we present the first information-theoretically secure implementation of a (strongly) oblivious universal Turing machine, that supports private processing of an unbounded number of inputs, while revealing nothing to the adversary besides the space complexity of the Turing Machine. Thus, in particular, implementing secure multi party computation on infinite sequence of inputs, at the cost of one communication round per transition of a Turing Machine. Comparison with one-shot multi-party computation and references to previous work in this area appear in an extended version of our paper [3]. We consider swarms that are dynamic in terms of membership, tasks, input and output.