Trevisan's extractor in the presence of quantum side information
arXiv:0912.5514 · doi:10.1137/100813683
Abstract
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.
20+10 pages; v2: extract more min-entropy, use weakly random seed; v3: extended introduction, matches published version with sections somewhat reordered
References in corpus (4)
Cited by in corpus (70)
- Secure quantum key distribution with realistic devices
- Random Numbers Certified by Bell's Theorem
- Quantum Random Number Generators
- Tight Finite-Key Analysis for Quantum Cryptography
- Fully device independent quantum key distribution
- Detection-Loophole-Free Test of Quantum Nonlocality, and Applications
- Quantum random number generation
- Security in Quantum Cryptography
- Free randomness can be amplified
- Leftover Hashing Against Quantum Side Information
- Postprocessing for quantum random number generators: entropy evaluation and randomness extraction
- Quantum Randomness Certified by the Uncertainty Principle
- Security of practical private randomness generation
- Source-device-independent Ultra-fast Quantum Random Number Generation
- Advances in device-independent quantum key distribution
- Simple and tight device-independent security proofs
- Maximization of Extractable Randomness in a Quantum Random-Number Generator
- Device-independent Randomness Expansion with Entangled Photons
- Security and Composability of Randomness Expansion from Bell Inequalities
- More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function
- Entropy accumulation with improved second-order term
- Experimental Realization of Device-Independent Quantum Randomness Expansion
- Experimental Low-Latency Device-Independent Quantum Randomness
- Security of quantum key distribution from generalised entropy accumulation
- Robustness of quantum randomness expansion protocols in the presence of noise
- Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
- Real-time inteferometric quantum random number generation on chip
- Device-independent randomness generation from several Bell estimators
- Quantum to Classical Randomness Extractors
- True randomness from realistic quantum devices
- Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction
- Randomness in post-selected events
- Certifiable Quantum Dice - Or, testable exponential randomness expansion
- A modular framework for randomness extraction based on Trevisan's construction
- Leftover hashing from quantum error correction: Unifying the two approaches to the security proof of quantum key distribution
- Physical Security in the Post-quantum Era: A Survey on Side-channel Analysis, Random Number Generators, and Physically Unclonable Functions
- Experimental quantum key distribution certified by Bell's theorem
- Completely Device Independent Quantum Key Distribution
- Quantum Side Information: Uncertainty Relations, Extractors, Channel Simulations
- Infinite Randomness Expansion and Amplification with a Constant Number of Devices
- Practical randomness amplification and privatisation with implementations on quantum computers
- Device and semi-device independent random numbers based on non-inequality paradox
- Quantum-proof randomness extractors via operator space theory
- Efficient methods for one-shot quantum communication
- The future of secure communications: device independence in quantum key distribution
- The Physics of Quantum Information: Complementarity, Uncertainty, and Entanglement
- Quantum key distribution with entangled photons generated on-demand by a quantum dot
- Variations on Classical and Quantum Extractors
- Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints
- Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
- Cryptomite: A versatile and user-friendly library of randomness extractors
- Computational Notions of Quantum Min-Entropy
- Device-independent uncloneable encryption
- Generation of quantum-certified random numbers using on-chip path-entangled single photons from an LED
- Two-Source Extractors Secure Against Quantum Adversaries
- Faster Spectral Sparsification in Dynamic Streams
- Secure Composition of Quantum Key Distribution and Symmetric Key Encryption
- Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices
- Quantum secure non-malleable codes in the split-state model
- Privacy Amplification Against Active Quantum Adversaries
- (Quantum) Min-Entropy Resources
- "Nonlocality-of-a-single-photon" based Quantum Key Distribution and Random Number Generation schemes and their device-independent security analysis
- Entropy Accumulation under Post-Quantum Cryptographic Assumptions
- Quantum secure non-malleable-extractors
- Bounding the seed length of Miller and Shi's unbounded randomness expansion protocol
- Better short-seed quantum-proof extractors
- Graphical Methods in Device-Independent Quantum Cryptography
- Quantum-Proof Extractors: Optimal up to Constant Factors
- Nearly-Linear Time Seeded Extractors with Short Seeds
- Security proofs for practical QKD: variations, techniques, gaps, and limitations