PFE: Linear Active Security, Double-Shuffle Proofs, and Low-Complexity Communication

We consider the private function evaluation (PFE) problem in the malicious adversary model. Current state-of-the-art in PFE based on Valiant’s universal circuits (Liu, Yu, etc., CRYPTO 2021) seems to reach a theoretical optimum (13g·logg) (g is the number of the gates in the circuit), but still does not avoid the logarithmic factor in circuit size. In constructing PFE with linear active security, one essential building block is to prove the correctness of an extended permutation (EP, Mohassel and Sadeghian at EUROCRYPT 2013) by a zero-knowledge (ZK) protocol with linear complexity. Mohassel, Sadeghian, and Smart (ASIACRYPT 2014) presented a three-phase instantiation ZK_EP, which is supposed to validate that the function owner has done his local computation in the right way. In particular, ZK_EP consists of a dummy placement phase, a replication phase, and a permutation phase, and each of the phases is of size 2g. The overhead required by ZK_EP thus seems really heavy, reducing its practicability. We present in this paper a novel and efficient framework ZK_DS for proving the correct EP. We show that double shuffles (DS) suffice in ZK_DS: one shuffle is of size u+g-o (u is the number of input wires in the circuit and o the number of output wires, and we have generally g≫u,u≈o), another is of size 2g, and no replication phase is required. The verifier generates the randomness for the first shuffle whose outputs determine the outgoing wires. The second shuffle reuses and extends the randomness and determines the incoming wires. Besides its linear complexity and succinct double-shuffle structure, ZK_DS reduces the communication overhead by more than 50% (including the ciphertexts and corresponding proofs), compared to ZK_EP. From ZK_DS, we can build an actively secure online/offline PFE framework with linear complexity. 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 function and uses ZK_DS to prove the EP relationship between u+g-o outgoing wires and 2g incoming wires in the topological circuit C_f derived from the private function f. The design pushes actively secure PFE to be more compact in practice.