Using abelian varieties to improve pairing-based cryptography (Q1027984)

In this long and quite technical paper the authors study several aspects of Pairing-Based Cryptography. Bilinear pairings (Weil and Tate pairings) on elliptic curves or higher dimensional abelian varieties are used in Cryptography both in a constructive and destructive way, see [Handbook of elliptic and hyperelliptic curve cryptography. Boca Raton, FL: Chapman \& Hall/CRC (2006; Zbl 1082.94001)]. In particular, given an abelian variety \(A\) defined over the finite field \(\mathbb{F}_q, q=p^n\), a prime \(l\neq p\) and a point \(0\neq P\in A(\mathbb{F}_q)[l]\), the algorithms of \textit{A. Menezes, T. Okamoto} and \textit{S. A. Vanstone} (MOV) [IEEE Trans. Inf. Theory 39, No. 5, 1639--1646 (1993; Zbl 0801.94011)] and of \textit{G. Frey} and \textit{H.-G. Rück} [Math. Comput. 62, No. 206, 865--874 (1994; Zbl 0813.14045)] allow to reduce the discrete logarithm problem in the cyclic group \(<P>\) to the same problem in the field \(\mathbb{F}_{q^k}\), where \(k\), called the embedding degree, is the multiplicative order of \(q\) modulo \(l\). Such embedding degree should be neither too small (to avoid MOV-like attacks) nor too large (for computational reasons). For this and other motivations supersingular varieties are usually used in Pairing-Based Cryptography. The paper (Section 4) introduces two new invariants: the cryptographic exponent \(c_{A,q}\) and the security parameter \(\alpha(A,q)\). The authors argue that the cryptographic exponent (a number in \(1/2Z\)) is a better security measure than the embedding degree: theorem 6.3 shows that for an elementary supersingular abelian variety and \(l\) large enough \(\mathbb{F}_{q^{c_{A,q}}}\) is the smallest extension of \(\mathbb{F}_p\) whose multiplicative group contains the \(l-th\)-roots of unity. The security parameter \(\alpha(A,q)=c_{A,q}/\dim(A)\), measures MOV security per bit and allows to compare security among abelian varieties of different dimension. Section 7 determines which values can occur as the security parameters. The results are also collected in Table 1 (Section 1) and show that it is possible to obtain higher MOV security per bit than using supersingular elliptic curves. The authors also discuss (Section 9) the cryptographic security of \textit{primitive} subgroups \(V_{q^r|q}\) of the Weil restriction of scalars. They prove that given a supersingular elliptic curve \(E\) defined over \(\mathbb{F}_q\) and a suitable prime \(r\) there exists an abelian variety \(E_r\) over \(\mathbb{F}_q\) (the \(rth\) primitive subgroup) with security parameter better, by a factor \(r/(r-1)\), than the parameter of \(E\). If \(A_0\) denotes the trace zero subgroup of \(E(\mathbb{F}_{q^r})\) then \(E_r(\mathbb{F}_q)\cong A_0\subseteq E(\mathbb{F}_{q^r})\). Section 10 gives a compression/decompression algorithm for the points of \(A_0\) which compresses by a factor of \(r/(r-1)\). The algorithm is efficient when \(r=3, p\neq 3\) (Section 10.3) and \(r=5, p=3\) (Section 10.4) . Section 12, keeping in mind the results of Table 1, constructs explicit examples of optimal abelian varieties (varieties with the highest \(c_{A,q}\) among abelian varieties of the same dimension) for those dimensions providing the highest MOV security per bit.