We present an approach to secure two-party computation that yields sublinear-time protocols, in an amortized sense, for functions that can be computed in sublinear time on a random access machine~(RAM). Furthermore, a party whose input is ``small'' is required to maintain only small state. We provide a generic protocol that achieves the claimed complexity, based on any oblivious RAM and any protocol for secure two-party computation. We then present an optimized version of this protocol, where generic secure two-party computation is used only for evaluating a small number of simple operations.
Category / Keywords: cryptographic protocols / amortized sublinear secure computation, oblivious RAM, RAM compiler Date: received 6 Sep 2011, last revised 8 Sep 2011 Contact author: mariana at cs columbia edu Available format(s): PDF | BibTeX Citation Version: 20110908:185138 (All versions of this report) Short URL: ia.cr/2011/482