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 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.

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 show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying \textbf{scalability}, which means the security parameter can be much larger than the number of qubits, \textbf{quantum accessibility}, which means the adversary can provide quantum input, and \textbf{adaptivity}, which means the adversary can query it adaptively. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility, such that the adversary can be ancilla-assisted, i.e., the input state may not be pure and entangled with other quantum registers. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS [AQY21, AGQY22]. This new construction may be helpful in some simplification of the microcrypt zoo.

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.