ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 32-44, 978-7-302-24517-9 Tsinghua University Press

Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation Authors : Shlomi Dolev, Juan Garay, Niv Gilboa, Vladimir Kolesnikov [Download PDF]

Abstract:
In this paper we consider the problem of n agents wishing to perform a given computation on common inputs in a privacy preserving manner, in the sense that even if the entire memory contents of some of them are exposed, no information is revealed about the state of the computation, and where there is no a priori bound on the number of inputs. The problem has received ample attention recently in the context of swarm computing and Unmanned Aerial Vehicles (UAV) that collaborate in a common mission, and schemes have been proposed that achieve this notion of privacy for arbitrary computations, at the expense of one round of communication per input among the n agents.
In this work we show how to avoid communication altogether during the course of the computation, with the trade-off of computing a smaller class of functions, namely, those carried out by finite state automata. Our scheme, which is based on a novel combination of secret-sharing techniques and the Krohn-Rhodes decomposition of finite state automata, achieves the above goal in an information-theoretically secure manner, and, furthermore, does not require randomness during its execution.

Preview: