From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking

Abstract

The existence of quantum uncertainty relations is the essential reason that some classically impossible cryptographic primitives become possible when quantum communication is allowed. One direct operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be "locked". Furthermore, knowing the key, it is possible to recover, that is "unlock", the message. In this paper, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of L2 into L1. We introduce the notion of metric uncertainty relations and connect it to low-distortion embeddings of L2 into L1. A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We apply this result to show the existence of locking schemes with key size independent of the message length. We give efficient constructions of metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. Moreover, we present a locking scheme that is close to being implementable with current technology. We apply our metric uncertainty relations to exhibit communication protocols that perform quantum equality testing.

60 pages, 5 figures. v4: published version

References in corpus (38)

• Mixed State Entanglement and Quantum Error Correction
• Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
• Quantum fingerprinting
• Unconditionally secure quantum bit commitment is impossible
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Tight Finite-Key Analysis for Quantum Cryptography
• Is Quantum Bit Commitment Really Possible?
• Monogamy of entanglement and other correlations
• Superadditivity of communication capacity using entangled inputs
• The Uncertainty Relation for Smooth Entropies
• Entropic uncertainty relations - A survey
• Aspects of generic entanglement
• Randomizing quantum states: Constructions and applications
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Locking classical correlation in quantum states
• Degrees of concealment and bindingness in quantum bit commitment protocols
• Superdense coding of quantum states
• Unconditional security from noisy quantum storage
• Locking of accessible information and implications for the security of quantum cryptography
• Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases
• Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1
• The decoupling approach to quantum information theory
• Locking entanglement measures with a single qubit
• Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment
• Hastings' additivity counterexample via Dvoretzky's theorem
• Security of quantum bit string commitment depends on the information measure
• How to reuse a one-time pad and other notes on authentication, encryption and protection of quantum information
• Locking classical information
• Cryptographic Distinguishability Measures for Quantum Mechanical States
• Non-additivity of Renyi entropy and Dvoretzky's Theorem
• Weak Decoupling Duality and Quantum Identification
• Quantum entropic security and approximate quantum encryption
• Almost-Euclidean subspaces of ${\ell }_1^N$ via tensor products: a simple approach to randomness reduction
• Cryptography in the Bounded-Quantum-Storage Model
• Quantum and Classical Message Identification via Quantum Channels
• Limits on entropic uncertainty relations for 3 and more MUBs
• A Tight High-Order Entropic Quantum Uncertainty Relation With Applications
• On the Key-Uncertainty of Quantum Ciphers and the Computational Security of One-way Quantum Transmission

Cited by in corpus (23)

• Advances in Quantum Cryptography
• Secure quantum key distribution with realistic devices
• Learning the Alpha-bits of Black Holes
• Fidelity of recovery, geometric squashed entanglement, and measurement recoverability
• A Quantum Enigma Machine: Experimentally Demonstrating Quantum Data Locking
• Quantum-locked key distribution at nearly the classical capacity rate
• Approximate Quantum Error Correction Revisited: Introducing the Alpha-bit
• Quantum enigma machines and the locking capacity of a quantum channel
• Certainty relations, mutual entanglement and non-displacable manifolds
• Robust quantum data locking from phase modulation
• Experimental quantum data locking
• Asymptotic entropic uncertainty relations
• Limitations on quantum dimensionality reduction
• Quantum cryptography beyond key distribution: theory and experiment
• Quantum data locking for high-rate private communication
• Random and free positive maps with applications to entanglement detection
• Continuous-variable quantum enigma machines for long-distance key distribution
• Photonic quantum data locking
• Weak locking capacity of quantum channels can be much larger than private capacity
• Locally restricted measurements on a multipartite quantum system: data hiding is generic
• Metric and classical fidelity uncertainty relations for random unitary matrices
• Fault tolerant quantum data locking
• Efficiently estimating average fidelity of a quantum logic gate using few classical random bits