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

Journal of Cryptology

On the (Im-)Possibility of Extending Coin Toss

Dennis Hofheinz, Jörn Müller‐Quade, Dominique Unruh

Published Apr 26, 2018• 0 citations
Publisher

Abstract

We consider the task of extending a given coin toss. By this, we mean the two-party task of using a single instance of a given coin toss protocol in order to interactively generate more random coins. A bit more formally, our goal is to generate n common random coins from a single use of an ideal functionality that gives $$m<n$$ common random coins to both parties. In the framework of universal composability, we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security, the existence of a protocol for coin toss extension depends on the number m of random coins that can be obtained “for free.” For the case of stand-alone security, i.e., a simulation-based security definition without an environment, we present a protocol for statistically secure coin toss extension. Our protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m. Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.

DOI
10.1007/s00145-018-9296-x

Related papers

On the impossibility of information-theoretic composable coin toss extension

Gregor Seiler, Ueli M. Maurer

Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•1 citation

Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation.

Yehuda Lindell

Abstract. In this paper we show that any two-party functionality can be securely computed in a constant number of rounds, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao’s constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round perfect coin-tossing protocol, where by “perfect ” we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom). 1

•Jan 1, 2001•0 citations

Unconditionally Secure Quantum Coin Tossing. (arXiv:quant-ph/9904078v2 UPDATED)

Dominic Mayers, Louis Salvail, Yoshie Chiba-Kohno

In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually $1/2 + \xi$ where the bias $\xi$ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where $n \in O(\lg m)$. The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than $1/m$. The result is discussed in the light of the impossibility result for exact coin tossing.

•Feb 27, 2018•0 citations

Unconditionally Secure Quantum Coin Tossing

Dominic Mayers, Louis Salvail, Yoshie Chiba-Kohno

In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually $1/2 + ξ$ where the bias $ξ$ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where $n \in O(\lg m)$. The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than $1/m$. The result is discussed in the light of the impossibility result for exact coin tossing.

arXiv:quant-ph/9904078•Apr 22, 1999•28 citations

AN INTRODUCTION TO QUANTUM COIN TOSSING

C. Doescher, Michael Keyl

We review the quantum version of a well known problem of cryptography called coin tossing ("flipping a coin via telephone"). It can be regarded as a game where two remote players (who distrust each other) try to generate a uniformly distributed random bit which is common to both parties. The only resource they can use to perform this task is a classical or quantum communication channel. In this paper we provide a general overview over such coin tossing protocols, concerning in particular their security.

arXiv:quant-ph/0206088•Fluctuation and Noise Letters•Dec 1, 2002•18 citations

Coin-based Secure Computations

Yuichi Komano, Takaaki Mizuki

Abstract In the history of cryptography, many cryptographic protocols have relied on random coin tosses to prove their security. Although flipping coins is indispensable in this manner, the coins themselves have never been in the spotlight. Therefore, we would like to make physical coins rise to the level of cryptography, just as a deck of physical playing cards has been used to perform a secure multi-party computation. Such a card-based protocol is known to be helpful both to perform a secure computation without any black-box computers and to understand the principles of secure protocols. In this paper, we propose a new framework of secure multi-party computation using physical coins, named a coin-based protocol. One advantage of the use of coins is that they are more ubiquitous than cards. Whereas a face-down card can conceal the information about its face side, one side of a coin reveals the information of its other side. Hence, more careful design is required for a secure coin-based protocol than for a card-based one. We formalize a computational model of the coin-based protocol and explicitly give protocols for NOT, AND, COPY, OR, and XOR computations. We also discuss the composability of the extended protocols and how to implement them in practice.

International Journal of Information Security•Apr 6, 2022•10 citations
We consider the task of extending a given coin toss. By this, we mean the two-party task of using a single instance of a given coin toss protocol in order to interactively generate more random coins. A bit more formally, our goal is to generate n common random coins from a single use of an ideal functionality that gives m<nm<nm<n common random coins to both parties. In the framework of universal composability, we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security, the existence of a protocol for coin toss extension depends on the number m of random coins that can be obtained “for free.” For the case of stand-alone security, i.e., a simulation-based security definition without an environment, we present a protocol for statistically secure coin toss extension. Our protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m. Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.
Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.
Abstract. In this paper we show that any two-party functionality can be securely computed in a constant number of rounds, where security is obtained against malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao’s constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round perfect coin-tossing protocol, where by “perfect ” we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom). 1
In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually 1/2+ξ1/2 + \xi1/2+ξ where the bias ξ\xiξ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where n∈O(lg⁡m)n \in O(\lg m)n∈O(lgm). The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than 1/m1/m1/m. The result is discussed in the light of the impossibility result for exact coin tossing.
In coin tossing two remote participants want to share a uniformly distributed random bit. At the least in the quantum version, each participant test whether or not the other has attempted to create a bias on this bit. It is requested that, for b = 0,1, the probability that Alice gets bit b and pass the test is smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2 holds perfectly against any of the two participants, the task realised is called an exact coin tossing. If the bound is actually 1/2+ξ1/2 + ξ1/2+ξ where the bias ξξξ vanishes when a security parameter m defined by the protocol increases, the task realised is a (non exact) coin tossing. It is found here that exact coin tossing is impossible. At the same time, an unconditionally secure quantum protocol that realises a (non exact) coin tossing is proposed. The protocol executes m biased quantum coin tossing procedures at the same time. It executes the first round in each of these m procedures sequentially, then the second rounds are executed, and so on until the end of the n procedures. Each procedure requires 4n particles where n∈O(lg⁡m)n \in O(\lg m)n∈O(lgm). The final bit x is the parity of the m random bits. The information about each of these m bits is announced a little bit at a time which implies that the principle used against bit commitment does not apply. The bias on x is smaller than 1/m1/m1/m. The result is discussed in the light of the impossibility result for exact coin tossing.
We review the quantum version of a well known problem of cryptography called coin tossing ("flipping a coin via telephone"). It can be regarded as a game where two remote players (who distrust each other) try to generate a uniformly distributed random bit which is common to both parties. The only resource they can use to perform this task is a classical or quantum communication channel. In this paper we provide a general overview over such coin tossing protocols, concerning in particular their security.
Abstract In the history of cryptography, many cryptographic protocols have relied on random coin tosses to prove their security. Although flipping coins is indispensable in this manner, the coins themselves have never been in the spotlight. Therefore, we would like to make physical coins rise to the level of cryptography, just as a deck of physical playing cards has been used to perform a secure multi-party computation. Such a card-based protocol is known to be helpful both to perform a secure computation without any black-box computers and to understand the principles of secure protocols. In this paper, we propose a new framework of secure multi-party computation using physical coins, named a coin-based protocol. One advantage of the use of coins is that they are more ubiquitous than cards. Whereas a face-down card can conceal the information about its face side, one side of a coin reveals the information of its other side. Hence, more careful design is required for a secure coin-based protocol than for a card-based one. We formalize a computational model of the coin-based protocol and explicitly give protocols for NOT, AND, COPY, OR, and XOR computations. We also discuss the composability of the extended protocols and how to implement them in practice.