Compressed Pairings

Suppose \(\mathbb{F}_q[\alpha]\) is a quadratic extension of \(F_q\) where \(\alpha^2 = \delta\) for some \(\delta \in \mathbb{F}_q\). Then let \(x = a + \alpha b\) be some \(r\)th root of unity in \(\mathbb{F}_q\) for some \(r\) dividing \(q+1\). (Note \(q+1 = \Phi_2(q)\).)

Then \(x^{q+1} = 1\), thus

\[ 1 = a^{q+1} + \alpha^{q+1} b^{q+1} = a^2 + (\alpha^q) \alpha b^2 = a^2 - \delta b^2 \]

since \(\alpha^q = -\alpha\).


Ben Lynn blynn@cs.stanford.edu 💡