Source-linked AI summary
Quantum cryptography: Public key distribution and coin tossing
Charles H. Bennett, Gilles Brassard
TL;DR
The paper asks whether quantum mechanics can overcome limitations of conventional cryptography and computationally based coin tossing. It develops quantum protocols for key distribution and coin tossing, showing secure key sharing without an initial secret while identifying an Einstein-Podolsky-Rosen-based attack on coin tossing.
Problem
Conventional communications can be passively copied, while prior coin-tossing protocols rely on unproved computational-complexity assumptions.
Method
The paper uses non-orthogonal photon polarizations for key distribution and exchanges classical and quantum messages for coin tossing.
Results
Quantum coding enables secure random-key distribution without initially shared secrets; the coin-tossing scheme resists traditional cheating but is subverted by the Einstein-Podolsky-Rosen effect.
Takeaways & Limitations
Quantum channels can provide cryptographic security against eavesdropping, but quantum coin tossing remains vulnerable to a subtler physical attack.
Takeaways & Limitations
The coin-tossing attack requires perfect photon-storage and detection efficiency beyond current capabilities.
Abstract
from arXiv · showhide
When elementary quantum systems, such as polarized photons, are used to transmit digital information, the uncertainty principle gives rise to novel cryptographic phenomena unachievable with traditional transmission media, e.g. a communications channel on which it is impossible in principle to eavesdrop without a high probability of disturbing the transmission in such a way as to be detected. Such a quantum channel can be used in conjunction with ordinary insecure classical channels to distribute random key information between two users with the assurance that it remains unknown to anyone else, even when the users share no secret information initially. We also present a protocol for coin-tossing by exchange of quantum messages, which is secure against traditional kinds of cheating, even by an opponent with unlimited computing power, but ironically can be subverted by use of a still subtler quantum phenomenon, the Einstein-Podolsky-Rosen paradox.
I. Introduction
The paper grounds cryptography in quantum uncertainty, using non-orthogonal photon states to enable secure random-key distribution without pre-shared secrets. It also notes practical limitations, including weak, non-amplifiable transmissions and the absence of digital signatures.
- Cryptographic foundations: Traditional secret-key systems require one-time keys at least as long as the cleartext, while computational security for public-key systems remains unproven.The introduction contrasts information-theoretic limits with incomplete understanding of computational complexity.
- Quantum foundation: Encoding information in non-orthogonal quantum states, including photons polarized at 0, 45, 90, and 135 degrees, makes passive monitoring or copying detectable in principle.The approach relies on the uncertainty principle of quantum physics rather than conventional cryptographic assumptions.
- Main contribution: Quantum coding alone permits secure distribution of random key information between parties who share no secret initially, providing a major advantage of public-key cryptography.The paper presents this as a result of quantum coding by itself, rather than requiring public-key techniques.
- Limitations: Quantum transmissions are necessarily very weak and cannot be amplified in transit, and quantum cryptography does not provide digital signatures or dispute-settlement applications.The introduction specifically mentions certified mail and settling disputes before a judge as unavailable applications.
II. Essential Properties of Polarized Photons
Polarized photons exhibit intrinsically probabilistic measurement behavior: a single-photon measurement reveals at most one bit about polarization, except when aligned with the measurement basis. Quantum mechanics models these states in Hilbert space, where conjugate bases produce randomness and measurements generally alter the state.
- Polarization measurement: A single-photon polarization measurement reveals no more than one bit, transmitting with probability cos^2(a-P) and absorbing with probability sin^2(a-P).The outcome is deterministic only for parallel or perpendicular polarizer axes.
- Polarization measurement: Repeating measurements cannot recover additional information because a transmitted photon emerges with the filter’s polarization and loses memory of its original polarization.Amplifying a photon into identical clones is likewise impossible under quantum mechanics.
- Hilbert-space formalism: Quantum mechanics represents a system’s internal state as a unit vector in a complex Hilbert space, with measurements described through projection operators.The identity operator is represented as a sum of projections onto measurement subspaces.
- Hilbert-space formalism: Measurements are generally probabilistic and leave the state unchanged only when the initial vector lies entirely within one of the measurement’s orthogonal subspaces.The single polarized photon occupies a 2-dimensional Hilbert space with rectilinear and diagonal bases.
- Conjugate bases: Rectilinear and diagonal bases are conjugate: a state prepared in one basis behaves entirely randomly when measured in the other and loses its stored information.The diagonal basis represents 45-degree and 135-degree photons.
lll. Quantum Public Key Distribution
Quantum public key distribution uses a quantum channel to establish shared random bits without an initial secret, while public comparison detects likely eavesdropping. The protocol’s security follows from a quantitative tradeoff between information gained and induced disagreement.
- Outcome: Undisturbed transmissions produce shared secret bits that can serve as a one-time pad or support other cryptographic applications such as authentication tags.The users initially share no secret information; the quantum channel supplies the random bits.
- Protocol: Afterward, Alice and Bob use an ordinary public channel to identify received photons and matching bases, then compare a random subset to test for disturbance.Compared bits are sacrificed, but disagreement indicates that the quantum transmission was likely disturbed.
- Security tradeoff: 1/2 expected bits is the maximum information an eavesdropper can obtain about a key bit when the original basis is revealed only afterward.This bound applies to measurements performed before the eavesdropper learns the photon’s original basis.
- Security tradeoff: b/2 disagreement probability is unavoidable for any measurement yielding b expected information, where b ≤ 1/2, when the photon is later re-measured in its original basis.Measuring and retransmitting every intercepted photon in the rectilinear basis achieves the optimum example: learning half the polarizations while inducing disagreement in one quarter.
R t D
The protocol authenticates messages against tampering by outsiders, while allowing consumed authentication-key bits to be replaced with fresh quantum-transmitted randomness. Suppression remains possible, but Alice and Bob can detect it with high probability.
- Message authentication: An eavesdropper ignorant of the key has only a small probability of generating valid message-tag pairs, so the tag evidences message legitimacy.The tag also indicates that the message was not generated or altered by someone ignorant of the key.
- Key management: Wegman-Carter key bits are gradually consumed and cannot be reused without compromising provable security.This limitation applies to the authentication scheme’s key material.
- Key management: In this application, consumed key bits can be replaced by fresh random bits successfully transmitted through the quantum channel.The replacement mechanism avoids permanently exhausting the authentication key material.
- Denial of communication: An eavesdropper can suppress public-channel messages or suppress or excessively perturb transmitted photons, preventing communication.These attacks deny communication rather than silently compromising its security.
- Denial of communication: With high probability, Alice and Bob conclude that secret communications are being suppressed and are not fooled into believing they are secure.This conclusion applies whether suppression occurs through the public channel or through the quantum channel.
IV. Quantura Coin Tossing
The paper presents a quantum coin-tossing protocol that detects traditional cheating without relying on computational assumptions, yet can be subverted by an EPR-based strategy requiring ideal photon storage and detection. The protocol uses random photon bases, classical disclosure, and table comparison to verify the result.
- Motivation: The protocol targets a 50 percent chance of winning for each distrustful party while detecting attempts to bias the outcome.Earlier protocols relied on unproved assumptions in computational complexity theory.
- EPR attack: EPR photon pairs let Alice measure stored partners in the opposite basis after Bob’s guess, obtaining results correlated with the table needed to force a win.This subversion requires perfect photon storage and detection, while the honestly followed protocol could use current technology.
- Protocol: Alice sends randomly encoded photons, Bob measures each in a randomly chosen basis and guesses Alice’s basis, then Alice reveals and certifies her original bit sequence.Bob wins if his basis guess is correct; otherwise he loses.
- Verification: Bob verifies honesty by checking perfect agreement with the table matching Alice’s basis and no correlation with the other table.Losses in detectors and transmission can create holes in Bob’s tables.
- Traditional cheating: Alice’s attempted substitutions or mixed-basis photons generally fail because Bob’s corresponding tables contain probabilistic results beyond her control, making cheating detectable.A fabricated sequence matching the wrong table requires luck and risks detection.