Document Open Access Logo

Foundations of Homomorphic Secret Sharing

Authors Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, Stefano Tessaro

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.21.pdf
  • Filesize: 0.62 MB
  • 21 pages

Document Identifiers

Author Details

Elette Boyle
Niv Gilboa
Yuval Ishai
Huijia Lin
Stefano Tessaro

Cite As Get BibTex

Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro. Foundations of Homomorphic Secret Sharing. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.21

Abstract

Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open.

We initiate a systematic study of HSS, making the following contributions.

 - A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework.
 - Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by  public-key encryption or even oblivious transfer.
 - Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.

Subject Classification

Keywords
  • Cryptography
  • homomorphic secret sharing
  • secure computation
  • communication complexity
  • worst-case to average case reductions.

Metrics

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

References

  1. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC^0. In FOCS 2004, pages 166-175, 2004. Google Scholar
  2. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Computationally private randomizing polynomials and their applications. In CCC, pages 260-274, 2005. Google Scholar
  3. Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty computation with low communication, computation and interaction via threshold FHE. In EUROCRYPT, pages 483-501, 2012. Google Scholar
  4. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. Google Scholar
  5. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137-166, 2003. Google Scholar
  6. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In STOC 2017, pages 483-496, 2017. Google Scholar
  7. Omer Barkol, Yuval Ishai, and Enav Weinreb. On d-multiplicative secret sharing. J. Cryptology, 23(4):580-593, 2010. Google Scholar
  8. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov. Share conversion and private information retrieval. In CCC 2012, pages 258-268, 2012. Google Scholar
  9. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In STOC, pages 1-10, 1988. Google Scholar
  10. Josh Cohen Benaloh. Secret sharing homomorphisms: Keeping shares of A secret sharing. In CRYPTO 1986, pages 251-260, 1986. Google Scholar
  11. Fabrice Benhamouda and Huijia Lin. k-round MPC from k-round OT via garbled interactive circuits. Manuscript, 2017. Google Scholar
  12. Manuel Blum and Sampath Kannan. Designing programs that check their work. In STOC 1989, pages 86-97, 1989. Google Scholar
  13. E. Boyle, N. Gilboa, and Y. Ishai. Function secret sharing. In EUROCRYPT, pages 337-367, 2015. Google Scholar
  14. Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the circuit size barrier for secure computation under DDH. In CRYPTO, pages 509-539, 2016. Full version: IACR Cryptology ePrint Archive 2016: 585 (2016). Google Scholar
  15. Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In ACM CCS 2016, pages 1292-1303, 2016. Google Scholar
  16. Elette Boyle, Niv Gilboa, and Yuval Ishai. Group-based secure computation: Optimizing rounds, communication, and computation. In EUROCRYPT, pages 163-193, 2017. Google Scholar
  17. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput., 43(2):831-871, 2014. Google Scholar
  18. Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, pages 143-202, 2000. Google Scholar
  19. Ignacio Cascudo Pueyo, Hao Chen, Ronald Cramer, and Chaoping Xing. Asymptotically good ideal linear secret sharing with strong multiplication over Any fixed finite field. In CRYPTO, pages 466-486, 2009. Google Scholar
  20. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols. In STOC, pages 11-19, 1988. Google Scholar
  21. Hao Chen and Ronald Cramer. Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In CRYPTO, pages 521-536, 2006. Google Scholar
  22. B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. J. ACM, 45(6):965-981, 1998. Google Scholar
  23. Benny Chor and Niv Gilboa. Computationally private information retrieval (extended abstract). In STOC 1997, pages 304-313, 1997. Google Scholar
  24. Kai-Min Chung, Yael Tauman Kalai, and Salil P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In CRYPTO 2010, pages 483-501, 2010. Google Scholar
  25. Ronald Cramer, Ivan Damgård, and Ueli M. Maurer. General secure multi-party computation from any linear secret-sharing scheme. In EUROCRYPT, pages 316-334, 2000. Google Scholar
  26. Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976. Google Scholar
  27. Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs. Spooky encryption and its applications. In CRYPTO, pages 93-122, 2016. Google Scholar
  28. Z. Dvir and S. Gopi. 2-server PIR with sub-polynomial communication. In STOC, pages 577-584, 2015. Google Scholar
  29. Klim Efremenko. 3-query locally decodable codes of subexponential length. In STOC, pages 39-44, 2009. Google Scholar
  30. Nelly Fazio, Rosario Gennaro, Tahereh Jafarikhah, and William E. Skeith III. Homomorphic secret sharing from paillier encryption. In ProvSec, pages 381-399, 2017. Google Scholar
  31. Matthew K. Franklin and Moti Yung. Communication complexity of secure computation (extended abstract). In STOC, pages 699-710, 1992. Google Scholar
  32. Sanjam Garg, Craig Gentry, Shai Halevi, and Mariana Raykova. Two-round secure MPC from indistinguishability obfuscation. In TCC, pages 74-94, 2014. Google Scholar
  33. Sanjam Garg and Akshayaram Srinivasan. Garbled protocols and two round MPC from bilinear maps. In FOCS 2017, 2017. Google Scholar
  34. Sanjam Garg and Akshayaram Srinivasan. Two-round secure multiparty computation from minimal assumptions. Manuscript, 2017. Google Scholar
  35. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169-178. ACM, 2009. URL: http://dx.doi.org/10.1145/1536414.1536440.
  36. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In CRYPTO (1), pages 75-92, 2013. Google Scholar
  37. N. Gilboa and Y. Ishai. Distributed point functions and their applications. In Proc. EUROCRYPT ’14, pages 640-658, 2014. Google Scholar
  38. Oded Goldreich. Foundations of Cryptography - Basic Applications. Cambridge University Press, 2004. Google Scholar
  39. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, and Luca Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity, 15(3):263-296, 2006. Google Scholar
  40. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In STOC, pages 218-229, 1987. Google Scholar
  41. Oded Goldreich and Guy N. Rothblum. Worst-case to average-case reductions for subclasses of p. Electronic Colloquium on Computational Complexity (ECCC), 17-130, 2017. Google Scholar
  42. S. Dov Gordon, Feng-Hao Liu, and Elaine Shi. Constant-round MPC with fairness and guarantee of output delivery. In CRYPTO, Part II, pages 63-82, 2015. Google Scholar
  43. Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In ICALP, pages 244-256, 2002. Google Scholar
  44. Aayush Jain, Peter M. R. Rasmussen, and Amit Sahai. Threshold fully homomorphic encryption. IACR Cryptology ePrint Archive, 2017:257, 2017. Google Scholar
  45. Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM J. Discret. Math., 5(4), 1992. Google Scholar
  46. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In STOC, pages 80-86, 2000. Google Scholar
  47. Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci., 69(3):395-420, 2004. Google Scholar
  48. Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Computational Complexity, 8(1):21-49, 1999. Google Scholar
  49. E. Kushilevitz and R. Ostrovsky. Replication is NOT needed: SINGLE database, computationally-private information retrieval. In Proc. FOCS ’97, pages 364-373, 1997. Google Scholar
  50. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  51. Richard J. Lipton. New directions in testing. In DIMACS Workshop on Distributed Computing And Cryptography, pages 191-202, 1989. Google Scholar
  52. Pratyay Mukherjee and Daniel Wichs. Two round multiparty computation via multi-key FHE. In EUROCRYPT, pages 735-763, 2016. Google Scholar
  53. Ronald L. Rivest, Len Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169-180, 1978. Google Scholar
  54. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. Google Scholar
  55. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. Google Scholar
  56. Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 24-43. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13190-5_2.
  57. Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In FOCS, pages 162-167, 1986. Google Scholar
  58. S. Yekhanin. Towards 3-query locally decodable codes of subexponential length. In Proc. STOC, pages 266-274, 2007. 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