Paper 2022/939

Multi-party Private Function Evaluation for RAM

Keyu Ji
Bingsheng Zhang
Tianpei Lu
Kui Ren
Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. IEEE Transactions on Information Forensics and Security
DOI
10.1109/TIFS.2023.3236457
Keywords
Private function evaluationMPC for RAMDistributed ORAM
Contact author(s)
jikeyu @ zju edu cn
bingsheng @ zju edu cn
History
2023-01-29: revised
2022-07-20: received
See all versions
Short URL
https://ia.cr/2022/939
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/939,
      author = {Keyu Ji and Bingsheng Zhang and Tianpei Lu and Kui Ren},
      title = {Multi-party Private Function Evaluation for {RAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/939},
      year = {2022},
      doi = {10.1109/TIFS.2023.3236457},
      url = {https://eprint.iacr.org/2022/939}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.