Document Open Access Logo

Information-Theoretic Distributed Point Functions

Authors Elette Boyle, Niv Gilboa, Yuval Ishai, Victor I. Kolobov

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.17.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Elette Boyle
  • IDC Herzliya, Israel
Niv Gilboa
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel
Yuval Ishai
  • Technion, Haifa, Israel
Victor I. Kolobov
  • Technion, Haifa, Israel

Funding

  • Boyle, Elette: Supported by AFOSR Award FA9550-21-1-0046, ERC Project HSS (852952), ERC Project NTSC (742754), and a Google Research Scholar Award.
  • Gilboa, Niv: Supported by ISF grant 2951/20, ERC grant 876110, and a grant by the BGU Cyber Center.
  • Ishai, Yuval: Supported by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20.
  • Kolobov, Victor I.: Supported by ERC Project NTSC (742754) and ISF grant 2774/20.

Cite As Get BibTex

Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor I. Kolobov. Information-Theoretic Distributed Point Functions. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITC.2022.17

Abstract

A distributed point function (DPF) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority.
We present the first statistically private 3-server DPF for domain size N with subpolynomial key size N^{o(1)}. We also present a similar perfectly private 4-server DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity and better protocols for distributed key generation, all while having comparable communication complexity for moderate-sized parameters.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
Keywords
  • Information-theoretic cryptography
  • homomorphic secret sharing
  • private information retrieval
  • secure multiparty computation

Metrics

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

References

  1. Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 503-513. ACM, 1990. URL: https://doi.org/10.1145/100216.100287.
  2. Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions. In Theory of Cryptography Conference, pages 317-342. Springer, 2014. Google Scholar
  3. Amos Beimel, Yuval Ishai, and Eyal Kushilevitz. General constructions for information-theoretic private information retrieval. J. Comput. Syst. Sci., 71(2):213-247, 2005. Google Scholar
  4. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov. Share conversion and private information retrieval. In 2012 IEEE 27th Conference on Computational Complexity, pages 258-268. IEEE, 2012. Google Scholar
  5. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and J-F Raymond. Breaking the O(n^1/(2k-1)) barrier for information-theoretic private information retrieval. In FOCS 2002, pages 261-270, 2002. Google Scholar
  6. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Oded Goldreich, editor, Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 351-371. ACM, 2019. URL: https://doi.org/10.1145/3335741.3335756.
  7. Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Lightweight techniques for private heavy hitters. In 42nd IEEE Symposium on Security and Privacy, SP 2021, pages 762-776. IEEE, 2021. Google Scholar
  8. 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 EUROCRYPT 2021, Part II, pages 871-900, 2021. Google Scholar
  9. Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 896-912, 2018. Google Scholar
  10. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In CRYPTO 2019, 2019. Google Scholar
  11. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators from ring-LPN. In Annual International Cryptology Conference, pages 387-416. Springer, 2020. Google Scholar
  12. Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing. In Eurocrypt 2015, pages 337-367, 2015. Google Scholar
  13. Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In CCS, 2016. Google Scholar
  14. Elette Boyle, Niv Gilboa, and Yuval Ishai. Secure computation with preprocessing via function secret sharing. In Theory of Cryptography Conference, pages 341-371, 2019. Google Scholar
  15. Paul Bunn, Jonathan Katz, Eyal Kushilevitz, and Rafail Ostrovsky. Efficient 3-party distributed oram. In International Conference on Security and Cryptography for Networks, pages 215-232. Springer, 2020. Google Scholar
  16. Benny Chor and Niv Gilboa. Computationally private information retrieval. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 304-313, 1997. Google Scholar
  17. Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 41-50. IEEE, 1995. Google Scholar
  18. Henry Corrigan-Gibbs, Dan Boneh, and David Mazières. Riposte: An anonymous messaging system handling millions of users. In 2015 IEEE Symposium on Security and Privacy, pages 321-338. IEEE, 2015. Google Scholar
  19. Ronald Cramer, Ivan Damgård, Daniel Escudero, Peter Scholl, and Chaoping Xing. Spdℤ_2^k : Efficient mpc mod 2^k for dishonest majority. In Annual International Cryptology Conference, pages 769-798. Springer, 2018. Google Scholar
  20. Ronald Cramer, Serge Fehr, Yuval Ishai, and Eyal Kushilevitz. Efficient multi-party computation over rings. In EUROCRYPT 2003, pages 596-613, 2003. Google Scholar
  21. Ivan Damgård and Yuval Ishai. Constant-round multiparty computation using a black-box pseudorandom generator. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, pages 378-394. Springer, 2005. URL: https://doi.org/10.1007/11535218_23.
  22. Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, and Angelos Stavrou. Function secret sharing for psi-ca: With applications to private contact tracing. arXiv preprint arXiv:2012.13053, 2020. Google Scholar
  23. Jack Doerner and Abhi Shelat. Scaling ORAM for secure computation. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 523-535, 2017. Google Scholar
  24. Zeev Dvir and Sivakanth Gopi. 2-server PIR with sub-polynomial communication. In Rocco A. Servedio and Ronitt Rubinfeld, editors, STOC 2015, pages 577-584. ACM, 2015. Google Scholar
  25. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM Journal on Computing, 41(6):1694-1703, 2012. Google Scholar
  26. Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, and Mary Wootters. On the download rate of homomorphic secret sharing. In ITCS, 2022. Google Scholar
  27. Peter Frankl. Constructing finite sets with given intersections. Combinatorial mathematics (Marseille-Luminy, 1981), pages 289-291, 1983. Google Scholar
  28. Niv Gilboa and Yuval Ishai. Distributed point functions and their applications. In EUROCRYPT, 2014. Google Scholar
  29. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game, or a completeness theorem for protocols with honest majority. In Oded Goldreich, editor, Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 307-328. ACM, 2019. URL: https://doi.org/10.1145/3335741.3335755.
  30. Vince Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica, 20(1):71-86, 2000. Google Scholar
  31. Matthew M Hong, Yuval Ishai, Victor I Kolobov, and Russell WF Lai. On computational shortcuts for information-theoretic pir. In Theory of Cryptography Conference, pages 504-534. Springer, 2020. Google Scholar
  32. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding cryptography on oblivious transfer-efficiently. In Annual international cryptology conference, pages 572-591. Springer, 2008. Google Scholar
  33. Joe Kilian. Founding cryptography on oblivious transfer. In Janos Simon, editor, STOC 1988, pages 20-31, 1988. Google Scholar
  34. Yehuda Lindell and Benny Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In Moni Naor, editor, Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings, volume 4515 of Lecture Notes in Computer Science, pages 52-78. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72540-4_4.
  35. Zachary Newman, Sacha Servan-Schreiber, and Srinivas Devadas. Spectrum: High-bandwidth anonymous broadcast. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), pages 229-248, 2022. Google Scholar
  36. Anat Paskin-Cherniavsky and Olga Nissenbaum. New bounds and a generalization for share conversion for 3-server PIR. Entropy, 24(4), 2022. URL: https://doi.org/10.3390/e24040497.
  37. Anat Paskin-Cherniavsky and Leora Schmerler. On share conversions for private information retrieval. Entropy, 21(9):826, 2019. Google Scholar
  38. Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 73-85, 1989. Google Scholar
  39. Ni Trieu, Kareem Shehata, Prateek Saxena, Reza Shokri, and Dawn Song. Epione: Lightweight contact tracing with strong privacy. arXiv preprint arXiv:2004.13293, 2020. Google Scholar
  40. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. Journal of the ACM (JACM), 55(1):1-16, 2008. Google Scholar
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 About DROPS Imprint Privacy Contact