Alice is a charismatic quantum cryptographer who believes her parties are unmissable; Bob is a (relatively) glamorous string theorist who believes he is an indispensable guest. To prevent possibly traumatic collisions of self-perception and reality, their social code requires that decisions about invitation or acceptance be made via a cryptographically secure variable-bias coin toss (VBCT). This generates a shared random bit by the toss of a coin whose bias is secretly chosen, within a stipulated range, by one of the parties; the other party learns only the random bit. Thus one party can secretly influence the outcome, while both can save face by blaming any negative decisions on bad luck. We describe here some cryptographic VBCT protocols whose security is guaranteed by quantum theory and the impossibility of superluminal signaling, setting our results in the context of a general discussion of secure two-party computation. We also briefly discuss other cryptographic applications of VBCT.
Alice is a charismatic quantum cryptographer who believes her parties are unmissable; Bob is a (relatively) glamorous string theorist who believes he is an indispensable guest. To prevent possibly traumatic collisions of self-perception and reality, their social code requires that decisions about invitation or acceptance be made via a cryptographically secure variable-bias coin toss (VBCT). This generates a shared random bit by the toss of a coin whose bias is secretly chosen, within a stipulated range, by one of the parties; the other party learns only the random bit. Thus one party can secretly influence the outcome, while both can save face by blaming any negative decisions on bad luck. We describe here some cryptographic VBCT protocols whose security is guaranteed by quantum theory and the impossibility of superluminal signaling, setting our results in the context of a general discussion of secure two-party computation. We also briefly discuss other cryptographic applications of VBCT.
Alice is a charismatic quantum cryptographer who believes her parties are unmissable; Bob is a (relatively) glamorous string theorist who believes he is an indispensable guest. To prevent possibly traumatic collisions of self-perception and reality, their social code requires that decisions about invitation or acceptance be made via a cryptographically secure variable bias coin toss (VBCT). This generates a shared random bit by the toss of a coin whose bias is secretly chosen, within a stipulated range, by one of the parties; the other party learns only the random bit. Thus one party can secretly influence the outcome, while both can save face by blaming any negative decisions on bad luck. We describe here some cryptographic VBCT protocols whose security is guaranteed by quantum theory and the impossibility of superluminal signalling, setting our results in the context of a general discussion of secure two-party computation. We also briefly discuss other cryptographic applications of VBCT.
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.
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∈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/m. The result is discussed in the light of the impossibility result for exact coin tossing.
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.
The cryptographic protocol of coin tossing consists of two parties, Alice and Bob, who do not trust each other, but want to generate a random bit. If the parties use a classical communication channel and have unlimited computational resources, one of them can always cheat perfectly. If the parties use a quantum communication channel, there exist protocols such that neither party can cheat perfectly, although they may be able to significantly bias the coin. Here, we analyze in detail how the performance of a quantum coin tossing experiment should be compared to classical protocols, taking into account the inevitable experimental imperfections. We then report an all-optical fiber experiment in which a single coin is tossed whose randomness is higher than achievable by any classical protocol and present some easily realizable cheating strategies by Alice and Bob.