AuthorsP. Fauzi, H. Lipmaa, J. Siim and M. Zając
EditorsT. Takagi and T. Peyrin
TitleAn Efficient Pairing-Based Shuffle Argument
AfilliationCryptography
StatusPublished
Publication TypeProceedings, refereed
Year of Publication2017
Conference NameInternational Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2017)
Volume1062524311562359528427
Pagination97 - 127
PublisherSpringer International Publishing
Place PublishedCham
ISBN Number978-3-319-70696-2
ISSN Number0302-9743
KeywordsCommon Reference String, Generic group model, Mix-net, Shuffle argument, Zero knowledge
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:

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ą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 100000100000 ciphertexts in less than a minute and verify it in less than 1.5 min.
URLhttp://link.springer.com/10.1007/978-3-319-70697-9_4
DOI10.1007/978-3-319-70697-910.1007/978-3-319-70697-9_4
Citation Key26618