Cryptology ePrint Archive: Report 2021/1430

Improved Zero-Knowledge Argument of Encrypted Extended Permutation

Yi Liu and 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.

Category / Keywords: cryptographic protocols / ElGamal encryption, Extended permutation, Private function evaluation, Zero-knowledge

Original Publication (in the same form): Inscrypt 2021

Date: received 25 Oct 2021

Contact author: liuy7 at mail sustech edu cn

Available format(s): PDF | BibTeX Citation

Version: 20211026:065655 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]