Cryptology ePrint Archive: Report 2021/354

Efficient permutation protocol for MPC in the head

Peeter Laud

Abstract: The MPC-in-the-head construction (Ishai et al., STOC'07) give zero-knowledge proofs from secure multiparty computation (MPC) protocols. This paper presents an efficient MPC protocol for permuting a vector of values, making use of the relaxed communication model that can be handled by the MPC-in-the-head construction. Our construction allows more efficient ZK proofs for relations expressed in the Random Access Machine (RAM) model. As a standalone application of our construction, we present batch anonymizable ring signatures.

Category / Keywords: cryptographic protocols / zero knowledge, public-key cryptography

Date: received 17 Mar 2021

Contact author: peeter laud at cyber ee

Available format(s): PDF | BibTeX Citation

Version: 20210318:094249 (All versions of this report)

Short URL: ia.cr/2021/354


[ Cryptology ePrint archive ]