Paper 2021/1430

Improved Zero-Knowledge Argument of Encrypted Extended Permutation

Yi Liu, Qi Wang, and Siu-Ming Yiu

Abstract

Extended permutation (EP) is a generalized notion of the standard permutation. Unlike the one-to-one correspondence mapping of the standard permutation, EP allows to replicate or omit elements as many times as needed during the mapping. EP is useful in the area of secure multi-party computation (MPC), especially for the problem of private function evaluation (PFE). As a special class of MPC problems, PFE focuses on the scenario where a party holds a private circuit $C$ while all other parties hold their private inputs $x_1, \ldots, x_n$, respectively. The goal of PFE protocols is to securely compute the evaluation result $C(x_1, \ldots, x_n)$, while any other information beyond $C(x_1, \ldots, x_n)$ is hidden. EP here is introduced to describe the topological structure of the circuit $C$, and it is further used to support the evaluation of $C$ privately. For an actively secure PFE protocol, it is crucial to guarantee that the private circuit provider cannot deviate from the protocol to learn more information. Hence, we need to ensure that the private circuit provider correctly performs an EP. This seeks the help of the so-called \emph{zero-knowledge argument of encrypted extended permutation} protocol. In this paper, we provide an improvement of this protocol. Our new protocol can be instantiated to be non-interactive while the previous protocol should be interactive. Meanwhile, compared with the previous protocol, our protocol is significantly (\eg more than $3.4\times$) faster, and the communication cost is only around $24\%$ of that of the previous one.