Pairings Redefined
In the last section we saw how to construct pairings with the help of an efficiently computable map that we named \(\phi\). In general such a map may not exist (e.g. for MNT curves), and we must redefine what it means to be a bilinear map. Pairing-based cryptosystems may also have to be slightly rewritten to accomodate the change.
The modification is minor. Essentially we no longer require that the inputs come from the same group. that is, we now desire an efficiently computable bilinear nondegenerate map
where \(G_1, G_2, G_T\) are all cyclic groups of prime order \(r\), the discrete log problem is hard in \(G_1\) and additionally there exists an efficiently computable isomorphism from \(G_2\) to \(G_1\) (thus ensuring discrete log is also hard in \(G_2\)).
Example
Suppose we have generated an MNT curve with \(k=6\). A toy example can be obtained with \(D = 1163\). Set \(q = 401\), and define
We have \(\#E(\mathbb{F}_q) = 381 = 3 \times 127\), hence set \(r = 127\). Then take any random \(P \in E(\mathbb{F}_q)\) of order \(r\) (such as \((151, 235)\)) and any random \(Q \in E(\mathbb{F}_{q^k}) \setminus \langle P \rangle\) of order \(r\). Then \(G_1 = \langle P \rangle, G_2 = \langle Q \rangle\), and \(G_T\) is the cyclic subgroup of \(\mathbb{F}_{q^k}^*\) of order \(r\). Note that the trace map can be used to construct an efficiently computable isomorphism from \(G_2\) to \(G_1\). If the Tate pairing is being used instead of the Weil pairing, \(Q\) does not even have to be of order \(r\) since it is now a representative of a coset of order \(r\).