© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:quant-ph/0408120 · Physical Review A

Security of quantum bit-string generation

Jonathan Barrett, Serge Massar

Published Nov 11, 2004• 16 citations

Abstract

We consider the cryptographic task of bit-string generation. This is a generalization of coin tossing in which two mistrustful parties wish to generate a string of random bits such that an honest party can be sure that the other cannot have biased the string too much. We consider a quantum protocol for this task, originally introduced in Phys. Rev. A 69, 022322 (2004), that is feasible with present day technology. We introduce security conditions based on the average bias of the bits and the Shannon entropy of the string. For each, we prove rigorous security bounds for this protocol in both noiseless and noisy conditions under the most general attacks allowed by quantum mechanics. Roughly speaking, in the absence of noise, a cheater can only bias significantly a vanishing fraction of the bits, whereas in the presence of noise, a cheater can bias a constant fraction, with this fraction depending quantitatively on the level of noise. We also discuss classical protocols for the same task, deriving upper bounds on how well a classical protocol can perform. This enables the determination of how much noise the quantum protocol can tolerate while still outperforming classical protocols. We raise several conjectures concerning both quantum and classical possibilities for large $n$ cryptography. An experiment corresponding to the scheme analyzed in this paper has been performed and is reported elsewhere.

DOI: 10.1103/physreva.70.052310

Related papers

Quantum coin tossing and bit-string generation in the presence of noise

Jonathan Barrett, Serge Massar

We discuss the security implications of noise for quantum coin tossing protocols. We find that if quantum error correction can be used, so that noise levels can be made arbitrarily small, then reasonable security conditions for coin tossing can be framed so that results from the noiseless case will continue to hold. If, however, error correction is not available (as is the case with present day technology), and significant noise is present, then tossing a single coin becomes problematic. In this case, we are led to consider random n-bit string generation in the presence of noise, rather than single-shot coin tossing. We introduce precise security criteria for n-bit string generation and describe an explicit protocol that could be implemented with present day technology. In general, a cheater can exploit noise in order to bias coins to their advantage. We derive explicit upper bounds on the average bias achievable by a cheater for given noise levels.

arXiv:quant-ph/0303182•Physical Review A•Feb 27, 2004•26 citations

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

Proposal for founding mistrustful quantum cryptography on coin tossing

Adrian Kent

A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process, or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multiparty computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signaling constraints into account. The best that can be hoped for, in general, are quantum protocols which are computationally secure against quantum attack. Here a method is described for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin-tossing protocol. No security proof is attempted, but reasons are sketched why these protocols might resist quantum computational attack.

arXiv:quant-ph/0111097•Physical Review A•Jul 15, 2003•3 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

Large N Quantum Cryptography

Adrian Kent

In quantum cryptography, the level of security attainable by a protocol which implements a particular task $N$ times bears no simple relation to the level of security attainable by a protocol implementing the task once. Useful partial security, and even near-perfect security in an appropriate sense, can be obtained for $N$ copies of a task which itself cannot be securely implemented. We illustrate this with protocols for quantum bit string commitment and quantum random number generation between mistrustful parties.

arXiv:quant-ph/0212043•Dec 8, 2002•3 citations

Founding Mistrustful Quantum Cryptography on Coin Tossing

Adrian Kent

A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multi-party computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signalling constraints into account. The best that can be hoped for, in general, are quantum protocols computationally secure against quantum attack. I describe here a method for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin tossing protocol. No security proof is attempted, but I sketch reasons why these protocols might resist quantum computational attack.

•Nov 19, 2001•0 citations

We consider the cryptographic task of bit-string generation. This is a generalization of coin tossing in which two mistrustful parties wish to generate a string of random bits such that an honest party can be sure that the other cannot have biased the string too much. We consider a quantum protocol for this task, originally introduced in Phys. Rev. A 69, 022322 (2004), that is feasible with present day technology. We introduce security conditions based on the average bias of the bits and the Shannon entropy of the string. For each, we prove rigorous security bounds for this protocol in both noiseless and noisy conditions under the most general attacks allowed by quantum mechanics. Roughly speaking, in the absence of noise, a cheater can only bias significantly a vanishing fraction of the bits, whereas in the presence of noise, a cheater can bias a constant fraction, with this fraction depending quantitatively on the level of noise. We also discuss classical protocols for the same task, deriving upper bounds on how well a classical protocol can perform. This enables the determination of how much noise the quantum protocol can tolerate while still outperforming classical protocols. We raise several conjectures concerning both quantum and classical possibilities for large

n

cryptography. An experiment corresponding to the scheme analyzed in this paper has been performed and is reported elsewhere.

We discuss the security implications of noise for quantum coin tossing protocols. We find that if quantum error correction can be used, so that noise levels can be made arbitrarily small, then reasonable security conditions for coin tossing can be framed so that results from the noiseless case will continue to hold. If, however, error correction is not available (as is the case with present day technology), and significant noise is present, then tossing a single coin becomes problematic. In this case, we are led to consider random n-bit string generation in the presence of noise, rather than single-shot coin tossing. We introduce precise security criteria for n-bit string generation and describe an explicit protocol that could be implemented with present day technology. In general, a cheater can exploit noise in order to bias coins to their advantage. We derive explicit upper bounds on the average bias achievable by a cheater for given noise levels.

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.

A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process, or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multiparty computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signaling constraints into account. The best that can be hoped for, in general, are quantum protocols which are computationally secure against quantum attack. Here a method is described for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin-tossing protocol. No security proof is attempted, but reasons are sketched why these protocols might resist quantum computational attack.

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.

In quantum cryptography, the level of security attainable by a protocol which implements a particular task

N

times bears no simple relation to the level of security attainable by a protocol implementing the task once. Useful partial security, and even near-perfect security in an appropriate sense, can be obtained for

N

copies of a task which itself cannot be securely implemented. We illustrate this with protocols for quantum bit string commitment and quantum random number generation between mistrustful parties.

A significant branch of classical cryptography deals with the problems which arise when mistrustful parties need to generate, process or exchange information. As Kilian showed a while ago, mistrustful classical cryptography can be founded on a single protocol, oblivious transfer, from which general secure multi-party computations can be built. The scope of mistrustful quantum cryptography is limited by no-go theorems, which rule out, inter alia, unconditionally secure quantum protocols for oblivious transfer or general secure two-party computations. These theorems apply even to protocols which take relativistic signalling constraints into account. The best that can be hoped for, in general, are quantum protocols computationally secure against quantum attack. I describe here a method for building a classically certified bit commitment, and hence every other mistrustful cryptographic task, from a secure coin tossing protocol. No security proof is attempted, but I sketch reasons why these protocols might resist quantum computational attack.