Document Open Access Logo

Hierarchical Functional Encryption

Authors Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai, Gil Segev

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.8.pdf
  • Filesize: 0.72 MB
  • 27 pages

Document Identifiers

Author Details

Zvika Brakerski
Nishanth Chandran
Vipul Goyal
Aayush Jain
Amit Sahai
Gil Segev

Cite AsGet BibTex

Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai, and Gil Segev. Hierarchical Functional Encryption. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 8:1-8:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.8

Abstract

Functional encryption provides fine-grained access control for encrypted data, allowing each user to learn only specific functions of the encrypted data. We study the notion of hierarchical functional encryption, which augments functional encryption with delegation capabilities, offering significantly more expressive access control. We present a generic transformation that converts any general-purpose public-key functional encryption scheme into a hierarchical one without relying on any additional assumptions. This significantly refines our understanding of the power of functional encryption, showing that the existence of functional encryption is equivalent to that of its hierarchical generalization. Instantiating our transformation with the existing functional encryption schemes yields a variety of hierarchical schemes offering various trade-offs between their delegation capabilities (i.e., the depth and width of their hierarchical structures) and underlying assumptions. When starting with a scheme secure against an unbounded number of collusions, we can support arbitrary hierarchical structures. In addition, even when starting with schemes that are secure against a bounded number of collusions (which are known to exist under rather minimal assumptions such as the existence of public-key encryption and shallow pseudorandom generators), we can support hierarchical structures of bounded depth and width.
Keywords
  • Functional Encryption
  • Delegatable Encryption
  • Cryptography

Metrics

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

References

  1. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice (H)IBE in the standard model. In Advances in Cryptology - EUROCRYPT'10, pages 553-572, 2010. Google Scholar
  2. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In Advances in Cryptology - CRYPTO'10, pages 98-115, 2010. Google Scholar
  3. Shweta Agrawal, Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Functional encryption: New perspectives and lower bounds. In Advances in Cryptology - CRYPTO'13, pages 500-518, 2013. Google Scholar
  4. Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry. Differing-inputs obfuscation and applications. Cryptology ePrint Archive, Report 2013/689, 2013. Google Scholar
  5. Prabhanjan Ananth, Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan. From selective to adaptive security in functional encryption. In Advances in Cryptology - CRYPTO'15, pages 657-677, 2015. Google Scholar
  6. Prabhanjan Ananth and Abhishek Jain. Indistinguishability obfuscation from compact functional encryption. In Advances in Cryptology - CRYPTO'15, pages 308-326, 2015. Google Scholar
  7. Gilad Asharov and Gil Segev. Limits on the power of indistinguishability obfuscation and functional encryption. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 191-209, 2015. Google Scholar
  8. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. Journal of the ACM, 59(2):6, 2012. Google Scholar
  9. Mihir Bellare and Adam O'Neill. Semantically-secure functional encryption: Possibility results, impossibility results and the quest for a general definition. In Proceedings of the 12th International Conference on Cryptology and Network Security, pages 218-234, 2013. Google Scholar
  10. Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation from functional encryption. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 171-190, 2015. Google Scholar
  11. Dan Boneh and Xavier Boyen. Efficient selective-ID secure identity-based encryption without random oracles. In Advances in Cryptology - EUROCRYPT'04, pages 223-238, 2004. Google Scholar
  12. Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. In Advances in Cryptology - EUROCRYPT'05, pages 440-456, 2005. Google Scholar
  13. Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. SIAM Journal on Computing, 32(3):586-615, 2003. Preliminary version in Advances in Cryptology - CRYPTO'01, pages 213-229, 2001. Google Scholar
  14. Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In Advances in Cryptology - EUROCRYPT'14, pages 533-556, 2014. Google Scholar
  15. Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: Definitions and challenges. In Proceedings of the 8th Theory of Cryptography Conference, pages 253-273, 2011. Google Scholar
  16. Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: a new vision for public-key cryptography. Communications of the ACM, 55(11):56-64, 2012. Google Scholar
  17. Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Advances in Cryptology - ASIACRYPT'13, pages 280-300, 2013. Google Scholar
  18. Xavier Boyen and Brent Waters. Anonymous hierarchical identity-based encryption (without random oracles). In Advances in Cryptology - CRYPTO'06, pages 290-307, 2006. Google Scholar
  19. Elette Boyle, Kai-Min Chung, and Rafael Pass. On extractability obfuscation. In Proceedings of the 11th Theory of Cryptography Conference, pages 52-73, 2014. Google Scholar
  20. Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography, pages 501-519, 2014. Google Scholar
  21. Zvika Brakerski, Ilan Komargodski, and Gil Segev. Multi-input functional encryption in the private-key setting: Stronger security from weaker assumptions. In Advances in Cryptology - EUROCRYPT'16, pages 852-880, 2016. Google Scholar
  22. Zvika Brakerski and Gil Segev. Function-private functional encryption in the private-key setting. In Proceedings of the 12th Theory of Cryptography Conference, pages 306-324, 2015. Google Scholar
  23. Zvika Brakerski and Gil Segev. Hierarchical functional encryption. Cryptology ePrint Archive, Report 2015/1011, 2015. Google Scholar
  24. David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. Journal of Cryptology, 25(4):601-639, 2012. Google Scholar
  25. Nishanth Chandran, Vipul Goyal, Aayush Jain, and Amit Sahai. Functional encryption: Decentralised and delegatable. Cryptology ePrint Archive, Report 2015/1017, 2015. Google Scholar
  26. Jie Chen and Hoeteck Wee. Semi-adaptive attribute-based encryption and improved delegation for Boolean formula. In Proceedings of the 9th International Conference on Security and Cryptography for Networks, pages 277-297, 2014. Google Scholar
  27. Clifford Cocks. An identity based encryption scheme based on quadratic residues. In Proceedings of the 8th IMA International Conference on Cryptography and Coding, pages 360-363, 2001. Google Scholar
  28. Ronald Cramer, Ivan Damgård, and Yuval Ishai. Share conversion, pseudorandom secret-sharing and applications to secure computation. In Proceedings of the 2nd Theory of Cryptography Conference, pages 342-362, 2005. Google Scholar
  29. Angelo De Caro, Vincenzo Iovino, Abhishek Jain, Adam O'Neill, Omer Paneth, and Giuseppe Persiano. On the achievability of simulation-based security for functional encryption. In Advances in Cryptology - CRYPTO'13, pages 519-535, 2013. Google Scholar
  30. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 40-49, 2013. Google Scholar
  31. Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs. On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input. In Advances in Cryptology - CRYPTO'14, pages 518-535, 2014. Google Scholar
  32. Sanjam Garg, Craig Gentry, Shai Halevi, and Mark Zhandry. Functional encryption without obfuscation. In Proceedings of the 1th Theory of Cryptography Conference, pages 480-511, 2016. Google Scholar
  33. Craig Gentry and Shai Halevi. Hierarchical identity based encryption with polynomially many levels. In Proceedings of the 6th Theory of Cryptography Conference, pages 437-456, 2009. Google Scholar
  34. Craig Gentry and Alice Silverberg. Hierarchical ID-based cryptography. In Advances in Cryptology - ASIACRYPT'02, pages 548-566, 2002. Google Scholar
  35. Oded Goldreich. Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. Google Scholar
  36. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, 1986. Google Scholar
  37. Shafi Goldwasser, Yael Kalai, Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. Reusable garbled circuits and succinct functional encryption. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 555-564, 2013. Google Scholar
  38. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Functional encryption with bounded collusions via multi-party computation. In Advances in Cryptology - CRYPTO'12, pages 162-179, 2012. Google Scholar
  39. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Attribute-based encryption for circuits. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 545-554, 2013. Google Scholar
  40. Jeremy Horwitz and Ben Lynn. Toward hierarchical identity-based encryption. In Advances in Cryptology - EUROCRYPT'02, pages 466-481, 2002. Google Scholar
  41. Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Proceedings of the 20th Annual ACM Conference on Computer and Communications Security, pages 669-684, 2013. Google Scholar
  42. Ilan Komargodski, Gil Segev, and Eylon Yogev. Functional encryption for randomized functionalities in the private-key setting from minimal assumptions. In Proceedings of the 12th Theory of Cryptography Conference, pages 352-377, 2015. Google Scholar
  43. Allison B. Lewko, Tatsuaki Okamoto, Amit Sahai, Katsuyuki Takashima, and Brent Waters. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In Advances in Cryptology - EUROCRYPT'10, pages 62-91, 2010. Google Scholar
  44. Allison B. Lewko and Brent Waters. New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In Poceedings of the 7th Theory of Cryptography Conference, pages 455-479, 2010. Google Scholar
  45. Allison B. Lewko and Brent Waters. Unbounded HIBE and attribute-based encryption. In Advances in Cryptology - EUROCRYPT'11, pages 547-567, 2011. Google Scholar
  46. Allison B. Lewko and Brent Waters. Why proving HIBE systems secure is difficult. In Advances in Cryptology - EUROCRYPT'14, pages 58-76, 2014. Google Scholar
  47. Pratyay Mukherjee and Daniel Wichs. Two round multiparty computation via multi-key FHE. In Advances in Cryptology - EUROCRYPT'16, pages 735-763, 2016. Google Scholar
  48. Adam O'Neill. Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556, 2010. Google Scholar
  49. Amit Sahai and Brent Waters. Slides on functional encryption. Available at http://www.cs.utexas.edu/~bwaters/presentations/files/functional.ppt, 2008.
  50. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 475-484, 2014. Google Scholar
  51. Adi Shamir. Identity-based cryptosystems and signature schemes. In Advances in Cryptology - CRYPTO'84, pages 47-53, 1984. Google Scholar
  52. Brent Waters. Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In Advances in Cryptology - CRYPTO'09, pages 619-636, 2009. Google Scholar
  53. Brent Waters. A punctured programming approach to adaptively secure functional encryption. In Advances in Cryptology - CRYPTO'15, pages 678-697, 2015. 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 Imprint Privacy Contact