- A secure 2-party computation protocol for evaluating any branching program of size $S$, where the communication complexity is linear in the input size and only the running time grows with $S$.
- A secure 2-party computation protocol for evaluating any layered boolean circuit of size $S$ and $m$ outputs with communication complexity $O(S/\log S)+m\cdot\poly(\lambda)$.
-A 2-party {\em function secret sharing} scheme, as defined by Boyle et al. (Eurocrypt 2015), for general branching programs (with inverse polynomial error probability).
- A 1-round 2-server {\em private information retrieval} scheme supporting general searches expressed by branching programs.
Category / Keywords: Secure computation, function secret sharing, private information retrieval, fully homomorphic encryption Original Publication (in the same form): IACR-Crypto-2016 Date: received 3 Jun 2016, last revised 2 Sep 2016 Contact author: eboyle at alum mit edu, gilboan@bgu ac il, yuvali@cs technion ac il Available format(s): PDF | BibTeX Citation Note: Preliminary full version of the Crypto 2016 paper. Version: 20190305:125121 (All versions of this report) Short URL: ia.cr/2016/585