Paper 2011/081

Secure Datastructures based on Multiparty Computation

Tomas Toft

Abstract

The problem of secure multiparty computation -- performing some computation based on distributed, private inputs -- has been studied intensively for more than twenty years. This work includes both ``one shot'' applications as well as reactive tasks, where the exact computation is not known in advance. We extend this line of work by asking whether it is possible to \emph{efficiently} both update and query secret data. A clearer formulation is, perhaps, to ask whether is it possible to construct efficient datastructures based on secure multiparty computation primitives. It is possible to construct arbitrary secure datastructures based on an oblivious RAM (ORAM). However, current state of the art information theoretically secure solutions incur a poly-logarithmic overhead on both secure computation and memory. The overhead is much smaller when considering computationally secure solutions, however, this requires secure evaluation of a one-way function as a primitive, which may reintroduce a considerable overhead. By constructing a secure priority queue we show that practical datastructures are possible. The ideas are radically different than those used in any ORAM implementation: The present solution accesses data in a \emph{deterministic} manner, whereas all ORAMs \emph{randomize} the access pattern in order to hide it. The priority queue operations -- insertion into the structure and deletion of the minimal element contained therein -- both require $\bigo(\log^2 n)$ invocations of the cryptographic primitives (secure arithmetic and comparison) amortized in $O(1)$ rounds amortized, where $n$ is the overall number of operations performed.