quantum-computing

Conditional disclosure of secrets with quantum resources

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

13 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Unsplash · Validated Fallback

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractThe 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.04012Cited byOn Crossref's cited-by service no data on citing works was found (last attempt 2025-10-24 01:51:19). Could not fetch ADS cited-by data during last attempt 2025-10-24 01:51:21: 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) 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.

Read Original

Source Information

Source: Quantum Journal

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

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Conditional disclosure of secrets with quantum resources

Tags

Source Information