Conditional disclosure of secrets with quantum resources

Vahid R. Asadi; Kohdai Kuroiwa; Debbie Leung; Alex May; Sabrina Pasterski; Chris Waddell

doi:10.22331/q-2025-10-16-1885

Conditional disclosure of secrets with quantum resources

Vahid R. Asadi², Kohdai Kuroiwa^1,2, Debbie Leung^1,2, Alex May^1,2, Sabrina Pasterski¹, and Chris Waddell¹

¹Perimeter Institute for Theoretical Physics
²Institute for Quantum Computing, Waterloo, Ontario

Published:	2025-10-16, volume 9, page 1885
Editor:	Xin Wang
Eprint:	arXiv:2404.14491v4
Doi:	https://doi.org/10.22331/q-2025-10-16-1885
Citation:	Quantum 9, 1885 (2025).

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

Abstract

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret $z$ to a referee if and only if a Boolean function $f$ has $f(x,y)=1$. Alice knows $x,z$, Bob knows $y$, and the referee knows $x,y$. Recently, a quantum analogue of this primitive called CDQS was defined and related to $f$-routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. We begin by looking for quantum analogues of results already established in the classical CDS literature. Doing so we establish a number of basic properties of CDQS, including lower bounds on entanglement and communication stated in terms of measures of communication complexity. Because of the close relationship to the $f$-routing position-verification scheme, our results have relevance to the security of these schemes.

► BibTeX data

@article{Asadi2025conditional,
  doi = {10.22331/q-2025-10-16-1885},
  url = {https://doi.org/10.22331/q-2025-10-16-1885},
  title = {Conditional disclosure of secrets with quantum resources},
  author = {Asadi, Vahid R. and Kuroiwa, Kohdai and Leung, Debbie and May, Alex and Pasterski, Sabrina and Waddell, Chris},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1885},
  month = oct,
  year = {2025}
}

► References

[1] Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. Journal of Computer and System Sciences, 60 (3): 592–629, 2000. ISSN 0022-0000. https://doi.org/10.1006/jcss.1999.1689. URL https://www.sciencedirect.com/science/article/pii/S0022000099916896.
https://doi.org/10.1006/jcss.1999.1689
https://www.sciencedirect.com/science/article/pii/S0022000099916896

[2] Romain Gay, Iordanis Kerenidis, and Hoeteck Wee. Communication complexity of conditional disclosure of secrets and attribute-based encryption. In Annual Cryptology Conference, pages 485–502. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_24.
https://doi.org/10.1007/978-3-662-48000-7_24

[3] Benny Applebaum and Barak Arkis. On the power of amortization in secret sharing: d-uniform secret sharing and CDS with constant information rate. ACM Transactions on Computation Theory (TOCT), 12 (4): 1–21, 2020. https://doi.org/10.1145/3417756.
https://doi.org/10.1145/3417756

[4] Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe. Journal of Cryptology, 34: 1–45, 2021. https://doi.org/10.1007/s00145-021-09376-1.
https://doi.org/10.1007/s00145-021-09376-1

[5] Uri Feige, Joe Killian, and Moni Naor. A minimal model for secure computation. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 554–563, 1994. https://doi.org/10.1145/195058.195408.
https://doi.org/10.1145/195058.195408

[6] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. Quantum, 8: 1387, 2024. https://doi.org/10.22331/q-2024-06-27-1387.
https://doi.org/10.22331/q-2024-06-27-1387

[7] Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326.
https://doi.org/10.1103/PhysRevA.84.012326

[8] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, pages 391–407. Springer, 2009. https://doi.org/10.1007/978-3-642-03356-8_23.
https://doi.org/10.1007/978-3-642-03356-8_23

[9] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://doi.org/10.1137/130913687.
https://doi.org/10.1137/130913687

[10] Vahid R. Asadi, Eric Culf, and Alex May. Rank lower bounds on non-local quantum computation. Proceedings, Innovations in theoretical computer science, 2025. 10.4230/LIPIcs.ITCS.2025.11.
https://doi.org/10.4230/LIPIcs.ITCS.2025.11

[11] Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Conditional disclosure of secrets via non-linear reconstruction. In Annual International Cryptology Conference, pages 758–790. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_25.
https://doi.org/10.1007/978-3-319-63688-7_25

[12] Amos Beimel and Yuval Ishai. On the power of nonlinear secret-sharing. In Proceedings 16th annual IEEE conference on computational complexity, pages 188–202. IEEE, 2001. 10.1109/CCC.2001.933886.
https://doi.org/10.1109/CCC.2001.933886

[13] Sam Cree and Alex May. Code-routing: a new attack on position-verification. arXiv preprint arXiv:2202.07812, 2022. https://doi.org/10.48550/arXiv.2202.07812.
https://doi.org/10.48550/arXiv.2202.07812
arXiv:2202.07812

[14] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1–4, 2022. https://doi.org/10.1038/s41567-022-01577-0.
https://doi.org/10.1038/s41567-022-01577-0

[15] Ronald De Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 32 (3): 681–699, 2003. https://doi.org/10.1137/S0097539702407345.
https://doi.org/10.1137/S0097539702407345

[16] Akinori Kawachi and Harumichi Nishimura. Communication complexity of private simultaneous quantum messages protocols. arXiv preprint arXiv:2105.07120, 2021. https://doi.org/10.4230/LIPIcs.ITC.2021.20.
https://doi.org/10.4230/LIPIcs.ITC.2021.20
arXiv:2105.07120

[17] Rene Allerstorfer, Andreas Bluhm, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel. Making existing quantum position verification protocols secure against arbitrary transmission loss. arXiv preprint arXiv:2312.12614, 2023. https://doi.org/10.48550/arXiv.2312.12614.
https://doi.org/10.48550/arXiv.2312.12614
arXiv:2312.12614

[18] Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan. Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations. In Annual International Cryptology Conference, pages 727–757. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_24.
https://doi.org/10.1007/978-3-319-63688-7_24

[19] Richard Cleve, Wim Van Dam, Michael Nielsen, and Alain Tapp. Quantum entanglement and the communication complexity of the inner product function. In NASA International Conference on Quantum Computing and Quantum Communications, pages 61–74. Springer, 1998. https://doi.org/10.1007/3-540-49208-9_4.
https://doi.org/10.1007/3-540-49208-9_4

[20] Ashwin Nayak and Julia Salzman. On communication over an entanglement-assisted quantum channel. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 698–704, 2002. https://doi.org/10.1145/509907.510007.
https://doi.org/10.1145/509907.510007

[21] Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. Exponential separation of quantum communication and classical information. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 277–288, 2017. 10.1145/3055399.3055401. URL https://doi.org/10.1145/3055399.3055401.
https://doi.org/10.1145/3055399.3055401

[22] Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, and Dave Touchette. Near-optimal bounds on the bounded-round quantum communication complexity of disjointness. SIAM Journal on Computing, 47 (6): 2277–2314, 2018. 10.1137/16M1061400.
https://doi.org/10.1137/16M1061400

[23] Mark M Wilde. Quantum information theory. Cambridge university press, 2013. https://doi.org/10.1017/CBO9781139525343.
https://doi.org/10.1017/CBO9781139525343

[24] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F Werner. The information-disturbance tradeoff and the continuity of Stinespring's representation. IEEE transactions on information theory, 54 (4): 1708–1717, 2008. 10.1109/TIT.2008.917696.
https://doi.org/10.1109/TIT.2008.917696

[25] A Robert Calderbank and Peter W Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098, 1996. https://doi.org/10.1103/PhysRevA.54.1098.
https://doi.org/10.1103/PhysRevA.54.1098

[26] Daniel Gottesman. Surviving as a Quantum Computer in a Classical World. 2024. URL https://www.cs.umd.edu/class/spring2024/cmsc858G/QECCbook-2024-ch1-8.pdf.
https://www.cs.umd.edu/class/spring2024/cmsc858G/QECCbook-2024-ch1-8.pdf

[27] Ryan O'Donnell and John Wright. Efficient quantum tomography. In 48th annual ACM symposium on Theory of Computing, 8 2015. 10.1145/2897518.2897544.
https://doi.org/10.1145/2897518.2897544

[28] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40 (6): 1969–2000, 2011. 10.1137/080733644. URL https://doi.org/10.1137/080733644.
https://doi.org/10.1137/080733644

[29] Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1 (3): 37–46, 2005. 10.4086/toc.2005.v001a003. URL https://theoryofcomputing.org/articles/v001a003.
https://doi.org/10.4086/toc.2005.v001a003
https://theoryofcomputing.org/articles/v001a003

[30] Samuel Kutin. Quantum lower bound for the collision problem with small range. Theory of Computing, 1 (2): 29–36, 2005. 10.4086/toc.2005.v001a002. URL https://theoryofcomputing.org/articles/v001a002.
https://doi.org/10.4086/toc.2005.v001a002
https://theoryofcomputing.org/articles/v001a002

[31] Hartmut Klauck. Lower bounds for quantum communication complexity. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 288–297. IEEE, 2001. 10.1109/SFCS.2001.959903.
https://doi.org/10.1109/SFCS.2001.959903

[32] Uma Girish, Alex May, Leo Orshansky, and Chris Waddell. Comparing classical and quantum conditional disclosure of secrets. arXiv preprint arXiv:2505.02939, 2025. https://doi.org/10.48550/arXiv.2505.02939.
https://doi.org/10.48550/arXiv.2505.02939
arXiv:2505.02939

[33] Ashley Montanaro. Learning stabilizer states by Bell sampling. arXiv preprint arXiv:1707.04012, 2017. https://doi.org/10.48550/arXiv.1707.04012.
https://doi.org/10.48550/arXiv.1707.04012
arXiv:1707.04012

Cited by

[1] Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen, "A complexity theory for non-local quantum computation", Quantum 10, 2152 (2026).

[2] Uma Girish, Alex May, Leo Orshansky, and Chris Waddell, "Comparing classical and quantum conditional disclosure of secrets", Quantum 10, 2049 (2026).

[3] Alex May, Sabrina Pasterski, Chris Waddell, and Michelle Xu, "Cryptographic tests of the python's lunch conjecture", SciPost Physics 19 4, 084 (2025).

[4] Vahid R. Asadi, Eric Culf, and Alex May, "Rank lower bounds on non-local quantum computation", arXiv:2402.18647, (2024).

[5] Uma Girish, Greg Gluch, Shafi Goldwasser, Tal Malkin, Leo Orshansky, and Henry Yuen, "Private Proofs of When and Where", arXiv:2601.18961, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 16:46:10) and SAO/NASA ADS (last updated successfully 2026-08-09 16:46:11). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.