Upendra Kapshikar

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 negligible (in λ) correctness and security errors 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 robust and secure against joint quantum attacks. This was a major open question in device-independent two-party distrustful cryptography, which we resolve. We prove a parallel repetition theorem for a certain class of entangled games with a hybrid (quantum-classical) strategy to show 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 rep- etition of classical games [Raz95, Hol07], quantum games [JPY14, JMS20, JK22], 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 state (without further justification) that we can extend our results, along the lines of [JK22] and [DFR`07], to incorporate linear (in the number of devices) long term quantum memory and linear leakage between the devices.

We present robust and composable device-independent quantum protocols for oblivious transfer (OT) and bit commitment (BC) using Magic Square devices. We assume there is no long-term quantum memory, that is, after a finite time interval, referred to as extbf DELAY, the states stored in the devices decohere. By robustness, which is a highlight of our protocols, we mean that the protocols are correct and secure even when devices are slightly off from their ideal specifications (the \emph{faulty but non-malicious} regime). This is an important property, since in the real world, devices would certainly have small manufacturing errors and cannot be expected to be ideal. To the best of our understanding and knowledge, none of the known DI protocols for OT and BC in the literature are robust; they can not guarantee correctness in the faulty but non-malicious regime. Our protocols are sequentially composable and hence, can be used as building blocks to construct larger protocols, while still preserving security guarantees.

We consider (Enc, Dec) schemes which are used to encode a classical/quantum message m and derive an n-qubit quantum codeword ψ_m. The quantum codeword ψ_m can adversarially tamper via a unitary U∈F_u from some known tampering unitary family F_u, resulting in Uψ_mU†. Firstly, we initiate the general study of quantum tamper detection codes, which must detect that tampering occurred with high probability. In case there was no tampering, we would like to output the message m with a probability of 1. We show that quantum tamper detection codes exist for both classical messages and quantum messages for any family F_u of unitary operators, such that |F_u|<2^{2^{αn}} for some known constant α∈(0,1) and all the unitary operators satisfy one additional condition : Far from Identity : For each U∈F_u, we require that its modulus of trace value isn't too much i.e. $ |Trace(U)| \leq \phi N$, where N=2^n. Quantum tamper-detection codes are quantum generalizations of classical tamper detection codes studied by Jafargholi et al. Additionally for classical message m, if we must either output message m or detect that tampering occurred and output ⊥ with high probability, we show that it is possible without the restriction of Far from Identity condition for any family of unitary operators F_u, such that |F_u|<2^{2^αn}. We also provide efficient (Enc, Dec) schemes when the family of tampering unitary operators are from Pauli group Pn, which can be thought of as a quantum version of the algebraic manipulation detection (AMD) codes of Cramer et al.