Notes on Bayer and Groth's verifiable shuffle

Bayer and Groth Verifiable Shuffles: Stephanie Bayer and Jens Groth. Efficient zero-knowledge argument for correctness of a shuffle. EUROCRYPT 2012.

The original version of the verifiable shuffle is here. Our modified version of the verified shuffle is here and mirrored here.

We modified Bayer and Groth's verifiable shuffle, decreasing latency by more than an order of magnitude. We optimized the shuffle by applying the following improvements:

• Added OpenMP directives to optimize key operations, such as Brickell et al.'s multi-exponentiation routines.
• Replaced the use of integers with Moon and Langley's implementation of Bernstein's curve25519 group. (We avoid point compression and decompression in intermediary operations to improve speed.)
• Improved point serialization and deserialization with byte-level representations of the data.
• Taking into account different performance profile of curve25519, replaced some multi-exponentiation routines with naive version and tweaked multi-exponentiation window sizes. The bottleneck for the shuffle is currently in multi-exponentiation routines.
• Added some more small optimizations (e.g. powers of 2, reduce dynamic memory allocations, etc.)

Stadium

SOSP Paper: Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. Stadium: A Distributed Metadata-Private Messaging System. SOSP 2017.

ePrint: Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. Stadium: A Distributed Metadata-Private Messaging System. Cryptology ePrint Archive, Report 2016/943. http://eprint.iacr.org/2016/943. 2016.

This version of the shuffle library was used to implement verifiable shuffles in Stadium.