The Bounded Storage Model in The Presence of a Quantum Adversary

Abstract

An extractor is a function E that is used to extract randomness. Given an imperfect random source X and a uniform seed Y, the output E(X,Y) is close to uniform. We study properties of such functions in the presence of prior quantum information about X, with a particular focus on cryptographic applications. We prove that certain extractors are suitable for key expansion in the bounded storage model where the adversary has a limited amount of quantum memory. For extractors with one-bit output we show that the extracted bit is essentially equally secure as in the case where the adversary has classical resources. We prove the security of certain constructions that output multiple bits in the bounded storage model.

13 pages Latex, v3: discussion of independent randomizers added

References in corpus (7)

• Reversing quantum dynamics with near-optimal quantum and classical fidelity
• Locking classical correlation in quantum states
• Locking of accessible information and implications for the security of quantum cryptography
• A de Finetti representation for finite symmetric quantum states
• A Generic Security Proof for Quantum Key Distribution
• On the Power of Quantum Memory
• Simulatable security for quantum protocols

Cited by in corpus (35)

• The Security of Practical Quantum Key Distribution
• Quantum Random Number Generators
• Fully device independent quantum key distribution
• Security in Quantum Cryptography
• Security of practical private randomness generation
• Unconditional security from noisy quantum storage
• Advances in device-independent quantum key distribution
• Trevisan's extractor in the presence of quantum side information
• Sampling of min-entropy relative to quantum knowledge
• Device-independent quantum key distribution secure against adversaries with no long-term quantum memory
• Dual universality of hash functions and its applications to quantum cryptography
• Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
• Certifying Quantum Randomness by Probability Estimation
• 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
• Quantum Randomness Generation by Probability Estimation with Classical Side Information
• Quantum Side Information: Uncertainty Relations, Extractors, Channel Simulations
• Infinite Randomness Expansion and Amplification with a Constant Number of Devices
• Quantum-proof randomness extractors via operator space theory
• Building one-time memories from isolated qubits
• Reductions to IID in Device-independent Quantum Information Processing
• Single-shot security for one-time memories in the isolated qubits model
• Variations on Classical and Quantum Extractors
• Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
• Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes
• Computational Notions of Quantum Min-Entropy
• Two-Source Extractors Secure Against Quantum Adversaries
• On relating one-way classical and quantum communication complexities
• Privacy Amplification Against Active Quantum Adversaries
• Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker
• Quantum hashing is maximally secure against classical leakage
• Quantum-Proof Extractors: Optimal up to Constant Factors
• Better short-seed quantum-proof extractors
• New bounds on classical and quantum one-way communication complexity