PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-Quantum Key Distribution

Michel Boyer, Ran Gelles, Dan Kenigsberg, Tal Mor

arXiv:0812.4835v1quant-phcs.CR

TL;DR

The paper asks how much quantumness is needed for key distribution when Bob is classical. It analyzes two semi-quantum protocols and proves robustness, including a randomization-based variant that leaks no information when undetectable and has entropy exponentially close to its length.

  • Problem

    The paper asks how much quantum capability a key-distribution protocol needs when one party, Bob, is classical.

    Source: §I · p. 1

  • Method

    The authors analyze measure-resend and randomization-based SQKD, proving robustness while considering collective attacks on qubits sent one by one.

    Source: §V · p. 5

  • Results

    The randomization-based variant aborts with exponentially small probability and leaks no information to Eve when she is undetectable; measure-resend robustness also holds in the generalized collective-attack scenario.

    Source: A. Protocol 1: Randomization-based SQKD · p. 4, §V · p. 5

  • Takeaways & Limitations

    The protocols demonstrate key distribution with Bob restricted to classical operations, addressing how much quantumness the task requires.

    Source: §VI · p. 12

    The analysis assumes perfect qubits and leaves PNS and other implementation-dependent attacks for future research.

    Source: §VI · p. 13

Abstract

from arXiv · show

Secure key distribution among two remote parties is impossible when both are classical, unless some unproven (and arguably unrealistic) computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? Recently, a semi-quantum key distribution protocol was presented (Boyer, Kenigsberg and Mor, Physical Review Letters, 2007), in which one of the parties (Bob) is classical, and yet, the protocol is proven to be completely robust against an eavesdropping attempt. Here we extend that result much further. We present two protocols with this constraint, and prove their robustness against attacks: we prove that any attempt of an adversary to obtain information (and even a tiny amount of information) necessarily induces some errors that the legitimate parties could notice. One protocol presented here is identical to the one referred to above, however, its robustness is proven here in a much more general scenario. The other protocol is very different as it is based on randomization.

I. INTRODUCTION

The paper studies semi-quantum key distribution, where Alice is quantum and Bob is classical, and presents two protocols with robustness proofs. It distinguishes detecting information-gathering attacks from securing the final key.

I. INTRODUCTION

  • SQKD asks how much quantumness key distribution requires; Bob's allowed operations keep qubits in the computational basis or leave them undisturbed, while Alice remains quantum.The paper names the measure-resend and randomization-based variants.Source: §I · p. 1

II. ROBUSTNESS

  • Robustness means any nonzero information Eve gains on the INFO string implies a nonzero chance of detected errors; partial robustness may still permit security, depending on privacy amplification.Complete nonrobustness means Eve can learn the INFO string without errors on tested bits; sufficiently high loss can make partly robust protocols completely nonrobust.Source: §II · p. 2

III. MOCK PROTOCOL AND ITS COMPLETE NONROBUSTNESS

  • In the mock protocol, Eve can copy every INFO bit with a CNOT attack while inducing no errors on TEST or CTRL bits, making the protocol completely nonrobust.A second CNOT when Bob reflects the qubit resets Eve's ancilla, hiding the interaction from CTRL checks.Source: §III · p. 3

IV. TWO SEMI-QUANTUM KEY DISTRIBUTION PROTOCOLS

  • The proposed protocols hide which returned qubits are SIFT versus CTRL, and both aim to produce an n-bit INFO string for an l-bit shared secret key.Protocol 1 is not completely robust, whereas Protocol 1′, which adds parameter ϵ with 0 ≤ ϵ < δ, is completely robust.Source: §IV · p. 3, A. Protocol 1: Randomization-based SQKD · p. 3

A. Protocol 1: Randomization-based SQKD.

  • Protocol 1 lets Eve learn the measured string's Hamming weight undetected, yielding about 0.3 bits of INFO-string information regardless of its length.Protocol 1′ fixes a subset of allowable INFO strings; for ϵ > 0, a random string from that set has entropy exponentially close to n bits.Source: A. Protocol 1: Randomization-based SQKD · p. 4
  • Protocol 7′ chooses a length-2h substring with h zeros and h ones (h = ⌊(1 + ϵ)n/2⌋) and random y ∈ I_n,ϵ; it aborts with exponentially small probability and leaks no information if Eve is undetectable.Source: A. Protocol 1: Randomization-based SQKD · p. 4

B. Protocol 2: Measure-Resend SQKD

Protocol 2 replaces returned-qubit randomization with Bob’s choice to measure and resend or reflect. Alice measures each return in her preparation basis, and neither Alice nor Eve can tell which qubits Bob reflected.

B. Protocol 2: Measure-Resend SQKD

C. Classical Post-Processing.

The section describes classical key post-processing and the attack model used to prove robustness. It models Bob’s measurement-or-reflection behavior and lets Eve attack qubits sequentially with a shared probe, encompassing the earlier all-at-once scenario.

C. Classical Post-Processing.

  • The final classical step uses published ECC and privacy-amplification data to extract an l-bit key from the INFO string, with l ≤ R for an ECC of rank R.Robustness excludes ECC disclosure: the published parities can reveal up to n − R bits, so security must instead make information on the final key negligible.Source: C. Classical Post-Processing · p. 4

V. PROOFS OF ROBUSTNESS

  • The robustness proof covers qubits sent individually or together, analyzes collective attacks, bounds Protocol 1 leakage, and proves Protocol 1′ completely robust.The earlier scenario in is a special case of the analyzed attack setup.Source: §V · pp. 4–5

1. Modeling the protocol.

  • Bob’s measured positions are SIFT bits, while the other qubits are reflected as CTRL bits; an equivalent register model represents his actions with unitary operations.This model simplifies the analysis while retaining the protocol’s measurement-and-resend or reflection behavior.Source: §1 · p. 5

2. Eve’s attack.

  • Eve’s general attack applies a sequence of unitaries as qubits travel to and from Bob, with the all-at-once attack in as a special case.Under a restricted individual-qubit attack class, robustness of Protocol 2 also implies robustness of the individual-qubit protocol.Source: §2 · pp. 5–6

3. The final global state.

The proof first constrains the final state under attacks that cause no TEST or CTRL errors. It then shows Eve’s probe is independent of Alice’s sent state, yielding no information about the INFO string and complete robustness for Protocol 2.

3. The final global state.

  • The proof considers attacks that induce no error on any TEST or CTRL bits that can occur under Protocol 2.The global state is analyzed by delaying measurements and representing Eve’s and Bob’s actions with unitary operations.Source: §3 · p. 6
  • For a computational-basis input, no TEST or CTRL errors force the final state to factor as Eve’s probe, Alice’s returned string, and Bob’s measured substring.Eve’s probe is not entangled with either the returned string or Bob’s register, and does not depend on Bob’s measured positions.Source: §3 · p. 6
  • The proof extends this constraint to superpositions and shows that Eve’s probe state is the same for every computational-basis string.Source: §3 · p. 6
  • Therefore, any attack with no TEST or CTRL errors leaves Eve’s state independent of Alice’s input and gives her no information on the INFO string.The paper concludes that Protocol 2 is completely robust.Source: §3 · pp. 6–7

B. Partial robustness of Protocol 1.

For attacks that cause no TEST or CTRL errors, Protocol 1 limits Eve’s information to the Hamming weight of Bob’s measured string. An example attack can learn that weight without detection, so INFO-bit selection needs care.

B. Partial robustness of Protocol 1.

  • The analysis models Eve’s attack with forward and return unitaries, while Bob measures some qubits and reflects the rest.Bob randomly reorders the reflected qubits, and Alice retains them in quantum memory until their positions are known.Source: B. Partial robustness of Protocol 1 · p. 7

3. The global final state.

  • For attacks causing no TEST errors, Eve’s forward interaction can be represented by probe states |Ei⟩ correlated with Alice’s unchanged computational-basis string |i⟩.If the return interaction also causes no CTRL errors, Eve’s final state is written |Fs,i⟩.Source: §3 · p. 7
  • An example attack lets Eve learn the Hamming weight of Bob’s measured string without inducing errors on TEST or CTRL bits.The example shows that Protocol 1 is not completely robust under this attack.Source: §3 · p. 8
  • Eve’s final probe state depends only on the Hamming weight of Bob’s measured string when an attack induces no TEST or CTRL errors.Because Eve knows the string length, this amounts to learning the counts of zeros and ones, not their positions.Source: §3 · p. 9

4. Information leaked by Protocol 1.

Eve’s undetectable knowledge of the measured string’s Hamming weight gives her indirect information about the INFO bits. The paper bounds that information asymptotically.

  • Eve’s Hamming-weight knowledge gives indirect information about INFO-bit statistics, so randomly selecting INFO bits from non-TEST SIFT bits would not make Protocol 1 robust.Source: §4 · p. 9
  • 0.293 + O(n^-1) bits is an asymptotic upper bound on Eve’s information about the INFO string for attacks causing no TEST or CTRL errors.Source: §4 · p. 9
  • Eve knows the Hamming weight of Bob’s measured bits, and the paper bounds the information this clue provides about the INFO string.Source: §4 · pp. 9–10

C. Properties of Protocol 1′.

Protocol 1′ chooses its INFO string uniformly from strings whose zero and one counts satisfy a tolerance. The tolerance changes the string’s entropy from a logarithmic deficit at zero tolerance to exponentially close to its full length when positive.

  • For ϵ > 0, the entropy of the uniform distribution on In,ϵ is exponentially close to n.Source: §1 · p. 10
  • For ϵ = 0, the entropy of the uniform distribution on In,0 is asymptotically n − 0.5 log2(n) − 0.5(log2(π) − 1).Source: §1 · p. 10
  • Choosing ϵ > 0 avoids asymptotically losing more than 0.5 log2(n) bits of information.Source: §1 · p. 10

2. Probability of aborting Protocol 1′.

Protocol 1′ aborts if the post-test SIFT string has too few zeros or ones. For fixed 0 ≤ ϵ < δ and ϵ ≤ 1, the probability of aborting is exponentially small.

  • The protocol aborts if fewer than h zeros or h ones remain in the SIFT string after n TEST bits are chosen, where h = ⌊(1 + ϵ)n/2⌋.Source: §2 · p. 10
  • For fixed 0 ≤ ϵ < δ and ϵ ≤ 1, Protocol 1′ has an exponentially small probability of aborting.Source: §2 · p. 10
  • The abort analysis bounds the probability that the post-test SIFT string lacks enough zeros or ones when the SIFT-bit count exceeds the stated threshold.Source: §2 · p. 11

D. Complete robustness of Protocol 1′.

The proof considers an undetectable attack and aims to show that Eve obtains no information about the INFO string.

D. Complete robustness of Protocol 1′.

1. Probabilistic setup.

The probabilistic setup uses Eve’s state dependence on Bob’s measured-bit count to compare probabilities for balanced strings and show that her state does not depend on the INFO string.

1. Probabilistic setup.

  • If Eve is unnoticeable, her final state may depend only on the number of 1s among Bob’s measured bits, not on the INFO string.Source: §1 · p. 11
  • The proof selects 2h SIFT indices that are not TEST bits and considers balanced strings with h zeros and h ones.Here h = ⌊(1 + ϵ)n/2⌋.Source: §1 · p. 11
  • For balanced strings x and x′, their conditional probabilities given y and r are equal.The passage gives each probability as 1/|E_h|.Source: §1 · p. 11
  • The proof pairs corresponding measured-bit strings with equal numbers of 1s, yielding equal summed probabilities for x and x′.Source: §1 · p. 11

2. Combinatorial lemmas.

The combinatorial lemmas count permutations matching a bitstring and count balanced strings compatible with those matches.

2. Combinatorial lemmas.

  • P(E, k) denotes the set of strings of k distinct elements chosen from E, and the setup fixes h and a set E of 2h non-TEST SIFT indices.The parameters satisfy 0 ≤ ϵ ≤ 1 and ϵ < δ.Source: §2 · pp. 11–12
  • For balanced x and y with at most h zeros and h ones, the lemma counts permutations q for which x_q = y.Such permutations correspond to choosing indices for y’s zeros and ones from the matching positions in x.Source: §2 · p. 12
  • For a fixed q, compatible balanced strings are formed by filling the 2h − n unindexed positions with the remaining required zeros and ones.The resulting count is stated in the passage’s combinatorial expression.Source: §2 · p. 12

3. Proof of robustness.

The proof establishes zero information leakage under undetectable attacks for the stated parameter range. The conclusion presents two semi-quantum protocols and notes that the analysis assumes perfect qubits.

3. Proof of robustness.

  • For 0 ≤ ϵ ≤ 1 and ϵ < δ, an undetectable attack implies I(Y; Q, R) = 0, establishing complete robustness.Source: §3 · p. 12
  • The proof uses the constant balanced-string count to show that Q is independent of (Y, R), and hence Y is independent of (Q, R).Source: §3 · p. 12

VI. CONCLUSION

  • The paper presents two QKD protocols with a classically operating party, using measurement, undisturbed return, randomization, or resend operations.Source: §VI · p. 12
  • The conclusion says the measure-resend protocol is proven robust in a more general scenario, while the randomization-based protocol’s full robustness eliminates information leakage.Source: §VI · p. 12
  • The analysis assumes perfect qubits and leaves PNS and other implementation-dependent attacks for future research.Source: §VI · p. 13

APPENDIX

The appendix excerpt introduces Hoeffding’s theorem [19] and states assumptions on independent random variables, their moments, and their bounded ranges.

APPENDIX

  • Hoeffding’s theorem [19] assumes independent variables with finite first and second moments, each lying within a specified range with probability 1.The excerpt ends before giving the theorem’s conclusion.Source: APPENDIX · p. 13
Loading 0812.4835v1…