Welcome to the resource topic for 2022/219
Title:
PFE: Linear Active Security, Double-Shuffle Proofs, and Low-Complexity Communication
Authors: Hanyu Jia, Xiangxue Li
Abstract:We consider private function evaluation (PFE) in malicious adversary model. Current state-of-the-art in PFE from Valiant’s universal circuits (Liu, Yu, et al., CRYPTO 2021) does not avoid the logarithmic factor in circuit size. In constructing linear active PFE, one essential building block is to prove the correctness of an extended permutation (EP, Mohassel and Sadeghian at EUROCRYPT 2013) by zero-knowledge protocols with linear complexity. The linear instantiation \mathcal{ZK}_{EP} by Mohassel, Sadeghian, and Smart (ASIACRYPT 2014) is a three-phase protocol, and each phase (dummy placement, replication, and permutation) is of size 2g. Its overhead thus seems really outrageous, reducing its practicability. We present in this paper a novel and efficient framework \mathcal{ZK}_{DS} for proving the correct EP. We show that \underline{d}ouble \underline{s}huffles suffice for EP (exponentiations and communication overheads are about 27% and 31% of \mathcal{ZK}_{EP}, respectively). Data owner(s) generates the randomness for the first shuffle whose outputs determine outgoing wires of the circuit defined by the function. Function owner reuses and extends the randomness in the second shuffle whose outputs determine the incoming wires. From \mathcal{ZK}_{DS}, we build an online/offline PFE framework with linear active security. The online phase could be instantiated by any well-studied secure function evaluation (SFE) with linear active security (e.g., Tiny-OT at CRYPTO 2012). The offline phase depends only on the private function f and uses \mathcal{ZK}_{DS} to prove the EP relationship between outgoing wires and incoming wires in the circuit \mathcal{C}_f derived from f.
ePrint: https://eprint.iacr.org/2022/219
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 .