Document Open Access Logo

Generic-Group Identity-Based Encryption: A Tight Impossibility Result

Authors Gili Schul-Ganz, Gil Segev

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.26.pdf
  • Filesize: 0.78 MB
  • 23 pages

Document Identifiers

Author Details

Gili Schul-Ganz
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel
Gil Segev
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel

Funding

Supported by the European Union’s Horizon 2020 Framework Program (H2020) via an ERC Grant (Grant No. 714253).

Cite As Get BibTex

Gili Schul-Ganz and Gil Segev. Generic-Group Identity-Based Encryption: A Tight Impossibility Result. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITC.2021.26

Abstract

Following the pioneering work of Boneh and Franklin (CRYPTO '01), the challenge of constructing an identity-based encryption scheme based on the Diffie-Hellman assumption remained unresolved for more than 15 years. Evidence supporting this lack of success was provided by Papakonstantinou, Rackoff and Vahlis (ePrint '12), who ruled out the existence of generic-group identity-based encryption schemes supporting an identity space of sufficiently large polynomial size. Nevertheless, the breakthrough result of Döttling and Garg (CRYPTO '17) settled this long-standing challenge via a non-generic construction.
We prove a tight impossibility result for generic-group identity-based encryption, ruling out the existence of any non-trivial construction: We show that any scheme whose public parameters include n_pp group elements may support at most n_pp identities. This threshold is trivially met by any generic-group public-key encryption scheme whose public keys consist of a single group element (e.g., ElGamal encryption). 
In the context of algebraic constructions, generic realizations are often both conceptually simpler and more efficient than non-generic ones. Thus, identifying exact thresholds for the limitations of generic groups is not only of theoretical significance but may in fact have practical implications when considering concrete security parameters.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
  • Theory of computation → Cryptographic primitives
Keywords
  • Identity-based encryption
  • generic-group model

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. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62-73, 1993. Google Scholar
  3. 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
  4. Dan Boneh and Xavier Boyen. Secure identity based encryption without random oracles. In Advances in Cryptology - CRYPTO '04, pages 443-459, 2004. Google Scholar
  5. Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. In Advances in Cryptology - CRYPTO '01, pages 213-229, 2001. Google Scholar
  6. Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis, and Brent Waters. On the impossibility of basing identity based encryption on trapdoor permutations. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 283-292, 2008. Google Scholar
  7. Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. In Advances in Cryptology - EUROCRYPT '03, pages 255-271, 2003. Google Scholar
  8. David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In Advances in Cryptology - EUROCRYPT '10, pages 523-552, 2010. Google Scholar
  9. 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
  10. Nico Döttling and Sanjam Garg. From selective IBE to full IBE and selective HIBE. In Proceedings of the 15th Theory of Cryptography Conference, pages 372-408, 2017. Google Scholar
  11. Nico Döttling and Sanjam Garg. Identity-based encryption from the Diffie-Hellman assumption. In Advances in Cryptology - CRYPTO '17, pages 537-569, 2017. Google Scholar
  12. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of computing, pages 197-206, 2008. Google Scholar
  13. Tibor Jager and Jörg Schwenk. On the equivalence of generic group models. In Proceedings of the 2nd International Conference on Provable Security, pages 200-209, 2008. Google Scholar
  14. Ueli Maurer. Abstract models of computation in cryptography. In Proceedings of the 10th IMA International Conference on Cryptography and Coding, pages 1-12, 2005. Google Scholar
  15. Periklis A. Papakonstantinou, Charles W. Rackoff, and Yevgeniy Vahlis. How powerful are the DDH hard groups? Cryptology ePrint Archive, Report 2012/653, 2012. Google Scholar
  16. Adi Shamir. Identity-based cryptosystems and signature schemes. In Advances in Cryptology - CRYPTO '84, pages 47-53, 1984. Google Scholar
  17. Victor Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology - EUROCRYPT '97, pages 256-266, 1997. Google Scholar
  18. Brent Waters. Efficient identity-based encryption without random oracles. In Advances in Cryptology - EUROCRYPT '05, pages 114-127, 2005. 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