# Exponentiation Problem of G2 in MNT curve

I made a simple python program in the Charm framework (https://github.com/JHUISI/charm):

from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair

group = PairingGroup("MNT224")
g = group.random(G1)
h = group.random(G2)
a, b = group.random(ZR, 2)

G1 = (g ** a) ** b
G2 = g ** (a * b)
H1 = (h ** a) ** b
H2 = h ** (a * b)

print('G1:', G1)
print('G2:', G2)
print('H1:', H1)
print('H2:', H2)


And I got this:

G1: [10078373295334768694563741838278622956778134163588850571046784075738, 11285206652127590502238684314907500254559622599368025831501761600958]
G2: [10078373295334768694563741838278622956778134163588850571046784075738, 11285206652127590502238684314907500254559622599368025831501761600958]
H1: [[3534196784717504462328757211224470588231695063171615945530129056656, 10211780109365030693121484817970351226593726986080067998578894245699, 6368599583350992357625322855407611464986270273403678555426952468683], [13684062230274089937149579621207233764284608067400053114106045228780, 9213593495915716016992145616323404591735310637893710560096176472666, 8444322233041608777047377989157187452524603129738981272127139119302]]
H2: [[1419904059378831003656260139736181866360018467588549133311449391908, 8009525015121730906488018517095803865211202805317619827555115979123, 13352161910105351377726749012042030874411151465492265223612708819089], [13998900821711144185326068030921609854586336394019796349518302780691, 4263873462088002148509836008014306558952369669692605762808882317126, 714307621193276272340511827939733717827940292614445171003103716515]]


So why H1 is not equal to H2?

• I've left this open for now to make some more math based discussion possible, but note that this question may be migrated to StackOverflow as it is hard to tell if the answer is mathematically incorrect or that it is a programming or library error. Aug 15 '20 at 14:33

Here's a guess: when you ask to compute h ** (a * b), it actually computes h ** (a * b mod q), where $$q$$ is the order of $$g$$ in $$G1$$.

If that is the case, well, a random element from $$G2$$ is not going to be a divisor of $$q$$ - any element that is the result of a pairing operation will be; however most elements of $$G2$$ cannot be the result of a pairing operation.

And, if the order of $$h$$ is not a divisor of $$q$$, then $$h^{a \cdot b} \ne h^{a \cdot b \bmod q}$$

The above would give the expected result if you set $$h$$ to be the result of a pairing operation, possibly with two random $$G1$$ elements...

(This is labeled a guess because I'm not familiar with the Charm framework, so I'm guessing about its behavior)

• Thank you very much! I'm not familiar with the the mathematic construction of pairings. I learned that in a (symmetric or asymmetric) pairing group, ord(G1)=ord(G2)=q always holds. And actually, I need to realize a pairing-based cryptosystem by applying this property. So could you please give more details?
– Ati
Aug 14 '20 at 8:32
• @Ati: actually, the full $G2$ group is much larger than $G1$; it does contain a subgroup that is isomorphic to $G1$ (and so that subgroup has the same order), however if you pick a random element in $G2$ (and I assume that's what group,random(G2) does), then you will likely get an element outside that subgroup. Aug 14 '20 at 11:41
• Thanks for your help! I very much appreciate it. I just found it might be a bug in the Charm framework. If we implicitly convert all ZR elements into the int type before the exponentiation, the output is correct. :)
– Ati
Aug 14 '20 at 12:10
• @Ati: I don't believe it's a bug; the system might be running as expected (even if it's not what you expected). $a, b$ were initialized as a, b = group.random(ZR, 2); if the system realized that those were members of a group, then a * b should mean "group multiplication", that is, $a \cdot b \bmod q$ (or R as charm defines in). And if h = group.random(G2) is defined to generate a random element of the entire extension group (rather than the specific subgroup the pairing operation works in), then the result is as expected (even if, again, it's not what you expected) Aug 14 '20 at 22:22
• Thank you very much! I realize this is not a bug and your guess is right. But I don't know how to generate a random element of the specific subgroup of G2 (in the Charm framework or the PBC library). Using the int type (to avoid group multiplication) might be a simple method to compare (h ** a) ** b and h ** (a * b), where h = group.random(G2)`.
– Ati
Aug 15 '20 at 23:47