Bugs in fp{12,48,54}_exp

[jdlee0]

The functions fp{12,48,54}_exp_cyc drop the sign of the exponent f when (bn_bits(f) > RLC_DIG) || ((w << 3) > bn_bits(f)). Repro, should be trivial to fix:

  bn_set_dig(f, 2);
  fp12_exp_cyc(b, a, f);
  bn_neg(f, f);
  fp12_exp_cyc(c, a, f);
  fp12_inv_cyc(c, c);
  TEST_ASSERT(fp12_cmp(c, b) == RLC_EQ, end);

For fp12, fp48, fp54, the _test_cyc function returns 1 for elements that aren't in the cyclotomic subgroup.

  fp12_rand(a);
  fp12_back_cyc(a, a);
  //Set c = a^(p^(2k/6) - p^(k/6) + 1)
  fp12_frb(c, a, 4);
  fp12_frb(b, a, 2);
  fp12_inv(b, b);
  fp12_mul(c, c, b);
  fp12_mul(c, c, a);
  TEST_ASSERT((fp12_cmp_dig(c, 1) == RLC_EQ) == (fp12_test_cyc(a) == 1), end);

For fp12, there's more subtle issue, most easily seen by testing vs. frobenius on the cyclotomic subgroup

  fp12_rand(a);
  fp12_conv_cyc(a, a);
  fp12_frb(b, a, 1);
  f->sign = RLC_POS;
  f->used = RLC_FP_DIGS;
  dv_copy(f->dp, fp_prime_get(), RLC_FP_DIGS);
  fp12_exp(c, a, f);
  TEST_ASSERT(fp12_cmp(c, b) == RLC_EQ, end);

_test_cyc functions have false positives (and can throw)
{fp12,fp48,fp54}_test_cyc return true if their associated _back_cyc functions do not alter the given point. By inspection, the fp{6k}_test_cyc functions return some c that only can only differ from a at [0][2] and [1][2], and throws ERR_NO_VALID if a[1][0] == 0.

So _test_cyc == true defines an affine variety of size (p^k)^4 - (p^k). But the cyclotomic subgroup has size (p^k)^2 - (p^k) + 1. This seems like a bug. The simlpest fix would be to replacing the existing test with checking Frob(a, 4k) . a == Frob(a, k) directly.

The _test_cyc functions throwing ERR_NO_VALID means _exp, _pck, _size_bin can also throw this error. This isn't documented and seems pretty surprising.

fp12_exp_cyc doesn't distinguish between the cyclotomic subgroup and the prime subgroup
For pairing friendly curves, fp12_exp_cyc uses some Frobenius based acceleration. Concretely for BLS12 curves, its correctness relies on a^x == Frob(a, 1). This is true for pairing outputs on the subgroup of order r, since p - x = r . (x-1)^2 / 3. It's not true on the cyclotomic subgroup in general. It appears that some similar optimization is happening for BN curves, assuming that a^{6u^2} == Frob(a, 1).

Fixing this without regressing pairing performance seems harder. It seems like the internal api has to change a little so that the pairings can correctly signal that they can use these frobenius based accelerations.

Testing Issues
fp8_exp, fp12_exp, fp48_exp all fall through to their respective _exp_cyc calls on any element which passes the associated _test_cyc calls. This renders consistency checks between _exp and _exp_cyc in test_fpx.c meaningless, and is probably why the above errors weren't caught earlier. It's not clear that this fall-through is sensible, since being on the cyclotomic subgroup is rare and testing slows the common case.

Independently, it might be reasonable to test correctness of _exp_cyc against _frb, since these are very unlikely to accidentally end falling through to each #other.

[dfaranha]

Thank you for the notification, Internet stranger, these are very specific! :)

First set of problems with sign is fixed and tests added, as it was the simplest. In the cyclotomic testing, I replaced the decompression test with Frobenius computations, and indeed this clears the problem with raising exceptions at very little cost in complexity.

I still need a little more time to think about how to improve the API to exponentiate elements in the various subgroups. This is a recurring problem with the library, for example when powering elements in E'(Fp^2).