Paper 2021/438

More Efficient Shuffle Argument from Unique Factorization

Toomas Krips and Helger Lipmaa

Abstract

Efficient shuffle arguments are essential in mixnet-based e-voting solutions. Terelius and Wikström (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the TW characterization of permutation matrices; this enables us to reduce the communication without adding too much to the computation. We make the TW shuffle argument computationally more efficient by using Groth's coefficient-product argument (JOC, 2010). Additionally, we use batching techniques. The resulting shuffle argument is the fastest known $\leq 5$-message shuffle argument, and, depending on the implementation, can be faster than Groth's argument (the fastest 7-message shuffle argument).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. CT-RSA 2021
Keywords
Mix-netshuffle argumentunique factorization
Contact author(s)
helger lipmaa @ gmail com
History
2021-04-06: received
Short URL
https://ia.cr/2021/438
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/438,
      author = {Toomas Krips and Helger Lipmaa},
      title = {More Efficient Shuffle Argument from Unique Factorization},
      howpublished = {Cryptology ePrint Archive, Paper 2021/438},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/438}},
      url = {https://eprint.iacr.org/2021/438}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.