PaperlayerView exact revision on arXiv

Source-linked AI summary

Unconditional security from noisy quantum storage

Robert Koenig, Stephanie Wehner, Juerg Wullschleger

arXiv:0906.1030v4quant-phcs.CR

TL;DR

The paper asks whether oblivious transfer and bit commitment can be secured when a cheating party lacks reliable large-scale quantum storage. It constructs protocols whose security against general attacks is tied to noisy-storage channel capacity, with higher noise yielding stronger security.

  • Problem

    The paper addresses unconditional security for oblivious transfer and bit commitment under the assumption that the cheating party lacks reliable large-scale quantum storage.

  • Method

    The protocols build bit commitment and oblivious transfer from weak string erasure, classical coding, interactive hashing, and privacy amplification, analyzing security through the adversary’s noisy-storage channel.

  • Results

    Oblivious transfer and bit commitment use O(n) qubits of communication and achieve exponential security against adversaries with noisy storage, including arbitrary channels under a classical-capacity condition.

  • Takeaways & Limitations

    Security rates trade off naturally with the classical capacity of the storage channel, while higher storage noise leads to stronger security.

  • Takeaways & Limitations

    The analysis assumes error-free honest-party operations and leaves the exact tradeoff between communication noise and malicious-storage noise unresolved.

Abstract

from arXiv · show

We consider the implementation of two-party cryptographic primitives based on the sole assumption that no large-scale reliable quantum storage is available to the cheating party. We construct novel protocols for oblivious transfer and bit commitment, and prove that realistic noise levels provide security even against the most general attack. Such unconditional results were previously only known in the so-called bounded-storage model which is a special case of our setting. Our protocols can be implemented with present-day hardware used for quantum key distribution. In particular, no quantum storage is required for the honest parties.

I. THE NOISY-STORAGE MODEL: DEFINITION AND RESULTS

The paper introduces a noisy-storage model that unifies bounded and noisy quantum storage, and establishes unconditional security for oblivious transfer and bit commitment against arbitrary attacks. Security is tied to the classical information capacity of the adversary’s storage channel, yielding exponential security under suitable coding conditions and improved bounded-storage parameters.

  • Model: The noisy-storage model incorporates both storage size and noise, with bounded-storage and earlier noisy-storage settings as special cases.The model allows an otherwise all-powerful adversary, subject only to noise that increases with storage time.
  • Protocols: The protocols use weak string erasure as a quantum primitive, while honest parties require no quantum memory and the subsequent bit-commitment and oblivious-transfer protocols are purely classical.Oblivious transfer additionally uses interactive hashing, while the constructions employ classical coding and privacy amplification techniques.
  • Main result: The paper proves security for oblivious transfer and bit commitment against fully general attacks for arbitrary noisy-storage channels.A sufficient condition is that the number of classical bits transmissible through the noisy-storage channel is limited.
  • Main result: Theorem I.1 gives O(n) qubits of communication and security exponential in n when decoding probabilities decay exponentially above a threshold.The theorem does not require the storage channel to have tensor-product form or to be known beyond its relation to the coding problem.
  • Results: For bounded noise-free qubit storage, security holds for storage rates ν < 1/2, improving the previous ν < 1/4 result.The improvement is attributed to interactive hashing replacing min-entropy splitting in oblivious-transfer post-processing.
  • Results: The analysis extends security to lower noise levels and higher storage rates than bounded-storage analysis, with a natural tradeoff between storage-channel capacity and primitive rates.The depolarizing-channel region is derived from the channel’s coding properties and capacity.

E. Techniques: weak string erasure

The paper introduces weak string erasure as a primitive underlying bit commitment and oblivious transfer. Its protocol is compatible with present-day quantum-key-distribution hardware and requires no quantum memory for honest parties.

  • Weak string erasure gives Alice a random bit string while Bob receives a randomly chosen substring and its index set.
  • The weak-string-erasure protocol can be implemented with present-day quantum-key-distribution hardware without quantum memory for honest parties.
  • Bit commitment and oblivious transfer are constructed from weak string erasure, with oblivious transfer additionally using interactive hashing.
  • The security analysis of oblivious transfer uses quantum-adversary entropy sampling, while the underlying framework uses min-entropy and uncertainty relations.

B. Quantifying adversarial information

The paper quantifies an adversary’s information about a classical variable using guessing probability and conditional min-entropy. Smooth min-entropy extends this framework to nearby states and supports the security proof.

  • The adversary’s information about X is measured by the maximal probability of guessing X from quantum system Q.
  • Conditional min-entropy provides an entropy-like form of the guessing-probability measure for classical-quantum states.
  • The min-entropy framework includes classical, quantum, and mixed classical-quantum information, including states generated by basis choices and measurements.
  • Smooth min-entropy allows optimization over states near the actual state, so proving closeness to a high-min-entropy state yields high smooth min-entropy for the protocol state.
  • The smooth min-entropy obeys a chain rule that relates uncertainty about X and additional classical information Y.

3) Uncertainty relations for post-measurement information:

The paper develops uncertainty relations for an adversary who measures quantum information before receiving additional classical information. It then relates storage noise to increased uncertainty through channel-based min-entropy bounds.

  • A measurement of Q producing classical K is modeled as a completely positive trace-preserving map, converting quantum side information into classical information.
  • The min-entropy identity relates uncertainty conditioned on quantum information Q to uncertainty conditioned on the measurement result K=K(Q).
  • When basis information Θ arrives after measurement, the optimized post-measurement uncertainty can match the min-entropy without post-measurement information.
  • Applying a quantum channel to the adversary’s system cannot decrease the relevant conditional min-entropy, reflecting that discarding information makes X harder to guess.
  • The channel bound connects post-storage uncertainty to the classical-bit transmission success probability of the storage channel.
  • A generalization handles classical side information, approximate states, and partial trace, using a high-probability good set of conditioning values.

D. Defeating a quantum adversary: essential building blocks

The cryptographic constructions rely on privacy amplification and min-entropy sampling to convert adversarial uncertainty into secure keys and usable substrings. The protocol treatment also specifies how malformed or missing messages are handled.

  • Privacy amplification uses a 2-universal hash function to turn a string with quantum-conditioned min-entropy into a shorter nearly secret string.
  • The extracted key remains secure even when the adversary receives the public hash-function seed in addition to quantum information Q.
  • Min-entropy sampling approximately preserves entropy rate for a randomly chosen substring, enabling reasoning about sampled portions of a longer string.
  • The concrete sampling construction uses uniformly random fixed-size subsets and accommodates block-structured strings in the quantum setting.
  • Malformed or missing messages are handled by treating them as a particular valid message rather than adding an explicit aborted output.

3) Aborting a protocol:

The paper treats aborts explicitly because honest parties are assumed to continue when a dishonest party refuses to send correctly formed messages. This convention supports the security definitions and the later use of interactive hashing, weak string erasure, bit commitment, and oblivious transfer.

  • Abort handling: Honest players always send messages when they are supposed to, and an honest player chooses the required messages if the dishonest player refuses to send correctly formed ones.The same convention is applied when a player aborts interactive hashing: the other player terminates the interaction and simulates the remainder.
  • Interactive hashing: Interactive hashing creates two strings, one equal to Bob’s input, while Alice does not learn which one it is and Bob has little control over the other.The primitive is later used as a tool for constructing oblivious transfer.
  • Role in the construction: The protocol is introduced as a weak-string-erasure primitive whose security is subsequently proved in the noisy-storage model.This primitive is the basis for the paper’s later cryptographic constructions.
  • Weak string erasure: Weak string erasure relaxes ideal string erasure by allowing a dishonest Bob limited additional information about Alice’s string while requiring residual uncertainty.For dishonest Alice, the protocol retains protection of Bob’s random index set and additionally requires Alice to be committed to a choice of string.
  • Security properties: The weak-string-erasure definition requires correctness, uniformly distributed index information independent of a dishonest Alice’s view, and closeness of real executions to suitable ideal states.When Bob is dishonest, the construction requires high min-entropy rather than uniformity of Alice’s string.

B. Protocol

The protocol uses BB84 states to realize weak string erasure: Alice sends randomly based qubits, Bob measures in random bases, and matching-basis positions form his output subset. Security is then analyzed against arbitrary cheating strategies constrained by the storage channel.

  • Protocol: Alice sends randomly encoded BB84 qubits, Bob measures in independently random bases, and matching-basis positions determine the subset and substring he outputs.Alice outputs the full random string, while Bob outputs the matching index set and corresponding measurement outcomes.
  • Channel specialization: For tensor-product storage channels, the theorem specializes to storage F = N ⊗νn under a strong-converse condition on N.The resulting parameters are expressed using the channel’s storage rate and associated security quantities.
  • Correctness: The protocol is correct for honest parties because Alice’s string is uniform and Bob correctly obtains the corresponding bits on a random subset.The remaining analysis addresses security against dishonest Bob and dishonest Alice.
  • Security model: A dishonest Bob may use an arbitrary encoding attack, retain unlimited classical information, store quantum information, and later receive the basis string.His stored quantum register then undergoes the storage noise channel before he attempts to reconstruct Alice’s string.
  • Security for honest Alice: The security proof shows that Bob’s information about Alice’s string is limited for sufficiently large n, yielding a state exponentially close to one with constant min-entropy rate.The proof uses uncertainty relations and the strong-converse behavior of the storage channel.

D. Security for honest Bob

The security proof models dishonest Alice by her sent quantum register, basis string, and retained system, then constructs a simulator whose ideal state matches the real protocol on the relevant registers.

  • Security model: Alice’s strategy is represented by an n-qubit register sent to Bob, a classical basis string, and a retained quantum system.Honest Bob measures in random bases and obtains the intersecting set I and substring ˜X_I.
  • Conclusion: Protocol 1 satisfies security for honest Bob.The theorem follows from constructing an ideal state with the required properties and identifying it with the real protocol state.
  • Simulator: The simulator measures Alice’s register in her basis string, randomly re-encodes the outcomes, and sends the resulting qubits with fresh basis information to Bob.This constructs the candidate ideal state used in the security definition.
  • Simulator: The simulator’s basis strings are independent and uniform, making I uniform over subsets of [n] and independent of Alice’s information.The proof uses this independence to establish the required ideal-state properties.
  • Security proof: The real protocol and simulator produce the same reduced state because measurements and re-encoding on matching bases can be removed, while discarded positions do not affect the output.This establishes equality on the registers relevant to security.

E. Application to concrete tensor product channels

The paper applies its security criterion to tensor-product noisy channels, relating storage noise and capacity to secure parameter regimes and min-entropy rates, then introduces commitment constructions built from the resulting primitive.

  • Concrete channels: Strong-converse channels yield security of weak string erasure through Corollary III.4.The analysis applies this to the d-dimensional depolarizing and one-qubit two-Pauli channels.
  • Concrete channels: For storage rate ν = 1, security is obtained when the channel capacity satisfies C_N < 1/2.The relevant noise thresholds are summarized in Figure 9.
  • Concrete channels: For storage rates other than ν = 1, Figure 10 examines secure regimes for the qutrit depolarizing and two-Pauli channels.The security region depends jointly on the storage rate ν and noise parameter r.
  • Min-entropy rates: The min-entropy rate λ(δ) is computed from the channel’s strong-converse characterization and evaluated for qubit and qutrit depolarizing channels.Figure 11 uses ν = 1 and δ = 0.01 and relates λ to the noise parameter r.
  • Bit commitment: A randomized commitment receives a random string during Commit, while an optional xor message converts it into a commitment to Alice’s chosen value.The formal protocol uses syndrome information, privacy amplification, and an Open procedure that accepts only when consistency checks pass.
  • Bit commitment: The commitment definition requires correctness, hiding against dishonest Bob, and binding against dishonest Alice within ε-error criteria.These properties are expressed through ideal-state closeness and acceptance conditions.

B. Protocol

The paper constructs randomized string commitment from weak string erasure using a syndrome and universal hashing, then proves correctness, hiding, and binding with explicit parameters.

  • Commit: Commit runs weak string erasure, sends a random hash seed and syndrome, and outputs c^ℓ = Ext(x^n, r) while Bob stores the seed, syndrome, index set, and substring.The protocol relies on a binary linear code and a 2-universal hash function.
  • Open: Open sends x^n, and Bob accepts only if both the weak-string-erasure substring and syndrome match; otherwise he rejects.On acceptance, Bob recomputes the extracted commitment string.
  • Guarantee: Theorem IV.2 gives commitment length ℓ = λn − (n−k) − 2 log 1/ε′ and error 2ε + ε′.The construction is based on one instance of (n, λ, ε)-WSE.
  • Guarantee: With codes satisfying k/n → 1, the commitment rate is roughly λ up to logarithmic losses.The cited Reed–Solomon construction yields ℓ ≥ λn − 2 log n log 1/ε.
  • Security properties: The protocol is (2ε + ε′)-hiding and correct with error at most 2ε + ε′.Hiding follows from privacy amplification after syndrome leakage, while correctness follows from weak string erasure properties.
  • Security properties: The protocol is ε-binding because a distinct string with the same syndrome must be separated by the code distance and is accepted only with small probability.The proof bounds the cheating acceptance probability using the distance condition and random index set.

V. 1-2 OBLIVIOUS TRANSFER FROM WEAK STRING

Weak string erasure yields fully randomized oblivious transfer by giving Alice two strings and Bob one randomly selected string while keeping the choice and unselected string hidden.

  • Security: Security for Alice requires that Bob’s choice bit remains hidden from her.The ideal state makes the choice bit uniform and independent of Alice’s information.
  • Definition: Fully randomized oblivious transfer outputs two random ℓ-bit strings to Alice and a random choice bit with the selected string to Bob.The protocol takes no inputs and permits abort provided security holds whenever it does not abort.
  • Security: Security for Bob requires that he learns at most one of Alice’s two strings, with the other string remaining unknown.The definition expresses this through an ideal choice variable C and closeness to an ideal state.
  • Reduction: The randomized primitive can be converted into standard 1-2 oblivious transfer by masking Alice’s inputs with the two random strings.Bob communicates whether the random choice equals his desired choice, without revealing the choice itself to Alice.
  • Definition: The formal FROT definition requires correctness and security for both parties, expressed as ε-closeness to corresponding ideal states.The ideal states specify Alice’s two strings, Bob’s choice and output, and the information each party may retain.

B. Protocol

The protocol converts weak string erasure into fully randomized oblivious transfer using interactive hashing, permutations, and universal hashing. It produces two strings for Alice and one selected string for Bob while supporting security against cheating parties.

  • Protocol construction: The protocol first executes weak string erasure, then normalizes Bob’s index set to size n/4.Bob pads smaller sets with zeros or randomly truncates larger sets.
  • Protocol construction: Interactive hashing generates two subset descriptions, one corresponding to Bob’s input and one intended to remain hidden from him.Subset encodings are injective and cover at least half of the relevant subsets.
  • Outputs: Bob outputs the hash associated with his choice bit, while Alice outputs both hashed strings.The selected subset is recovered from Bob’s weak-string-erasure information and the permutation.
  • Guarantee: Theorem V.2 states that WSE-to-FROT constructs fully randomized oblivious transfer under the stated β and ω parameter conditions.The construction has output length ℓ defined by the theorem’s parameters, and the proof-of-principle setting may choose ω=2.

C. Security proof

The security proof analyzes cheating Alice and Bob separately by combining weak string erasure, interactive hashing, min-entropy sampling, and privacy amplification. It also establishes correctness for honest executions.

  • Security for Alice: Security against Alice follows because she remains ignorant of Bob’s index set, while interactive hashing prevents her from learning which subset determines Bob’s output.The proof constructs an ideal state in which Alice’s view is independent of the choice bit.
  • Security for Bob: Security against Bob follows because weak string erasure limits his information about X^n and interactive hashing limits his control over one generated subset.Min-entropy sampling and privacy amplification then produce a nearly uniform secret string unknown to Bob.
  • Proof strategy: The protocol’s security analysis handles arbitrary quantum attacks rather than restricting the adversary to individual measurements.The argument tracks the adversary’s quantum side information through the protocol and applies min-entropy reasoning.
  • Security for Alice: The proof bounds Alice’s security error by at most 41δ + 2ε.This follows after conditioning on the high-probability event used in the privacy-amplification argument.
  • Correctness: The correctness proof uses random-subset concentration and privacy amplification to show that honest outputs are close to the ideal functionality.The padding event has probability at most ξ=2^-n/16, and the final closeness bound includes ξ and the security error.

VI. CONCLUSIONS AND OPEN PROBLEMS

The paper concludes that noisy quantum storage enables unconditionally secure bit commitment and oblivious transfer, with security linked to storage-channel capacity. It identifies practical limitations and open problems concerning composability, robustness, channel classes, and attack optimality.

  • Conclusions: The protocols achieve unconditional security for bit commitment and oblivious transfer in the noisy-storage model.Security is connected to the information-carrying capacity of the malicious party’s storage channel.
  • Conclusions: Higher noise levels in the adversary’s storage lead to stronger security, producing a tradeoff between storage capacity and protocol rates.The conclusion describes this as a natural tradeoff for both oblivious transfer and bit commitment.
  • Open problems: The results are restricted to memoryless channels and may not apply to channels with high classical capacity, such as the dephasing channel.Whether small classical capacity is necessary for security against fully general attacks is left unresolved.
  • Extensions: Continuous-variable channels are within scope when a suitable bound on their information-carrying capacity is available.The paper presents this as a practically interesting extension of the capacity-based analysis.
  • Open problems: It remains open whether fully general coherent attacks reduce the achievability region compared with individual storage attacks.The paper notes that the two attack classes are equivalent in QKD but not established as equivalent here.
  • Limitations: The work remains a proof of principle rather than a practically optimized realization.The authors identify efficiency, composability, and robustness as issues requiring further work.
  • Open problems: Formal composability in the noisy-storage model remains open even though the security definitions are motivated by composability.The paper notes that a composability framework for this setting still needs to be established.
  • Open problems: The analysis assumes error-free honest operations and does not yet determine the tradeoff between communication noise and malicious-storage noise.Error-correction techniques are suggested, but the exact tolerable-noise tradeoff remains unresolved.

APPENDIX A. The parameters for sampling – proof of Lemma II.4

The appendix derives the sampling parameters needed for the min-entropy argument. It combines averaging samplers, block sampling, and bitwise-uniform sampling to obtain the bound used in the main security proof.

  • Sampler parameters: Uniform sampling of subsets of fixed size s is an averaging sampler with error parameter 2^-sξ^2/2.This follows by specializing the sampler construction to uniform fixed-size subsets.
  • Block sampling: The min-entropy block-sampling lemma applies averaging-sampler guarantees to cq-states whose classical strings are partitioned into β-bit blocks.The lemma transfers average entropy information from the full string to a sampled collection of blocks.
  • Parameter specialization: For the protocol parameters, β≥67 and β≥256ω^2/λ^2 ensure the required sampling condition and yield δ=2^-mλ^2/(512ω^2).The appendix derives this by setting ξ=λ/(4ω) and using s≥m/4.
  • Bit sampling: A separate result extends the block-sampling bound to subsets chosen uniformly bitwise rather than blockwise.The appendix uses a random permutation to relate bitwise sampling to blockwise sampling.
  • Combined bound: The appendix combines the block and bit-sampling lemmas to obtain Lemma II.4.The resulting statement is the sampling tool invoked in the main security analysis.
Loading 0906.1030v4…