April 16, 2021


Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

More Efficient Shuffle Argument from Unique Factorization, by Toomas Krips and Helger Lipmaa

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).