Please check the code for FP12.pow(BIG) #38
Comments
|
@mhewett-ks Can you add your example code for AMCL? One caveatis that |
|
Zip file attached (143KB). Open the HTML file in a browser and examine the console log for output. The HTML page has the desired output. |
|
One thing I spotted iin the code s that in amcl BIGs are decoded little-endian in |
|
fromBytes() calls frombytearray() which is going left-to-right in the input array and doing a "fshl" operation on the resulting BIG. I would hazard a guess that "fshl" is a left shift. So it does appear to be building left-to-right. Anyway, I found that if I don't left-pad it, AMCL puts zeroes on the right end and changes it to something bigger. When I left-pad it, it produces the value I want. |
|
The discussion above is another indicator that AMCL needs useful setHex(string) functions. Then the library could handle the details and the programmer wouldn't have to worry about them. |
|
You are right, it is big endian and must be left-padded to BIG.MODBYTES. Sorry for the confusion! |
|
Here are five test cases. The first one is the same as above. Because of the way the values are constructed, the answer to f.pow(b) for each one should be exactly the same. This should help you check whether the fix is correct. |
|
I am not sure I completely understand the problem. First point: there are different ways of representing an element Fp^{12}, depending on the towering method used. The AMCL library towers 12-4-2-1, and most other libraries tower as 12-6-2-1. Since the final 2-1 is the same for both we can ignore that. So if A,B,C,D,E,F \in Fp2 For the AMCL towering an element (A,B),(C,D),(E,F) represents the polynomial (A+Bx^3)+(C+Dx^3)x+(E+Fx^3)x^2 - (1) For the alternate towering (A,E,D),(C,B,F) represents the polynomial (A+Ex^2+Dx^4)+(C+Bx^2+Fx^4)x - (2) Clearly these are both the same, both representations of A+Cx+Ex^2+Bx^3+Dx^4+Fx^5 - (3) So clearly it is easy to move between representations, its just a permutation of terms. I am not clear how the other libraries output an Fp^{12}. Maybe in the order A,C,E,B,D,F? Or maybe following their towering as A,E,D,C,B,F? (In fact ideally for interoperability it would make sense for everyone to use the towering-independent order (3)) Second point: the functions toString() are intended for internal debugging use only. The external API |
|
OK, I think I see (another part of) the problem. The example FP12 you are using [[[18cd...c6b8]]] does not appear to be of the correct order, and is therefore not an element in G_T. The FP12 powering algorithm is dependent on the FP12 being a member of the cyclotomic subgroup. It uses a fast squaring algorithm usqr() that depends on this. It also uses an optimization that depends on inversions being the same as conjugations (and therefore costing nothing), which only applies if the order is correct. So I suggest you try again with FP12 values that are the outputs of pairings (and therefore of the correct order). |
|
Ah, when I apply the simple permutation to your FP12 I get [[[18cd7a565a749009cc4c5f6601ea0856a47a3323f9ebb5953e4c2b1c4010d0dc7ca86ef548c4332b4cc2602e92e19f0f,09e148c258387a5e91c961df72cd340c19cdcdf799c249458969e00bf4d1275dbfcb139b49857e189f19ce71ae7fa8ee],[1301d3f107fdcbbaffc05707e0e2611dc8d4ed9ad90c0fd221df7e706b4b4d46c943daf03a6f3a1eddd2d2c9bc4ddbc5,018fde8c2958612913a7ac368d9c778adaaf7dd88bedab9ada2e709ef173091735dd153382584c2bc0c7993937318ecd]],[[171201bdd27cbe71d915e6e7d3cef10ce7251fa9b863c71652e0e63c16702c83993559129ee682b9c8c597b9849b843d,12c5a8f92088dba00d78e4c33bb18010e5bcd5ae193aedc291186dd9091ada24fc0d61f0efe90857e4528fc013583d12],[0938dfc7cb18005c641319bb00149ce4a25edfa4aa50557aa8c780cce9cc6351261920f7212a41a3b0b097d3e827d3c3,07e500c72020555a613e32a7726c5d66350163663e4bdbc1b8b65b22c49dd19c91e7c859790a5290c526a391d2e896ef]],[[0a2ac22c8737727e985aea988b18549379dc9821dd42d0974e7fd89b3d3c13114371ebfb3304cbda9d26c7a0a0b83025,0728ccef15044f5df498bb80ce5313d6dfc9a3ae9d4e4bb0f3ea398d8a2af607479cd6f66a6daeeb495d22aa8de2e256],[19b0de4003f7f0c81918595a674a1d9d67bfcdafc2194aa7c2d799c3f21015e52018cd6999add6bc685dfc8b33ef41e2,03bce826c38b87e80c66b61ef71d705e67faeb0acf6f89fc5a6d4d9957bb766dc76b5c82d7f0d553260f4e2a7ef1c6b8]]] And now it is of the correct order! To test FP12 for correct order in AMCL. // Compute T^order the output should be 1. |
|
My pairings are constructed by a different library and they are definitely in GT. However, the other library does use a different tower. Good work on detecting the ordering problem. I should have thought of that. I'll permute the values and run some more tests. Ethereum has proposed a standard representation for G1 points. I don't know if they have extended it to G2 and GT but perhaps AMCL should propose a standard and support it. The Ethereum standard is here: https://github.com/ethereum/eth2.0-specs/blob/dev/specs/simple-serialize.md |
|
Since G1 are just points on an elliptic curve, a standard already exists. See section 2.3.3 of http://www.secg.org/sec1-v2.pdf Basically its 04|x|y, or 02|x if point compression is used and the least significant bit of y is 0, or 03|x if the least significant bit is a 1. As far as I know nothing has been proposed for G2 and GT. Both can be compressed, which complicates matters... |
|
I have confirmed that swapping elements 2 and 8, 3 and 9, 4 and 6, & 5 and 7 permutes the FP12 values from the other representation to AMCL's representation. After that change my code produces the value I was expecting. Thanks for the help. |
|
Great! |
|
Now I am seeing different results from FP12.pow(BIG) and PAIR.GTpow(FP12, BIG). I have tested both the Java and JavaScript implementations and both produce different results. This is using the BLS381 curve In both cases I am using an actual computed FP12 value, NOT transliterating from object to text and back to object. Here is a trace from Java: The results should be the same, right? Here is my Java code: // Testing -------------------------------------------------------
BIG testmul = new BIG(myBigNum);
testmul.invmodp(modulus);
FP12 pairing2 = new FP12(pairing);
System.out.println("pairing2 = " + pairing2.toString());
System.out.println("testmul = " + testmul.toString());
// Compute T^secret
FP12 test1 = pairing.pow(testmul);
System.out.println("pairing ^ testmul = " + test1.toString());
System.out.println("testmul = " + testmul.toString());
// Compute T2^secret
FP12 test2 = PAIR.GTpow(pairing2, testmul);
System.out.println("pairing2 ^ testmul = " + test2.toString());
// END Testing ---------------------------------------------------Here is the curve configuration CONFIG_CURVE.java: public class CONFIG_CURVE {
public static final int WEIERSTRASS=0;
public static final int EDWARDS=1;
public static final int MONTGOMERY=2;
public static final int NOT=0;
public static final int BN=1;
public static final int BLS=2;
public static final int D_TYPE=0;
public static final int M_TYPE=1;
public static final int POSITIVEX=0;
public static final int NEGATIVEX=1;
public static final int CURVETYPE=WEIERSTRASS;
public static final int CURVE_PAIRING_TYPE=BLS;
public static final int SEXTIC_TWIST=M_TYPE;
public static final int SIGN_OF_X=NEGATIVEX;
public static final int ATE_BITS= 65;
public static final int SHA256=32;
public static final int SHA384=48;
public static final int SHA512=64;
public static final int HASH_TYPE=32;
public static final int AESKEY=16;
public static final boolean USE_GLV =true;
public static final boolean USE_GS_G2 =true;
public static final boolean USE_GS_GT =true;
}The JavaScript code does exactly the same thing. Both of them produce different values for the two varieties of pow(). I am using the same set of libraries that I sent earlier in this Issue. |
|
OK, I suspect the problem here is that PAIR.fexp(..) is not called after PAIR.ate(..). PAIR.ate(..) does not calculate a complete pairing. It must be followed by the "final exponentiation" to produce the pairing value of the correct order. The complete ate pairing requires a call to PAIR.ate() followed by PAIR.fexp(), for example These functions are kept separate as a multi-pairing can share the same final exponentiation, as in |
|
Adding fexp() resolved the problem. Thanks. |
|
I am having a problem with AMCL that I had with another library. When I do FP12.pow(BIG), it produces the result I expect iff BIG is at most a 255-bit number but not if BIG is a larger number. Is there a theoretical reason why if my BIG > r the FP12.pow() function wouldn't work as expected? |
|
When powering to a BIG value x, mathematically its the same as powering to x mod r, where r is the group order. If x < r then this clearly makes no difference, and if x>r there is no point is using an unnecessarily large value for x, and it makes sense to reduce it modulo r. The powering functions do not automatically do this reduction, as they assume that the input x<r, and implicitly assume that the function is only called with such a constraint. But they could easily be modified to internally reduce the proffered exponent modulo r (and maybe they should be!) |
|
Final note: Thanks for all your help. I have a pure-AMCL version of my code working using JS on the front end and Java on the backend. I may have some future comments as I try to also get it to run in IE 11 and Swift (:-) |
|
@mhewett-ks Could you share a final test case of externally generated test data for FP12.pow? Would be great to have that in the unitests. I tried to follow the permutation from #38 (comment) but do get different results. |
|
Here are a couple of test cases. These are all in AMCL-compatible format: TEST #1 in:BIG in:FP12 out:FP12^BIG TEST #2 in:BIG in:FP12 out:FP12^BIG |
|
Great, thanks. Added the first one in #45. I'd add more if there is test data with some specific properties (e.g. exponent larger than group order). But this should be a great base-line and also work as example code for users. |
I have been testing a number of crypto libraries with the BLS12-381 curve and have noticed a discrepancy in the result of FP12.pow(BIG) in the JS library for AMCL version 3.
Here is a test case:
(By the way, it would be VERY nice if there was a set(string) function on each class that accepts the output of the toString() for that class.)
For the other libraries I get this result for pt.pow(num):
But in AMCL I get:
In case it's not clear, if you remove the brackets from the AMCL result you get 12 hex strings. The result from the other libraries is presented as 12 hex strings, in the same order as the AMCL result. The 12 hex strings from the two results should be exactly the same, in the same order.
I can provide a number of other examples if you need them.
Thank you
The text was updated successfully, but these errors were encountered: