Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming

Akshay Bansal; Jamie Sikora

doi:10.22331/q-2025-01-20-1602

Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming

Akshay Bansal and Jamie Sikora

Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, USA

Published:	2025-01-20, volume 9, page 1602
Eprint:	arXiv:2304.13200v2
Doi:	https://doi.org/10.22331/q-2025-01-20-1602
Citation:	Quantum 9, 1602 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

In the last two decades, there has been much effort in finding secure protocols for two-party cryptographic tasks. It has since been discovered that even with quantum mechanics, many such protocols are limited in their security promises. In this work, we use stochastic selection, an idea from stochastic programming, to circumvent such limitations. For example, we find a way to switch between bit commitment, weak coin flipping, and oblivious transfer protocols to improve their security. We also use stochastic selection to turn trash into treasure yielding the first quantum protocol for Rabin oblivious transfer.

Featured image: Let $S_j$ denote the set of optimal cheating strategies for Alice in $Task_j$. If Bob is allowed to switch between the two sub-tasks (e.g., $Task_1$ and $Task_2$), then if the two sets are disjoint, Alice would have to hedge her cheating attempts.
On the other hand, if the two sets have a nonempty intersection, Alice would have no difficulty cheating if Bob switches between those two sub-tasks (e.g., $Task_3$ and $Task_4$).

Popular summary

Over the last several years, there has been significant progress in understanding the limits of information-theoretic security for various two-party cryptographic primitives such as coin flipping, bit commitment, and oblivious transfer. In this work, we introduce a novel framework called stochastic switching, conceptualized along the lines of stochastic programming. We utilize this framework to devise protocols for tasks that allow switching between two or more primitives, and analyze their security using techniques based on stochastic semidefinite programming. We subsequently extend this idea to study another primitive known as Rabin oblivious transfer, where we stochastically combine two or more insecure protocols to reveal the first quantum protocol with non-trivial security.

► BibTeX data

@article{Bansal2025breakingbarriersin,
  doi = {10.22331/q-2025-01-20-1602},
  url = {https://doi.org/10.22331/q-2025-01-20-1602},
  title = {Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming},
  author = {Bansal, Akshay and Sikora, Jamie},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1602},
  month = jan,
  year = {2025}
}

► References

[1] Stephen Wiesner. ``Conjugate coding''. ACM Sigact News 15, 78–88 (1983).
https://doi.org/10.1145/1008908.1008920

[2] Michael O. Rabin. ``How to exchange secrets with oblivious transfer''. Cryptology ePrint Archive, Paper 2005/187 (2005). https://eprint.iacr.org/2005/187.
https://eprint.iacr.org/2005/187

[3] Claude Crépeau. ``Quantum oblivious transfer''. Journal of Modern Optics 41, 2445–2454 (1994).
https://doi.org/10.1080/09500349414552291

[4] Sarah A. Osborn and Jamie Sikora. ``A Constant Lower Bound for Any Quantum Protocol for Secure Function Evaluation''. In François Le Gall and Tomoyuki Morimae, editors, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Volume 232 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14. Dagstuhl, Germany (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2022.8

[5] Schaffner Christian. ``Cryptography in the bounded-quantum-storage model'' (2007). arXiv:0709.0289.
arXiv:0709.0289

[6] André Chailloux, Iordanis Kerenidis, and Jamie Sikora. ``Lower bounds for quantum oblivious transfer''. Quantum Information & Computation 13, 158–177 (2013).
https://doi.org/10.26421/QIC13.1-2-9

[7] Harry Buhrman, Matthias Christandl, and Christian Schaffner. ``Complete insecurity of quantum protocols for classical two-party computation''. Physical Review Letters 109, 160501 (2012).
https://doi.org/10.1103/PhysRevLett.109.160501

[8] Ryan Amiri, Robert Stárek, David Reichmuth, Ittoop V Puthoor, Michal Mičuda, Ladislav Mišta Jr, Miloslav Dušek, Petros Wallden, and Erika Andersson. ``Imperfect 1-out-of-2 quantum oblivious transfer: bounds, a protocol, and its experimental implementation''. PRX Quantum 2, 010335 (2021).
https://doi.org/10.1103/PRXQuantum.2.010335

[9] Gus Gutoski André Chailloux and Jamie Sikora. ``Optimal bounds for semi-honest quantum oblivious transfer''. Chicago Journal of Theoretical Computer Science 13, 1–17 (2016).
https://doi.org/10.4086/cjtcs.2016.013

[10] Andris Ambainis. ``A new protocol and lower bounds for quantum coin flipping''. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Page 134–142. STOC '01New York, NY, USA (2001). Association for Computing Machinery.
https://doi.org/10.1145/380752.380788

[11] Carlos Mochon. ``Quantum weak coin flipping with arbitrarily small bias'' (2007). arXiv:0711.4114.
arXiv:0711.4114

[12] Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, and Loïck Magnin. ``A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias''. SIAM Journal on Computing 45, 633–679 (2016).
https://doi.org/10.1137/14096387X

[13] Atul Singh Arora, Jérémie Roland, and Stephan Weis. ``Quantum weak coin flipping''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Page 205–216. STOC 2019New York, NY, USA (2019). Association for Computing Machinery.
https://doi.org/10.1145/3313276.3316306

[14] Atul Singh Arora, Jérémie Roland, and Chrysoula Vlachou. ``Analytic quantum weak coin flipping protocols with arbitrarily small bias''. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 919–938. (2021).
https://doi.org/10.1137/1.9781611976465.58

[15] Carl A. Miller. ``The impossibility of efficient quantum weak coin flipping''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Page 916–929. STOC 2020New York, NY, USA (2020). Association for Computing Machinery.
https://doi.org/10.1145/3357713.3384276

[16] Carlos Mochon. ``Large family of quantum weak coin-flipping protocols''. Physical Review A 72, 022341 (2005).
https://doi.org/10.1103/PhysRevA.72.022341

[17] Alexei Kitaev. ``Quantum coin flipping''. In 6th Annual workshop on Quantum Information Processing (Unpublished result). (2002).

[18] Nati Aharon and Jonathan Silman. ``Quantum dice rolling: a multi-outcome generalization of quantum coin flipping''. New Journal of Physics 12, 033027 (2010).
https://doi.org/10.1088/1367-2630/12/3/033027

[19] Howard Barnum, Jonathan Barrett, Matthew Leifer, and Alexander Wilce. ``Generalized no-broadcasting theorem''. Physical Review Letters 99, 240501 (2007).
https://doi.org/10.1103/PhysRevLett.99.240501

[20] WK Wootters and WH Zurek. ``A single quantum cannot be cloned''. Nature 299, 802–803 (1982).
https://doi.org/10.1038/299802a0

[21] Yehuda Lindell. ``Fast cut-and-choose-based protocols for malicious and covert adversaries''. Journal of Cryptology 29, 456–490 (2016).
https://doi.org/10.1007/s00145-015-9198-0

[22] Jos F Sturm. ``Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones''. Optimization methods and software 11, 625–653 (1999).
https://doi.org/10.1080/10556789908805766

[23] Kim-Chuan Toh, Michael J Todd, and Reha H Tütüncü. ``SDPT3—a MATLAB software package for semidefinite programming, version 1.3''. Optimization Methods and Software 11, 545–581 (1999).
https://doi.org/10.1080/10556789908805762

[24] MOSEK ApS. ``The mosek optimization toolbox for matlab manual. version 9.0.''. (2019). url: http://docs.mosek.com/9.0/toolbox/index.html.
http://docs.mosek.com/9.0/toolbox/index.html

[25] Ashwin Nayak and Peter Shor. ``Bit-commitment-based quantum coin flipping''. Physical Review A 67, 012304 (2003).
https://doi.org/10.1103/PhysRevA.67.012304

[26] Michael A Nielsen and Isaac L Chuang. ``Quantum Computation and Quantum Information''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667

[27] John Watrous. ``The Theory of Quantum Information''. Cambridge University Press. (2018).
https://doi.org/10.1017/9781316848142

[28] Christoph Helmberg, Franz Rendl, Robert J Vanderbei, and Henry Wolkowicz. ``An interior-point method for semidefinite programming''. SIAM Journal on Optimization 6, 342–361 (1996).
https://doi.org/10.1137/0806020

[29] Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. ``Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results''. SIAM Journal on Optimization 8, 746–768 (1998).
https://doi.org/10.1137/S1052623496304700

[30] Stephen Boyd and Lieven Vandenberghe. ``Convex Optimization''. Cambridge University Press. (2004).
https://doi.org/10.1017/CBO9780511804441

[31] Sanjay Mehrotra and M Gökhan Özevin. ``Decomposition-based interior point methods for two-stage stochastic semidefinite programming''. SIAM Journal on Optimization 18, 206–222 (2007).
https://doi.org/10.1137/050622067

[32] Hoi-Kwong Lo and Hoi Fung Chau. ``Is quantum bit commitment really possible?''. Physical Review Letters 78, 3410 (1997).
https://doi.org/10.1103/PhysRevLett.78.3410

[33] Dominic Mayers. ``Unconditionally secure quantum bit commitment is impossible''. Physical Review Letters 78, 3414 (1997).
https://doi.org/10.1103/PhysRevLett.78.3414

[34] Jamie Sikora and John H Selby. ``Simple proof of the impossibility of bit commitment in generalized probabilistic theories using cone programming''. Physical Review A 97, 042302 (2018).
https://doi.org/10.1103/PhysRevA.97.042302

[35] Andre Chailloux and Iordanis Kerenidis. ``Optimal bounds for quantum bit commitment''. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Pages 354–362. (2011).
https://doi.org/10.1109/FOCS.2011.42

[36] André Chailloux and Iordanis Kerenidis. ``Optimal quantum strong coin flipping''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 527–533. (2009).
https://doi.org/10.1109/FOCS.2009.71

[37] Iordanis Kerenidis and Ashwin Nayak. ``Weak coin flipping with small bias''. Information Processing Letters 89, 131–135 (2004).
https://doi.org/10.1016/j.ipl.2003.07.007

[38] Roger Colbeck. ``An entanglement-based protocol for strong coin tossing with bias 1/4''. Physics Letters A 362, 390–392 (2007).
https://doi.org/10.1016/j.physleta.2006.10.062

[39] Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303–332 (1999).
https://doi.org/10.1137/S0036144598347011

[40] Michael J Fischer, Silvio Micali, and Charles Rackoff. ``A secure protocol for the oblivious transfer''. Journal of Cryptology 9, 191–196 (1996).
https://doi.org/10.1007/BF00208002

[41] Michael Grant and Stephen Boyd. ``CVX: Matlab software for disciplined convex programming, version 2.1''. http://cvxr.com/cvx (2014).
http://cvxr.com/cvx

[42] Michael Grant and Stephen Boyd. ``Graph implementations for nonsmooth convex programs''. In V. Blondel, S. Boyd, and H. Kimura, editors, Recent Advances in Learning and Control. Pages 95–110. Lecture Notes in Control and Information Sciences. Springer-Verlag Limited (2008).
https://doi.org/10.1007/978-1-84800-155-8_7

[43] Nathaniel Johnston. ``QETLAB: A MATLAB toolbox for quantum entanglement, version 0.9''. http://qetlab.com (2016).
http://qetlab.com

[44] Nati Aharon, André Chailloux, Iordanis Kerenidis, Serge Massar, Stefano Pironio, and Jonathan Silman. ``Weak coin flipping in a device-independent setting''. In Theory of Quantum Computation, Communication, and Cryptography: Revised Selected Papers. Pages 1–12. Springer (2011).
https://doi.org/10.1007/978-3-642-54429-3_1

[45] Nati Aharon, Serge Massar, Stefano Pironio, and Jonathan Silman. ``Device-independent bit commitment based on the CHSH inequality''. New Journal of Physics 18, 025014 (2016).
https://doi.org/10.1088/1367-2630/18/2/025014

[46] Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, and Andrew C. Yao. ``Quantum bit escrow''. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Page 705–714. STOC '00New York, NY, USA (2000). Association for Computing Machinery.
https://doi.org/10.1145/335305.335404

[47] Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Rohrig. ``Multiparty quantum coin flipping''. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity. Pages 250–259. (2004).
https://doi.org/10.1109/CCC.2004.1313848

[48] Howard Barnum, Carlton M Caves, Christopher A Fuchs, Richard Jozsa, and Benjamin Schumacher. ``Noncommuting mixed states cannot be broadcast''. Physical Review Letters 76, 2818 (1996).
https://doi.org/10.1103/PhysRevLett.76.2818

[49] Manuel Blum. ``Coin flipping by telephone a protocol for solving impossible problems''. ACM SIGACT News 15, 23–27 (1983).
https://doi.org/10.1145/1008908.1008911

[50] Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, Dirk Schlingemann, and Reinhard Werner. ``A short impossibility proof of quantum bit commitment''. Physics Letters A 377, 1076–1087 (2013).
https://doi.org/10.1016/j.physleta.2013.02.045

[51] Ivan B. Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner. ``Cryptography in the bounded-quantum-storage model''. SIAM Journal on Computing 37, 1865–1890 (2008).
https://doi.org/10.1137/060651343

[52] Gus Gutoski and John Watrous. ``Toward a general theory of quantum games''. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Page 565–574. STOC '07New York, NY, USA (2007). Association for Computing Machinery.
https://doi.org/10.1145/1250790.1250873

[53] Gus Gutoski, Ansis Rosmanis, and Jamie Sikora. ``Fidelity of quantum strategies with applications to cryptography''. Quantum 2, 89 (2018).
https://doi.org/10.22331/q-2018-09-03-89

[54] Joe Kilian. ``Founding crytpography on oblivious transfer''. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. Page 20–31. STOC '88New York, NY, USA (1988). Association for Computing Machinery.
https://doi.org/10.1145/62212.62215

[55] Srijita Kundu, Jamie Sikora, and Ernest Y-Z Tan. ``A device-independent protocol for XOR oblivious transfer''. Quantum 6, 725 (2022).
https://doi.org/10.22331/q-2022-05-30-725

[56] Hoi-Kwong Lo. ``Insecurity of quantum secure computations''. Physical Review A 56, 1154 (1997).
https://doi.org/10.1103/PhysRevA.56.1154

[57] Hoi-Kwong Lo and Hoi Fung Chau. ``Why quantum bit commitment and ideal quantum coin tossing are impossible''. Physica D: Nonlinear Phenomena 120, 177–187 (1998).
https://doi.org/10.1016/S0167-2789(98)00053-0

[58] Ashwin Nayak, Jamie Sikora, and Levent Tunçel. ``Quantum and classical coin-flipping protocols based on bit-commitment and their point games'' (2015). arXiv:1504.04217.
arXiv:1504.04217

[59] Ashwin Nayak, Jamie Sikora, and Levent Tunçel. ``A search for quantum coin-flipping protocols using optimization techniques''. Mathematical Programming 156, 581–613 (2016).
https://doi.org/10.1007/s10107-015-0909-y

[60] R Tyrrell Rockafellar. ``Convex Analysis''. Volume 18. Princeton University Press. (1970).
https://doi.org/10.1515/9781400873173

[61] Christian Schaffner, Barbara Terhal, and Stephanie Wehner. ``Robust cryptography in the noisy-quantum-storage model''. Quantum Information and Computation 9, 963–996 (2009).
https://doi.org/10.26421/QIC9.11-12-4

[62] Jamie Sikora, André Chailloux, and Iordanis Kerenidis. ``Strong connections between quantum encodings, nonlocality, and quantum cryptography''. Physical Review A 89, 022334 (2014).
https://doi.org/10.1103/PhysRevA.89.022334

[63] Jamie Sikora. ``Simple, near-optimal quantum protocols for die-rolling''. Cryptography 1, 11 (2017).
https://doi.org/10.3390/cryptography1020011

[64] Jamie Sikora and John H Selby. ``Impossibility of coin flipping in generalized probabilistic theories via discretizations of semi-infinite programs''. Physical Review Research 2, 043128 (2020).
https://doi.org/10.1103/PhysRevResearch.2.043128

[65] Jonathan Silman, André Chailloux, Nati Aharon, Iordanis Kerenidis, Stefano Pironio, and Serge Massar. ``Fully distrustful quantum bit commitment and coin flipping''. Physical Review Letters 106, 220501 (2011).
https://doi.org/10.1103/PhysRevLett.106.220501

[66] Robert W Spekkens and Terry Rudolph. ``Degrees of concealment and bindingness in quantum bit commitment protocols''. Physical Review A 65, 012310 (2001).
https://doi.org/10.1103/PhysRevA.65.012310

[67] Stephanie Wehner, Christian Schaffner, and Barbara M Terhal. ``Cryptography from noisy storage''. Physical Review Letters 100, 220502 (2008).
https://doi.org/10.1103/PhysRevLett.100.220502

[68] Andrew Chi-Chih Yao. ``How to generate and exchange secrets''. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). Pages 162–167. (1986).
https://doi.org/10.1109/SFCS.1986.25

Cited by

[1] Lara Stroh, James T. Peat, Mats Kroneberg, Ittoop V. Puthoor, and Erika Andersson, "Quantum Rabin oblivious transfer using two pure states", Physical Review Research 6 4, 043004 (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2026-07-15 11:53:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-07-15 11:53:50).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.