Paper 2017/894

An Efficient Pairing-Based Shuffle Argument

Prastudy Fauzi, Helger Lipmaa, 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.

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

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
Keywords
Common reference stringgeneric group modelmix-netshuffle argumentzero knowledge
Contact author(s)
prastudy fauzi @ gmail com
helger lipmaa @ gmail com
jannosiim @ gmail com
michal zajac @ ut ee
History
2019-05-08: revised
2017-09-17: received
See all versions
Short URL
https://ia.cr/2017/894
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/894,
      author = {Prastudy Fauzi and Helger Lipmaa and Janno Siim and Michal Zajac},
      title = {An Efficient Pairing-Based Shuffle Argument},
      howpublished = {Cryptology ePrint Archive, Paper 2017/894},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/894}},
      url = {https://eprint.iacr.org/2017/894}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.