# Must the order of the groups in a bilinear map be the same?

I've been reading up on bilinear maps and their application to cryptography and one thing I keep seeing hasn't yet clicked.

If $e:G_1\times G_2\to G_n$ is a bilinear map, $G_1,G_2,G_n$ are always defined as having the same order.

It seems to me, however, that $ord(G_n)$ should be $ord(G_1)\cdot ord(G_2)$. Is there a reason that I always see the groups having the same order by definition? Must that be the case?

-
You could have a bijective (linear) mapping (i.e. an isomorphism) with this order, but not a bilinear (and surjective) mapping. Bilinear mappings are not injective (other than in trivial cases). –  Paŭlo Ebermann Nov 18 '11 at 2:49

If both $G_1$ and $G_2$ have prime order $r$, then this means that there are generators $g_1$ and $g_2$; thus, for every $u_1 \in G_1$, there is an integer $x_1$ modulo $r$ such that $u_1 = g_1^{x_1}$. Therefore, every pairing value $e(u_1, u_2)$ is equal to $e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2}$ by bilinearity. It follows that $e(g_1,g_2)$ is a generator of all the possible pairing values, and the bilinearity implies that $e(g_1,g_2)^r = e(g_1^r, g_2) = 1$. Hence, the group of possible pairing values also has prime order $r$.

Now you can imagine $G_n$ as being larger, with possible pairing values being only a strict subset of $G_n$, but that's just cheating.

Note that bilinearity and non-degeneracy imply that if a prime $p$ divides the order of $G_1$, then $1 = e(u_1^p,u_2) = e(u_1,u_2^p)$, from which we can conclude that $p$ also divides the order of $G_2$, and the order of $G_n$ as well. So we cannot have pairings over just any groups.

It is possible, however, that $G_1$ and/or $G_2$ are larger than $G_n$. In practice, the currently known efficient pairings are all derived from Weil or Tate pairings, which work over elliptic curves. From now on, I will denote operations in $G_1$ and $G_2$ additively, because Tradition requires that we talk about point additions. The basic setup of Weil and Tate pairings goes thus:

Let $\mathbb{F}_q$ be a finite field of order $q$. Let $E$ be an elliptic curve over $\mathbb{F}_q$. Let $r$ be a prime divisor of the order of $E$, such that $r^2$ does not divide the order of $E$, and $r$ is not equal to the field characteristic (this is to avoid a lot of degenerate cases). We denote $E[r](\mathbb{F}_q)$ the subgroup of points of $r$-torsion: these are the points which yield $0$ (the "point at infinity") when multiplied by $r$, and there are $r$ of them.

Then there is an embedding degree which is the lowest integer $k \geq 2$ such that $r$ divides $q^k-1$. It so happens (theorem of Balasubramanian-Koblitz) that $E[r](\mathbb{F}_{q^k})$ (the group of $r$-torsion points over the curve $E$, this time considering point coordinates over the field $\mathbb{F}_{q^k}$) contains $r^2$ points.

In that situation, both Weil and Tate pairings become non-trivial; they take as input $r$-torsion points in $E[r](\mathbb{F}_{q^k})$, and yield as output values in $\mathbb{F}_{q^k}^*$, and more specifically $r$-th roots of $1$ in that extended field. This is a subgroup of size exactly $r$ of the invertible elements in the field. This is our group $G_n$.

So we have the following situation:

• $G_1$ and $G_2$ are both subgroups of $E[r](\mathbb{F}_{q^k})$, and thus may have order $r$ or $r^2$.
• $G_n$ has always order $r$, no more, no less.

At that point, we must choose our groups so that we get some desirable properties:

• $G_1$ and $G_2$ both have order $r$.
• It is easy to hash arbitrary data messages into elements of $G_2$ (i.e. we can "randomly" generate elements of $G_2$ without knowing the discrete logarithm of the resulting point with regards to a given generator of $G_2$).
• There exists a one-way non-trivial morphism from $G_2$ to $G_1$: this is a linear function which outputs values in $G_1$, such that values other than 0 are achievable, the function is easy to compute, but its inverse is computationally infeasible.

Unfortunately, we cannot have all three properties simultaneously. We end up with the following usual choices:

• We use a supersingular curve of embedding degree $2$. $G_1$ is $E[r](\mathbb{F}_q)$ (the $r$-torsion points on the curve in the base field, not the extended field). $G_2$ is the very same group; to compute the pairing, we first map $G_2$ into another subgroup of $E[r](\mathbb{F}_{q^k})$ through a distortion map (if both operands of Weil or Tate pairing are from the curver over the unextended field, the pairing output is always 1, hence trivial). Easily computable distortion maps are a rarity, but with a supersingular curve, we have some. For that scenario, $G_1$, $G_2$ and $G_n$ all have the same order $r$; it is easy to hash data into elements of $G_2$; an isomorphism between $G_1$ and $G_2$ is easily computed in both directions since they are the same group.

• We use a non-supersingular curve. $G_1$ is $E[r](\mathbb{F}_q)$ and $G_2$ is a subgroup of $E[r](\mathbb{F}_{q^k})$ generated by a conventional $r$-torsion point (not one which is in $G_1$); thus, $G_1$ and $G_2$ both have order $r$. We do not know how to hash points into $G_2$. The Trace of Frobenius of a point $P = (X, Y)$ is defined as:

$$\phi(X,Y) = \sum_{i=0}^{k-1} (X^{q^i}, Y^{q^i})$$

(it is a sum of elliptic curve points, and each of these points is obtained by taking the coordinates of the input point, raised to power $i$). $\phi$ happens to be an isomorphism from $G_2$ onto $G_1$, and it appears to be difficult to invert.

• We use a non-supersingular curve. $G_1$ is $E[r](\mathbb{F}_q)$. $G_2$ is the subset of $E[r](\mathbb{F}_{q^k})$ consisting in points $P$ such that $\phi(P) = 0$ (the set of "points of trace zero"). $G_2$ is a group of order $r$ and we know how to hash points into $G_2$. However, we do not know any easily computable non-trivial morphism from $G_2$ to $G_1$, or from $G_1$ to $G_2$.

• We use a non-supersingular curve. $G_2$ is the complete $E[r](\mathbb{F}_{q^k})$; thus, it has order $r^2$. $G_1$ is any subgroup of $G_2$ (of order $r$), possibly $G_2$ itself (of order $r^2$). It is easy to hash into $G_2$.

One way to think of pairings is that a pairing is a product. If we had a group $G$ with an "addition" and we could find a pairing of pairs of elements of $G$ into elements of $G$ itself, then that pairing would behave just as multiplication behaves with regards to addition (it would, by the way, totally break Diffie-Hellman on the group $G$). So the "natural" situation is really that $G_1$, $G_2$ and $G_n$ all have the same order.

-
Why $e(g_1^r, g_2) = 1$ ? –  curious Sep 27 '12 at 12:08
@curious: because $g_1^r = 1$ (group $G_1$ has order $r$) and bilinearity implies that $e(1,x) = 1$ for all $x$. –  Thomas Pornin Sep 27 '12 at 12:32
But if we think pairings as products then $e(1,x)=x$ no? –  curious Sep 27 '12 at 12:57
@curious: sorry, that's the usual confusion. In the first part of the post, I use multiplicative notation on the groups; in the second part, I use additive. With the additive notation for groups $G_1$, $G_2$ and $G_n$, that's $e(rg_1, g_2) = 0$ because $rg_1 = 0$ and $e(0,x) = 0$ by bilinearity. –  Thomas Pornin Sep 27 '12 at 13:02
I still can't get why $e(1,x)=1$. $e(0,x)=0$ seems reasonable with multiplication on mind.Thanks in any case. I am missing some theory maybe –  curious Sep 27 '12 at 13:08