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

Wuhan University Journal of Natural Sciences

Transmutation scheme of coin flipping protocol and utilization

Xie Yumin, Ming Yang, Shi Feng, Muhammad Kamran

Published Nov 1, 2006• 0 citations
Publisher

Abstract

Coin flipping by telephone protocol(CFP) is utilized in a system to exchange a binary sequence at random between two person apart far from each other. However, CFP cannot be used in a system with many users like in a group environment system. A transmutation of CFP named T-CFP is proposed in this paper. The precondition of T-CFP is the system's user trusts the system center and center's cheating is meaningless at the same time. The significant difference between CFP and T-CFP is that CFP supports only two users while T-CFP can support many users to exchange special information. The security and efficiency of T-CFP are discussed with a detailed example on T-CFP utilization is demonstrated in this paper.

DOI
10.1007/bf02831905

Related papers

Coin flipping by telephone a protocol for solving impossible problems

Manuel Blum

Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes . . . I'm flipping the coin. . . . You lost!"Coin-flipping in the SPECIAL way done here has a serious purpose. Indeed, it should prove an INDISPENSABLE TOOL of the protocol designer. Whenever a protocol requires one of two adversaries, say Alice, to pick a sequence of bits at random, and whenever it serves Alice's interests best NOT to pick her sequence of bits at random, then coin-flipping (Bob flipping coins to Alice) as defined here achieves the desired goal:1. It GUARANTEES to Bob that Alice will pick her sequence of bits at random. Her bit is 1 if Bob flips heads to her, O otherwise.2. It GUARANTEES to Alice that Bob will not know WHAT sequence of bits he flipped to her.Coin-flipping has already proved useful in solving a number of problems once thought impossible: mental poker, certified mail, and exchange of secrets. It will certainly prove a useful tool in solving other problems as well.

ACM SIGACT News•Jan 1, 1983•525 citations

Coin flipping by telephone (Corresp.)

Justin M. Reyneri, Ehud D. Karnin

Two parties, who do not trust each other, wish to agree on the result of a coin toss while they are conversing by telephone. A new protocol which solves this problem is proposed and compared with previous protocols.

IEEE Transactions on Information Theory•Sep 1, 1984•3 citations

On the Computational Complexity of Coin Flipping

Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai

Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•29 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.

Fluctuation and Noise Letters•Dec 1, 2002•10 citations

Quantum Weak Coin-Flipping with Bias of 0.192

Carlos Mochon

We present a family of protocols for flipping a coin over a telephone in a quantum mechanical setting. The family contains protocols with n + 2 messages for all n > 1, and asymptotically achieves a bias of 0.192. The case n = 2 is equivalent to the protocol of Spekkens and Rudolph with bias 0.207, which was the best known protocol. The case n = 3 achieves a bias of 0.199, and n = 8 achieves a bias of 0.193. The analysis of the protocols uses Kitaev's description of coin-flipping as a semidefinite program. We construct an analytical solution to the dual problem which provides an upper bound on the amount that a party can cheat.

arXiv:quant-ph/0403193•Annual Symposium on Foundations of Computer Science•Dec 23, 2004•34 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) tries 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•Jun 13, 2002•3 citations
Coin flipping by telephone protocol(CFP) is utilized in a system to exchange a binary sequence at random between two person apart far from each other. However, CFP cannot be used in a system with many users like in a group environment system. A transmutation of CFP named T-CFP is proposed in this paper. The precondition of T-CFP is the system's user trusts the system center and center's cheating is meaningless at the same time. The significant difference between CFP and T-CFP is that CFP supports only two users while T-CFP can support many users to exchange special information. The security and efficiency of T-CFP are discussed with a detailed example on T-CFP utilization is demonstrated in this paper.
Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes . . . I'm flipping the coin. . . . You lost!"Coin-flipping in the SPECIAL way done here has a serious purpose. Indeed, it should prove an INDISPENSABLE TOOL of the protocol designer. Whenever a protocol requires one of two adversaries, say Alice, to pick a sequence of bits at random, and whenever it serves Alice's interests best NOT to pick her sequence of bits at random, then coin-flipping (Bob flipping coins to Alice) as defined here achieves the desired goal:1. It GUARANTEES to Bob that Alice will pick her sequence of bits at random. Her bit is 1 if Bob flips heads to her, O otherwise.2. It GUARANTEES to Alice that Bob will not know WHAT sequence of bits he flipped to her.Coin-flipping has already proved useful in solving a number of problems once thought impossible: mental poker, certified mail, and exchange of secrets. It will certainly prove a useful tool in solving other problems as well.
Coin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) Security: a cheating party cannot increase the probability of its desired outcome by any significant amount. Since its introduction by Blum, coin flipping has occupied a central place in the theory of cryptographic protocols. In this paper, we explore what are the implications of the existence of secure coin flipping protocols for complexity theory. As exposited recently by Impagliazzo, surprisingly little is known about this question. Previous work has shown that if we interpret the Security property of coin flipping protocols very strongly, namely that nothing beyond a negligible bias by cheating parties is allowed, then one-way functions must exist. However, for even a slight weakening of this security property (for example that cheating parties cannot bias the outcome by any additive constant ε > 0), the only complexity-theoretic implication that was known was that PSPACE ⊈ BPP. We put forward a new attack to establish our main result, which shows that, informally speaking, the existence of any (weak) coin flipping protocol that prevents a cheating adversary from biasing the output by more than 1/4 - ε implies that NP ⊈ BPP. Furthermore, for constant-round protocols, we show that the existence of any (weak) coin flipping protocol that allows an honest party to maintain any noticeable chance of prevailing against a cheating party implies the existence of (infinitely often) one-way functions.
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.
We present a family of protocols for flipping a coin over a telephone in a quantum mechanical setting. The family contains protocols with n + 2 messages for all n > 1, and asymptotically achieves a bias of 0.192. The case n = 2 is equivalent to the protocol of Spekkens and Rudolph with bias 0.207, which was the best known protocol. The case n = 3 achieves a bias of 0.199, and n = 8 achieves a bias of 0.193. The analysis of the protocols uses Kitaev's description of coin-flipping as a semidefinite program. We construct an analytical solution to the dual problem which provides an upper bound on the amount that a party can cheat.
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) tries 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.