Cryptography from Noisy Storage

A. Related work

• Earlier storage-noise proposals included no rigorous analysis in, while the original bounded-quantum-storage analysis applies when noise reduces dishonest storage rank to n/4; this work gives explicit security trade-offs even for small noise.Source: A. Related work · p. 2
• The analysis gives an explicit security trade-off even for small amounts of storage noise.Its proof does not exploit noise in the communication channel.Source: A. Related work · p. 2
• Classical noisy-storage and bounded-storage models are difficult to enforce in practice, and prior bit-commitment work restricted coherent measurement.This analysis allows any coherent destructive measurement at the end of the protocol.Source: A. Related work · p. 2

I. DEFINITIONS AND TOOLS

• The section relates non-uniformity of X given quantum state ρE to how close X is to uniform despite that side information.It also presents a simplified bound using the adversary's average guessing success probability.Source: §I · pp. 2–3
• Randomized OT gives Alice two uniformly random strings, which she can use as one-time pads to convert ROT into OT.Bob can recover the message selected by his choice while remaining ignorant of the other message.Source: §I · p. 2
• An ε-secure 1-2 ROT requires correctness for honest parties and security against either a cheating sender or receiver.The definition includes receiver-security and sender-security conditions, including bounds on the dishonest party's information.Source: §I · pp. 2–3
• Two-universal hash functions support privacy amplification by hashing an n-bit input to ℓ bits, with collision probability at most 2^-ℓ for distinct inputs.The cited theorem bounds the non-uniformity of the hashed output given quantum side information.Source: §I · p. 3

E. Then Pg(X|ρE) = supM

• The section defines a guessing-success quantity for measurements and relates non-uniformity bounds to the maximal average probability of guessing X.Additional classical information about X is also considered in bounding that quantity.Source: E. Then Pg(X|ρE) = supM · p. 3
• With individual quantum information about bits of X, the optimal probability of guessing the whole string is the product of the per-register guessing probabilities.This optimum is achieved by measuring each register separately.Source: E. Then Pg(X|ρE) = supM · p. 3
• For BB84 states passed through a superoperator, the section introduces an uncertainty relation between guessing success in the two encoding bases.The states use the computational and Hadamard bases.Source: E. Then Pg(X|ρE) = supM · p. 3
• A measurement of BB84 states can attain guessing success 1/2(1 + 2^-1/2) using the Breidbart basis, while unitary operations are reversible.The text also states that reversible operations can attain ∆(U)^2 = 1.Source: E. Then Pg(X|ρE) = supM · p. 3

II. PROTOCOL AND ANALYSIS

• Alice chooses random bit and basis strings and sends the corresponding BB84 states to Bob.The states are prepared as a tensor product, one for each position.Source: §II · p. 3
• Bob measures every received qubit in the basis selected by his choice bit, producing an outcome string.Source: §II · p. 3
• Alice later reveals the basis-position sets and sends independent two-universal hash functions for the two bases.She hashes the corresponding substrings of her original bit string to obtain S+ and S×.Source: §II · p. 4
• Bob outputs the hash value for his chosen basis, applied to his measurement outcomes at the matching positions.Source: §II · p. 4

• The protocol is correct, and a dishonest Alice learns nothing from Bob because the protocol is noninteractive.Source: A. Analysis · p. 4
• The proof bounds Bob’s guessing probability using per-qubit uncertainty relations and the product structure of his collective storage attack.Source: A. Analysis · p. 4
• For essentially any noisy superoperator with Δ(S)<1, choosing n sufficiently large makes security arbitrarily high against collective attacks.Source: A. Analysis · p. 4

• The attack model writes Bob’s storage operation as depolarizing noise after an arbitrary one-qubit operation that may produce classical output.Source: B. Example · p. 4
• The analysis solves the optimization over partial measurements for depolarizing noise by exploiting the problem’s symmetries.Source: B. Example · p. 4
• For r<1/2, Bob’s best strategy is to store each qubit unchanged; Theorem 2 also identifies direct Breidbart measurement as optimal in the measurement-optimal regime.Source: B. Example · pp. 4–5

• The honest protocol models erasures as basis-independent and other preparation, transmission, and measurement errors as an independent binary symmetric channel with error probability perror<1/2.Source: §III · p. 5
• Alice sends weak light pulses, Bob measures and reports detected qubits, and Alice restricts the protocol to the reported non-erased subset.Source: §III · p. 5
• Syndrome information lets Bob correct errors before producing his output, while Alice uses two-universal hash functions to form the OT strings.Source: §III · p. 5
• With basis-independent erasures and suitable error-correcting codes, honest parties obtain matching strings with exponentially small error, while the security bound depends on Δmax versus h(perror).Source: §III · pp. 5–6

• The cited passages state that Bob’s optimal attack is to measure each qubit individually in the Breidbart basis; in that case, security requires perror ⪅ 0.029.Source: A. Depolarizing noise · p. 6
• For short-distance implementations, transmission depolarization may be negligible, leaving honest measurement noise as the main depolarization source.Source: A. Depolarizing noise · p. 6
• The security trade-off between honest noise scaling a and storage parameter r depends on where the stated bound falls below zero.Source: A. Depolarizing noise · p. 6

B. Other Attacks

• For mean photon number µ, the probability of more than one photon is approximately µ/2, allowing Bob to know when he may measure in both bases.With the remaining probability, the discussed attack assumes a Breidbart-basis measurement.Source: B. Other Attacks · pp. 6–7
• A beam-splitting attack can give Bob about nµ/4 slots with multiple photons to measure in both bases, but its security bound and optimal cheating strategy remain unproved.The analysis assumes perfect detector efficiency; single-photon sources would exclude this attack.Source: B. Other Attacks · p. 7
• The protocol assumes Alice can establish a reliable lower bound on the erasure rate, since detector-efficiency claims could otherwise conceal an insecure attack.A dishonest Bob could claim poor detection while using better detectors to measure two-photon pulses in both bases.Source: B. Other Attacks · p. 7
• Because current photon measurements are destructive, Bob must guess which qubits were erased if he wants to store them; an erasure channel has ∆(S_erasure) = 1 − p_erasure/2.Erasure rates around O(10^-1) can limit storage attacks in current technology.Source: B. Other Attacks · p. 7

C. Fault-tolerant computation

• Fault-tolerant memory could make effective storage noise arbitrarily small, but encoding a single unknown state still introduces errors that cannot be reduced arbitrarily by greater effort.The residual rate comes from the unprotected encoding operation.Source: C. Fault-tolerant computation · p. 7
• Security in this setting depends on the trade-off between residual encoding noise and the intrinsic storage-noise rate.The paper identifies this trade-off as the relevant question once fault-tolerant memory is available.Source: C. Fault-tolerant computation · p. 7
• The current security bound is too weak to show security when fault-tolerant storage leaves only residual encoding noise.Source: C. Fault-tolerant computation · p. 7

IV. CONCLUSION

• The paper establishes security bounds for perfect and practical ROT against collective storage attacks, while general coherent noisy attacks remain an ideal for future analysis.A de Finetti approach may help for a symmetrized protocol, and a specific QKD-like coherent noise model is analyzable when Bob's information matches Eve's.Source: §IV · p. 7
• When Bob's information under a coherent noise model matches Eve's in QKD, QKD security implies that he learns nothing about the two generated keys.The protocol can be viewed as two interleaved QKD runs, with the two strings serving as keys.Source: §IV · p. 7
• Better trade-offs between honest-protocol noise and noise induced by dishonest Bob, and composability within this model, remain open.Source: §IV · pp. 7–8

APPENDIX A: TOOLS

• For independent registers, the maximum probability of guessing the entire string is the product of the per-register guessing probabilities.The appendix also derives the corresponding product relation for its primal optimum.Source: Appendix A · p. 9

APPENDIX B: DEPOLARIZING NOISE

• The optimization over partial measurements reduces to maximizing over a single operator, with symmetry limiting the measurement to at most four operators.Source: Appendix B · p. 11

1. F is diagonal in the Breidbart basis

• The optimizer is restricted to the XZ plane, has equal x and z coordinates at optimum, and is diagonal in the Breidbart basis.Source: §1 · pp. 12–13, §2 · p. 13

2. Optimality of the trivial strategies

• Bob’s optimal strategy is either to store each qubit or measure in the Breidbart basis, with the choice depending on storage noise.Source: §2 · p. 13