Source-linked AI summary
Trevisan's extractor in the presence of quantum side information
Anindya De, Christopher Portmann, Thomas Vidick, Renato Renner
TL;DR
The paper addresses whether randomness extractors remain secure when classical sources have quantum side information, a central issue for cryptographic applications. It proves that Trevisan’s modular extractor paradigm is quantum-proof and yields concrete constructions with near-optimal output, polylogarithmic seeds, or weakly random seeds. The paper also notes practical limitations concerning implementation and prior limitations of bounded-storage analyses.
Problem
Classical extractor criteria can be insufficient for quantum side information, even though adversaries in cryptographic applications may hold quantum information.
Method
The paper analyzes Trevisan’s modular construction by combining one-bit extractors with pseudorandom designs and adapting the soundness proof to conditional quantum min-entropy.
Results
Trevisan’s extractor is quantum-proof for arbitrary quantum side information, with output close to Hmin(X|E), polylogarithmic seed constructions, and soundness for weakly random seeds.
Takeaways & Limitations
The modular paradigm supports concrete extractors optimized for near-optimal output length, short seeds, or non-uniform seeds in quantum-information settings.
Takeaways & Limitations
Trevisan’s construction does not appear practically executable enough for applications, leaving practical variations as an open problem.
Abstract
from arXiv · showhide
Randomness extraction involves the processing of purely classical information and is therefore usually studied in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications, where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g, extract all the conditional (smooth) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random.
1 Introduction
The paper studies randomness extractors when side information is quantum, where the stronger security criterion is necessary for cryptographic applications. It proves that Trevisan’s modular construction remains sound in this setting and yields constructions with near-optimal output, polylogarithmic seeds, or weakly random seeds.
- Motivation: Quantum side information makes the relevant extraction criterion strictly stronger than the classical criterion, and classical security need not imply security against quantum side information.This matters because cryptographic adversaries may hold quantum information, including when the protocol itself is classical.
- Motivation: The paper defines an extractor as quantum-proof when its output is approximately uniform and independent of arbitrary quantum side information.The criterion is motivated by the role of conditional smooth min-entropy as the essentially optimal amount of extractable randomness.
- Our contribution: Trevisan’s extractor is proved sound under the general conditional-min-entropy criterion, improving on prior bounded-storage results and allowing output close to Hmin(X|E).The authors present this as the first soundness proof for a polylogarithmic-seed extractor against arbitrary quantum side information.
- Proof technique: The proof applies to a generic modular scheme formed by concatenating one-bit extractors with pseudorandom seeds, whose quantum-side-information performance is roughly equivalent to the classical case.The modularity permits arbitrary one-bit extractors and pseudorandom seed constructions to be plugged into the scheme.
- Our contribution: The construction remains quantum-proof when the seed is only weakly random, addressing settings where users lack access to uniform randomness.The paper also derives concrete variants optimized for output length, seed length, or non-uniform seeds.
- Proof technique: The proof uses a distinguishing test, a hybrid argument, and design properties to turn a successful distinguisher into a predictor for a random bit of the one-bit extractor output.The quantum min-entropy framework requires changes to the earlier proof strategy.
2 Technical preliminaries
The preliminaries represent classical and quantum systems with density operators and introduce conditional and smooth conditional min-entropy. For classical sources conditioned on quantum systems, conditional min-entropy has an operational interpretation through optimal guessing probability.
- Quantum-state notation: Classical strings and random variables are represented as diagonal quantum states, while composite systems use tensor products and reduced density operators.The notation also introduces trace norms and finite-dimensional Hilbert spaces.
- Min-entropy: Conditional min-entropy measures the randomness of one system relative to another system and is defined for sub-normalized quantum states.The paper introduces this notion before defining its smooth version.
- Min-entropy: When the first system is classical, conditional min-entropy is operationally related to the maximum probability of guessing it using the conditioning system.The guessing strategy is optimized over POVMs on the conditioning system.
- Min-entropy: Without side information, min-entropy reduces to Renyi entropy of order infinity and equals −log maxx∈X px.In that case, the optimal guess is the most probable value of the source.
- Smooth min-entropy: Smooth min-entropy maximizes min-entropy over sub-normalized states within ε of the actual state, allowing additional entropy at the cost of error ε.The smooth measure is used to characterize the amount of nearly uniform randomness extractable from a source.
3 Extractors
Extractors transform weak randomness into output that is nearly uniform and independent of a seed and side information. With quantum side information, the relevant criterion is conditional min-entropy, and smooth min-entropy characterizes the optimal extractable randomness.
- Definitions: A strong extractor maps a weak source and random seed to almost-uniform output that is approximately independent of the seed.The standard definition uses a uniform seed; strong extractors are also considered with weakly random seeds.
- Side information: Quantum-proof extraction requires output that is nearly uniform and independent of both the seed and quantum side information.Classical-proof extraction restricts the side-information system to classical states.
- Side information: A classical-proof strong extractor may fail against quantum side information, even when Hmin(X|E) is significantly larger than its threshold k.Classical and quantum side information therefore lead to different extraction criteria.
- Seed assumptions: Weakly random seeds must remain independent of the input, and Trevisan’s extractor is shown to remain quantum-proof in this setting.The weak-seed definition offers weaker composability guarantees than the stronger criterion used here.
4 Constructing m-bit extractors from one-bit extractors and weak designs
Trevisan’s paradigm builds an m-bit extractor by applying a one-bit extractor with overlapping pseudorandom seeds selected by a weak design. The paper proves this construction quantum-proof, including when the overall seed is only weakly random.
- Construction: Trevisan’s construction derandomizes m independent one-bit extractor applications, reducing the seed length from mt to poly(t, log m).The total seed is split into m overlapping t-bit blocks selected by sets in a weak design.
- Construction: A weak design controls overlap among the seed sets, enabling the generic m-bit construction ExtC(x, y) := C(x, yS1) ··· C(x, ySm).The scheme can use any weak design and one-bit strong extractor.
- Proof strategy: The proof reduces distinguishing the m-bit output from uniform to distinguishing the underlying one-bit extractor with limited additional classical advice.The reduction is combined with a theorem upgrading a classical strong extractor to a quantum-proof one.
- Uniform seed: With a uniform seed, the constructed extractor is quantum-proof with entropy requirement k + rm + log 1/ε and error parameter stated in Theorem 4.6.The bound follows by combining the weak-design reduction with the one-bit quantum-proof guarantee.
- Weak random seed: With a weakly random seed, the construction remains quantum-proof for seeds meeting the stated min-entropy condition, with the theorem’s corresponding error bound.The weak-seed result is stated for a one-bit extractor whose seed requires at least s bits of min-entropy.
5 Concrete constructions
The paper instantiates the quantum-proof Trevisan paradigm with different one-bit extractors and weak designs, trading seed length, output, locality, and seed randomness. These constructions include near-optimal entropy loss, logarithmic seeds, local computation, and weakly random seeds.
- General construction paradigm: The constructions combine classical one-bit extractors and weak designs through the generic Trevisan framework to obtain quantum-proof parameters.Different goals require different one-bit extractors and weak designs.
- 5.3 Local extractors: The local construction gives each output bit dependence on only O(log(m/ε)) input bits.It is a quantum-proof ℓ-local strong extractor with d = O(log^2(n/ε)).
- 5.4 Weak random seed: The weak-seed construction remains quantum-proof when the seed is only weakly random, while constant parameter choices give d = O(log n).It can output m = H_min(X|E)^(1−γ) − o(1) bits, with possible entropy loss linear in d; combining it with the all-entropy construction yields d = O(log^3 n).
- 5.1 Near optimal entropy loss: The near-optimal construction uses seed length d = O(log^2(n/ε) log m) and entropy loss Δ = 4 log 1/ε + O(1).For ε = poly(1/n), the seed length becomes O(log^3 n), and the entropy loss is twice optimal.
- 5.2 Seed of logarithmic size: The logarithmic-seed construction achieves d = O(log n) but extracts only m = H_min(X|E)^(1−γ) − o(1) bits for constant γ.The shorter seed requires a different weak design and sacrifices extracted entropy.
6 Outlook
The outlook identifies extensions and practical limitations of quantum-proof Trevisan-style extractors. It highlights related constructions, unresolved quantum-side-information questions, implementation challenges, and quantum-proof two-source extraction.
- Related constructions: Trevisan-style modifications retaining the design-and-one-bit-extractor structure inherit quantum-proofness with roughly the same parameters.Other modifications using multivariate codes may not be quantum-proof because their connection to one-bit extractors is unclear.
- Related constructions: Raz et al. extract slightly more randomness, while the paper’s quantum-side-information result has entropy loss 4 log 1/ε + O(1) and may be improvable.The comparison attributes the weaker result to the quantum-proof analysis used for the composed extractor.
- Open problems: Whether Trevisan modifications for sub-polynomial entropy preserve the design-and-one-bit-extractor structure remains an open problem for quantum side information.These modifications include constructions with seed size O(log n) that can extract all source min-entropy for some k = o(n).
- Practical implementation: Trevisan’s construction does not appear practically implementable because its running time is unsuitable for applications such as privacy amplification and randomness recycling.Finding practical variations is identified as an important open problem.
- Open problems: Quantum-proof two-source extractors remain an important research direction, with only limited prior study cited.The setting involves two independent sources, each correlated with independent quantum side information.
A.1 Weak random seed
The paper extends extractor definitions to seeds that are only weakly random, while requiring independence from the input and quantum side information. It also states a corresponding entropy condition and notes that quantum side information correlated with both input and seed is excluded.
- Weak random seed: Weak-seed extractors allow the seed to have bounded min-entropy rather than being uniformly random.The extension applies to both classical and quantum-proof strong extractors.
- Weak random seed: A strong extractor with an s-bit seed requires the seed Y to be independent of X and satisfy Hmin(Y) ≥ s.The definition is given for all sources X with Hmin(X) ≥ k.
- Weak random seed: A quantum-proof strong extractor requires Y to be independent from XE, with Hmin(Y) ≥ s, while X may have conditional min-entropy Hmin(X|E) ≥ k.The output is required to be uniform and independent in the corresponding quantum setting.
- Weak random seed: Classical side information about the input or seed preserves essentially the same extractor parameters.This is stated through Lemma 3.3 for classical side information.
- Weak random seed: The analysis excludes quantum side information correlated with both the input and the seed.The paper explicitly identifies this case as outside its scope.
A.2 Composing extractors
The paper generalizes extractor composition to quantum side information by applying a second extractor to the entropy remaining after the first output is revealed. The composition theorem combines two quantum-proof strong extractors with appropriately reduced entropy and additive error parameters.
- Composing extractors: A second extractor can recover entropy that remains in the original input after the first extractor’s output is known.This extends earlier classical and quantum composition results to arbitrary quantum extractors.
- Composing extractors: Two quantum-proof strong extractors compose when the first has parameters (k, ε1) and the second has parameters (k−m1, ε2).The second extractor operates after the first outputs m1 bits.
- Composing extractors: The composed extractor uses both seeds and outputs the concatenation of the two extractor outputs.Its domain is {0,1}n × {0,1}d1 × {0,1}d2 and its output length is m1 + m2.
- Composing extractors: The composition error is bounded by ε1 + ε2.The proof bounds the two terms separately using the definitions of Ext1 and Ext2.
B.1 Min-entropy chain rules
This appendix develops min-entropy chain-rule tools used in the quantum extractor analysis. The stated lemmas relate conditional min-entropy when classical registers are added or conditioned upon.
- Min-entropy chain rules: The paper uses chain-rule-type statements about min-entropy, with the first two proofs attributed to Renner.These statements support later bounds in the analysis.
- Min-entropy chain rules: For a state classical on Z, Hmin(AZ|B) ≥ Hmin(A|B).Adding the classical register Z to the conditioned system does not lower the stated lower bound.
- Min-entropy chain rules: The appendix notes that one lemma follows immediately by combining Lemmas B.1 and B.2.This establishes the result without a separate substantive argument.
B.2 Reduction step
The reduction step converts distinguishability of a multi-bit extractor output from uniform into distinguishability of one output bit given preceding bits. For Trevisan’s construction, the proof controls the auxiliary information using the weak-design structure.
- Reduction step: The reduction targets the extractor ExtC by showing that a distinguisher can guess one output bit when given extra classical information.This connects multi-bit distinguishability to a single-bit prediction task.
- Reduction step: If an m-bit output is distinguishable from uniform by more than ε, some bit is distinguishable from uniform given the preceding bits by more than ε.This is the quantum analogue of a result by Yao and follows from a hybrid argument.
- Reduction step: For Trevisan’s construction, the seed is split into V and W, while an auxiliary variable G summarizes prior output information.The construction ensures V ↔ W ↔ G forms a Markov chain.
- Reduction step: The auxiliary information G has size H0(G) ≤ rm, where r is a weak-design parameter.This bounds the extra information needed to reduce the distinguisher’s task.
- Reduction step: The proof describes each component g(w, x, j, ·) using at most 2|Sj∩Si| bits, linking the reduction to weak-design overlap bounds.The overlap structure controls how much prior output information must be represented.
C List-decodable codes are one-bit extractors
A list-decodable code yields a one-bit extractor: distinguishing the encoded bit from uniform implies that the source has low min-entropy. Trevisan’s and Raz et al.’s implicit argument is formalized through list decoding and guessing.
- Definitions: A (ε, L)-list-decodable code is one whose Hamming balls of relative radius 1/2 − ε contain at most L codewords.This bounded-list property underlies the extractor guarantee.
- Extractor guarantee: The code-based one-bit function is a (log L + log 1/2ε, 2ε)-strong extractor.This formalizes an implicit argument in Trevisan’s and Raz et al.’s work.
- Code constructions: For every n and δ > 0, there are efficiently evaluable (δ, 1/δ^2)-list-decodable codes with output length poly(n, 1/δ).The output length can also be assumed to be a power of 2.
- Code constructions: Standard list-decodable codes read all input bits to compute any single output bit, whereas local-code constructions address this access cost.The passage points to Lu’s construction for the local-code setting.
- Proof strategy: The proof first constructs a string close to C(X) on average, then uses list decoding to reconstruct X from a short candidate list.A successful distinguisher yields a nearby codeword description, and choosing uniformly among at most L candidates guesses X with probability at least 2ε/L.
- Extractor guarantee: If the encoded bit can be distinguished from uniform with probability at least 2ε, the source has min-entropy Hmin(X) < log L + log 1/2ε.The proof converts distinguishing advantage into a guessing strategy for X using the bounded list size.