License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.26
URN: urn:nbn:de:0030-drops-143455
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14345/
Go to the corresponding LIPIcs Volume Portal

Schul-Ganz, Gili ; Segev, Gil

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

pdf-format:
LIPIcs-ITC-2021-26.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{schulganz_et_al:LIPIcs.ITC.2021.26,
  author =	{Schul-Ganz, Gili and Segev, Gil},
  title =	{{Generic-Group Identity-Based Encryption: A Tight Impossibility Result}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{26:1--26:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14345},
  URN =		{urn:nbn:de:0030-drops-143455},
  doi =		{10.4230/LIPIcs.ITC.2021.26},
  annote =	{Keywords: Identity-based encryption, generic-group model}
}

Keywords: Identity-based encryption, generic-group model
Collection: 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Issue Date: 2021
Date of publication: 19.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI