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 (14)

• Tight Finite-Key Analysis for Quantum Cryptography
• The Uncertainty Relation for Smooth Entropies
• Aspects of generic entanglement
• Randomizing quantum states: Constructions and applications
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Superdense coding of quantum states
• Entropic uncertainty relations and locking: tight bounds for mutually unbiased bases
• The decoupling approach to quantum information theory
• Hastings' additivity counterexample via Dvoretzky's theorem
• Security of quantum bit string commitment depends on the information measure
• Locking classical information
• Cryptography in the Bounded-Quantum-Storage Model
• On the Key-Uncertainty of Quantum Ciphers and the Computational Security of One-way Quantum Transmission
• A Tight High-Order Entropic Quantum Uncertainty Relation With Applications

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