# Group description in pairing based cryptography

Suppose we have a public key encryption scheme, in which public parameter contains $(p, G, G_t, e, g)$, where $p$ is prime number, $G$ is a (cyclic) group of prime order, $e:G \times G \mapsto G_t$. Now my question is, what is the meaning of $G$ which occur in the public parameter? Does it represent the group order (here $p$) and the operation (say $*$ multiplication)?

• If you have a very simple group structure such as $G$ being $\mathbb{Z}_q^*$ for some prime $q$, then to describe $G$ it would be sufficient to use $q$. However, here in a pairing setting $G$ is some elliptic curve group and requires a more exhaustive description just as the elliptic curve domain parameters for (standardized) elliptic curve (including coefficients for the curve equation, etc). Same for the pairing $e$ and $G_t$. This notation is simply used to abstract away from all the details of a concrete choice of groups. – DrLecter Dec 11 '14 at 14:10

DrLecter's comment should really be an answer, but one point which bears emphasis is that it is not sufficient for crypto purposes to say "a (cyclic) group of prime order $p$", because even though mathematically all groups of order $p$ are essentially the same group (i.e., they are isomorphic), we can't really say the same thing in crypto.

When doing crypto in cyclic groups, we generally make the assumption that the discrete logarithm problem is difficult to solve in the groups in question (most often implicitly through a stronger assumption like those in the DH family). But the choice of a particular cyclic group makes a dramatic difference in the difficulty of solving the discrete logarithm problem, at least in the current state of our knowledge: we know cyclic groups of prime order in which the discrete logarithm problem is easy (which ones?), and others in which it seems to be difficult. And even among the groups in which the discrete logarithm problem is considered difficult, it seems to be more difficult in some than in others.

Hence, any discrete log-based cryptosystem needs to specify explicitly which group it operates in if we want to have any idea of its security. This is what $G$ and $G_t$ represent in the definition of a pairing: they are simply the groups in question (e.g., $G$ is the group of points of the elliptic curve with equation [...] generated by the point [...]).

EDIT: Of course, in abstract discussions we can simply say that $G$ is a cyclic group of prime order in which such-and-such assumption holds, but still we would need to be more specific than just saying we operate in cyclic groups of prime order. It is also very helpful in discussions and proofs to have a name for the groups we are working in, especially in pairing settings where there are two (sometimes three) groups involved.

I think that there are some confusion about the parameters of computing Pairing, and specially in the definition of group order. Pairing which make use of elliptic curves, were firstly intoduced by Dan Boneh from his first seminal "Identity Based Encryption from Weil Pairing; SIAM J. of Computing 2001. Many other sheemes were introduced since, and make use of another Pairing. To recall what are the public parameters: (p,G,Gt,e,g):

• If p is a prime number, the finite Field $F_p$ = GF(p), of order p exists, and where all the computations will be conducted in this ground field or in a algebraic closure,
• We know that all elliptic curves defined over $F_p$, do have a structure of algebraic curves whose order N must satisfies the Hasse bound $|N-(p+1)| \leq 2.\times \sqrt{p}$. Let G be a group of point on an elliptic curve. This group must be carrefully chosen to fit with security requirement. (Briefly: G must have a sub-group of large order)
• The Weil pairing (many other exists since, such as Tate's pairing, ...) is a bilinear application from $G\times G$ to $G_t$, (in fact it produce a n-rooth of Unity located in an algebraic closure fo $F_p$). Note also that Weil Pairing use a evaluation function know as Miller's Algorithm.