The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform
Jens Groth - One of the best experts on this subject based on the ideXlab platform.
-
efficient zero knowledge argument for correctness of a Shuffle
Theory and Application of Cryptographic Techniques, 2012Co-Authors: Stephanie Bayer, Jens GrothAbstract:Mix-nets are used in e-voting schemes and other applications that require anonymity. Shuffles of homomorphic encryptions are often used in the construction of mix-nets. A Shuffle permutes and re-encrypts a set of ciphertexts, but as the plaintexts are encrypted it is not possible to verify directly whether the Shuffle operation was done correctly or not. Therefore, to prove the correctness of a Shuffle it is often necessary to use zero-knowledge arguments. We propose an honest verifier zero-knowledge argument for the correctness of a Shuffle of homomorphic encryptions. The suggested argument has sublinear communication complexity that is much smaller than the size of the Shuffle itself. In addition the suggested argument matches the lowest computation cost for the verifier compared to previous work and also has an efficient prover. As a result our scheme is significantly more efficient than previous zero-knowledge schemes in literature. We give performance measures from an implementation where the correctness of a Shuffle of 100,000 ElGamal ciphertexts is proved and verified in around 2 minutes.
-
sub linear zero knowledge argument for correctness of a Shuffle
International Cryptology Conference, 2008Co-Authors: Jens Groth, Yuval IshaiAbstract:A Shuffle of a set of ciphertexts is a new set of ciphertexts with the same plaintexts in permuted order. Shuffles of homomorphic encryptions are a key component in mix-nets, which in turn are used in protocols for anonymization and voting. Since the plaintexts are encrypted it is not directly verifiable whether a Shuffle is correct, and it is often necessary to prove the correctness of a Shuffle using a zero-knowledge proof or argument. In previous zero-knowledge Shuffle arguments from the literature the communication complexity grows linearly with the number of ciphertexts in the Shuffle. We suggest the first practical Shuffle argument with sub-linear communication complexity. Our result stems from combining previous work on Shuffle arguments with ideas taken from probabilistically checkable proofs.
-
a non interactive Shuffle with pairing based verifiability
International Conference on the Theory and Application of Cryptology and Information Security, 2007Co-Authors: Jens GrothAbstract:A Shuffle is a permutation and re-encryption of a set of ciphertexts. Shuffles are for instance used in mix-nets for anonymous broadcast and voting. One way to make a Shuffle verifiable is to give a zero-knowledge proof of correctness. All currently known practical zero-knowledge proofs for correctness of a Shuffle rely on interaction. We give the first efficient noninteractive zero-knowledge proof for correctness of a Shuffle.
-
a verifiable secret Shuffle of homomorphic encryptions
IACR Cryptology ePrint Archive, 2005Co-Authors: Jens GrothAbstract:We suggest an honest verifier zero-knowledge argument for the correctness of a Shuffle of homomorphic encryptions. A Shuffle consists of a rearrangement of the input ciphertexts and a re-encryption of them. One application of Shuffles is to build mix-nets. Our scheme is more efficient than previous schemes in terms of both communication and computational complexity. Indeed, the HVZK argument has a size that is independent of the actual cryptosystem being used and will typically be smaller than the size of the Shuffle itself. Moreover, our scheme is well suited for the use of multi-exponentiation techniques and batch-verification. Additionally, we suggest a more efficient honest verifier zero-knowledge argument for a commitment containing a permutation of a set of publicly known messages. We also suggest an honest verifier zeroknowledge argument for the correctness of a combined Shuffle-and-decrypt operation that can be used in connection with decrypting mix-nets based on ElGamal encryption. All our honest verifier zero-knowledge arguments can be turned into honest verifier zero-knowledge proofs. We use homomorphic commitments as an essential part of our schemes. When the commitment scheme is statistically hiding we obtain statistical honest verifier zero-knowledge arguments, when the commitment scheme is statistically binding we obtain computational honest verifier zero-knowledge proofs.
Douglas Wikström - One of the best experts on this subject based on the ideXlab platform.
-
AFRICACRYPT - Proofs of restricted Shuffles
Progress in Cryptology – AFRICACRYPT 2010, 2010Co-Authors: Björn Terelius, Douglas WikströmAbstract:A proof of a Shuffle is a zero-knowledge proof that one list of ciphertexts is a permutation and re-encryption of another list of ciphertexts. We call a Shuffle restricted if the permutation is chosen from a public subset of all permutations. In this paper, we introduce a general technique for constructing proofs of Shuffles which restrict the permutation to a group that is characterized by a public polynomial. This generalizes previous work by Reiter and Wang [22], and de Hoogh et al. [7]. Our approach also gives a new efficient proof of an unrestricted Shuffle that we think is conceptually simpler and allow a simpler analysis than all previous proofs of Shuffles.
-
ACISP - A Commitment-Consistent Proof of a Shuffle
Information Security and Privacy, 2009Co-Authors: Douglas WikströmAbstract:We introduce a pre-computation technique that drastically reduces the online computational complexity of mix-nets based on homomorphic cryptosystems. More precisely, we show that there is a permutation commitment scheme that allows a mix-server to: (1) commit to a permutation and efficiently prove knowledge of doing so correctly in the offline phase, and (2) Shuffle its input and give an extremely efficient commitment-consistent proof of a Shuffle in the online phase. We prove our result for a general class of Shuffle maps that generalize all known types of Shuffles, and even allows shuffling ciphertexts of different cryptosystems in parallel.
-
how to Shuffle in public
Theory of Cryptography Conference, 2007Co-Authors: Ben Adida, Douglas WikströmAbstract:We show how to obfuscate a secret Shuffle of ciphertexts: shuffling becomes a public operation. Given a trusted party that samples and obfuscates a Shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct public-key obfuscations of a decryption Shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem and a re-encryption Shuffle based on the Paillier cryptosystem. Both allow efficient distributed verifiable decryption. Finally, we give a distributed protocol for sampling and obfuscating each of the above Shuffles and show how it can be used in a trivial way to construct a universally composable mix-net. Our constructions are practical when the number of senders N is small, yet large enough to handle a number of practical cases, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.
-
How to Shuffle in Public.
IACR Cryptology ePrint Archive, 2005Co-Authors: Ben Adida, Douglas WikströmAbstract:We show how to public-key obfuscate two commonly used Shuffles: decryption Shuffles which permute and decrypt ciphertexts, and re-encryption Shuffles which permute and re-encrypt ciphertexts. Given a trusted party that samples and obfuscates a Shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct a decryption Shuffle from any additively homomorphic cryptosystem and show how it can be public-key obfuscated. This construction does not allow efficient distributed verifiable decryption. Then we show how to public-key obfuscate: a decryption Shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem, and a re-encryption Shuffle based on the Paillier cryptosystem. Both constructions allow efficient distributed verifiable decryption. In the Paillier case we identify and exploit a previously overlooked “homomorphic” property of the cryptosystem. Finally, we give a distributed protocol for sampling and obfuscating each of the above Shuffles and show how it can be used in a trivial way to construct a universally composable mix-net. Our constructions are practical when the number of senders N is reasonably small, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.
-
TCC - How to Shuffle in public
Theory of Cryptography, 1Co-Authors: Ben Adida, Douglas WikströmAbstract:We show how to obfuscate a secret Shuffle of ciphertexts: shuffling becomes a public operation. Given a trusted party that samples and obfuscates a Shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct public-key obfuscations of a decryption Shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem and a re-encryption Shuffle based on the Paillier cryptosystem. Both allow efficient distributed verifiable decryption. Finally, we give a distributed protocol for sampling and obfuscating each of the above Shuffles and show how it can be used in a trivial way to construct a universally composable mix-net. Our constructions are practical when the number of senders N is small, yet large enough to handle a number of practical cases, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.
C. Andrew Neff - One of the best experts on this subject based on the ideXlab platform.
-
A verifiable secret Shuffle and its application to e-voting
Proceedings of the 8th ACM conference on Computer and Communications Security - CCS '01, 2001Co-Authors: C. Andrew NeffAbstract:We present a mathematical construct which provides a cryptographic protocol to verifiably Shuffle a sequence of k modular integers, and discuss its application to secure, universally verifiable, multi-authority election schemes. The output of the Shuffle operation is another sequence of k modular integers, each of which is the same secret power of a correspond- ing input element, but the order of elements in the output is kept secret. Though it is a trivial matter for the “Shuffler” (who chooses the permuta- tion of the elements to be applied) to compute the output from the input, the construction is important because it provides a linear size proof of correctness for the output sequence (i.e. a proof that it is of the form claimed) that can be checked by an arbitrary verifiers. The complexity of the protocol improves on that of Furukawa-Sako[16] both measured by number of exponentiations and by overall size. The protocol is shown to be honest-verifier zeroknowledge in a special case, and is computational zeroknowledge in general. On the way to the final result, we also construct a generalization of the well known Chaum- Pedersen protocol for knowledge of discrete logarithm equality ([10], [7]). In fact, the generalization specializes exactly to the Chaum-Pedersen pro- tocol in the case k = 2. This result may be of interest on its own. An application to electronic voting is given that matches the features of the best current protocols with significant efficiency improvements. An alternative application to electronic voting is also given that introduces an entirely new paradigm for achieving Universally Verifiable elections.
Borja Balle - One of the best experts on this subject based on the ideXlab platform.
-
private summation in the multi message Shuffle model
arXiv: Cryptography and Security, 2020Co-Authors: Borja Balle, James Bell, Adria Gascon, Kobbi NissimAbstract:The Shuffle model of differential privacy (Erlingsson et al. SODA 2019; Cheu et al. EUROCRYPT 2019) and its close relative encode-Shuffle-analyze (Bittau et al. SOSP 2017) provide a fertile middle ground between the well-known local and central models. Similarly to the local model, the Shuffle model assumes an untrusted data collector who receives privatized messages from users, but in this case a secure Shuffler is used to transmit messages from users to the collector in a way that hides which messages came from which user. An interesting feature of the Shuffle model is that increasing the amount of messages sent by each user can lead to protocols with accuracies comparable to the ones achievable in the central model. In particular, for the problem of privately computing the sum of $n$ bounded real values held by $n$ different users, Cheu et al. showed that $O(\sqrt{n})$ messages per user suffice to achieve $O(1)$ error (the optimal rate in the central model), while Balle et al. (CRYPTO 2019) recently showed that a single message per user leads to $\Theta(n^{1/3})$ MSE (mean squared error), a rate strictly in-between what is achievable in the local and central models. This paper introduces two new protocols for summation in the Shuffle model with improved accuracy and communication trade-offs. Our first contribution is a recursive construction based on the protocol from Balle et al. mentioned above, providing $\mathrm{poly}(\log \log n)$ error with $O(\log \log n)$ messages per user. The second contribution is a protocol with $O(1)$ error and $O(1)$ messages per user based on a novel analysis of the reduction from secure summation to shuffling introduced by Ishai et al. (FOCS 2006) (the original reduction required $O(\log n)$ messages per user).
-
the privacy blanket of the Shuffle model
International Cryptology Conference, 2019Co-Authors: Borja Balle, James Bell, Adria Gascon, Kobbi NissimAbstract:This work studies differential privacy in the context of the recently proposed Shuffle model. Unlike in the local model, where the server collecting privatized data from users can track back an input to a specific user, in the Shuffle model users submit their privatized inputs to a server anonymously. This setup yields a trust model which sits in between the classical curator and local models for differential privacy. The Shuffle model is the core idea in the Encode, Shuffle, Analyze (ESA) model introduced by Bittau et al. (SOPS 2017). Recent work by Cheu et al. (EUROCRYPT 2019) analyzes the differential privacy properties of the Shuffle model and shows that in some cases Shuffled protocols provide strictly better accuracy than local protocols. Additionally, Erlingsson et al. (SODA 2019) provide a privacy amplification bound quantifying the level of curator differential privacy achieved by the Shuffle model in terms of the local differential privacy of the randomizer used by each user.
-
The Privacy Blanket of the Shuffle Model
arXiv: Learning, 2019Co-Authors: Borja Balle, James Bell, Adria Gascon, Kobbi NissimAbstract:This work studies differential privacy in the context of the recently proposed Shuffle model. Unlike in the local model, where the server collecting privatized data from users can track back an input to a specific user, in the Shuffle model users submit their privatized inputs to a server anonymously. This setup yields a trust model which sits in between the classical curator and local models for differential privacy. The Shuffle model is the core idea in the Encode, Shuffle, Analyze (ESA) model introduced by Bittau et al. (SOPS 2017). Recent work by Cheu et al. (EUROCRYPT 2019) analyzes the differential privacy properties of the Shuffle model and shows that in some cases Shuffled protocols provide strictly better accuracy than local protocols. Additionally, Erlingsson et al. (SODA 2019) provide a privacy amplification bound quantifying the level of curator differential privacy achieved by the Shuffle model in terms of the local differential privacy of the randomizer used by each user. In this context, we make three contributions. First, we provide an optimal single message protocol for summation of real numbers in the Shuffle model. Our protocol is very simple and has better accuracy and communication than the protocols for this same problem proposed by Cheu et al. Optimality of this protocol follows from our second contribution, a new lower bound for the accuracy of private protocols for summation of real numbers in the Shuffle model. The third contribution is a new amplification bound for analyzing the privacy of protocols in the Shuffle model in terms of the privacy provided by the corresponding local randomizer. Our amplification bound generalizes the results by Erlingsson et al. to a wider range of parameters, and provides a whole family of methods to analyze privacy amplification in the Shuffle model.
Ben Adida - One of the best experts on this subject based on the ideXlab platform.
-
how to Shuffle in public
Theory of Cryptography Conference, 2007Co-Authors: Ben Adida, Douglas WikströmAbstract:We show how to obfuscate a secret Shuffle of ciphertexts: shuffling becomes a public operation. Given a trusted party that samples and obfuscates a Shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct public-key obfuscations of a decryption Shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem and a re-encryption Shuffle based on the Paillier cryptosystem. Both allow efficient distributed verifiable decryption. Finally, we give a distributed protocol for sampling and obfuscating each of the above Shuffles and show how it can be used in a trivial way to construct a universally composable mix-net. Our constructions are practical when the number of senders N is small, yet large enough to handle a number of practical cases, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.
-
How to Shuffle in Public.
IACR Cryptology ePrint Archive, 2005Co-Authors: Ben Adida, Douglas WikströmAbstract:We show how to public-key obfuscate two commonly used Shuffles: decryption Shuffles which permute and decrypt ciphertexts, and re-encryption Shuffles which permute and re-encrypt ciphertexts. Given a trusted party that samples and obfuscates a Shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct a decryption Shuffle from any additively homomorphic cryptosystem and show how it can be public-key obfuscated. This construction does not allow efficient distributed verifiable decryption. Then we show how to public-key obfuscate: a decryption Shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem, and a re-encryption Shuffle based on the Paillier cryptosystem. Both constructions allow efficient distributed verifiable decryption. In the Paillier case we identify and exploit a previously overlooked “homomorphic” property of the cryptosystem. Finally, we give a distributed protocol for sampling and obfuscating each of the above Shuffles and show how it can be used in a trivial way to construct a universally composable mix-net. Our constructions are practical when the number of senders N is reasonably small, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.
-
TCC - How to Shuffle in public
Theory of Cryptography, 1Co-Authors: Ben Adida, Douglas WikströmAbstract:We show how to obfuscate a secret Shuffle of ciphertexts: shuffling becomes a public operation. Given a trusted party that samples and obfuscates a Shuffle before any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct public-key obfuscations of a decryption Shuffle based on the Boneh-Goh-Nissim (BGN) cryptosystem and a re-encryption Shuffle based on the Paillier cryptosystem. Both allow efficient distributed verifiable decryption. Finally, we give a distributed protocol for sampling and obfuscating each of the above Shuffles and show how it can be used in a trivial way to construct a universally composable mix-net. Our constructions are practical when the number of senders N is small, yet large enough to handle a number of practical cases, e.g. N = 350 in the BGN case and N = 2000 in the Paillier case.
