[Cfrg] Compression of tori in draft-irtf-cfrg-pairing-friendly-curves-02

[Watson Ladd <[e-mail]>]

Dear all,

In the latest draft I see that F_{p^k} is represented directly as
polynomials modulo an irreducible of degree k, and GT is encoded
accordingly. This is space inefficient.

In most cases k is even. Let q=p^(k/2) Consider F_q[x]/(x^2+d), the
quadratic extension of F_{q }, and now consider the result of a
pairing in it. As in https://eprint.iacr.org/2004/032.pdf, it is clear
that the result satisfies a quadratic equation: a^2-db^2=1, where the
element is a+bx.

Therefore we can send only a, which is much smaller, and ecode b as a
single bit.

This technique is very useful in any protocol where an element of GT
must be sent.

Sincerely,
Watson Ladd