Paper 2013/267

Multi-Party Computation of Polynomials and Branching Programs without Simultaneous Interaction

S. Dov Gordon, Tal Malkin, Mike Rosulek, and Hoeteck Wee


Halevi, Lindell, and Pinkas (CRYPTO 2011) recently proposed a model for secure computation that captures communication patterns that arise in many practical settings, such as secure computation on the web. In their model, each party interacts only once, with a single centralized server. Parties do not interact with each other; in fact, the parties need not even be online simultaneously. In this work we present a suite of new, simple and efficient protocols for secure computation in this "one-pass" model. We give protocols that obtain optimal privacy for the following general tasks: -- Evaluating any multivariate polynomial $F(x_1, \ldots ,x_n)$ (modulo a large RSA modulus N), where the parties each hold an input $x_i$. -- Evaluating any read once branching program over the parties' inputs. As a special case, these function classes include all previous functions for which an optimally private, one-pass computation was known, as well as many new functions, including variance and other statistical functions, string matching, second-price auctions, classification algorithms and some classes of finite automata and decision trees.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Eurocrypt 2013.
secure computation
Contact author(s)
sgordon @ appcomsci com
2013-05-13: received
Short URL
Creative Commons Attribution


      author = {S.  Dov Gordon and Tal Malkin and Mike Rosulek and Hoeteck Wee},
      title = {Multi-Party Computation of Polynomials and Branching Programs without Simultaneous Interaction},
      howpublished = {Cryptology ePrint Archive, Paper 2013/267},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.