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_{\sf pp}$ group elements may support at most $n_{\sf 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.
Category / Keywords: foundations / Generic-group model; Identity-based encryption Original Publication (in the same form): ITC 2021 Date: received 3 Jun 2021 Contact author: gili schul at cs huji ac il, segev at cs huji ac il Available format(s): PDF | BibTeX Citation Version: 20210607:062607 (All versions of this report) Short URL: ia.cr/2021/745