Must the order of the groups in a bilinear map be the same? - Cryptography Stack Exchange most recent 30 from crypto.stackexchange.com 2022-01-20T19:49:11Z https://crypto.stackexchange.com/feeds/question/1246 https://creativecommons.org/licenses/by-sa/4.0/rdf https://crypto.stackexchange.com/q/1246 5 Must the order of the groups in a bilinear map be the same? mikeazo https://crypto.stackexchange.com/users/706 2011-11-17T18:43:26Z 2013-08-22T08:48:12Z <p>I've been reading up on bilinear maps and their application to cryptography and one thing I keep seeing hasn't yet clicked. </p> <p>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. </p> <p>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?</p> https://crypto.stackexchange.com/questions/1246/-/1252#1252 14 Answer by Thomas Pornin for Must the order of the groups in a bilinear map be the same? Thomas Pornin https://crypto.stackexchange.com/users/28 2011-11-17T20:21:43Z 2011-11-17T20:21:43Z <p>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$.</p> <p>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.</p> <p>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.</p> <hr /> <p>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 <em>additions</em>. The basic setup of Weil and Tate pairings goes thus:</p> <p>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.</p> <p>Then there is an <em>embedding degree</em> 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.</p> <p>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$.</p> <p>So we have the following situation:</p> <ul> <li>$G_1$ and $G_2$ are both subgroups of $E[r](\mathbb{F}_{q^k})$, and thus may have order $r$ or $r^2$.</li> <li>$G_n$ has always order $r$, no more, no less.</li> </ul> <p>At that point, we must choose our groups so that we get some desirable properties:</p> <ul> <li>$G_1$ and $G_2$ both have order $r$.</li> <li>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$).</li> <li>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.</li> </ul> <p>Unfortunately, we cannot have all three properties simultaneously. We end up with the following usual choices:</p> <ul> <li><p>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 <em>distortion map</em> (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.</p></li> <li><p>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:</p> <p>$$\phi(X,Y) = \sum_{i=0}^{k-1} (X^{q^i}, Y^{q^i})$$</p> <p>(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.</p></li> <li><p>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$.</p></li> <li><p>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$.</p></li> </ul> <hr /> <p>One way to think of pairings is that a pairing is a <em>product</em>. 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.</p>