IACR News item: 06 April 2021
Toomas Krips, 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).
Additional news items may be found on the IACR news page.