Since the seminal work of Diffie and Hellman [DH76], group-based cryptosystems have become a cornerstone of modern cryptography, enabling secure key exchange, public key encryption, digital signatures, and many more. Building on this f oundation, various types of cryptographic groups have been proposed, including multiplicative groups [DH76,ElG85], elliptic curve (EC) groups [Mil86,Kob87], and pairing-friendly groups [FR94,BGOS07], all of which play crucial roles in constructing c ryptographic schemes and protocols.
In practical group-based cryptosystems, the length of group encodings plays a crucial role in efficiency, particularly affecting communication complexity. At equivalent security levels, groups with more compact encodings are typically preferred for implementation. NIST SP 800-186 [CMR+23] lists several recommended curves with 128-bit security, including Curve 25519, an elliptic curve defined over a 255-bit prime field. With standard point compression, a group element on Curve 25519 can be encoded in 256 bits (255 bits plus 1 for sign). Because EC groups generally offer more compact encodings at the same security level, they are widely favored for practical cryptographic constructions.
Importantly, EC groups always have admissible encodings; see [BF03,Ica09,BCI+10,LPS23]. Admissible encodings are broadly defined as efficiently computable functions that map from Z pfoot_0 to group elements, satisfying two key properties: regularity (having constant preimage sizes) and preimagecomputability (enabling efficient computation of all preimages for a given element in the range). These encodings enable the oblivious sampling of group elements without revealing their discrete logarithms, a critical feature for many group-based cryptosystems [BF03,BBB+18,MR19].
However, a fundamental limitation arises when attempting to prove the security of group-based cryptosystems-the inability to establish the unconditional hardness of the underlying computational assumptions (e.g., discrete logarithm, computational or decisional Diffie-Hellman) for any specific group. Over the past few decades, researchers have explored various approaches to establishing lower bounds on computational hardness, with the most prevalent method being the generic group model (GGM), where algorithms are limited to performing only generic group operations.
Roughly speaking, there are two widely accepted versions of t he generic group model: Maurer's GGM [Mau05] and Shoup's GGM [Sho97]. Maurer's GGM is modeled as a stateful system where algorithms make queries by referencing two group elements encountered during the computation (e.g., the 5th and 9th elements). In contrast, Shoup's GGM is modeled as a random injection from the additive group Z N to sufficiently long strings, where algorithms specify queries by providing two previously encountered strings from the computation.
Although both formulations appear in the literature, Maurer's GGM is generally viewed as more restrictive. In particular, digital-signature schemes are impossible in Maurer's GGM [DHH+21], and foundational constructions such as the Blum-Micali pseudorandom generator and the Goldreich-Goldwasser-Micali pseudorandom function cannot be realized in this model [Zha22]. For these reasons, we focus exclusiv ely on Shoup's GGM.
In Shoup's GGM, the length of group encodings also plays a significant role. Numerous applications (e.g., [Gro16,Zha22,HMQS23,LZ24]) within this model rely on the requirement that algorithms cannot produce valid group elements without querying the oracle. To uphold this property, the generic group model must employ sparse encodings, making the sparse GGM a critical component of Shoup's framework. How ever, sparse GGM does not support oblivious sampling, which implies that admissible encodings are effectively absent in sparse GGM!
Attention is still needed! A potential gap arises between sparse variant of Shoup's GGM and practical cryptographic groups, such as elliptic curve groups or other dense g roups. Therefore, we plan to conduct further exploration of Shoup's GGM, leading to the following research question:
Can sparse GGM effectively and accurately model elliptic curve groups or other dense cryptographic groups?
In this work, we answer the question above negatively. Specifically, let G be a cryptographic group such that: (1) computational Diffie-Hellman (CDH) is assumed to hold with respect to G; (2) the group enco dings are dense or the group is associated with nice admissible encodings. Then G does not exist in the sparse GGM unconditionally.
In order to understand our results better, we start with a brief explanation of several important concepts including (1) sparse generic group models (GGMs), (2) dense groups, and (3) groups with nice admissible encodings. Let λ be the security parameter, -Sparse and dense GGMs. We say GGM G is sparse if the GGM represents a random injection from Z N to S, where N is a λ-bit prime, S = {0, 1} m , and the difference mλ satisfying mλ ≥ ω(log λ). Conversely, we say the GGM G is dense if the difference mλ ≤ Θ(log λ).
-Sparse and dense group encodings. Similarly, we say a cryptographic group G of order N is sparse if the length of its group encodings, denoted by m, satisfies mλ ≥ ω(log λ), and we say the group is dense if mλ ≤ Θ(log λ). -Groups with nice admissible encodings. We define a group G of order N to have a nice admissible encoding with respect to a constant and a polynomial poly AE if there exists an efficiently computable function AE : Z p → G satisfying the following conditions: (1) the preimage of any group element under AE is efficiently computable; (2) the encoding is -regular, meaning the size of any preimage set is at most ; (3) the domain size p is sufficiently large, i.e., p N ≥ poly AE . As shown in [Ica09], all elliptic curve groups satisfy these conditions with = 4, and are therefore considered groups with nice admissible encodings.
As previously discussed, the sparse GGM does not provide an admissible encoding. We argue that this limitation is an inherent drawback of the sparse GGM and proceed to establish a black-box separation between CDH-secure groups with admissible encodings and the sparse GGM.
Theorem 1.1 (Informal). For any constant , CDH-secure groups with admissible encodings with respect to do not exist in the sparse generic group model.
We now turn our attention to the dense groups. Intuitively, the encodings in sparse GGM cannot be compressed in a generic manner and we demonstrate that this limitation represents another inheren t drawback of the sparse GGM and proceed to establish a black-box separation between CDH-secure dense groups and the sparse GGM.
Theorem 1.2 (Informal). CDH-secure dense groups do not exist in the sparse generic group model. Remark 1.1. In [JZW+24], Ji et al. investigate the relationship between CDHsecure groups with varying lengths of group encodings and demonstrate that shorter CDH-secure groups are separated from longer GGMs. However, we highlight that their analysis heavily depends on the assumption that both the groups and the GGM share the same security parameter-a condition we believe is not fully justified. In contrast, our results establish the black-box separation between dense groups and sparse GGM, resolving the open problem posed in [JZW+24].
We further argue that the inherent difficulty in constructing groups with admissible encodings or dense groups persists as long as the idealized model remains sparse, even when the model is extended to the generic bilinear group model (GBM). The GBM B models two generic groups, i.e., the source generic group and the target generic group, and we say B is sparse if both the source generic group and the target generic group are sparse. We then establish black-box separations between CDH-secure g roups with admissible encodings (CDH-secure dense groups) and the sparse GBM.
For any constant , CDH-secure groups with admissible encodings with respect to do es not exist in the sparse generic bilinear group model.
Theorem 1.4 (Informal). CDH-secure dense groups do not exist in the sp arse generic bilinear group model. Groth and Shoup [GS22] introduce a variant of the GGM, known as the elliptic curve generic group model (EC-GGM). Let E be the set of all points on an elliptic curve group of order N . The EC-GGM models a random injection from Z N to E, while preserving certain structural properties inherent t o elliptic curvesfor instance, the preservation of which points share the same x-coordinate. It follows that CDH-secure groups with nice admissible encodings exist relative to the EC-GGM.
Theorem 1.5 (Informal). CDH-secure groups with nice admissible encodings exist in the elliptic curve generic group model.
We next study the relationship between the EC-GGM and the sparse GGM in the f ramework of indifferentiability. Following Zhang and Zhandry's analysis [ZZ23], we explore the relationship against computationally bounded adve rsary and prove that: Theorem 1.6 (Informal). In the framework of indifferentiability, EC-GGM is strictly stronger than sparse GGM.
Remark 1.2. In [JZW+24], Ji et al. also prove that, within the framework of indifferentiability, the dense GGM is strictly stronger than the sparse GGM. However, we stress that their analysis also highly depends on the assumption that both the dense GGM and the sparse GGM share the same se curity parameter, which we believe is not fully justified. In contrast, our separation between the dense GGM and the sparse GGM is unconditional.
Theorem 1.7 (Informal). CDH-secure dense groups e xist in the dense GGM.
Shoup's GGM serves as the foundation for the group-based cryptosystems. Our findings show that extreme caution must be taken when proving security or establishing black-box separations within Shoup's GGM. We next elaborate it from two perspectives.
Instantiating the GGM with Elliptic Curve Groups. In the generic group model, algorithms are required to be generic. However, not all algorithms for group-based assumptions, such as the discrete logarithm problem, adhere to this requirement-for example, the index calculus attack against Z * N [Adl79]. Fortunately, in the case of elliptic curve groups, the only known attacks are generic in nature. As a result, the generic group model is typically instantiated using elliptic curve groups. H owever, to the best of our knowledge, in many practical cryptographic constructions (e.g., the zk-SNARKs in [Gro16]), the generic group model is often treated as a sparse GGM, where adversaries are restricted from obtaining valid group elements without making explicit queries. Furthermore, as shown in [Ica09], all elliptic curve groups fall into the category o f groups with nice admissible encodings.
Our results establish a black-box separation between CDH-secure groups with admissible encodings and the sparse GGM, highlighting a potential and previously overlooked gap when instantiating the GGM with elliptic curve groups.
Black-Box Separations within the GGM. The generic group model is used to demonstrate the limitations o f certain group-based cryptosystems. Notably, most known separations [Zha22,HMQS23] are established within sparse GGM. Our findings highlight important limitations of the black-box impossibility of sparse GGM, as it excludes both CDH-secure groups with nice admissible encodings and CDH-secure dense groups. Consequently, the relativizing separation between these groups and identity-based encryption (IBE) r emains unresolved. Since many practical groups used fall under the category of groups with nice admissible encodings, our results motivate the further study of the complexity of such groups.
Furthermore, our findings indicate that, when examined in a fine-grained manner, the relationship between the GGM and the GBM must be reinterpreted. Specifically, Zhang and Zhandry [ZZ23] demonstrate that the GBM is strictly stronger than the GGM. In contrast, our results reveal that EC-GGM (or dense GGM) and sparse GBM are, in fact, incomparable.
In conclusion, our results encourage further investigation into both the construction of practical schemes and the establishment of black-box separations within the EC-GGM (or dense GGM). Additionally, our findings offer a deeper understanding of the complexities in GGMs and GBMs.
We now provide an overview of the core intuition and no velty behind our techniques.
To demonstrate the impossibility of a cryptographic primitive P within an idealized model O, we typically employ the black-box separation methodology. Specifically, for any instantiation Π O of P, we construct a computationally unbounded adversary A such that (1) A breaks the security of Π O ; and (2) A is query-efficient. The seminal result of Impagliazzo and Rudich [IR89], tells that the key agreement primitive cannot exist in the random oracle model (ROM). Specifically, for any protocol in this model, there exists an adversary capable of winning in a key recovery attack (KRA), which breaks the fundamental security requirement for key agreement. Returning to our context, it is important to note that CDH-secure groups with admissible enco dings inherently imply KRA-secure key agreement (e.g., the Diffie-Hellman key exchange protocol). Therefore, if we could establish that KRA-secure key agreement is impossible in sparse GGM, the analysis would be complete.
For clarity of elaboration, we focus our analysis on a particular case of the key agreement primitive, i.e., the non-interactive key exchange (NIKE). We begin by briefly reviewing t he key concepts behind the impossibility of KRA-secure NIKE in the random oracle model [IR89,BKSY11], and then proceed to integrate those insigh ts into our analysis.
Let Π H := (KGen H , SHK H ) be a NIKE scheme in the random oracle model H, where (1) Π H achieves perfect correctness, and (2) both KGen and SHK make at most q queries. Consider Alice and Bob as two honest parties, each associated with public keys pk 1 and pk 2 , respectively. We then construct an adversary A that, given pk 1 and pk 2 , o utputs the valid shared key with a good probability. Specifically, the adversary A initializes two empty sets S que-res and S key , and then proceeds through 4q + 1 iterations of the following phases:
-Simulation. Simulate a proper view for Alice. Specifically, this view contains a set of query/response pairs SA along with a private k ey sk 1 such that: (1) SA is consistent with S que-resfoot_3 ; and (2) this view induces the correct public key for Alice: KGen SA∪Sque-res (sk 1 ) = pk 1 . Next, compute the shared key based on the simulated view, i.e., shk = SHK ˜ SA∪Sque-res (sk 1 , pk 2 ), and insert shk into the set S key .
-Update. Update all queries in SA \ S que-res by accessing the random oracle H, and add the corresp onding query/response pairs into the set S que-res .
Finally, A outputs the majority of the shared keys f rom the set S key . Next, we outline the key intuition behind why A is likely to win in the KRAsecure game with a good probability. Let S Bob denote the set of query/response pairs made by B ob during the real execution of the key exchange protocol. For any iteration, there are two cases:
Observe that case 1 can occur in at most 2q iterations, as |S Bob | ≤ 2q. Once this case takes place, the update phase will absorb at least one pair (que B , res B ) ∈ S Bob into S que-res . For case 2, we note that when it occurs, there exists an alternate oracle H that remains consistent with both SA and S Bob . Due to p erfect correctness, the shared key computed during that iteration is guaranteed to be valid. Furthermore, since case 2 occurs in at least 2q + 1 iterations, this ensures that the majority of keys in S key are valid. However, in the case of GGM, the attack fails immediately, as the GGM itself implies the KRA-secure N IKE. Next, we explain the reasoning behind the failure of the attack.
In contrast to the ROM, the GGM features two types of queries: labeling queries (e.g., x, G(x)) and addition queries (e.g., G(x), G(y), G(x + y)). Hence, to guarantee the validity of the shared key, we should define S Bob to include all group encodings p resent in the queries (both labeling and addition) along with their corresponding discrete logarithms (which Bob may not know). Consequently, for any iteration, there are three cases:
-Case 1 (Bad):
que A = que B then res A = res B , and vice versa.
Observe that case 1 and case 3 can be handled similarly as above. However, case 2 may always occur, meaning it is impossible to find a GGM instance that is consistent with both SA and S Bob . This implies the aforementioned attack fails.
Upon further exploration, we observe that the occurrence of case 2 indicates that the adversary is able to generate a valid group element without knowing its discrete logarithm, i.e., without making labeling queries. Therefore, to advance the analysis, it is necessary to handle the NIKE and GGM with a more finegrained approach, ensuring that no query-efficient adversary can generate a valid group element without knowing its discrete logarithm. Specifically, the analysis aims to identify a hard problem related to the fine-grained NIKE and GGM, and prove that if an adversary, given the public keys pk 1 and pk 2 , succeeds in outputting a valid group element without making queries, then the hard problem does not hold anymore.
Solution in [JZW+24] and Its Limitations. Recently,Ji et.al. [JZW+24] demonstrated that CDH-secure cryptographic groups with shorter group descriptions cannot exist in the generic group model with longer encodings. Specifically, they establish a somewhat black-box separation b etween KRA-secure NIKE schemes associated with shorter public keys and the GGMs with longer group encodings 3 . The key idea in their work is that, given the public keys pk 1 and 3 The formal primitive can be trivially constructed via shorter CDH-secure groups.
pk 2 , the extracted group element str can fall into one of two cases: (1) str is related to both pk 1 and pk 2 ; or (2) str is related to only one of the public keys but independent of the other. In the former case, Ji et.al. explain that str is typically a frequent query, which can be easily handled by repeatedly running the key generation algorithm on sufficiently many random inputs. In the latter case, where str is only relevant to only one public key (e.g., pk 1 ), they observe that pk 1 is the sole carrier of information about str. However, since the length of pk 1 is significantly shorter than that of str, it lacks the necessary capacity to encode all the information required for the recovery of str. Consequently, no query-efficient algorithm can extract str with a non-negligible probability.
Furthermore, the hard problem identified in [JZW+24] can be interpreted as follows: given any public key (which is shorter), no query-efficient algorithm can extract a valid group element (which is longer) except with negligible probability.
However, the hard problem in [JZW+24] faces an inherent limitation. Specifically, it holds only if the length of pk 1 is significantly shorter than that of str. This condition is guaranteed when both the KRA-secure NIKE and the GGM share the same security parameter. However, if NIKE and the GGM are associated with different security parameters, this condition may no longer hold. Exploring deeper, we observe that the reason for this limitation lies in the fact that "shorter" and "longer" are relative terms with respect to the security parameter. A public key considered "shorter" under a large security parameter may still carry enough information to extract a "longer" GGM encoding when the security parameter is small. Therefore, we argue that the hard problem in [JZW+24] is based on an unjustified assumption, and their analysis deviates from the conventional black-box separationfoot_4 .
Our Techniques. To establish a black-box separation between groups with nice admissible encodings and sparse GGMs, it is essential to identify a new and unconditional hard problem. We leverage the sparseness property of the GGM and define the hard problem as follows: for any query-efficient algorithm with access to the sparse GGM, which only receives the security parameter as input, it cannot output a new and valid group element except with negligible probabilityfoot_5 . By saying that a group element str is new, we mean that: (1) str has been used as an input in some addition queries made by t he algorithm, and (2) str has not appeared as the output of any prior queries. As discussed in [Zha22], the hardness of this problem holds unconditionally. Next we elaborate on the high-level strategy for int ergrating this hard problem into the black-box separation.
Roughly speaking, we show that if the adversary A, given inputs pk 1 and pk 2 , is able to generate a new group element with a good probability, then we can construct an extractor E which, given only the security parameter as input, can also output a new group element with a good probability.
The first technical challenge of our analysis is determining how the extractor E generates the tw o public keys. A natural approach would be:
Step 1: E randomly selects two private keys (sk 1 and sk 2 ), computes the corresponding public keys (pk i = KGen G (sk i )), and runs A G (pk 1 , pk 2 ).
Step 2: Whenever A issues an addition query using a new group element (denoted as str) as input, E outputs str.
Unfortunately, this approach fails immediately. Given the fact that the GGM is sparse, any new group element str generated by A should be related to either pk 1 or pk 2 . More precisely, str is likely to appear during the execution of KGen G (sk 1 ) or KGen G (sk 2 ) with high probability. As a result, if following the aforementioned approach, then the extractor would fail to output a new group element, even if A does so.
To overcome this challenge, we must adopt an alternative method for generating the public keys, leveraging admissible encodings as part of the solution. Specifically, we configure the NIKE as a KRA-secure NIKE with nice admissible encodings, meaning there exists an admissible encoding that maps from Z p to the public keys, where p is sufficiently large. Clearly, CDH-secure groups with nice admissible encodings implies such a NIKE. We then construct the extractor E as follows:
Step 1: E randomly selects two seeds (seed 1 and seed 2 ), computes the corresponding public keys via admissible encodings (pk i = AE G (seed i )), and runs A G (pk 1 , pk 2 ).
Step 2: Whenever A issues an addition query using a new group element (denoted as str) as input, E outputs str.
At this point, the second technical challenge emerges. Specifically, let S AE denote the set of the query/response pairs that arise during the execution of pk 1 = AE G (seed 1 ) and pk 2 = AE G (seed 2 ). Note that if the new group element generated b y the adversary A consistently falls within the set S AE , the extractor above will still fail to output a new group element.
To address this challenge, we refine the adversary's strategy. Specifically, we introduce a prepro cessing phase for the adversary, define as follows:
-Preprocessing. Given the inputs pk 1 and pk 2 , the adversary A runs the inverse of the admissible encodings, computing seed i = inv-AE G (pk i ). Subsequently, A recalculates pk i = AE G ( seed i ) and collects all associated query/response pairs into the set S que-res .
The adversary then proceeds as follows: before entering the iteration phase, it first executes the preprocessing phase.
Next, we explain why the preprocessing phase is effective. It is important to note that, following the preprocessing phase, the adversary A has already gathered all the query/response pairs contained in S AE . As a result, whenever A generates a new group element, it will also be new to E.
The above outline is not comprehensive; for detailed tec hnical explanations, please refer to Sect. 3.
The key idea of our analysis is that valid public keys can be generated through two distinct methods. In the context of NIKE with dense encodings, there are likewise two methods for generating public keys, one of which even does not require making any queries. Thus, our analysis can be naturally extended to establish a black-box separation between CDH-secure dense groups and sparse GGM. Furthermore, the hard problem above remains valid within the sparse generic bilinear group model (GBM), allowing all impossibility results to naturally extend to the sparse GBM as well.
To demonstrate that the elliptic curve generic group model (EC-GGM) is strictly stronger than the sparse generic group model (sparse GGM), we frame our goal within framework of indifferentiability. In particular, we establish t hat EC-GGM (denoted as ec-G) statistically implies sparse GGM (denoted as G); while the sparse GGM does not computationally imply EC-GGM.
We begin by explaining how ec-G implies G against statistical adversaries. Let ec-G = (ec-G L , ec-G A ) denote an EC-GGM corresponding to an elliptic curve defined over Z p , where each group element is represented as (u, b) ∈ Z p × {0, 1}. According to the Hasse bound, the encoding of EC-GGM is inherently dense. To extend the encoding length to m bits for the sparse GGM, we in troduce an additional oracle, the random permutation Perm over {0, 1} m , along with its inverse, Perm Inv . The labeling function is then defined as follows:
The addition algorithm is constructed by applying the inverse oracle Perm Inv . To demonstrate indifferentiability, we need to construct a simulator S that, with access to G, can accurately simulate both ec-G and (Perm, Perm Inv ).
To simulate ec-G, the simulator maintains a tabel to record the correspondence between the elliptic curve points P := (u, b) and str := G(x). An important property of the EC-GGM is that for any (u, b) ← ec-G L (x) and (u , b ) ← ec-G L (-x), it holds that u = u and b = 1b . Consequently, whenever the simulator records the tuple (P, str), where P := (u, b) and str := G(x), it additionally records (-P, G(-x)) with -P := (u, 1b). Notably, G(-x) can be obtained by making additional queries to G on str, even without knowledge of x.
To simulate Perm, the simulator S first checks whether the query corresponds to an elliptic curve point and whether there exists a corresponding G(x). If both conditions are satisfied, S just responds with G. If not, S responds with G(x) for a randomly sampled x ∈ Z N or with a randomly chosen invalid string str, depending on whether the query corresponds to a valid point. The simulation of Perm Inv follows a similar strategy.
Remark 1.3. Careful readers might argue that, within the elliptic curve generic group model, adversaries could perform certain non-generic operations, such as oblivious sampling. As a result, EC-GGM extends the adversaries' capabilities, necessitating a reinterpretation of the hardness of certain security assumptions (e.g., DLOG or CDH).
Fortunately, due to statistical indifferentiability, the hardness of the CDH assumption remains intact. Specifically, we demonstrate that if a statistical yet query-efficient adversary exists that can break CDH in EC-GGM, we can construct a differentiator capable of breaking indifferentiability. More precisely, the differentiator acts as the challenger in the CDH game, interacts with the adversary, and distinguishes between the real and ideal worlds by observing whether the adversary successfully wins the CDH game.
Next, we demonstrate that even in the context of computationally bounded adversaries, it is not possible to construct an indifferentiable EC-GGM within a sparse GGM.
Suppose we have a proposed construction of an elliptic curve generic group model derived from a sparse GGM, denoted as Π G := (L G , A G ). How can we demonstrate that a computationally bounded adversary is able to differentiate Π G from ec-G? A common approach is to identify a security game that remains secure in ec-G but can be easily broken in any construction of Π G .
Following the strategy outlined in [ZZ23], we define the security game as discrete logarithm identification (DLI), a variant of the discrete logarithm problem. Intuitively, the DLI game involves the following: given str := L(x), construct a probabilistic, efficient, and query-free circuit C such that C(x) accepts with high probability, while C(x ) overwhelmingly rejects for all x = x.
Next, we briefly recall the techniques from [ZZ23], where Zhang and Zhandry establish a separation between GGM and ROM against computationally bounded adversaries. Clearly, DLI is secure in GGM. To establish the separation, Zhang and Zhandry show that DLI can be easily broken in any group constructed from the ROM. In a nutshell, the adversary constructs the circuit C as follo ws: C(•) functions identically to L H (•), but without access to H, and accepts the input if the reconstructed result matches L H (x) (hardwired in C).
The key idea in [ZZ23] is to anticipate the queries that C will make to the random oracle model. This enables the adversary to make all sensitive queries in advance and hardcode the corresponding query/response pairs into C , thereby creating an oracle-free circuit. Zhang and Zhandry demonstrate that, with high probability, all sensitive queries can be collected as follows:
2. execute L H (xr) ← A H (L H (x), L H (-r)) and A H (L H (xr), L H (r)), and collect all the queries into S que-res .
Next, we outline our approach for the incorporating aforementioned technique into the analysis within sparse GGM. Specifically, given an input L G (x), the adversary A collects all the queries as described above, hardwires both the query/response pairs and L G (x) into the circuit C, which operates identically to L G (• ), and then outputs C(•). We then analyze the probability of A wins. Let Q x be the set of all query/response pairs generated during the execution of L G (x)foot_7 , for each pair (que, res) ∈ Q x , there are four possible cases:
-Case 1: The label L G (x) does not depend on res at all; -Case 2: The label L G (x) depends on res, but res does not appear in the response when computing A G (L G (xr), L G (r)); -Case 3: The label L G (x) depends on res, which is obtained by making "labeling" query to G when computing A G (L G (xr), L G (r)); -Case 4: The label L G (x) depends on res, which is obtained by making "addition" query to G when computing
Next, we present the analysis for handling eac h of the four cases.
For (que, res) in case 1 (same as in [ZZ23]), referred to as a non-sensitive query, since L G (x) does not depend on res, we can replace the resp onse to que with a uniformly sampled string without affecting the final outcome.
For (que, res) in case 2 (same as in [ZZ23]), referred to as a sensitive but frequent query, since the computation of A G (L G (xr), L G (r)) does not obtain res by making queries, res must be extracted from the inputs, i.e., L G (xr) and/or L G (r). This indicates that, with high probability, (que, res) ∈ Q x ∩(Q x-r ∪ Q r ). Moreover, since x, xr and r are pairwise indep endent, which means that Q x ∩ Q x-r and Q x ∩ Q r only contains "frequent" queries. Therefore, this query/response tuple can be collected by running L G (•) on sufficiently many random inputs.
For (que, res) in case 3 (same as in [ZZ23]), referred to as a sensitive labeling query, we can collect all labeling queries made during the computation of
For (que, res) in case 4 (different from [ZZ23]), referred to as a sensitive addition query, where que = (str 1 , str 2 ) consists of two valid group elements. Although res appears in this query, collecting this kind of query is not usually useful for our purpose. Specifically, when executing L G (x), the algorithm may only issue labeling queries at points (x 1 , . . . , x q ), whereas S que-res might only contain query/response pairs in the form of addition, such as (G(y i ), G(z i ), G(y i + z i )), without explicitly knowing y i or z i . Consequently, during the reconstruction of L G (x), the algorithm may issue labeling queries at certain points, but C is unable to identify which tuple corresponds to the correct response, resulting in the reconstruction failure.
To overcome this technical challenge, we once again leverage the sparseness property of the GGM. Note that the occurrence of the query in case 4 indicates that the adversary is able to generate a new and valid group element without knowing its discrete logarithm. Thus, by applying the same analysis as outlined in Sect. 1.3.1, we can construct an extractor that, given only the security parameter as input, is able to produce a new and valid group element whenever the query in case 4 occurs. This demonstrates that the query in case 4 occurs with negligible probability.
Notations. In this paper, let λ ∈ Z denote the security parameter. We use x||y to represent the concatenation of the strings x and y. For a finite set S, we denote a random sample s from S according to the uniform distribution as s $ ← S, and the size of S as |S|. For a probabilistic algorithm Alg, we overload the notation and w rite y $ ← Alg(I) to denote that the variable y is obtained by running Alg on input I, where I may be a tuple I = (I 1 , ..., I n ). If Alg is deterministic, we use the notation "←" instead of " $ ←". A positive function negl(•) is said to be negligible if, for all positive polynomial poly(•), there exists a constant λ 0 > 0 such that for all λ > λ 0 , it holds that negl(λ) < 1/poly( λ). We say that a function ρ(•) is noticeable in λ if its inverse, 1/ρ(λ), is polynomial in λ.
In this work, we treat groups with admissible encodings as a cryptographic primitive. We first recall the formal definition of a primitive given by [RTV04].
, , where F is a set of functions f : {0, 1} * → {0, 1} * specifying correctness property, and R is a relation on pairs f, , with f ∈ F and A an adversarial machine, specifying security property.
-Efficient implementation. A function f is said to implement P or be an implementation of P if f ∈ F. A n efficient implementation of P is an implementation of P that is computable in polynomial time. -Secure implementation. An adversarial machine A is said to P-break f ∈ F if f, . A secure implementation of P is an implementation of P such that no ppt adversarial machine can P-break f . We say that the primitive P exists if there is an efficient and secure implementation of P.
To ensure correctness, we consider cryptographic groups that support an efficiently computable encoding from Z p (for some integer p) into the group. Various formulations of such admissible encodings appear in the literature [BF03,BCI+10,LPS23]; in this work, we adopt the definition from [LPS23].
Computable: The function AE is computable in polynomial time. Sampleable: Given any element t in the image of AE, one can efficiently compute its full preimage inv-AE(t).
-regular: For any t ∈ T , the size of the preimage |inv-AE(t)| is at most , where is a samll constant.
Remark 2.1. The definition of admissible encodings in [BCI+10] differs slightly from that in Definition 2.2. Specifically, it requires that for uniformly distributed inputs s ∈ S, the output distribution AE(s) is statistically close to uniform over T . However, most known admissible encodings-such as Icart's encoding [Ica09, FT10]-do not produce uniformly distributed outputs. In this w ork, we adopt the definition from [LPS23], and note that the formulation in [BCI+10] can be seen as a special case of Definition 2.2 with = 1 .
When working with admissible encodings for cryptographic groups, the target set T is typically identified with the set of group elements. A key application of admissible encodings is oblivious sampling, which requires that the encoding's image covers a noticeable fraction of the set T . This, in turn, requires the domain to b e sufficiently large. Specifically, we say an admissible encoding AE for a group G is nice if: (1) AE maps from Z p to G, and (2) the ratio p |G| is not small. As shown in [Ica09], all elliptic curve groups admit nice admissible encodings. We now formalize the notion of CDH-secure groups equipped with nice admissible encodings.
The CDH-secure group with nice admissible encoding with respect to a constant and a polynomial poly AE , denoted ae-P CDH , is defined as a pair ae-F CDH , ae-R CDH , satisfying the following conditions:
1. The set ae-F CDH consists of group-generation functions f that, on input a security parameter, f outputs the description of a finite cyclic group along with an additional function. Specifically, we write (G, g, N,
where G is a cyclic group of λ-bit prime order N , g is a generator of G, and AE : Z p G is a -regular admissible encoding, with p ≥ N/poly AE (λ).
belongs to ae-R CDH for a function f ∈ ae-F CDH and a ppt adversarial machine A if there exists a polynomial poly A (•) such that
for infinitely many values of λ, where (G, g, N, AE) ← f (1 λ ) and x 1 , x 2 are chosen uniformly from Z N .
We say that a CDH-secure group with nice admissible encoding ae-P CDH exists if there is a function f ∈ ae-F CDH such that no ppt adversarial machine A satisfies f, ae-R CDH .
We also consider cryptographic groups with dense encodings and formalize this primitive following the definition style in
[RTV04]. Definition 2.4. (CDH-Secure Dense Group). The CDH-secure dense group, denoted d-P CDH , is defined as a pair d-F CDH , d-R CDH , satisfying the following conditions: 1. The set d-F CDH consists of group-generation functions f that, on input of a security parameter λ, output the description of a finite cyclic group with a dense encoding. Specifically, we write (G, g, N, m) ← f (1 λ ), where G is a cyclic group of λ-bit prime order N , g is a generator of G, and m is the length of the group encoding. Here, m satisfies mlog N ≤ Θ(log λ), meaning that each group element in G can be represented as an m-bit string. 2. The pair f, belongs to d-R CDH for a function f ∈ d-F CDH and a ppt adversarial machine A if there exists a polynomial poly A
for infinitely many values of λ, where (G, g, N, m) ← f (1 λ ) and x 1 , x 2 are chosen uniformly from Z N .
We say that a CDH-secure dense group d-P CDH exists if there is a function
In this subsection, we introduce the idealized models discussed in this pap er, including the Generic Group Model (GGM) [Sho97], the Generic Bilinear Group Model (GBM) [BB04], and the Elliptic Curve Generic Group Model (EC-GGM) [GS22]. In each model, all entities, including the adversary and the challenger, have access to the corresponding oracle. Below, we specify the behavior of the oracle in each idealized model. In this work, we further say that the generic group model G N,m is dense if mlog N ≤ Θ(log λ). Otherwise, we refer to it as sparse.
Definition 2.6. (Generic Bilinear Group Model [BB04]). For a given security parameter λ ∈ N, let I ZN ,Si denote the set of all injections from Z N to S i , where N is a λ-bit prime number and S i = {0, 1} mi for i ∈ {1, 2, T}.
The generic bilinear group model B is an idealized model that samples random injections σ 1 , σ 2 , and σ T from I ZN ,Si , respectively, and provides seven oracles: B 1-label , B 1-add , B 2-label , B 2-add , B T-label , B T-add and B map . Concretely, -The labeling oracle B i-label , for i ∈ {1, 2, T}, takes as input x ∈ Z N and returns σ i (x); -The addition oracle B i-add , for i ∈ {1, 2, T}, takes as input strings str, str ∈ S i , and behaves as follows: if there exist x, x ∈ Z N such that σ i (x) = str and σ i (x ) = str , the oracle returns σ T (x + x ); otherwise, it returns ⊥. -The bilinear map oracle B map takes as input strings str 1 ∈ S 1 and str 2 ∈ S 2 , and behaves as follows: if there exist x 1 , x 2 ∈ Z N such that σ 1 (x 1 ) = str 1 and σ 2 ( x 2 ) = str 2 , the oracle returns σ T (x 1 • x 2 ); otherwise, it returns ⊥.
In this work, we consider only symmetric generic bilinear group models, meaning that B 1-label = B 2-label and B 1-add = B 2-add . We make the functions N , m S and m T explicitfoot_8 , and refer to the model as
We
The framework of indifferentiability is proposed by M aurer, Renner, and Holenstein [MRH04], which formalizes a set of necessary and sufficient conditions for securely replacing one cryptosystem with another in an arbitrary environment. This framework is used to justify the structural soundness of various cryptographic primitives, including hash functions [CDMP05,DRS09], block ciphers [ABD+13,CHK+16,DSSL16,GWL23], domain extenders [CDMS10], authenticated encryption with associated data [BF18], and public-key cryptosystems [ZZ20]. It can also be used to study the relationship b etween idealized models [ZZ23]. In the following, we proceed to the definition of indifferentiability:
A cryptosystem Σ consists of a set of algorithms. Here, Σ is accessible via two interfaces Σ.hon and Σ.adv, where Σ.hon provides an honest interface through which the system can be a ccessed by all parties in a black-box manner, and Σ.adv models the adversarial access to Σ.
). Let Σ 1 and Σ 2 be two cryptosystems and S be a simulator. The indifferentiability advantage of a differentiator D against (Σ 1 , Σ 2 ) with respect to S is
where games Real Σ1,D and Ideal Σ2,S,D are defined in Fig. 1. We say Σ 1 is indifferentiable from Σ 2 , if there exists an efficient simulator S such that for any efficient differentiator D, the advantage above is negligible. Moreover, we say Σ 1 is statistically indifferentiable from Σ 2 , if there exists an efficient simulator such that, for any unbounded differentiator D, the advantage above is negligible. Below, we also use the notations in [BF18] and consider the definition above to two systems with interfaces as:
where F 1 and F 2 are two ideal objects sampled from their distributions and Π F1 is a construction of F 2 by calling F 1 . MRH prove the composition theorem for the framework of indifferentiability; for simplify, we give a game-based formalization from [RSS11].
). Let Σ 1 := (Π F1 , F 1 ) and Σ 2 := (F 2 , F 2 ) be two systems that Σ 1 is indifferentiable from Σ 2 with respect to a simulator S, then Σ 1 is as secure as Σ 2 for any single-stage game. More concretely, let Game be a single-stage game, then for any adversary A, there is an adversary B and a differentiator D such that
The proof of Thm. 2.1 is straightforward; due to space limit, we skip it here. Next, we give the formal definition of the separation between tw o idealized models in the framework of indifferentiability against computational adversaries.
Let Σ 1 , Σ 2 be two idealized models, we say Σ 2 is computationally indifferentiably separated from Σ 1 if for any efficient algorithm Π and any efficient simulator S, there exists an efficient differentiator D Π,S and a noticeable function ρ such that
Observe that, if an idealized model Σ 2 is computationally indifferentiably separated from another idealized model Σ 1 , it means that, we cannot build a scheme Π Σ 1 such that Π Σ1 is indifferentiable from Σ 2 , even under arbitrarily strong computational assumptions.
In this section, we elaborate the main constraint of the sparse GGM/GBM. We demonstrate that any the cryptographic group with nice admissible encodings that is CDH-secure, denoted as ae-P CDH , cannot exist within the sparse GGM/GBM. Roughly speaking, to establish the black-box separation, the standard approach is t o build an adversary that, while computationally unbounded, is query-efficient and capable of breaking the CDH game with respect to any construction of ae-P CDH in the sparse GGM/GBM.
For easier readability, our strategy follows the one in [IR89]. We introduces an intermediary primitive, i.e. non-interactive key exchange (NIKE) with nice admissible encoding that is secure against key-recovery attack (KRA-secure), denoted as ae-P NIKE , and prove that:
ae-P CDH implies ae-P NIKE ; -ae-P NIKE does not exist in the sparse GGM/GBM.
In this section, we present the formal definition of the KRA-secure noninteractiv e key exchange with nice admissible encoding.
A KRA-secure non-interactive key exchange protocol with nice admissible encoding, denoted ae-P NIKE , is define d as a pair ae-F NIKE , ae-R NIKE :
1. The set ae-F NIKE consists of functions f , each associated with a constant and a polynomial poly AE in λ. For a given input security parameter, f outputs the description of a non-interactive key exchange protocol along with an additional function. Specifically, w e write (KGen, SHK, AE) ← f (1 λ ), where algorithms are associated with SK, PK, and K.
-SK, PK, and K are the private-key space, public-key space and shared-key space, respectively, satisfying that SK := Z N , where N is a λ-bit integer. -The public-key generation function KGen : SK → PK is an injection, for generating a public key pk ∈ PK from a randomly chosen private key sk ∈ SK. -The shared-key generation function SHK : PK×SK → K∪{⊥} for generating a shared key shk ∈ K∪{ ⊥}, where ⊥ indicates a failed computation. -The encoding function AE : Z p → PK is a -regular admissible encoding from Z p to the codomain o f KGen, with p ≥ N/poly AE (λ).
Concretely, for randomly chosen sk $ ← SK and sk $ ← SK, compute pk ← KGen(sk) and pk ← KGen(sk ). We write shk ← SHK(pk , sk) and shk ← SHK(pk, sk ). The protocol is required t o achieve perfect correctness, meaning that:
2. For a function f = (KGen, SHK, AE) ∈ ae-F NIKE and a ppt (adversarial) machine A, we define f, ae-R NIKE if A can break the security property of f against key-recovery attack (KRA). Specifically, there exists a polynomial poly A (•) such that:
for infinitely many values of λ. Here, for randomly chosen sk $ ← SK and sk $ ← SK, compute pk ← KGen(sk) and pk ← KGen(sk ), respectively.
We say ae-P NIKE exists if there is a function f ∈ ae-F NIKE such that no ppt adversarial machine A satisfies f, ae-R NIKE .
It is apparent that ae-P CDH implies ae-P NIKE by defining KGen(x) := g x and SHK(pk, sk ) := pk sk . Therefore, it is sufficient to prove that ae-P NIKE does not exist in the sparse GGM.
In this section, we establish the black-box separation between ae-P NIKE and the sparse GGM. Specifically, we construct an adversary that, while computationally unbounded, is query-efficient and capable of breaking the KRA-secure game with a noticeable probability. The corresponding proof for the sparse GBM proceeds analogously and is deferred to the full version of this paper. Theorem 3.1. Let G N,m be a generic group model such that mlog N ≥ ω(log λ). Let Π GN,m = (KGen GN,m , SHK GN,m , AE GN,m ) be any non-interactive key exchange protocol with nice admissible encoding par ameterized by a constant and a polynomial poly AE . Then there exists an adversary A and two polynomials poly 1 and poly 2 such that:
-A makes poly 1 queries to G N,m ; -A breaks the KRA-secure game with advantage 1 poly 2 . Proof. To establish the proof, we present a formal description of the a dversary A, as illustrated in Fig. 2. Here, we specify that any algorithm in Π GN,m makes at most q queries, where q is a polynomial. We then clarify some undefined notions: By (que 1 , res 1 ), . . . , (que q , res q ) query ←-KGen GN,m (x), we mean that when running KGen GN,m (x), the algorithm makes queries (que 1 , . . . , que q ) to the oracle G N,m , and obtains (res 1 , . . . , res q )foot_10 .
Trivial to note that the adversary A GN,m is query-efficient. We next prove that the adversary A GN,m can successfully guess the valid shared key with a noticeable probability. Let S Bob-L denote the set of all valid group encodings that appear when running the algorithms KGen GN,m (sk 2 ) and SHK GN,m (pk 1 , sk 2 ); these encodings are either the responses of labeling/addition queries or the valid inputs of the addition queries. Clearly, |S Bob-L | ≤ 6q, since each algorithm makes at most q queries to G N,m . We then define:
Note that in each iteration, if the encoding pairs in SA are consistent with S Bob , the shared key computed in that iteration would be correct. Specifically, in such a context, there exists another instance of GGM that is consistent with both the simulation view of A and the real view of user Bob. The perfect correctness of ae-P NIKE guarantees that the shared key computed in this iteration must be equal to the true key computed by Bob. However, without knowledge of sk 2 , SA might be inconsistent with S Bob with high probability. In fact, there are three events:
-Event 1: There exist (x, str) ∈ SA and (x , str ) ∈ S Bob such that x = x but str = str . -Event 2: There exist (x, str) ∈ SA and (x , str ) ∈ S Bob suc h that x = x but str = str . -Event 3: For any (x, str) ∈ SA and (x , str ) ∈ S Bob , we have that i f x = x then str = str , and vice versa.
We immediately observe that Event 1 occurs at most 6q times, since the updating phase would eliminate at least one pair in S Bob with each occurrence. Next we show that, with a noticeable probability, Event 3 would deduce the valid shared key. According to the adversary, decipted in Fig. 2, we note that the set SA ∪ S que-res responds to the labeling queries properly. For the addition queries, say que = (str 1 , str 2 ), there are two cases:
-Case 1: SA ∪ S que-res covers (x 1 , str 1 ), (x 2 , str 2 ), and ( x 1 + x 2 , str 3 ); -Case 2: either str 1 or str 2 is not collected in ˜ S A ∪ S que-res .
For the former case, SA ∪ S que-res responds to the addition query properly; for the latter case, SA ∪ S que-res always responds with ⊥, which means that if both str 1 and str 2 are valid group elements then the response is invalid. Therefore, the only bad case that prevents Event 3 from guessing a valid shared key is that the adversary A generates valid group elements str without making labeling queries (i.e., without knowing the corresponding discrete logarithm). Besides, we observe that, when Event 2 occurs, the adversary also generates valid group elements without making labeling queries. Hence, if the probability of such a bad case is small, then the adversary A GN,m can break the KRA-secure game and output the valid shared key with a good probability.
According to the description of the adversary A GN,m , we immediately observe that, A GN,m aborts if either pk 1 or pk 2 has no preimage with respect to AE GN,m . To analyze the probability of such a bad event , we define a tuple (G N,m , sk 1 , sk 2 ) is invertible if the following conditions are satisfied:
Due to the fact that AE GN,m is a -regular admissible encoding from Z p to the N valid public keys, there are at least p public keys with preimages under AE GN,m . Each such public key corresponds to a unique private key. Therefore, we have that
where the probability of over the sampling of the instance of the GGM and private keys.
Moreover, we observe that once the randomness of the adversary is fixed, then the algorithm A GN,m (pk 1 , pk 2 ) is deterministic. Let r be a nonce, we say the adversary performs good with respect to the tuple (G N,m , sk 1 , sk 2 , r), if the adversary A GN,m (pk 1 , pk 2 ), utilizing r as its source of randomness, is unable to generate a valid group element without knowing the discrete logarithm. Here, pk i represents the public key generated from the private key sk i .
Next, we introduce the concept of "good" for the tuple (G N,m , sk 1 , sk 2 ). More formally, we say a tuple (G N,m , sk 1 , sk 2 ) is good if
where pk 1 ← KGen GN,m (sk 1 ) and pk 2 ← KGen GN,m (sk 2 ), and the probability is over the internal randomness of A. Analogously, we say a tuple (G N,m , sk 1 , sk 2 ) is bad if
Pr[A performs good with respect to (G N,m , sk 1 , sk 2 , r)] < 1 2 .
For clarity, we denote these three events in which the tuple (G N,m , sk 1 , sk 2 ) is invertible, good or bad as Invertible, Good and Bad, respectively. Due to the perfect correctness of Π GN,m , it is apparent that the probability A wins the KRAsecure game, conditioned on Good ∧ Invertible, is ≥ 1 2 . Thus, the probability of A wins can be bounded by
Therefore, it suffices to prove that Pr[Good|Invertible] is noticeable. To finalize the proof, we utilize the sparsity property of the GGM. As discussed in [Zha22], given access to a sparse GGM, any algorithm that receives only the security parameter as input cannot output a valid group element without knowledge of the corresponding discrete logarithm except with negligible probability 11 . For ease of exposition, we refer to this event as the algorithm outputs a new group element. More precisely, we say an algorithm E outputs a new group element str, if (1) str has been used as an input to some addition queries made by E, and (2) str has not appeared as the output of any previous queries (whether labeling or addition) made by E.
We note that, if Pr[Good|Invertible] is small, then, conditioned on Invertible, the adversary A is likely to generate a new group element with a g ood probability. Consequently, our proof strategy proceeds in two steps:
1. Construct an extractor E that takes only the s ecurity parameter as input; 2. Demonstrate that, if Pr[Good|Invertible] is small, then E outputs a new group element with a good probability.
We now present the formal description of the e xtractor E, as depicted in Fig. 3. The extractor E takes only the security parameter as input, randomly selects two seeds (i.e., seed 1 and seed 2 ), and computes the corresponding public keys (i.e., pk 1 and pk 2 ) using admissible encodings. Following this, the extractor proceeds in a manner closely resembling the adversary in the KRA-security game, as shown in Fig. 2. Specifically, the extractor proceeds the preprocessing phase and the iteration phase. During the simulation process of each iteration phase, if a new and valid group element appears, either in SA or as an input of some addition queries, then E outputs this element (highlighted in red). Observe that the randomness of E is composed of three components: seed 1 , seed 2 , and r, where r represents the randomness used during the iteration phase. Furthermore, once the GGM instance and the two seeds are fixed, the extractor E proceeds identically to the adversary A in the KRA-security game, continuing until E successfully outputs a new and valid group element.
Next, we analyze the probability of the extractor wins, which occurs when E outputs a new and valid group element. Let G N,m denote the GGM to which the extractor E has access. Let seed 1 and seed 2 denote the seeds sampled by the extractor. We define the seed pair, (seed 1 , seed 2 ), to be bad with respect to G N,m , if the tuple (G N,m , sk 1 , sk 2 ), deduced from (seed 1 , seed 2 ), is a Bad and Invertible tuple. More precisely, when we say a tuple (G N,m , sk 1 , sk 2 ) deduced from (seed 1 , seed 2 ) with respect to G N,m , we mean that KGen GN,m (sk 1 ) = AE GN,m (seed 1 ) and KGen GN, m (sk 2 ) = AE GN,m (seed 2 ).
For clarity, we refer to this event as BadSeed in the following analysis. According to the definition of Bad, we note that if E fortunately samples a bad seed pair, i.e., BadSeed occurs, then E wins with a good probability. Concretely,
Next, we analyze the probability of BadSeed with respect to any specific GGM instance. To facility the analysis, we introduce several concepts relevant to the generic group model. For any instance of the GGM, denoted as G N,m , we define Q GN,m as the set of all private keys such that for any private key sk ∈ Q GN,m , the corresponding public ke y (denoted pk = KGen GN,m (sk)) has valid preimages under the admissible encodings. Moreover, due to that the admissible encodings is -regular, it is apparent that
We then categorize all instances of the GGM into two types: good GGM instances and bad GGM instances. Specifically, let G N,m be a GGM instance, and Q GN,m := {sk 1 , . . . , sk t }. Let (i, j) be a pair where i, j ∈ [1, t] 12 . We classify G N,m as a bad instance if there are more than 1 2 2 •t 2 pairs such that each induces a Bad and Invertible tuple. More precisely, when we say a pair such as (i * , j * ) induces a Bad and Invertible tuple, we mean that the tuple (G N,m , sk i * , sk j * ) is bad and invertible. Analogously, we classify G N,m as a good instance if there are at most 1 2 2 •t 2 pairs, each of which induces a Bad and Invertible tuple. Therefore, for any good GGM instance, there are at least (1 -1 2 2 ) • t 2 tuples that are both Good and Invertible.
Furthermore, for any GGM instance G N,m , if a tuple (G N,m , sk 1 , sk 2 ) is invertible, then there are at least one seed pair, such as (seed 1 , seed 2 ), from which (G N,m , sk 1 , sk 2 ) can be deduced from. Consequently, for any fixed GGM instance, we have that, Num of bad and invertible tuples ≤ Num of bad seed pairs. We are now prepared to establish the lower bound on the probability of the extractor E wins when accessing G N,m , conditioned on G N,m being a bad GGM instance. Concretely, let t be the size of Q GN,m , we have that,
Pr[E GN,m wins|G N,m is bad] ≥ Pr[E GN,m wins|BadSeed] • Num of bad seed pairs Num of all seed pairs ≥ 1 2 • Num of bad and invertible tuples Num of all seed pairs ≥ 1 2 • 1 2 2 • t 2 p 2 ≥ 1 4 4 . Next, we analyze the probability of E wins, where the probability is also considered o ver the uniform sampling of the GGM instance. Specifically, Pr[E wins] ≥ Pr[E GN,m wins|G N,m is bad] • Num of bad GGM instances Num of all GGM instances ≥ 1 4 4 • Num of bad GGM instances Num of all GGM instances . For clarity in exposition, we define TotalGGM as the set of all GGM instances, BadGGM as the subset of bad GGM instances, and GoodGGM as the subset of good GGM instances. Moreover, we define BadRatio := |BadGGM| |TotalGGM| ; GoodRatio := |GoodGGM| |TotalGGM| . Thus, the probability of the extractor E wins is bounded by Pr[ E wins] ≥ 1 4 4 • BadRatio. According to the sparsity property of the GGM, we know that the probability of E outputs a new group element is negligible, indicating that BadRatio is negligible. T herefore, it suffices to prove that, if Pr[Good|Invertible] is not noticeable, then BadRatio is not negligible. Claim. If Pr[Good|Invertible] ≤ 1 4 2 • 1 poly AE (λ) 2 , then BadRatio ≥ 1 2 . We proceed our analysis by contraposition. Specifically, we prove that if BadRatio < 1 2 , then Pr[Good|Invertible] > 1 4 2 • 1 poly AE (λ) 2 . By definition, we have that Pr[Good|Invertible] = Pr[Good ∧ Invertible] Pr[Invertible] = Σ GN,m Num of Good and Invertible tuples w.r.t. G N,m Σ GN,m Num of Invertible tuples w.r.t. G N,m , where the summation Σ GN,m is taken over all GGM instances. Note that for any GGM instance G N,m , since the size of the private-key space is N , there are at most N 2 relevant tuples associated with G N,m . This implies that Σ GN,m Num of Invertible tuples w.r.t. G N,m ≤ |TotalGGM| • N 2 . Furthermore, by the definition of good GGM instance, for any good GGM instance G N,m , there are at least (1 -1 2 2 ) • t 2 tuples that are both Good and Invertible tuples associated with G N,m . Therefore, we know that Σ GN,m Num of Good and Invertible tuples w.r.t. G N,m ≥ |GoodGGM|•(1-1 2 2 )•t 2 , where t = |Q GN,m | ≥ p . Thus, we hav e that Pr[Good|Invertible]
Therefore, we conclude that, if BadRatio < 1 2 , then
Combining together, we establish the entire proof.
In this section, we focus on cryptographic groups with dense group encodings, demonstrating that any such group that is CDH-secure, denoted as d -P CDH , cannot exist within the sparse GGM/GBM. Following a similar strategy as in Sect. 3, we introduce an intermediary primitive, i.e. non-interactive key exchange (NIKE) with dense public-key space, which is secure against key-recove ry attack (KRA-secure), denoted as d-P NIKE , and prove that:
d-P CDH implies d-P NIKE ; -d-P NIKE does not exist in the sparse GGM/GBM. 1. The set d-F NIKE consists of functions f that, on input of a security parameter, output the description of a non-interactive key exchange protocol. Specifically, we write (KGen, SHK) ← f (1 λ ), where algorithms are associated with SK, PK, and K.
-SK, PK, and K are the private-key space, public-key space and shared-key space, respectively, satisfying that SK := Z N , where N is a λ-bit integer, and log |PK|log |SK| ≤ Θ(log λ); -The public-key generation function KGen : SK → PK is an injection, for generating a public key pk ∈ PK from a randomly chosen private key sk ∈ SK. -The shared-key generation function SHK : PK×SK → K∪{⊥} for generating a shared key shk ∈ K∪{ ⊥}, where ⊥ indicates a failed computation.
Concretely, for randomly chosen sk $ ← SK and sk $ ← SK , compute pk ← KGen(sk) and pk ← KGen(sk ). We write shk ← SHK(pk , sk) and shk ← SHK(pk, sk ). The protocol is required t o achieve perfect correctness, meaning that:
Pr shk = ⊥ ∨ shk = ⊥ ∨ shk = shk = 0.
2. For a function f = (KGen, SHK) ∈ d-F NIKE and a ppt (adversarial) machine A, we define f, d-R NIKE if A can br eak the security property of f against key-recovery attack (KRA).
We say d-P NIKE exists if there is a function f ∈ d-F NIKE such that no ppt adversarial machine A satisfies f, d-R NIKE .
It is apparent that d-P CDH implies d-P NIKE by defining KGen(x) := g x and SHK(pk, sk ) := pk sk . Therefore, it is sufficient to prove that d-P NIKE does not exist in the sparse GGM/GBM. Due to space limit, we leave the proof in the full version of this paper.
In this section, we analyze the relationship between the Elliptic Curve Generic Group Model (EC-GGM) and t he sparse GGM within the framework of indifferentiability.
We describe how to build a sparse generic group from an EC-GGM equipped with an independent random permutation. Denote Orac as the tuple (ec-G N , Perm), where ec-G N = (ec-G label N , ec-G add N ) is an elliptic curve generic group model over a point set E, and Perm is a random permutation over {0, 1} m . Define Δm := m -( log p + 1), the construction Π Orac = (L Orac , A Orac ) is depicted in Fig. 4. Theorem 5.1. Let G N,m be a sparse generic group model. The scheme Π Orac is indifferentiable from G N,m . More precisely, there exists a simulator S such that for all q-query differentiator D, we have
Π Orac ,GN,m,S,D ≤ 36q 2 N + 12q 2 + q 2 λ + q 2 ω(log λ) . The simulator makes at most λq queries to G N,m .
Due to space limit, we leave the proof in the full version of this paper. Our strategy fundamentally builds on the analytical framework develop ed by Zhandry and Zhang [ZZ23]. Due to space limit, we leave the proof in the full version of this paper.
Here, p denotes the prime modulus used in elliptic curve groups, where the curve is typically defined b y the equation y
= x
+ Ax + B mod p.
Since Sque-res is only a subset of H, it is possible that SA may be inconsistent with the random oracle H.
The conventional black-box separation framework establishes impossibility r esults unconditionally, whereas [JZW+24] demonstrates impossibility only under certain unjustified conditions.
The probability is taken over the sampling of the GGM instances and the internal randomness of the algorithm.
randomly sample r, r 1 , . . . , r n 6 , execute L H (r), L H (-r), L H (r 1 ), . . . , L H (r n ), and collect all the queries into S que-res ;6 Here n is a sufficiently large integer.
Without loss of generality, we assume that L G (•) only makes labeling queries.
GBM is symmetric indicating that m1 = m2, and we redenote by m S the encoding length of source group.
For any u ∈ Zp there are at most two points on the curve with u as their x-coordinate, namely, (u, ±y) for some y. To simplify, point compression is applied, and we denote the point (u, y) by the pair(u, b), where b = 0 if y is even and b = 1 if y is odd.
As explained above, we assume that the algorithms KGen G N,m and AE G N,m only make labeling queries.