1. An Efficient Pairing-Based Shuffle Argument 2017 Asiacrypt NIZK Pairings
    Prastudy Fauzi and Helger Lipmaa and Janno Siim and Michal Zajac
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @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, Report 2017/894},
    year = {2017},
    note = {\url{https://eprint.iacr.org/2017/894}},
    }

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 100000 ciphertexts in less than a minute and verify it in less than 1.5 minutes.

  1.