Towards Efficient Private Distributed Computation on Unbounded Input Streams

In the problem of swarm computing, $n$ agents wish to securely and distributively perform a computation on common inputs, in such a way that even if the entire memory contents of some of them are exposed, no information is revealed about the state of the computation. Recently, Dolev, Garay, Gilboa and Kolesnikov [ICS'11] considered this problem in the setting of information-theoretic semi-honest security, showing how to perform such computations on input streams of {unbounded length}. The cost of their solution, however, is exponential in the size of the Finite State Automaton (FSA) computing the function. In this work we consider the computational setting, and show how to still process {a priori} unbounded inputs at a cost {linear} in $m$, the number of FSA states. In particular, our algorithms achieve the following: + In the case of $(n,n)$ reconstruction (i.e. in which all $n$ agents participate in reconstruction of the distributed computation), the storage and reconstruction complexity is $O(mn^2$). Each agent requires $O(mn)$ time to process each input symbol. + In the case of $(t+1,n)$ reconstruction (where $t$ corrupted agents do not take part in the reconstruction), the above costs are $O({n X t})$. + Using additively homomorphic encryption, the costs are $O(m)$ for each input symbol and for reconstruction, which is asymptotically optimal.