AuthorsP. Fauzi, H. Lipmaa, M. Zając and J. Siim
EditorsT. Takagi and T. Peyrin
TitleAn Efficient Pairing-Based Shuffle Argument
AfilliationCryptography
Project(s)No Simula project
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