close this window
Complete the following form to e-mail a copy of this event to a friend.
Hello, The following event may be of interest to you: Secure Two-Party Computation Sublinear (Amortized) Time Tuesday, November 20, 2012 A lecture byMarina Raykova, Class of 2006Traditional approaches to generic secure computation begin by representing the function ⨍ being computed as a circuit. If ⨍ depends on each of its input bits, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for non-trivial functions since each party must “touch” every bit of their input lest information about the other party's input be leaked. This seems to rule out many applications of secure computation (e.g., database search) in scenarios where inputs are huge. Adapting and extending an idea of Ostrovsky and Shoup, we present an approach to secure two-party computation that yields protocols running in sublinear time, in an amortized sense, for functions that can be computed in sublinear time on a random-access machine (RAM). Moreover, each party is required to maintain state that is only (essentially) linear in its own input size. Our protocol applies generic secure two-party computation on top of oblivious RAM (ORAM). We present an optimized version of our protocol using Yao's garbled-circuit approach and a recent ORAM construction of Shi et al.We describe an implementation of this protocol, and evaluate its performance for the task of obliviously searching a database with over 1 million entries.Because of the cost of our basic steps, our solution is slower than Yao on small inputs. However, our implementation outperforms Yao already on DB sizes of 218 entries (a quite small DB by today's standards). Location: RKC 100 Sponsor: Computer Science Program Contact: Keith O'Hara. E-mail: [email protected] Phone: 845-752-2359 If you would like to see more events please visit the following URL: http://www.bard.edu/news/events/