[Resource Topic] 2022/939: Multi-party Private Function Evaluation for RAM

Welcome to the resource topic for 2022/939

Multi-party Private Function Evaluation for RAM

Authors: Keyu Ji, Bingsheng Zhang, Tianpei Lu, and Kui Ren


Private function evaluation (PFE) is a special type of MPC protocols that, in addition to the input privacy, can preserve the function privacy. In this work, we propose a PFE scheme for RAM. In particular, we first design an efficient 4-server distributed ORAM scheme with amortized communication O(\log n) per access (both reading and writing). We then simulate a RISC RAM machine over the MPC platform, hiding (i) the memory access pattern, (ii) the machine state (including registers, program counter, condition flag, etc.), and (iii) the executed instructions. Our scheme can naturally support a simplified TinyRAM instruction set; if a public RAM program P with given inputs x needs to execute z instruction cycles, our PFE scheme is able to securely evaluate P(x) on private P and x within 5z+1 online rounds. We prototype and benchmark our system for set intersection, binary search, quicksort, and heapsort algorithms. For instance, to obliviously perform the binary search algorithm on a 2^{10} array takes 5.81s with function privacy.

ePrint: https://eprint.iacr.org/2022/939

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .