quantum-computing

Comparing classical and quantum conditional disclosure of secrets

Quantum Journal

14 min read

0 likes

⚡ Quantum Brief

Researchers Uma Girish, Alex May, Leo Orshansky, and Chris Waddell proved quantum conditional disclosure of secrets (CDS) has a logarithmic lower bound tied to classical one-way communication complexity, establishing a fundamental limit. The team linked quantum CDS to two-prover interactive proofs, showing its complexity is bounded by two-round public-coin protocols, bridging cryptography and quantum information theory. For the "not-equals" function, they demonstrated a quantum CDS advantage: logarithmic complexity versus classical linear, proving exponential separation even with perfect correctness. Quantum CDS achieves logarithmic efficiency for "forrelation," a problem requiring linear resources classically, suggesting inherent quantum superiority even with error tolerance. The study also improved separations in private simultaneous message passing, combining non-local quantum computation techniques with communication complexity to advance information-theoretic cryptography.

Comparing classical and quantum conditional disclosure of secrets

Summarize this article with:

AbstractThe conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results: 1) We prove a $\Omega(\log \mathsf{R}_{0,A\rightarrow B}(f)+\log \mathsf{R}_{0,B\rightarrow A}(f))$ lower bound on quantum CDS where $\mathsf{R}_{0,A\rightarrow B}(f)$ is the classical one-way communication complexity with perfect correctness. 2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs. 3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of $O(\log n)$ and classical lower bound of $\Omega(n)$. 4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed. We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.► BibTeX data@article{Girish2026comparingclassical, doi = {10.22331/q-2026-04-01-2049}, url = {https://doi.org/10.22331/q-2026-04-01-2049}, title = {Comparing classical and quantum conditional disclosure of secrets}, author = {Girish, Uma and May, Alex and Orshansky, Leo and Waddell, Chris}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2049}, month = apr, year = {2026} }► References [1] Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 151–160, 1998. https://doi.org/10.1145/276698.276723. https://doi.org/10.1145/276698.276723 [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] 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 [6] Alex May, Sabrina Pasterski, Chris Waddell, and Michelle Xu. Cryptographic tests of the python's lunch conjecture. arXiv preprint arXiv:2411.10527, 2024. https://doi.org/10.48550/arXiv.2411.10527. https://doi.org/10.48550/arXiv.2411.10527 arXiv:2411.10527 [7] Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources. Quantum, 9: 1885, October 2025a. ISSN 2521-327X. 10.22331/q-2025-10-16-1885. URL https://doi.org/10.22331/q-2025-10-16-1885. https://doi.org/10.22331/q-2025-10-16-1885 [8] Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A—Atomic, Molecular, and Optical Physics, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326. https://doi.org/10.1103/PhysRevA.84.012326 [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 PDF. https://doi.org/10.1137/130913687%20PDF [10] Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. Leibniz Int. Proc. Inf., 61: 9:1–9:24, 2016. 10.4230/LIPIcs.TQC.2016.9. https://doi.org/10.4230/LIPIcs.TQC.2016.9 [11] Vahid R. Asadi, Eric Culf, and Alex May.

Rank Lower Bounds on Non-Local Quantum Computation.

In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, Dagstuhl, Germany, 2025b. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-361-4. 10.4230/LIPIcs.ITCS.2025.11. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.11. https://doi.org/10.4230/LIPIcs.ITCS.2025.11 [12] Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 307–316, 2015. https://doi.org/10.1145/2746539.2746547. https://doi.org/10.1145/2746539.2746547 [13] Uma Girish, Ran Raz, and Avishay Tal. Quantum versus randomized communication complexity, with efficient players. Computational Complexity, 31 (2): 17, 2022. https://doi.org/10.1007/s00037-022-00232-7. https://doi.org/10.1007/s00037-022-00232-7 [14] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation. Number 47.

American Mathematical Soc., 2002. http://doi.org/10.1090/gsm/047. https://doi.org/10.1090/gsm/047 [15] Mark M Wilde. Quantum information theory.

Cambridge University Press, 2013. http://doi.org/10.1017/9781316809976. https://doi.org/10.1017/9781316809976 [16] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F Werner. A continuity theorem for Stinespring's dilation. Journal of Functional Analysis, 255 (8): 1889–1904, 2008. http://doi.org/10.1016/j.jfa.2008.07.023. https://doi.org/10.1016/j.jfa.2008.07.023 [17] A Afham, Richard Kueng, and Chris Ferrie. Quantum mean states are nicer than you think: Fast algorithms to compute states maximizing average fidelity. arXiv preprint arXiv:2206.08183, 2022. https://doi.org/10.48550/arXiv.2206.08183. https://doi.org/10.48550/arXiv.2206.08183 arXiv:2206.08183 [18] Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan. Conditional disclosure of secrets: Amplification, closure, amortization, lower-bounds, and separations. SIAM Journal on Computing, 50 (1): 32–67, 2021. 10.1137/18M1217097. URL https://doi.org/10.1137/18M1217097. https://doi.org/10.1137/18M1217097 [19] Benny Applebaum and Pavel Raykov. From private simultaneous messages to zero-information Arthur—Merlin protocols and back. J. Cryptol., 30 (4): 961–988, October 2017. ISSN 0933-2790. 10.1007/s00145-016-9239-3. URL https://doi.org/10.1007/s00145-016-9239-3. https://doi.org/10.1007/s00145-016-9239-3 [20] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 145–158, 2013. https://doi.org/10.1145/2422436.2422455. https://doi.org/10.1145/2422436.2422455 [21] Akinori Kawachi and Harumichi Nishimura. Communication complexity of private simultaneous quantum messages protocols. In 2nd Conference on Information-Theoretic Cryptography, 2021. https://doi.org/10.48550/arXiv.2105.07120. https://doi.org/10.48550/arXiv.2105.07120 [22] Eyal Kushilevitz and Noam Nisan. Communication Complexity.

Cambridge University Press, 1996. https://doi.org/10.1017/CBO9780511574948. https://doi.org/10.1017/CBO9780511574948 [23] Peter Frankl and Vojtěch Rödl. Forbidden intersections. Transactions of the American Mathematical Society, 300 (1): 259–286, 1987. https://doi.org/10.1090/S0002-9947-1987-0871675-6. https://doi.org/10.1090/S0002-9947-1987-0871675-6 [24] Harry Buhrman, Richard Cleve, Serge Massar, and Ronald De Wolf. Nonlocality and communication complexity. Reviews of modern physics, 82 (1): 665–698, 2010. https://doi.org/10.1103/RevModPhys.82.665. https://doi.org/10.1103/RevModPhys.82.665 [25] Iordanis Kerenidis and Ran Raz. The one-way communication complexity of the Boolean Hidden Matching Problem, 2006. URL https://arxiv.org/abs/quant-ph/0607173. arXiv:quant-ph/0607173 [26] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, page 516–525, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145/1250790.1250866. URL https://doi.org/10.1145/1250790.1250866. https://doi.org/10.1145/1250790.1250866 [27] Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited. Cryptology ePrint Archive, Paper 2018/144, 2018. URL https://eprint.iacr.org/2018/144. https://eprint.iacr.org/2018/144 [28] Scott Aaronson. BQP and the polynomial hierarchy. In STOC'10: Proceedings of the forty-second ACM symposium on Theory of computing, pages 141–150, 2010. https://doi.org/10.1145/1806689.1806711. https://doi.org/10.1145/1806689.1806711 [29] Ran Raz and Avishay Tal. Oracle separation of BQP and PH. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 13–23, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. 10.1145/3313276.3316315. URL https://doi.org/10.1145/3313276.3316315. https://doi.org/10.1145/3313276.3316315 [30] Nikhil Bansal and Makrand Sinha. $k$-forrelation optimally separates quantum and classical query complexity.

In Samir Khuller and Virginia Vassilevska Williams, editors, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1303–1316, 2021. https://doi.org/10.1145/3406325.3451040. https://doi.org/10.1145/3406325.3451040 [31] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. Trans. Comp.-Aided Des. Integ. Cir. Sys., 32 (6): 818–830, June 2013. ISSN 0278-0070. 10.1109/TCAD.2013.2244643. URL https://doi.org/10.1109/TCAD.2013.2244643. https://doi.org/10.1109/TCAD.2013.2244643 [32] Benny Applebaum and Oded Nir. Advisor-verifier-prover games and the hardness of information theoretic cryptography. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 539–555. IEEE, 2023. 10.1109/FOCS57990.2023.00039. https://doi.org/10.1109/FOCS57990.2023.00039Cited byCould not fetch Crossref cited-by data during last attempt 2026-04-01 11:12:21: Could not fetch cited-by data for 10.22331/q-2026-04-01-2049 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-04-01 11:12:22: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractThe conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results: 1) We prove a $\Omega(\log \mathsf{R}_{0,A\rightarrow B}(f)+\log \mathsf{R}_{0,B\rightarrow A}(f))$ lower bound on quantum CDS where $\mathsf{R}_{0,A\rightarrow B}(f)$ is the classical one-way communication complexity with perfect correctness. 2) We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs. 3) For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of $O(\log n)$ and classical lower bound of $\Omega(n)$. 4) We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed. We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.► BibTeX data@article{Girish2026comparingclassical, doi = {10.22331/q-2026-04-01-2049}, url = {https://doi.org/10.22331/q-2026-04-01-2049}, title = {Comparing classical and quantum conditional disclosure of secrets}, author = {Girish, Uma and May, Alex and Orshansky, Leo and Waddell, Chris}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2049}, month = apr, year = {2026} }► References [1] Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 151–160, 1998. https://doi.org/10.1145/276698.276723. https://doi.org/10.1145/276698.276723 [2] Romain Gay, Iordanis Kerenidis, and Hoeteck Wee. Communication complexity of conditional disclosure of secrets and attribute-based encryption.

Rank Lower Bounds on Non-Local Quantum Computation.

American Mathematical Soc., 2002. http://doi.org/10.1090/gsm/047. https://doi.org/10.1090/gsm/047 [15] Mark M Wilde. Quantum information theory.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/