Abstract We present a device-independent protocol for oblivious transfer (DIOT) and analyse its security under the assumption that the receiver’s quantum storage is bounded during protocol execution and that the device behaves independently and identically in each round. We additionally require that, for each device component, the input corresponding to the choice of measurement basis, and the resulting output, is communicated only with the party holding that component. Our protocol is everlastingly secure and, compared to previous DIOT protocols, it is less strict about the non-communication assumptions that are typical from protocols that use Bell inequality violations; instead, the device-independence comes from a protocol for self-testing of a single (quantum) device which makes use of a post-quantum computational assumption.
Abstract We present a device-independent protocol for oblivious transfer (DIOT) and analyse its security under the assumption that the receiver’s quantum storage is bounded during protocol execution and that the device behaves independently and identically in each round. We additionally require that, for each device component, the input corresponding to the choice of measurement basis, and the resulting output, is communicated only with the party holding that component. Our protocol is everlastingly secure and, compared to previous DIOT protocols, it is less strict about the non-communication assumptions that are typical from protocols that use Bell inequality violations; instead, the device-independence comes from a protocol for self-testing of a single (quantum) device which makes use of a post-quantum computational assumption.
Assuming post-quantum one-way functions, we construct device-independent (DI) oblivious transfer (OT) and bit commitment: honest parties use only trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and behave non-IID. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. One protocol skeleton serves both, in two regimes. With isolated laboratories and coordinate-local measurements in the honest receiver's device, it tolerates a constant rate of honest-device faults. With polylogarithmically many qubits of adaptive leakage between the laboratories and arbitrary joint measurements, it tolerates an inverse-polylogarithmic rate. Each elementary DI call uses a fresh, isolated batch of polylogarithmically many device coordinates, and total device use in the compiled OT protocol is polynomial. The commitment has efficient simulators against both parties and yields DI coin tossing with abort.
Because OT is complete for secure computation, the construction yields a DI protocol, with abort, for every efficiently computable classical functionality on a fixed number of parties, secure against static corruption of any proper subset of them.
The commitment's extractor changes a public parity relation through classical equivocation and leaves the device execution, hence its leakage, unchanged. A commit-and-prove functionality, disjoint audits, and an affine consistency check link the certified correlations to ideal OT. Sender security rests on a selector-aware parallel-repetition bound for the Magic Square game, which we derive from the two-round threshold theorem of Kundu and Tan.
Among the most studied tasks in Quantum Cryptography one can find Bit Commitment (BC) and Oblivious Transfer (OT), two central cryptographic primitives. In this paper we propose for the first time protocols for these tasks in the measurement-device independent (MDI) settings and analyze their security. We analyze two different cases: first we assume the parties have access to perfect single photon sources (but still in the presence of noise and losses), and second we assume that they only have imperfect single photon sources. In the first case we propose a protocol for both BC and OT and prove their security in the Noisy Quantum Storage model. Interestingly, in the case where honest parties do not have access to perfect single photon sources, we find that BC is still possible, but that it is "more difficult" to get a secure protocol for OT: We show that there is a whole class of protocols that cannot be secure. All our security analyses are done in the finite round regime.
Abstract In device-independent quantum key distribution (DIQKD), an adversary prepares a device consisting of two components, distributed to Alice and Bob, who use the device to generate a secure key. The security of existing DIQKD schemes holds under the assumption that the two components of the device cannot communicate with one another during the protocol execution. This is called the no-communication assumption in DIQKD. Here, we show how to replace this assumption, which can be hard to enforce in practice, by a standard computational assumption from post-quantum cryptography: we give a protocol that produces secure keys even when the components of an adversarial device can exchange arbitrary quantum communication, assuming the device is computationally bounded. Importantly, the computational assumption only needs to hold during the protocol execution—the keys generated at the end of the protocol are information-theoretically secure as in standard DIQKD protocols.
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 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.
Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.
Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system's state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device's state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.