Cryptography

Abstract: Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on even most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, and typically lead to non-trivial lower bounds. Concretely, we give lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\SWAP}$, the XX interaction, Haar random two qubit gates, and many others, none of which previously had known lower bounds. For the CNOT gate one of our techniques gives a tight lower bound, fully resolving its entanglement cost. Our proof technique makes use of two new properties of unitaries that we introduce, called the \emph{controllable correlation} and \emph{controllable entanglement}. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting. The lower bound from controllable correlation has an elementary proof and applies to most unitaries, but does not appear to be tight for any of the unitaries we study. The lower bound from controllable entanglement is tight for CNOT but fails for generic unitaries. Its proof is less elementary; it requires the consideration of the i.i.d. setting and application of Shannon theory results, with the characterization of finite block length Schumacher compression being a key tool.

Abstract: We present a robust and composable device-independent (DI) quantum protocol between two parties for oblivious transfer (OT) using Magic Square devices in the bounded storage model [DFR`07, DFSS08] in which the (honest and cheating) devices and parties have no long-term quantum memory. After a fixed constant (real-world) time interval, referred to as DELAY, the quantum states decohere completely. The adversary (cheating party), with full control over the devices, is allowed joint (non-IID) quantum operations on the devices, and there are no time and space complexity bounds placed on its powers. The running time of the honest parties is polylog(λ) (where λ is the security parameter). Our protocol has a negligible (in λ) security error and can be implemented in the NISQ (Noisy Intermediate Scale Quantum) era. By robustness, we mean that our protocol is correct even when devices are slightly off (by a small constant) from their ideal specification. This is an important property since small manufacturing errors in the real-world devices are inevitable. Our protocol is sequentially composable and, hence, can be used as a building block to construct larger protocols (including DI bit-commitment and DI secure multi-party computation) while still preserving correctness and security guarantees. None of the known DI protocols for OT in the literature are secure against arbitrary (non-IID) devices and provide simulator-based (composable) security. This was a major open question in device-independent two-party distrustful cryptography, which we resolved. We prove a parallel repetition theorem for a certain class of entangled games with a hybrid (quantum-classical) strategy. This parallel repetition allows us to show min-entropy guarantees on certain random variables, which helps in proving the security of our protocol. The hybrid strategy helps to incorporate DELAY in our protocol. This parallel repetition theorem is a main technical contribution of our work. Since our games use hybrid strategies and the inputs to our games are not independent, we use a novel combination of ideas from previous works showing parallel repetition of classical games [Raz95, Hol07], quantum games [JPY14, JMS20, JK25], and anchored games [BVY17, JK21]. Although we present security proof for protocols in the bounded storage model with no long-term quantum memory (after DELAY), we can extend our results, along the lines of [DFR`07], to incorporate linear (in the number of devices) long-term quantum memory.