Quantum coin flipping

Last updated

Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. [1] Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, [2] e.g. Quantum Byzantine agreement.

Contents

Unlike other types of quantum cryptography (in particular, quantum key distribution), quantum coin flipping is a protocol used between two users who do not trust each other. [3] Consequently, both users (or players) want to win the coin toss and will attempt to cheat in various ways. [3]

It is known that if the communication between the players is over a classical channel, i.e. a channel over which quantum information cannot be communicated, then one player can (in principle) always cheat regardless of which protocol is used. [4] We say in principle because it might be that cheating requires an unfeasible amount of computational resource. Under standard computational assumptions, coin flipping can be achieved with classical communication.

The most basic figure of merit for a coin-flipping protocol is given by its bias, a number between and . The bias of a protocol captures the success probability of an all-powerful cheating player who uses the best conceivable strategy. A protocol with bias means that no player can cheat. A protocol with bias means that at least one player can always succeed at cheating. Obviously, the smaller the bias better the protocol.

When the communication is over a quantum channel, it has been shown that even the best conceivable protocol can not have a bias less than . [5] [6]

Consider the case where each player knows the preferred bit of the other. A coin flipping problem which makes this additional assumption constitutes the weaker variant thereof called weak coin flipping (WCF). In the case of classical channels this extra assumption yields no improvement. On the other hand, it has been proven that WCF protocols with arbitrarily small biases do exist. [7] [8] However, the best known explicit WCF protocol has bias . [9]

Although quantum coin flipping offers clear advantages over its classical counterpart in theory, accomplishing it in practice has proven difficult. [3] [10]

History

Theory

Manuel Blum introduced coin flipping as part of a classical system in 1983 based on computational algorithms and assumptions. [11] Blum's version of coin flipping answers the following cryptographic problem:

Alice and Bob are recently divorced, living in two separate cities, and want to decide who gets to keep the car. To decide, Alice wants to flip a coin over the telephone. However, Bob is concerned that if he were to tell Alice heads, she would flip the coin and automatically tell him that he lost. [12]

Thus, the problem with Alice and Bob is that they do not trust each other; the only resource they have is the telephone communication channel, and there is not a third party available to read the coin. Therefore, Alice and Bob must be either truthful and agree on a value or be convinced that the other is cheating. [12]

In 1984, quantum cryptography emerged from a paper written by Charles H. Bennett and Giles Brassard. In this paper, the two introduced the idea of using quantum mechanics to enhance previous cryptographic protocols such as coin flipping. [3] Since then, many researchers have applied quantum mechanics to cryptography as they have proven theoretically to be more secure than classical cryptography, however, demonstrating these protocols in practical systems is difficult to accomplish.

Experiment

As published in 2014, a group of scientists at the Laboratory for Communication and Processing of Information (LTCI) in Paris have implemented quantum coin flipping protocols experimentally. [3] The researchers have reported that the protocol performs better than a classical system over a suitable distance for a metropolitan area optical network. [3]

Definition

Coin flipping

In cryptography, coin flipping is defined to be the problem where two mutually distrustful and remote players want to agree on a random bit without relying on any third party. [1]

Strong coin flipping

In quantum cryptography, strong coin flipping (SCF) is defined to be a coin flipping problem where each player is oblivious to the preference of the other. [13]

Weak coin flipping

In quantum cryptography, weak coin flipping (WCF) is defined to be a coin flipping problem where each player knows the preference of the other. [14]

It follows that the players have opposite preferences. If this were not the case then the problem will be pointless as the players can simply choose the outcome they desire.

Bias

Consider any coin flipping protocol. Let Alice and Bob be the two players who wish to implement the protocol. Consider the scenario where Alice cheats using her best strategy against Bob who honestly follows the protocol. Let the probability that Bob obtains the outcome Alice preferred be given by . Consider the reversed situation, i.e. Bob cheats using his best strategy against Alice who honestly follows the protocol. Let the corresponding probability that Alice obtains the outcome Bob preferred to be given by .

The bias of the protocol is defined to be .

The half is subtracted because a player will get the desired value half the time purely by chance.

Extensions

Coin flipping can be defined for biased coins as well, i.e. the bits are not equally likely. The notion of correctness has also been formalized which requires that when both players follow the protocol (nobody cheats) the players always agree on the bit generated and that the bit follows some fixed probability distribution.

Protocols

Using conjugate encoding

Quantum coin flipping and other types of quantum cryptography communicate information through the transmission of qubits. The accepting player does not know the information in the qubit until he performs a measurement. [12] Information about each qubit is stored on and carried by a single photon. [10] Once the receiving player measures the photon, it is altered, and will not produce the same output if measured again. [10] Since a photon can only be read the same way once, any other party attempting to intercept the message is easily detectable. [10]

Quantum coin flipping is when random qubits are generated between two players that do not trust each other because both of them want to win the coin toss, which could lead them to cheat in a variety of ways. [3] The essence of coin flipping occurs when the two players issue a sequence of instructions over a communication channel that then eventually results in an output. [10]

A basic quantum coin flipping protocol involves two people: Alice and Bob. [11]

  1. Alice sends Bob a set number of Κ photon pulses in the quantum states . Each of these photon pulses is independently prepared following a random choice by Alice of basis αi and bit ci where i = 1, 2, 3...Κ.
  2. Bob then measures the pulses from Alice by identifying a random basis βi. Bob records these photons and then reports back the first successfully measured photon j to Alice along with a random bit b.
  3. Alice reveals the basis and bit that she used at the basis Bob gave her. If the two bases and bits match, then both parties are truthful and can exchange information. If the bit reported by Bob is different than that of Alice's, one is not being truthful.
Alice decides her random basis and sequence of qubits. She then sends the qubits as photons to Bob via the quantum channel. Bob detects these qubits and records his results in a table. Based on the table, Bob makes his guess to Alice on what basis she used. Quantum Coin Flipping Protocol.png
Alice decides her random basis and sequence of qubits. She then sends the qubits as photons to Bob via the quantum channel. Bob detects these qubits and records his results in a table. Based on the table, Bob makes his guess to Alice on what basis she used.

A more general explanation of the above protocol is as follows: [15]

  1. Alice first chooses a random basis (such as diagonally) and a sequence of random qubits. Alice then encodes her chosen qubits as a sequence of photons following the chosen basis. She then sends these qubits as a train of polarized photons to Bob through the communication channel.
  2. Bob chooses a sequence of reading bases randomly for each individual photon. He then reads the photons and records the results in two tables. One table is of the rectilinear (horizontal or vertical) received photons and one of the diagonally received photons. Bob may have holes in his tables due to losses in his detectors or in the transmission channels. Bob now makes a guess as to which basis Alice used and announces his guess to Alice. If he guessed correctly, he wins and if not, he loses.
  3. Alice reports whether he won or not by announcing what basis she used to Bob. Alice then confirms the information by sending Bob her entire original qubit sequence that she used in step 1.
  4. Bob compares Alice's sequence with his tables to confirm that no cheating occurred on Alice's part. The tables should correspond to Alice's basis and there should be no correlation with the other table.

Assumptions

There are a few assumptions that must be made for this protocol to work properly. The first is that Alice can create each state independent of Bob, and with an equal probability. Second, for the first bit that Bob successfully measures, his basis and bit are both random and completely independent of Alice. The last assumption, is that when Bob measures a state, he has a uniform probability to measure each state, and no state is easier to be detected than others. This last assumption is especially important because if Alice were aware of Bob's inability to measure certain states, she could use that to her advantage. [11]

Cheating

The key issue with coin flipping is that it occurs between two distrustful parties. [15] These two parties are communicating through the communication channel some distance from each other and they have to agree on a winner or loser with each having a 50 percent chance of winning. [15] However, since they are distrustful of one another, cheating is likely to occur. Cheating can occur in a number of ways such as claiming they lost some of the message when they do not like the result or increasing the average number of photons contained in each of the pulses. [3]

For Bob to cheat, he would have to be able to guess Alice's basis with a probability greater than 1/2. [15] In order to accomplish this, Bob would have to be able to determine a train of photons randomly polarized in one basis from a train of photons polarized in another basis. [15]

Alice, on the other hand, could cheat in a couple of different ways, but she has to be careful because Bob could easily detect it. [15] When Bob sends a correct guess to Alice, she could convince Bob that her photons are actually polarized the opposite of Bob's correct guess. [15] Alice could also send Bob a different original sequence than she actually used in order to beat Bob. [15]

Detecting a third-party

Single photons are used to pass the information from one player to the other (qubits). [10] In this protocol, the information is encoded in the single photons with polarization directions of 0, 45, 90, and 135 degrees, non-orthogonal quantum states. [15] When a third party attempts to read or gain information on the transmission, they alter the photon's polarization in a random way that is likely detected by the two players because it does not match the pattern exchanged between the two legitimate users. [15]

The Dip Dip Boom protocol (weak coin flipping with bias )

The Dip Dip Boom (DDB) protocol is a quantum version of the following game. [9] Consider a list of numbers , each between 0 and 1. The players, Alice and Bob, take turns to say "Dip" or "Boom" with probability at round . The player who says "Boom" wins. Obviously, a cheating player can simply say "Boom" and win as there are no rewards for longer games. We will consider games that terminate so that for some (large) , say , we set .

Consider round . Let us denote by and the probability of, respectively, Alice and Bob winning. Let be the probability that the game remains undecided. These numbers for the classical game described above can be evaluated inductively.

We now describe the quantum version. Let be a three dimensional Hilbert space spanned by . Let be a two dimensional Hilbert space which is spanned by .

  1. Initialisation: Alice holds the registers and initialises the state to . Bob holds the register and initialises it to the state .
  2. Iteration: For to the following must be performed. For odd we set X=A (for Alice) and Y=B (for Bob); for even we set X=B and Y=A.
    • X implements the operation .
    • X sends the message register to Y.
    • Y implements the operation .
    • Y measures the message register in the computational basis. If the outcome is BOOM then Y aborts and declares him/herself the winner.
  3. Measurement: Alice and Bob both measure their local register and respectively. If the outcome is U then they declare themselves to be the winner. If the outcome is A then Alice is the winner and for B it is Bob.

Remarks

  • To obtain a balanced protocol one must choose the s such that .
  • If both players follow the protocol, i.e. no player cheats, then the outcome at the end of step two will never be BOOM and neither will the outcome at step 3 be .
  • The bias analysis of this protocol uses SDP duality.
  • For large the bias of the protocol can be made arbitrarily close to .

Optimal strong coin flipping

It has been shown that using a WCF protocol with an arbitrarily small bias one can construct a SCF protocol with bias arbitrarily close to which is known to be optimal. [16]

Experimental implementation

Using conjugate encoding

As mentioned in the history section, scientists at the LTCI in Paris have experimentally carried out a quantum coin flipping protocol. Previous protocols called for a single photon source or an entangled source to be secure. However, these sources are why it is difficult for quantum coin flipping to be implemented. Instead, the researchers at LTCI used the effects of quantum superposition rather than a single photon source, which they claim makes implementation easier with the standard photon sources available. [3]

The researchers used the Clavis2 platform developed by IdQuantique for their protocol, but needed to modify the Clavis2 system in order for it to work for the coin flipping protocol. The experimental setup they used with the Clavis2 system, involves a two-way approach. Light pulsed at 1550 nanometres is sent from Bob to Alice. Alice then uses a phase modulator to encrypt the information. After encryption, she then uses a Faraday mirror to reflect and attenuate the pulses at her chosen level and sends them back to Bob. Using two high quality single photon detectors, Bob chooses a measurement basis in his phase modulator to detect the pulses from Alice. [11]

They replaced the detectors on Bob's side because of the low detection efficiencies of the previous detectors. When they replaced the detectors, they were able to show a quantum advantage on a channel for over 15 kilometres (9.3 mi). A couple of other challenges the group faced was reprogramming the system because photon source attenuation was high and performing system analyses to identify losses and errors in system components. With these corrections, the scientists were capable of implementing a coin flipping protocol by introducing a small honest abort probability, the probability that two honest participants cannot obtain a coin flip at the end of the protocol, but at a short communication distance. [3]

Related Research Articles

<span class="mw-page-title-main">Quantum teleportation</span> Physical phenomenon

Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from one location to the next, quantum teleportation only transfers quantum information. The sender does not have to know the particular quantum state being transferred. Moreover, the location of the recipient can be unknown, but to complete the quantum teleportation, classical information needs to be sent from sender to receiver. Because classical information needs to be sent, quantum teleportation cannot occur faster than the speed of light.

<span class="mw-page-title-main">Qubit</span> Basic unit of quantum information

In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two spin states can also be measured as horizontal and vertical linear polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of multiple states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.

Quantum key distribution (QKD) is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. It enables two parties to produce a shared random secret key known only to them, which then can be used to encrypt and decrypt messages. The process of quantum key distribution is not to be confused with quantum cryptography, as it is the best-known example of a quantum-cryptographic task.

In physics, the CHSH inequality can be used in the proof of Bell's theorem, which states that certain consequences of entanglement in quantum mechanics cannot be reproduced by local hidden-variable theories. Experimental verification of the inequality being violated is seen as confirmation that nature cannot be described by such theories. CHSH stands for John Clauser, Michael Horne, Abner Shimony, and Richard Holt, who described it in a much-cited paper published in 1969. They derived the CHSH inequality, which, as with John Stewart Bell's original inequality, is a constraint—on the statistical occurrence of "coincidences" in a Bell test—which is necessarily true if an underlying local hidden-variable theory exists. In practice, the inequality is routinely violated by modern experiments in quantum mechanics.

Quantum error correction (QEC) is a set of techniques used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is theorised as essential to achieve fault tolerant quantum computing that can reduce the effects of noise on stored quantum information, faulty quantum gates, faulty quantum state preparation, and faulty measurements. Effective quantum error correction would allow quantum computers with low qubit fidelity to execute algorithms of higher complexity or greater circuit depth.

In quantum information science, the Bell's states or EPR pairs are specific quantum states of two qubits that represent the simplest examples of quantum entanglement. The Bell's states are a form of entangled and normalized basis vectors. This normalization implies that the overall probability of the particle being in one of the mentioned states is 1: . Entanglement is a basis-independent result of superposition. Due to this superposition, measurement of the qubit will "collapse" it into one of its basis states with a given probability. Because of the entanglement, measurement of one qubit will "collapse" the other qubit to a state whose measurement will yield one of two possible values, where the value depends on which Bell's state the two qubits are in initially. Bell's states can be generalized to certain quantum states of multi-qubit systems, such as the GHZ state for three or more subsystems.

<span class="mw-page-title-main">Superdense coding</span> Two-bit quantum communication protocol

In quantum information theory, superdense coding is a quantum communication protocol to communicate a number of classical bits of information by only transmitting a smaller number of qubits, under the assumption of sender and receiver pre-sharing an entangled resource. In its simplest form, the protocol involves two parties, often referred to as Alice and Bob in this context, which share a pair of maximally entangled qubits, and allows Alice to transmit two bits to Bob by sending only one qubit. This protocol was first proposed by Charles H. Bennett and Stephen Wiesner in 1970 and experimentally actualized in 1996 by Klaus Mattle, Harald Weinfurter, Paul G. Kwiat and Anton Zeilinger using entangled photon pairs. Superdense coding can be thought of as the opposite of quantum teleportation, in which one transfers one qubit from Alice to Bob by communicating two classical bits, as long as Alice and Bob have a pre-shared Bell pair.

BB84 is a quantum key distribution scheme developed by Charles Bennett and Gilles Brassard in 1984. It is the first quantum cryptography protocol. The protocol is provably secure assuming a perfect implementation, relying on two conditions: (1) the quantum property that information gain is only possible at the expense of disturbing the signal if the two states one is trying to distinguish are not orthogonal ; and (2) the existence of an authenticated public classical channel. It is usually explained as a method of securely communicating a private key from one party to another for use in one-time pad encryption. The proof of BB84 depends on a perfect implementation. Side channel attacks exist, taking advantage of non-quantum sources of information. Since this information is non-quantum, it can be intercepted without measuring or cloning quantum particles.

A Quantum Digital Signature (QDS) refers to the quantum mechanical equivalent of either a classical digital signature or, more generally, a handwritten signature on a paper document. Like a handwritten signature, a digital signature is used to protect a document, such as a digital contract, against forgery by another party or by one of the participating parties.

Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, is described below.

SARG04 is a 2004 quantum cryptography protocol derived from the first protocol of that kind, BB84.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state into some number of approximately pure Bell pairs, using only local operations and classical communication.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

The noisy-storage model refers to a cryptographic model employed in quantum cryptography. It assumes that the quantum memory device of an attacker (adversary) trying to break the protocol is imperfect (noisy). The main goal of this model is to enable the secure implementation of two-party cryptographic primitives, such as bit commitment, oblivious transfer and secure identification.

Quantum refereed game in quantum information processing is a class of games in the general theory of quantum games. It is played between two players, Alice and Bob, and arbitrated by a referee. The referee outputs the pay-off for the players after interacting with them for a fixed number of rounds, while exchanging quantum information.

Linear optical quantum computing or linear optics quantum computation (LOQC), also photonic quantum computing (PQC), is a paradigm of quantum computation, allowing (under certain conditions, described below) universal quantum computation. LOQC uses photons as information carriers, mainly uses linear optical elements, or optical instruments (including reciprocal mirrors and waveplates) to process quantum information, and uses photon detectors and quantum memories to detect and store quantum information.

The KLM scheme or KLM protocol is an implementation of linear optical quantum computing (LOQC) developed in 2000 by Emanuel Knill, Raymond Laflamme and Gerard J. Milburn. This protocol allows for the creation of universal quantum computers using solely linear optical tools. The KLM protocol uses linear optical elements, single-photon sources and photon detectors as resources to construct a quantum computation scheme involving only ancilla resources, quantum teleportations and error corrections.

The Hidden Matching Problem is a computation complexity problem that can be solved using quantum protocols: Let be a positive even integer. In the Hidden Matching Problem, Alice is given and Bob is given ( denotes the family of all possible perfect matchings on nodes). Their goal is to output a tuple such that the edge belongs to the matching and .

Quantum secret sharing (QSS) is a quantum cryptographic scheme for secure communication that extends beyond simple quantum key distribution. It modifies the classical secret sharing (CSS) scheme by using quantum information and the no-cloning theorem to attain the ultimate security for communications.

<span class="mw-page-title-main">Phase kickback</span>

In quantum computing, phase kickback refers to the fact that controlled operations have effects on their controls, in addition to on their targets, and that these effects correspond to phasing operations. The phase of one qubit is effectively transferred to another qubit during a controlled operation, creating entanglement and computational advantages that enable various popular quantum algorithms and protocols.

References

  1. 1 2 Blum, Manuel (1983-01-01). "Coin flipping by telephone a protocol for solving impossible problems". ACM SIGACT News. 15 (1): 23–27. doi: 10.1145/1008908.1008911 . ISSN   0163-5700. S2CID   19928725.
  2. Oded., Goldreich (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. ISBN   9780521791724. OCLC   45093786.
  3. 1 2 3 4 5 6 7 8 9 10 Stuart Mason Dambort, "Heads or tails: Experimental quantum coin flipping cryptography performs better than classical protocols", Phys.org, March 26, 2014
  4. Cleve, R. (1986-11-01). "Limits on the security of coin flips when half the processors are faulty". Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. ACM. pp. 364–369. doi:10.1145/12130.12168. ISBN   0897911938. S2CID   17394663.
  5. A. Kitaev, Quantum Coin Flipping, Quantum Information Processing Workshop, Mathematical Sciences Research Institute, University of California, Berkeley, 2003.
  6. Ambainis, A.; Buhrman, H.; Dodis, Y.; Rohrig, H. (2004). "Multiparty quantum coin flipping". Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004. IEEE. pp. 250–259. arXiv: quant-ph/0304112 . doi:10.1109/ccc.2004.1313848. ISBN   0769521207. S2CID   3261413.
  7. C. Mochon, Quantum Weak Coin Flipping with Arbitrarily Small Bias, preprint, arXiv:0711.4114, 2007.
  8. Aharonov, Dorit; Chailloux, André; Ganz, Maor; Kerenidis, Iordanis; Magnin, Loïck (January 2016). "A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias". SIAM Journal on Computing. 45 (3): 633–679. arXiv: 1402.7166 . doi:10.1137/14096387x. ISSN   0097-5397. S2CID   7519640.
  9. 1 2 Mochon, Carlos (2005). "Large family of quantum weak coin-flipping protocols". Physical Review A. 72 (2): 022341. arXiv: quant-ph/0502068 . Bibcode:2005PhRvA..72b2341M. doi:10.1103/PhysRevA.72.022341. S2CID   46533337.
  10. 1 2 3 4 Anna Pappa et al., "Experimental Plug and Play Quantum Coin Flipping", Nature Communications, April 24, 2014
  11. 1 2 3 C. Döscher and M. Keyl, "An Introduction to Quantum Coin-Tossing", Cornell University Library, February 1, 2008
  12. D. Aharonov, A. Ta-Shma, U. V. Vazirani, and A. C. Yao, Quantum bit escrow, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 705–714.
  13. Spekkens, R. W. (2002). "Quantum Protocol for Cheat-Sensitive Weak Coin Flipping". Physical Review Letters. 89 (22): 227901. arXiv: quant-ph/0202118 . Bibcode:2002PhRvL..89v7901S. doi:10.1103/PhysRevLett.89.227901. PMID   12485105. S2CID   42694366.
  14. 1 2 3 4 5 6 7 8 9 10 Charles H. Bennett and Giles Brassard, "Quantum cryptography: Public key distribution and coin tossing", Theoretical Computer Science, December 4, 2014
  15. 50th Annual IEEE Symposium on Foundations of Computer Science, 2009 FOCS '09; 25-27 Oct. 2009, Atlanta, Georgia, USA; proceedings. IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, Annual IEEE Symposium on Foundations of Computer Science 50 2009.10.25-27 Atlanta, Ga., FOCS 50 2009.10.25-27 Atlanta, Ga. Piscataway, NJ. 2009. ISBN   9781424451166. OCLC   838170374.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)