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

Access Restriction
Subscribed

 Author Fawzi, Omar ♦ Hayden, Patrick ♦ Sen, Pranab Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Low-distortion norm embedding ♦ Quantum cryptography ♦ Quantum information theory ♦ Quantum uncertainty relation ♦ Randomness extractor Abstract The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking [DiVincenzo et al. 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random $\textit{n}-bit$ message is encoded in a quantum system using a classical key of size much smaller than $\textit{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 article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the $ℓ_{1}$ norm. We introduce the notion of a metric uncertainty relation and connect it to low-distortion embeddings of $ℓ_{2}$ into $ℓ_{1}.$ 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 then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give $\textit{efficient}$ constructions of bases satisfying 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. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of Guruswami et al. [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of $\textit{n}-qubit$ states. We prove that this task can be performed by a single message protocol using $O(log^{2}$ $\textit{n})$ qubits and $\textit{n}$ bits of communication, where the computation of the sender is efficient. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 6 Page Count 61 Starting Page 1 Ending Page 61

#### Open content in new tab

Source: ACM Digital Library