Document Open Access Logo

Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation

Authors Keitaro Hiwatashi, Koji Nuida

PDF
Thumbnail PDF

File

LIPIcs.ITC.2023.18.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

Keitaro Hiwatashi
  • The University of Tokyo, Japan
  • National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan
Koji Nuida
  • Kyushu University, Japan
  • National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

Funding

Supported by JST CREST Grant Number JPMJCR2113.
  • Hiwatashi, Keitaro: This research was in part conducted under a contract of "Research and development on new generation cryptography for secure wireless communication services" among "Research and Development for Expansion of Radio Wave Resources (JPJ000254)," which was supported by the Ministry of Internal Affairs and Communications, Japan. The author was also partially supported by JSPS KAKENHI Grant Number JP21J20186 and JP22KJ0546.
  • Nuida, Koji: Supported by JSPS KAKENHI Grant Number JP19H01109, JP22K11906, and JST AIP Acceleration Research JPMJCR22U5.

Cite AsGet BibTex

Keitaro Hiwatashi and Koji Nuida. Exponential Correlated Randomness Is Necessary in Communication-Optimal Perfectly Secure Two-Party Computation. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITC.2023.18

Abstract

Secure two-party computation is a cryptographic technique that enables two parties to compute a function jointly while keeping each input secret. It is known that most functions cannot be realized by information-theoretically secure two-party computation, but any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. In the CR model, three kinds of complexities are mainly considered; the size of CR, the number of rounds, and the communication complexity. Ishai et al. (TCC 2013) showed that any function can be securely computed with optimal online communication cost, i.e., the number of rounds is one round and the communication complexity is the same as the input length, at the price of exponentially large CR. In this paper, we prove that exponentially large CR is necessary to achieve perfect security and online optimality for a general function and that the protocol by Ishai et al. is asymptotically optimal in terms of the size of CR. Furthermore, we also prove that exponentially large CR is still necessary even when we allow multiple rounds while keeping the optimality of communication complexity.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • Secure Computation
  • Correlated Randomness
  • Lower Bound

Metrics

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

References

  1. Nuttapong Attrapadung, Goichiro Hanaoaka, Takahiro Matsuda, Hiraku Morita, Kazuma Ohara, Jacob C. N. Schuldt, Tadanori Teruya, and Kazunari Tozawa. Oblivious linear group actions and applications. In CCS'21, pages 630-650. ACM, 2021. URL: https://doi.org/10.1145/3460120.3484584.
  2. Donald Beaver. Efficient multiparty protocols using circuit randomization. In 11th CRYPTO, volume 576 of LNCS, pages 420-432. Springer, 1991. URL: https://doi.org/10.1007/3-540-46766-1_34.
  3. Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions. In 11th TCC, volume 8349 of LNCS, pages 317-342. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_14.
  4. Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions (full version of [3]). https://people.csail.mit.edu/ranjit/papers/BIKK.pdf, 2014.
  5. Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathee. Function secret sharing for mixed-mode and fixed-point secure computation. In 40th EUROCRYPT, volume 12697 of LNCS, pages 871-900. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-77886-6_30.
  6. Elette Boyle, Niv Gilboa, and Yuval Ishai. Secure computation with preprocessing via function secret sharing. In 17th TCC, volume 11891 of LNCS, pages 341-371. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36030-6_14.
  7. Benny Chor and Eyal Kushilevitz. A zero-one law for boolean privacy. In 21st STOC, pages 62-72. ACM, 1989. URL: https://doi.org/10.1145/73007.73013.
  8. Geoffroy Couteau. A note on the communication complexity of multiparty computation in the correlated randomness model. In 38th EUROCRYPT, volume 11477 of LNCS, pages 473-503. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17656-3_17.
  9. Ivan Damgård, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. The tinytable protocol for 2-party secure computation, or: Gate-scrambling revisited. In 37th CRYPTO, volume 10401 of LNCS, pages 167-187. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-63688-7_6.
  10. Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou, and Michael Raskin. On the communication required for unconditionally secure multiplication. In 36th CRYPTO, volume 9815 of LNCS, pages 459-488. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_16.
  11. Ivan Bjerre Damgård, Boyang Li, and Nikolaj Ignatieff Schwartzbach. More communication lower bounds for information-theoretic mpc. In 2nd ITC, volume 199 of LIPIcs, pages 2:1-2:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITC.2021.2.
  12. Deepesh Data, Manoj M. Prabhakaran, and Vinod M. Prabhakaran. On the communication complexity of secure computation. In 34th CRYPTO, volume 8617 of LNCS, pages 199-216. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44381-1_12.
  13. Anna Gál and Adi Rosén. Lower bounds on the amount of randomness in private computation. In 35th STOC, pages 659-666. ACM, 2003. URL: https://doi.org/10.1145/780542.780638.
  14. Niv Gilboa and Yuval Ishai. Distributed point functions and their applications. In 33rd EUROCRYPT, volume 8441 of LNCS, pages 640-658. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_35.
  15. Vipul Goyal, Yuval Ishai, and Yifan Song. Tight bounds on the randomness complexity of secure multiparty computation. In 42nd CRYPTO, volume 13510 of LNCS, pages 483-513. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-15985-5_17.
  16. Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi, and Anat Paskin-Cherniavsky. On the power of correlated randomness in secure computation. In 10th TCC, volume 7785 of LNCS, pages 600-620. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_34.
  17. Marcel Keller, Emmanuela Orsini, and Peter Scholl. Mascot: Faster malicious arithmetic secure computation with oblivious transfer. In CCS'16, pages 830-842. ACM, 2016. URL: https://doi.org/10.1145/2976749.2978357.
  18. Eyal Kushilevitz. Privacy and communication complexity. In 30th FOCS, pages 416-421. IEEE Computer Society, 1989. URL: https://doi.org/10.1109/sfcs.1989.63512.
  19. Eyal Kushilevitz and Yishay Mansour. Randomness in private computations. In 15th PODC, pages 181-190. ACM Press, 1996. URL: https://doi.org/10.1145/248052.248089.
  20. Eyal Kushilevitz, Rafail Ostrovsky, Emmanuel Prouff, Adi Rosén, Adrian Thillard, and Damien Vergnaud. Lower and upper bounds on the randomness complexity of private computations of and. In 17th TCC, volume 11892 of LNCS, pages 386-406. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36033-7_15.
  21. Eyal Kushilevitz, Rafail Ostrovsky, and Adi Rosén. Characterizing linear size circuits in terms of privacy. In 28th STOC. ACM, 1996. URL: https://doi.org/10.1145/237814.238002.
  22. Eyal Kushilevitz, Rafail Ostrovsky, and Adi Rosén. Amortizing randomness in private multiparty computations. In 17th PODC, pages 81-90. ACM, 1998. URL: https://doi.org/10.1145/277697.277710.
  23. Eyal Kushilevitz and Adi Rosén. A randomness-rounds tradeoff in private computation. In 14th CRYPTO, volume 839 of LNCS, pages 397-410. Springer, 1994. URL: https://doi.org/10.1007/3-540-48658-5_36.
  24. Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: improved mixed-protocol secure two-party computation. In 30th USENIX Security Symposium, pages 2165-2182. USENIX Association, 2021. URL: https://www.usenix.org/conference/usenixsecurity21/presentation/patra.
  25. Andrew C.-C. Yao. How to generate and exchange secrets (extended abstract). In 27th FOCS, pages 162-167. IEEE Computer Society, 1986. URL: https://doi.org/10.1109/SFCS.1986.25.
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