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

Rahul Jain; Rishabh Batra; Sayantan Chakraborty; Upendra Kapshikar

arxiv: 2404.11283 · v4 · submitted 2024-04-17 · 🪐 quant-ph

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

Rishabh Batra , Sayantan Chakraborty , Rahul Jain , Upendra Kapshikar This is my paper

Pith reviewed 2026-05-24 02:08 UTC · model grok-4.3

classification 🪐 quant-ph

keywords device-independentoblivious transferbounded storage modelmagic square gameparallel repetitionquantum cryptographyNISQ implementationcomposable security

0 comments

The pith

A device-independent protocol for oblivious transfer achieves robustness to small device errors and security against joint quantum attacks in the bounded storage model.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a protocol for oblivious transfer between two parties that remains correct and secure when the quantum devices are untrusted and may deviate slightly from ideal behavior. It operates in the bounded storage model, where all quantum states decohere completely after a fixed real-world time interval called DELAY, so neither honest parties nor the adversary can retain long-term quantum memory. The protocol tolerates joint non-IID operations by an unbounded adversary who fully controls the devices, yet honest parties need only polylog time in the security parameter. Security and correctness errors are negligible, the protocol is sequentially composable, and it can therefore serve as a building block for larger tasks such as bit-commitment and multi-party computation. The central technical step is a parallel repetition theorem for a class of entangled games under hybrid quantum-classical strategies that correctly incorporates the DELAY decoherence.

Core claim

There exists a robust, composable device-independent protocol for oblivious transfer that uses Magic Square devices in the bounded storage model with a fixed DELAY decoherence time; the protocol has negligible correctness and security errors, runs in polylog time for honest parties, remains correct under small constant deviations from ideal device behavior, and is secure against joint non-IID quantum attacks by an unbounded adversary who controls the devices, thereby resolving the open question of whether any DI OT protocol can be both robust and secure against such attacks.

What carries the argument

Parallel repetition theorem for entangled games under hybrid (quantum-classical) strategies that incorporates the fixed DELAY decoherence time to reduce security to the bounded-storage assumption even under joint attacks.

If this is right

The protocol can be plugged directly into larger constructions while preserving device-independence, robustness, and security, yielding device-independent bit-commitment and device-independent secure multi-party computation.
The protocol remains correct and secure when the devices are manufactured with small constant imperfections, making it suitable for near-term NISQ hardware.
Honest parties require only polylog time in the security parameter and no long-term quantum memory, so the protocol is practical under realistic resource bounds.
Sequential composability guarantees that the security and correctness properties survive when the OT primitive is used as a subroutine inside bigger protocols.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same hybrid-strategy parallel repetition technique may extend to other two-party distrustful primitives that currently lack robust DI versions.
If the DELAY decoherence assumption can be realized experimentally with current hardware, the protocol supplies a concrete route to testing full device-independent two-party cryptography.
The bounded-storage-plus-decoherence model could be applied to additional cryptographic tasks that already possess DI protocols but lack robustness or composability.

Load-bearing premise

The parallel repetition theorem holds for the relevant class of entangled games with hybrid strategies and correctly folds in the fixed DELAY decoherence time so that the security reduction survives joint non-IID attacks.

What would settle it

An explicit counter-example showing that the parallel repetition theorem fails for hybrid strategies once the DELAY decoherence is included, or a concrete joint attack on the Magic Square devices that breaks the OT security despite the DELAY and the claimed robustness margin.

Figures

Figures reproduced from arXiv: 2404.11283 by Rahul Jain, Rishabh Batra, Sayantan Chakraborty, Upendra Kapshikar.

**Figure 1.** Figure 1: Protocol P for G1. Proof of Claim 14 Proof. Let C :“tii , . . . iru. Suppose there exists some protocol (with the restricted strategy) that wins in C with a probability greater than 2´δ2n , and conditioning on success in C, let the probability of winning the game in coordinate j be ω. In other words, consider the state φ XjYjRjEAEB where XjEA is given to Charlie, YjEB is given to Dave and Rj is shared betw… view at source ↗

read the original abstract

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({\lambda}) (where {\lambda} is the security parameter). Our protocol has negligible (in {\lambda}) 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The abstract claims a first robust composable DI OT protocol against joint attacks via a new parallel repetition theorem for hybrid strategies, but the theorem itself is not shown.

read the letter

The main point is that the authors present a DI OT protocol using Magic Square devices in the bounded storage model with a fixed DELAY for complete decoherence. Honest parties run in polylog time, the protocol tolerates small constant deviations from ideal devices, achieves negligible error, and is sequentially composable. They state this resolves the open question of getting both robustness and security against joint non-IID quantum attacks, which prior DI OT work did not achieve. The bounded storage plus DELAY setup is a concrete way to limit long-term quantum memory while allowing NISQ-era implementation. That construction and the explicit claim to close the gap are the concrete advances visible here. The parallel repetition theorem for entangled games with hybrid quantum-classical strategies is listed as the main technical tool to incorporate DELAY and bound the error under unbounded joint attacks. If that theorem is correct and the reduction works, the protocol would indeed be a useful primitive. The soft spot is exactly where the stress-test note points: the security reduction rests on this new theorem, yet the abstract gives no proof sketch, no error analysis, and no indication of how the hybrid strategy is formalized or how the fixed DELAY decoherence is folded into the winning-probability bound. Without those details it is not possible to check whether the negligible security claim actually follows for non-IID joint attacks. The rest of the protocol description looks standard for the area. This is for people working on device-independent two-party protocols who need a candidate OT primitive that is both robust and composable. A reader who wants to see whether the open question can be closed would get value from the construction, but would still have to verify the theorem. It deserves serious referee time because the claimed result is substantial enough that experts should check the central lemma rather than desk-reject on the abstract alone. I would send it out for review.

Referee Report

2 major / 1 minor

Summary. The paper presents a device-independent protocol for oblivious transfer between two parties using Magic Square devices in the bounded storage model, where devices and parties have no long-term quantum memory and quantum states decohere completely after a fixed DELAY interval. It claims negligible correctness and security errors (in the security parameter λ), robustness to small constant deviations from ideal device specifications, sequential composability, and security against joint non-IID quantum attacks by unbounded adversaries with no time or space bounds. The honest parties run in polylog(λ) time, making it NISQ-compatible. The main technical contribution is a new parallel repetition theorem for entangled games with hybrid (quantum-classical) strategies that incorporates the fixed DELAY to prove security.

Significance. If the parallel repetition theorem holds and the security reduction is valid, this would resolve a stated open question by providing the first robust and composable DI OT protocol secure against joint quantum attacks, enabling constructions for DI bit-commitment and secure multi-party computation. The bounded-storage model with explicit DELAY, polylog runtime, and explicit robustness to manufacturing imperfections are practical strengths not present in prior DI OT work.

major comments (2)

[Abstract] Abstract and §1: The central security claim rests on a new parallel repetition theorem for entangled games under hybrid (quantum-classical) strategies that incorporates the fixed DELAY decoherence time and yields negligible error under joint non-IID attacks, but the manuscript provides no proof sketch, lemma statement, or error analysis for this theorem, making the reduction unverifiable from the given text.
[Abstract] The robustness claim (correctness even when devices deviate by a small constant from ideal Magic Square specifications) is load-bearing for practical relevance, but no quantitative bound, section, or equation shows how this tolerance propagates through the parallel repetition or security reduction.

minor comments (1)

Notation for the security parameter λ and DELAY should be introduced with explicit definitions in the main body rather than only in the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recognizing the potential significance of the protocol and the parallel repetition theorem. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

Referee: [Abstract] Abstract and §1: The central security claim rests on a new parallel repetition theorem for entangled games under hybrid (quantum-classical) strategies that incorporates the fixed DELAY decoherence time and yields negligible error under joint non-IID attacks, but the manuscript provides no proof sketch, lemma statement, or error analysis for this theorem, making the reduction unverifiable from the given text.

Authors: We appreciate the referee highlighting the need for greater accessibility of the central technical result. The complete proof of the parallel repetition theorem for hybrid strategies, including the incorporation of the fixed DELAY and the analysis yielding negligible error under joint non-IID attacks, appears in Section 5. We agree, however, that a concise proof sketch, statement of the main lemma, and explicit error analysis in the abstract and §1 would improve verifiability without altering the result. We will insert this overview in the revised manuscript. revision: yes
Referee: [Abstract] The robustness claim (correctness even when devices deviate by a small constant from ideal Magic Square specifications) is load-bearing for practical relevance, but no quantitative bound, section, or equation shows how this tolerance propagates through the parallel repetition or security reduction.

Authors: We thank the referee for this observation on the robustness analysis. The tolerance to small constant deviations from ideal Magic Square behavior, together with the quantitative bound on how the deviation error propagates through parallel repetition, is derived in Section 3.2 and used in the security reduction of Section 6. We agree that an explicit reference to this bound and the relevant equation should appear already in the abstract and §1. We will add the necessary cross-reference and a brief statement of the bound in the revision. revision: yes

Circularity Check

0 steps flagged

No circularity: new parallel-repetition theorem presented as independent technical contribution

full rationale

The paper's security argument rests on a newly proved parallel repetition theorem for entangled games under hybrid (quantum-classical) strategies that incorporate the fixed DELAY decoherence time. This theorem is explicitly identified as a main technical contribution and is not shown to be derived from the OT functionality, from fitted parameters, or from prior self-citations whose content reduces to the target result. No equations or reductions in the provided text equate the security bound to its own inputs by construction, nor does the argument invoke a uniqueness theorem or ansatz smuggled via self-citation. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The protocol rests on the bounded-storage model with a fixed real-world DELAY after which states decohere completely, the existence of Magic Square devices (even when slightly off-spec), and the validity of a new parallel-repetition theorem for hybrid strategies. No free parameters are explicitly fitted in the abstract; the security parameter λ appears only in runtime and error bounds.

axioms (2)

domain assumption Quantum states decohere completely after a fixed constant real-world time interval DELAY.
Invoked to define the bounded-storage model and to incorporate decoherence into the hybrid strategy of the parallel-repetition theorem.
domain assumption Magic Square devices exist and remain functional (within small constant deviation) under the bounded-storage constraint.
Central to the device-independent setting; the protocol is claimed to be robust to small manufacturing errors.

pith-pipeline@v0.9.0 · 5876 in / 1473 out tokens · 26992 ms · 2026-05-24T02:08:20.119761+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our protocol has negligible (in λ) correctness and security errors and can be implemented in the NISQ era.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 1 internal anchor

[1]

Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions

Anne Broadbent and Peter Yuen. Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions. New Journal of Physics , 25, 05 2023

work page 2023
[2]

Damg rd, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner

Ivan B. Damg rd, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner. A tight high-order entropic quantum uncertainty relation with applications. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007 , pages 360--378, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

work page 2007
[3]

Damg A rd, Serge Fehr, Louis Salvail, and Christian Schaffner

Ivan B. Damg A rd, Serge Fehr, Louis Salvail, and Christian Schaffner. Cryptography in the bounded-quantum-storage model. SIAM Journal on Computing , 37(6):1865--1890, 2008

work page 2008
[4]

Fuzzy extractors: How to generate strong keys from biometrics and other noisy data

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing , 38(1):97--139, 2008

work page 2008
[5]

Trevisan's extractor in the presence of quantum side information

Anindya De, Christopher Portmann, Thomas Vidick, and Renato Renner. Trevisan's extractor in the presence of quantum side information. SIAM Journal on Computing , 41(4):915--940, 2012

work page 2012
[6]

Essential coding theory

Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book , 2(1), 2012

work page 2012
[7]

Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A device-independent protocol for XOR oblivious transfer. Quantum , 6:725, May 2022

work page 2022
[8]

Srijita Kundu and Ernest Y.-Z. Tan. Composably secure device-independent encryption with certified deletion. Quantum , 7:1047, July 2023

work page 2023
[9]

Device-independent two-party cryptography secure against sequential attacks

Jedrzej Kaniewski and Stephanie Wehner. Device-independent two-party cryptography secure against sequential attacks. New Journal of Physics , 18(5):055004, 2016

work page 2016
[10]

Unconditional security from noisy quantum storage

Robert Konig, Stephanie Wehner, and Jürg Wullschleger. Unconditional security from noisy quantum storage. IEEE Transactions on Information Theory , 58(3):1962--1984, 2012

work page 1962
[11]

Three-Source Extractors for Polylogarithmic Min-Entropy

Xin Li. Three-source extractors for polylogarithmic min-entropy. CoRR , abs/1503.02286, 2015

work page internal anchor Pith review Pith/arXiv arXiv 2015
[12]

Composability in quantum cryptography

Jörn Müller-Quade and Renato Renner. Composability in quantum cryptography. New Journal of Physics , 11(8):085006, aug 2009

work page 2009
[13]

Code-based cryptography , pages 95--145

Raphael Overbeck and Nicolas Sendrier. Code-based cryptography , pages 95--145. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009

work page 2009
[14]

On lattices, learning with errors, random linear codes, and cryptography

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , STOC '05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery

work page 2005
[15]

Simulatable security for quantum protocols, 2004

Dominique Unruh. Simulatable security for quantum protocols, 2004

work page 2004
[16]

Universally composable quantum multi-party computation

Dominique Unruh. Universally composable quantum multi-party computation. In Henri Gilbert, editor, Advances in Cryptology -- EUROCRYPT 2010 , pages 486--505, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

work page 2010
[17]

Concurrent composition in the bounded quantum storage model

Dominique Unruh. Concurrent composition in the bounded quantum storage model. In Kenneth G. Paterson, editor, Advances in Cryptology -- EUROCRYPT 2011 , pages 467--486, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

work page 2011
[18]

Composable security in the bounded-quantum-storage model

Stephanie Wehner and J \"u rg Wullschleger. Composable security in the bounded-quantum-storage model. In Luca Aceto, Ivan Damg rd, Leslie Ann Goldberg, Magn \'u s M. Halld \'o rsson, Anna Ing \'o lfsd \'o ttir, and Igor Walukiewicz, editors, Automata, Languages and Programming , pages 604--615, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg

work page 2008

[1] [1]

Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions

Anne Broadbent and Peter Yuen. Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions. New Journal of Physics , 25, 05 2023

work page 2023

[2] [2]

Damg rd, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner

Ivan B. Damg rd, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner. A tight high-order entropic quantum uncertainty relation with applications. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007 , pages 360--378, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

work page 2007

[3] [3]

Damg A rd, Serge Fehr, Louis Salvail, and Christian Schaffner

Ivan B. Damg A rd, Serge Fehr, Louis Salvail, and Christian Schaffner. Cryptography in the bounded-quantum-storage model. SIAM Journal on Computing , 37(6):1865--1890, 2008

work page 2008

[4] [4]

Fuzzy extractors: How to generate strong keys from biometrics and other noisy data

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing , 38(1):97--139, 2008

work page 2008

[5] [5]

Trevisan's extractor in the presence of quantum side information

Anindya De, Christopher Portmann, Thomas Vidick, and Renato Renner. Trevisan's extractor in the presence of quantum side information. SIAM Journal on Computing , 41(4):915--940, 2012

work page 2012

[6] [6]

Essential coding theory

Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory. Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book , 2(1), 2012

work page 2012

[7] [7]

Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A device-independent protocol for XOR oblivious transfer. Quantum , 6:725, May 2022

work page 2022

[8] [8]

Srijita Kundu and Ernest Y.-Z. Tan. Composably secure device-independent encryption with certified deletion. Quantum , 7:1047, July 2023

work page 2023

[9] [9]

Device-independent two-party cryptography secure against sequential attacks

Jedrzej Kaniewski and Stephanie Wehner. Device-independent two-party cryptography secure against sequential attacks. New Journal of Physics , 18(5):055004, 2016

work page 2016

[10] [10]

Unconditional security from noisy quantum storage

Robert Konig, Stephanie Wehner, and Jürg Wullschleger. Unconditional security from noisy quantum storage. IEEE Transactions on Information Theory , 58(3):1962--1984, 2012

work page 1962

[11] [11]

Three-Source Extractors for Polylogarithmic Min-Entropy

Xin Li. Three-source extractors for polylogarithmic min-entropy. CoRR , abs/1503.02286, 2015

work page internal anchor Pith review Pith/arXiv arXiv 2015

[12] [12]

Composability in quantum cryptography

Jörn Müller-Quade and Renato Renner. Composability in quantum cryptography. New Journal of Physics , 11(8):085006, aug 2009

work page 2009

[13] [13]

Code-based cryptography , pages 95--145

Raphael Overbeck and Nicolas Sendrier. Code-based cryptography , pages 95--145. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009

work page 2009

[14] [14]

On lattices, learning with errors, random linear codes, and cryptography

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , STOC '05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery

work page 2005

[15] [15]

Simulatable security for quantum protocols, 2004

Dominique Unruh. Simulatable security for quantum protocols, 2004

work page 2004

[16] [16]

Universally composable quantum multi-party computation

Dominique Unruh. Universally composable quantum multi-party computation. In Henri Gilbert, editor, Advances in Cryptology -- EUROCRYPT 2010 , pages 486--505, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

work page 2010

[17] [17]

Concurrent composition in the bounded quantum storage model

Dominique Unruh. Concurrent composition in the bounded quantum storage model. In Kenneth G. Paterson, editor, Advances in Cryptology -- EUROCRYPT 2011 , pages 467--486, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

work page 2011

[18] [18]

Composable security in the bounded-quantum-storage model

Stephanie Wehner and J \"u rg Wullschleger. Composable security in the bounded-quantum-storage model. In Luca Aceto, Ivan Damg rd, Leslie Ann Goldberg, Magn \'u s M. Halld \'o rsson, Anna Ing \'o lfsd \'o ttir, and Igor Walukiewicz, editors, Automata, Languages and Programming , pages 604--615, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg

work page 2008