Helger Lipmaa's publications

An Efficient Pairing-Based Shuffle Argument

Prastudy Fauzi, Helger Lipmaa, Janno Siim and Michal Zajac. An Efficient Pairing-Based Shuffle Argument. In Thomas Peyrin and Tsuyoshi Takagi, editors, ASIACRYPT 2017, volume ? of Lecture Notes in Computer Science, pages ?--?, Hong Kong, China, December 3--7, 2017. Springer, Heidelberg.

File: [.pdf (713 KB)] pdf recommended.


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: 1 A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee, 2 A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zaj\k{a}c, 3 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.

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


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.