Document Open Access Logo

Communication Complexity of Private Simultaneous Quantum Messages Protocols

Authors Akinori Kawachi , Harumichi Nishimura

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.20.pdf
  • Filesize: 0.8 MB
  • 19 pages

Document Identifiers

Author Details

Akinori Kawachi
  • Graduate School of Engineering, Mie University, Tsu, Japan
Harumichi Nishimura
  • Graduate School of Informatics, Nagoya University, Japan
  • Institute for Advanced Study, Nagoya University, Japan

Funding

  • Kawachi, Akinori: JSPS Grant-in-Aid for Scientific Research (A) Nos. 16H01705, 21H04879, (B) No. 17H01695, JSPS Grant-in-Aid for Young Scientists (B) No. 17K12640, and MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant Number JPMXS0120319794.
  • Nishimura, Harumichi: JSPS Grant-in-Aid for Scientific Research (A) Nos. 16H01705, 21H04879, (B) No. 19H04066, Grant-in-Aid for Transformative Research Areas No. 20H05966 and MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grant Number JPMXS0120319794.

Acknowledgements

We thank the anonymous reviewers of ITC 2021 for helpful comments.

Cite AsGet BibTex

Akinori Kawachi and Harumichi Nishimura. Communication Complexity of Private Simultaneous Quantum Messages Protocols. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.20

Abstract

The private simultaneous messages (PSM) model is a non-interactive version of the multiparty secure computation (MPC), which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, k parties P₁,…,P_k initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x₁,…, x_k. Every P_i generates a quantum message from the private input x_i and the shared random string (entangled states), and then sends it to the referee R. Receiving the messages from the k parties, R computes F(x₁,…,x_k) from the messages. Then, R learns nothing except for F(x₁,…,x_k) as the privacy condition. We obtain the following results for this PSQM model. (i) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz [Journal of Cryptology(3), 916-953 (2020)]. In particular, we prove a lower bound (3-o(1))n of the communication complexity in PSQM protocols with a shared random string for random Boolean functions of 2n-bit input, which is larger than the trivial upper bound 2n of the communication complexity without the privacy condition. (ii) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (iii) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Communication complexity
  • private simultaneous messages
  • quantum protocols
  • secure multi-party computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited. Journal of Cryptology, 33(3):916-953, 2020. URL: https://doi.org/10.1007/s00145-019-09334-y.
  2. Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the complexity of decomposable randomized encodings, or: how friendly can a garbling-friendly PRF be? In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pages 86:1-86:22, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.86.
  3. Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM Journal on Computing, 38(1):366-384, 2008. URL: https://doi.org/10.1137/060651835.
  4. Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions. In Proceedings of the 11th IACR Theory of Cryptography Conference (TCC 2014), pages 317-342, 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_14.
  5. Amos Beimel, Eyal Kushilevitz, and Pnina Nissim. The complexity of multiparty PSM protocols and related models. In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part II, pages 287-318, 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_10.
  6. Zvika Brakerski and Henry Yuen. Quantum garbled circuits. arXiv:2006.01085, 2020. URL: https://arxiv.org/abs/2006.01085.
  7. Gilles Brassard, Richard Cleve, and Alain Tapp. Cost of exactly simulating quantum entanglement with classical communication. Physical Review Letters, 83:1874-1877, 1999. URL: https://doi.org/10.1103/PhysRevLett.83.1874.
  8. Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87:167902 (4pages), 2001. URL: https://doi.org/10.1103/PhysRevLett.87.167902.
  9. Harry Buhrman, Richard Cleve, and Avi Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th annual ACM Symposium on Theory of Computing (STOC 1998), pages 63-68, 1998. URL: https://doi.org/10.1145/276698.276713.
  10. Claude Crépeau, Daniel Gottesman, and Adam Smith. Secure multi-party quantum computation. In Proceedings of the 34th Annual Symposium on Theory of Computing (STOC 2002), pages 643-652, 2002. URL: https://doi.org/10.1145/509907.510000.
  11. Ivan Damgård, Kasper Green Larsen, and Jesper Buus Nielsen. Communication lower bounds for statistically secure MPC, with or without preprocessing. In Proceedings of the 39th Annual International Cryptology Conference (CRYPTO 2019) Part II, pages 61-84, 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_3.
  12. Deepesh Data, Manoj M. Prabhakaran, and Vinod M. Prabhakaran. Communication and randomness lower bounds for secure computation. IEEE Transactions on Information Theory, 62(7):3901-3929, 2016. URL: https://doi.org/10.1109/TIT.2016.2568207.
  13. Yfke Dulek, Alex B. Grilo, Stacey Jeffery, Christian Majenz, and Christian Schaffner. Secure multi-party quantum computation with a dishonest majority. In Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2020) Part III, pages 729-758, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_25.
  14. Uriel Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation (extended abstract). In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC 1994), pages 554-563, 1994. URL: https://doi.org/10.1145/195058.195408.
  15. Dmitry Gavinsky. Quantum versus classical simultaneity in communication complexity. IEEE Transactions on Information Theory, 65(10):6466-6483, 2019. URL: https://doi.org/10.1109/TIT.2019.2918453.
  16. Dmitry Gavinsky. Bare quantum simultaneity versus classical interactivity in communication complexity. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC 2020), pages 401-411, 2020. URL: https://doi.org/10.1145/3357713.3384243.
  17. Dmitry Gavinsky and Tsuyoshi Ito. Quantum fingerprints that keep secrets. Quantum Information and Computation, 13(7-8):583-606, 2013. URL: https://doi.org/10.26421/QIC13.7-8-3.
  18. Dmitry Gavinsky, Julia Kempe, Oded Regev, and Ronald de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. SIAM Journal on Computing, 39(1):1-24, 2009. URL: https://doi.org/10.1137/060665798.
  19. Masahito Hayashi, Satoshi Ishizuka, Akinori Kawachi, Gen Kimura, and Tomohiro Ogawa. Introduction to Quantum Information Science. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-43502-1.
  20. Rolf T. Horn, A. J. Scott, Jonathan Walgate, Richard Cleve, A. I. Lvovsky, and Barry C. Sanders. Classical and quantum fingerprinting with shared randomness and one-sided error. Quantum Information and Computation, 5(3):258-271, 2005. URL: https://doi.org/10.26421/QIC5.3-6.
  21. Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocol with applications. In Proceedings of the 5th Israel Symposium on Theory of Computing and Systems (ISTCS 1997), pages 174-183, 1997. URL: https://doi.org/10.1109/ISTCS.1997.595170.
  22. Roy Kasher and Julia Kempe. Two-source extractors secure against quantum adversaries. Theory of Computing, 8:461-486, 2012. URL: https://doi.org/10.4086/toc.2012.v008a021.
  23. Hartmut Klauck. Quantum and approximate privacy. Theory of Computing Systems, 37(1):221-246, 2004. URL: https://doi.org/10.1007/s00224-003-1113-7.
  24. Hartmut Klauck. One-way communication complexity and the Nečiporuk lower bound on formula size. SIAM Journal on Computing, 37(2):552-583, 2007. URL: https://doi.org/10.1137/S009753970140004X.
  25. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. URL: https://doi.org/10.1017/CBO9780511574948.
  26. Tomoyuki Morimae. Quantum randomized encoding, verification of quantum computing, no-cloning, and blind quantum computing. arXiv:2011.03141, 2020. URL: https://arxiv.org/abs/2011.03141.
  27. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  28. Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC 1999), pages 358-367, 1999. URL: https://doi.org/10.1145/301250.301343.
  29. Dominique Unruh. Universally composable quantum multi-party computation. In Proceedings of 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2010), pages 486-505, 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_25.
  30. Ronald de Wolf. Quantum Computing and Communication Complexity. PhD thesis, University of Amsterdam, 2001. URL: https://dare.uva.nl/search?identifier=480e76ad-11b7-4226-9c54-6b39c51e6f37.
  31. Andrew C.-C. Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC 1979), pages 209-213, 1979. URL: https://doi.org/10.1145/800135.804414.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact