Cryptology ePrint Archive: Report 2017/894

An Efficient Pairing-Based Shuffle Argument

Prastudy Fauzi and Helger Lipmaa and Janno Siim and Michal Zajac

Abstract: We construct the most efficient known pairing-based NIZK shuffle argument. It consists of three subarguments that were carefully chosen to obtain optimal efficiency of the shuffle argument:

* A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee,

* A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zając,

* A (simplified) consistency argument of Groth and Lu.

We prove the knowledge-soundness of the first two subarguments in the generic bilinear group model, and the culpable soundness of the third subargument under a KerMDH assumption. This proves the soundness of the shuffle argument. We also discuss our partially optimized implementation that allows one to prove a shuffle of $100\,000$ ciphertexts in less than a minute and verify it in less than $1.5$ minutes.

Category / Keywords: Common reference string, generic group model, mix-net, shuffle argument, zero knowledge

Original Publication (with minor differences): IACR-ASIACRYPT-2017

Date: received 7 Sep 2017, last revised 8 May 2019

Contact author: prastudy fauzi at gmail com,helger lipmaa@gmail com,jannosiim@gmail com,michal zajac@ut ee

Available format(s): PDF | BibTeX Citation

Note: Fixed a subtle flaw with the zero-knowledge property

Version: 20190508:083956 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]