Perennial secure multiparty computation of universal Turing machine
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2018 Elsevier B.V. Consider a user who needs to perform computation over an initially unbounded stream of input. The user would like to compute functions of the input that change dynamically due to external events. The focus of this work is outsourcing such computation to a set of agents. The outsourcing must meet several constraints. Any large enough subset of agents must correctly emulate the user's computation on the unbounded stream of input. Any small subset of agents must obtain as little information as possible on the user's data, including the computed functions and any initial input. This privacy assurance must be maintained in an informationtheoretic sense. Finally, the set of agents is dynamic with agents joining and leaving the set and different sets of agents being merged, cloned or split. In this work, we show how to securely outsource such perennial computation. The user's required computation is modeled as programs for a universal Turing machine. The only information that the agents obtain on the user's secrets is an upper bound on the space complexity required to perform the computation. Each state transition of the user's Turing machine requires computation and communication that are linear in the Turing machine's space complexity and polynomial in the number of agents performing the computation for every round of computation. The communication and computational complexity for an agent joining or leaving the set of computing agents in a transition round are linear in the space complexity of the Turing machine and polynomial in the number of agents. Some of the tools we develop may be of independent interest. We construct a strongly oblivious Turing machine, in which the tape head moves only as a function of its current location. We also show how to securely share the description of a Turing machine among several agents and how to securely compute each Turing machine's transition in a constant number of communication rounds.
published proceedings

Theoretical Computer Science
citation count
complete list of authors

Dolev, ShlomiGaray, Juan AGilboa, NivKolesnikov, VladimirKumaramangalam, Muni Venkateswarlu
publication date
publisher
published in
Research
keywords

Informationtheoretic Security

Oblivious Turingmachine

Perennial Computation

Secret Sharing
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume