arXiv:2011.12704 · Quantum

Composably secure device-independent encryption with certified deletion

Srijita Kundu, Ernest Y.-Z. Tan

Published Jul 6, 2023• 8 citations

Abstract

We study the task of encryption with certified deletion (ECD) introduced by Broadbent and Islam (2020), but in a device-independent setting: we show that it is possible to achieve this task even when the honest parties do not trust their quantum devices. Moreover, we define security for the ECD task in a composable manner and show that our ECD protocol satisfies conditions that lead to composable security. Our protocol is based on device-independent quantum key distribution (DIQKD), and in particular the parallel DIQKD protocol based on the magic square non-local game, given by Jain, Miller and Shi (2020). To achieve certified deletion, we use a property of the magic square game observed by Fu and Miller (2018), namely that a two-round variant of the game can be used to certify deletion of a single random bit. In order to achieve certified deletion security for arbitrarily long messages from this property, we prove a parallel repetition theorem for two-round non-local games, which may be of independent interest.

DOI: 10.22331/q-2023-07-06-1047

Related papers

A robust and composable device-independent protocol for oblivious transfer using (fully) untrusted quantum devices in the bounded storage model

Rishabh Batra, Chakraborty, Sayantan, Rahul Jain +1 more

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.

arXiv:2404.11283Apr 17, 20241 citation

Robust and leakage-resilient device-independent oblivious transfer in MiniQCrypt

Zhili Chen, Rahul Jain, YaoNan Zhang

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.

quant-pharXiv:2610.01421Oct 2, 20260 citations

Parallel DIQKD from parallel repetition

Thomas Vidick

We give an arguably simpler and more direct proof of a recent result by Miller, Jain and Shi, who proved device-independent security of a protocol for quantum key distribution in which the devices can be used in parallel. Our proof combines existing results on immunization (Kempe et al., SICOMP 2011) and parallel repetition (Bavarian et al., STOC 2017) of entangled games.

arXiv:1703.08508Mar 24, 201710 citations

Device-independent uncloneable encryption

Srijita Kundu, Ernest Y.-Z. Tan

Uncloneable encryption, first introduced by Broadbent and Lord (TQC 2020) is a quantum encryption scheme in which a quantum ciphertext cannot be distributed between two non-communicating parties such that, given access to the decryption key, both parties cannot learn the underlying plaintext. In this work, we introduce a variant of uncloneable encryption in which several possible decryption keys can decrypt a particular encryption, and the security requirement is that two parties who receive independently generated decryption keys cannot both learn the underlying ciphertext. We show that this variant of uncloneable encryption can be achieved device-independently, i.e., without trusting the quantum states and measurements used in the scheme, and that this variant works just as well as the original definition in constructing quantum money. Moreover, we show that a simple modification of our scheme yields a single-decryptor encryption scheme, which was a related notion introduced by Georgiou and Zhandry. In particular, the resulting single-decryptor encryption scheme achieves device-independent security with respect to a standard definition of security against random plaintexts. Finally, we derive an ``extractor'' result for a two-adversary scenario, which in particular yields a single-decryptor encryption scheme for single bit-messages that achieves perfect anti-piracy security without needing the quantum random oracle model.

arXiv:2210.01058QuantumJan 8, 20256 citations

Device-Independent Quantum Key Distribution Based on the Mermin-Peres Magic Square Game

Yi-Zheng Zhen, Yingqiu Mao, Yuzhe Zhang +2 more

Device-independent quantum key distribution (DIQKD) is information-theoretically secure against adversaries who possess a scalable quantum computer and who have supplied malicious key-establishment systems; however, the DIQKD key rate is currently too low. Consequently, we devise a DIQKD scheme based on the quantum nonlocal Mermin-Peres magic square game: our scheme asymptotically delivers DIQKD against collective attacks, even with noise. Our scheme outperforms DIQKD using the Clauser-Horne-Shimony-Holt game with respect to the number of game rounds, albeit not number of entangled pairs, provided that both state visibility and detection efficiency are high enough.

arXiv:2308.14037Physical Review LettersAug 25, 202321 citations

Security proof for parallel DIQKD

Marwah, Ashutosh, Frédéric Dupuis

We present a parallel device independent quantum key distribution (DIQKD) protocol based on the CHSH game and prove its security. Using techniques developed for analysing the parallel repetition of anchored non-local games, we show that the answers on a small random linear subset of the games in the DIQKD protocol can be simulated as the output of a single-round strategy for playing the CHSH game. Then, we use the recently developed unstructured approximate entropy accumulation theorem to establish the smooth min-entropy lower bound required for the security proof. Our approach yields a more information-theoretic and general proof for parallel DIQKD compared to previous proofs.

arXiv:2507.03991Jul 5, 20250 citations