Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Transactions on Networks and Communications

Practical generation of common random strings for secure multiparty computations over the Internet

István Vajda

Published Dec 31, 2020• 0 citations
Publisher

Abstract

It is known that most of the interesting multiparty cryptographic tasks cannot be implemented securely without trusted setup in a general concurrent network environment like the Internet. We need an appropriate trusted third party to solve this problem. An important trusted setup is a public random string shared by the parties. We present a practical n-bit coin toss protocol for provably secure implementation of such setup. Our idea is inviting external peers into the execution of the protocol to establish an honest majority among the parties. We guarantee security in the presence of an unconditional, static, malicious adversary. Additionally, we present an original practical idea of using live public radio broadcast channels for the generation of common physical random source.

DOI
10.14738/tnc.86.9447

Related papers

Provably Secure Experimental Quantum Bit-String Generation

L.-P. Lamoureux, Edouard Brainis, David Amans +2 more

Coin tossing is a cryptographic task in which two parties who do not trust each other aim to generate a common random bit. Using classical communication this is impossible, but nontrivial coin tossing is possible using quantum communication. Here we consider the case when the parties do not want to toss a single coin, but many. This is called bit-string generation. We report the experimental generation of strings of coins which are provably more random than achievable using classical communication. The experiment is based on the "plug and play" scheme developed for quantum cryptography, and therefore well suited for long distance quantum communication.

arXiv:quant-ph/0408121•Physical Review Letters•Feb 7, 2005•24 citations

Quantum And Relativistic Protocols For Secure Multi-Party Computation

Roger Colbeck

After a general introduction, the thesis is divided into four parts. In the first, we discuss the task of coin tossing, principally in order to highlight the effect different physical theories have on security in a straightforward manner, but, also, to introduce a new protocol for non-relativistic strong coin tossing. This protocol matches the security of the best protocol known to date while using a conceptually different approach to achieve the task. In the second part variable bias coin tossing is introduced. This is a variant of coin tossing in which one party secretly chooses one of two biased coins to toss. It is shown that this can be achieved with unconditional security for a specified range of biases, and with cheat-evident security for any bias. We also discuss two further protocols which are conjectured to be unconditionally secure for any bias. The third section looks at other two-party secure computations for which, prior to our work, protocols and no-go theorems were unknown. We introduce a general model for such computations, and show that, within this model, a wide range of functions are impossible to compute securely. We give explicit cheating attacks for such functions. In the final chapter we discuss the task of expanding a private random string, while dropping the usual assumption that the protocol's user trusts her devices. Instead we assume that all quantum devices are supplied by an arbitrarily malicious adversary. We give two protocols that we conjecture securely perform this task. The first allows a private random string to be expanded by a finite amount, while the second generates an arbitrarily large expansion of such a string.

arXiv:0911.3814•Nov 19, 2009•267 citations

Protocols for Multiparty Coin Toss With Dishonest Majority.

Amos Beimel, Eran Omri, Ilan Orlov

Abstract. Coin-tossing protocols are protocols that generate a random bit with uniform distribution. These protocols are used as a building block in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any r-round coin-tossing protocol, the malicious parties can cause a bias of Ω(1/r) to the bit that the honest parties output. However, for more than two t, where t is the number

•Jan 1, 2012•2 citations

Cryptography in the Multi-string Model.

Jens Groth, Rafail Ostrovsky

The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random string and gives it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets. In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority, we only assume a majority of them generate the random string honestly. We demonstrate the use of this model for two fundamental cryptographic taks. We define non-interactive zero-knowledge in the multi-string model and construct NIZK proofs in the multi-string model. We also consider multi-party computation and show that any functionality can be securely realized in the multi-string model.

•Jan 1, 2006•0 citations

Universally Composable Multiparty Computation with Partially Isolated Parties.

Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs

It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). Recently, an alternative solution was proposed by Katz in [K07], suggesting that one may rely on physical assumptions rather than trusted third parties. Concretely, the solution assumed it physically possible to construct tamper proof hardware tokens which can be run in complete isolation from the surrounding environment. Here we improve upon the work of [K07] by constructing a scheme in which the tokens only need to be partially isolated and may have some limited communication with the environment. In addition we improve on Katz’s work by presenting a scheme which is secure against adaptive adversaries and is based on general cryptographic assumptions. We also consider an alternative scenario, in which there are some trusted third parties but no single such party is trusted by all of the players. This compromise allows us to limit the use of the physical set-up and hence might be preferred in practice.

•Jan 1, 2007•4 citations

A constant-round perfect parallel coin-tossing protocol

Xiaolan Zhang, Hong-xiang Sun, Hua Zhang +2 more

A coin-tossing protocol lets two parties decide on a string that should be a random (or at least pseudorandom) string. In this paper, we focus on taking advantage of the perfectly hiding commitment scheme, constant-round perfect zero-knowledge arguments and arguments of knowledge to construct a two-party constant-round perfect protocol for secure coin-tossing, where both of two parties can obtain the common resulting coins and the resulting coins are guaranteed to be statistically close to uniform. The security of our protocol is obtained against malicious non-uniform adversaries that may arbitrarily deviate from the protocol specification. Comparing with the Barak's protocol, we utilize the black-box reduction in the process of security proof and the rounds of our protocol decrease obviously.

IEEE International Conference on Progress in Informatics and Computing•Dec 1, 2010•0 citations
It is known that most of the interesting multiparty cryptographic tasks cannot be implemented securely without trusted setup in a general concurrent network environment like the Internet. We need an appropriate trusted third party to solve this problem. An important trusted setup is a public random string shared by the parties. We present a practical n-bit coin toss protocol for provably secure implementation of such setup. Our idea is inviting external peers into the execution of the protocol to establish an honest majority among the parties. We guarantee security in the presence of an unconditional, static, malicious adversary. Additionally, we present an original practical idea of using live public radio broadcast channels for the generation of common physical random source.
Coin tossing is a cryptographic task in which two parties who do not trust each other aim to generate a common random bit. Using classical communication this is impossible, but nontrivial coin tossing is possible using quantum communication. Here we consider the case when the parties do not want to toss a single coin, but many. This is called bit-string generation. We report the experimental generation of strings of coins which are provably more random than achievable using classical communication. The experiment is based on the "plug and play" scheme developed for quantum cryptography, and therefore well suited for long distance quantum communication.
After a general introduction, the thesis is divided into four parts. In the first, we discuss the task of coin tossing, principally in order to highlight the effect different physical theories have on security in a straightforward manner, but, also, to introduce a new protocol for non-relativistic strong coin tossing. This protocol matches the security of the best protocol known to date while using a conceptually different approach to achieve the task. In the second part variable bias coin tossing is introduced. This is a variant of coin tossing in which one party secretly chooses one of two biased coins to toss. It is shown that this can be achieved with unconditional security for a specified range of biases, and with cheat-evident security for any bias. We also discuss two further protocols which are conjectured to be unconditionally secure for any bias. The third section looks at other two-party secure computations for which, prior to our work, protocols and no-go theorems were unknown. We introduce a general model for such computations, and show that, within this model, a wide range of functions are impossible to compute securely. We give explicit cheating attacks for such functions. In the final chapter we discuss the task of expanding a private random string, while dropping the usual assumption that the protocol's user trusts her devices. Instead we assume that all quantum devices are supplied by an arbitrarily malicious adversary. We give two protocols that we conjecture securely perform this task. The first allows a private random string to be expanded by a finite amount, while the second generates an arbitrarily large expansion of such a string.
The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random string and gives it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets. In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority, we only assume a majority of them generate the random string honestly. We demonstrate the use of this model for two fundamental cryptographic taks. We define non-interactive zero-knowledge in the multi-string model and construct NIZK proofs in the multi-string model. We also consider multi-party computation and show that any functionality can be securely realized in the multi-string model.
It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). Recently, an alternative solution was proposed by Katz in [K07], suggesting that one may rely on physical assumptions rather than trusted third parties. Concretely, the solution assumed it physically possible to construct tamper proof hardware tokens which can be run in complete isolation from the surrounding environment. Here we improve upon the work of [K07] by constructing a scheme in which the tokens only need to be partially isolated and may have some limited communication with the environment. In addition we improve on Katz’s work by presenting a scheme which is secure against adaptive adversaries and is based on general cryptographic assumptions. We also consider an alternative scenario, in which there are some trusted third parties but no single such party is trusted by all of the players. This compromise allows us to limit the use of the physical set-up and hence might be preferred in practice.
A coin-tossing protocol lets two parties decide on a string that should be a random (or at least pseudorandom) string. In this paper, we focus on taking advantage of the perfectly hiding commitment scheme, constant-round perfect zero-knowledge arguments and arguments of knowledge to construct a two-party constant-round perfect protocol for secure coin-tossing, where both of two parties can obtain the common resulting coins and the resulting coins are guaranteed to be statistically close to uniform. The security of our protocol is obtained against malicious non-uniform adversaries that may arbitrarily deviate from the protocol specification. Comparing with the Barak's protocol, we utilize the black-box reduction in the process of security proof and the rounds of our protocol decrease obviously.