Rishabh Batra

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.

One-way state generators (OWSG) [MY22a] are natural quantum analogs to classical one-way functions. We show that O(n/log(n))-copy OWSGs (n represents the input length) are equivalent to poly(n)-copy OWSGs and to quantum commitments. Since known results show that o(n/log(n))-copy OWSGs cannot imply commitments [CGG`23], this shows that O(n/log(n))-copy OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of Håstad, Impagliazzo, Levin and Luby [HILL99], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL99]. Since we do not argue conditioned on the output of the one-way function, our construction and analysis are arguably simpler and may be of independent interest.

“Non-Malleable Randomness Encoder” (NMRE) was introduced by Kanukurthi, Obbattu, and Sekar [KOS18] as a useful cryptographic primitive helpful in the construction of non- malleable codes. To the best of our knowledge, their construction is not known to be quantum secure. We provide a construction of a first rate-$1/2$, $2$-split, quantum secure NMRE and use this in a black-box manner, to construct for the first time the following: 1. rate $1/11$, $3$-split, quantum non-malleable code, 2. rate $1/3$, $3$-split, quantum secure non-malleable code, 3. rate $1/5$, $2$-split, quantum secure non-malleable code.

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.