Title: Private Branching Programs: On Communication-Efficient Cryptocomputing
Speaker: Helger Lipmaa University College London
Time: 2008-05-21 13:30-2008-05-21 14:30
Venue: FIT Building 4-603, Tsinghua University
We polish a recent cryptocomputing method that makes it possible to cryptocompute every language in $\mathbf{L/poly}$. We give several nontrivial applications, including: (a) A CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (b) A protocol that makes it possible to compute (say) how similar is client's input to an element in server's database, without revealing any information to the server, (c) A protocol for private database updating with low amortized complexity.