An Efficient Scheme for Proving a Shuffle

By Jun Furukawa, Kazue Sako. 2001

339 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “It has many applications in voting [18], [19], mix-nets [20], and solvency proofs [17].”
Proactively Accountable Anonymous Messaging in Verdict (2012, background): “A cascade of cryptographically verifiable shuffles [23, 36] can offer the same security guarantees that Verdict does, but these shuffles generally require more expensive proofs-of-knowledge.”
Breaking and Mending Resilient Mix-Nets (2003, background): “The next two sections show attacks, countermeasures and analysis for Furukawa-Sako01 and Millimix mix-nets.”
A Verifiable Secret Shuffle of Homomorphic Encryptions (2003, methodology): “We use seven rounds, and the Furukawa–Sako paradigm can be used to obtain three-round HVZK arguments for correctness of a shuffle.”
Mixminion: design of a type III anonymous remailer protocol (2003, background): “These include flash mixes [16], hybrid mixes [17, 29], and provable shuffles [13, 28].”
Dissent in Numbers: Making Strong Anonymity Scale (2012, positive): “Two other approaches to anonymity theoretically offer security even against traffic analysis: verifiable shuffles [11, 32, 44], and “dining cryptographers” or DCnets [14, 36, 58].”
A verifiable secret shuffle and its application to e-voting (2001, background): “The notion of a shuffle of a collection of objects, records, or tokens is simple and intuitive, and useful examples abound in various daily human activities.”
Towards efficient traffic-analysis resistant anonymity networks (2013, background): “Dining cryptographers (D-C) nets [6, 16] and verifiable shuffles [13, 22, 31] are cryptographic techniques that offer strong resistance to traffic analysis without requiring batching.”
Sub-linear Zero-Knowledge Argument for Correctness of a Shuffle (2008, background): “Furukawa and Sako [17] suggested an efficient argument for correctness of a shuffle based on committing to a permutation matrix.”
Efficient Zero-Knowledge Argument for Correctness of a Shuffle (2012, methodology): “Furukawa and Sako [FS01] and Neff [Nef01, Nef03] proposed the first shuffles for ElGamal encryption with a complexity that depends linearly on the number of ciphertexts.”
Privacy-Preserving Set Operations (2005, background): “Shuffling can be easily accomplished with standard techniques [4,17,8,13,22], with communication complexity at most O(n(2)k).”
Structure-Preserving Signatures and Commitments to Group Elements (2010, background): “Such commitments have been found useful in contexts such as mix-nets, voting, digital credentials, blind signatures, leakage-resilient one-way functions and zero-knowledge proofs [11,30,50,66,77,81].”
Hang with your buddies to resist intersection attacks (2013, methodology): “However, particular variants such as MIX cascades [24, 1] and verifiable shuffles [22, 11] offer formally provable anonymity guarantees even against limited traffic analysis (though not against intersection attacks when messages are linkable).”
Stadium: A Distributed Metadata-Private Messaging System (2017, background): “Verifiable shuffles were originally proposed to allow globally verifiable e-voting [3, 13, 23, 35], another privacy related scenario; but they have typically been considered prohibitively expensive for low-latency applications such as messaging.”
Five Practical Attacks for "Optimistic Mixing for Exit-Polls" (2003, background): “Furukawa and Sako [7], and Neff [19] respectively have both found efficient ways to design such proofs.”
Coercion-resistant electronic elections (2005, methodology): “A drawback of our scheme is that, even with use of asymptotically efficient mix networks as in [22, 34], the overhead for tallying authorities is quadratic in the number of voters.”