Polynomial approximation of bilinear Diffie-Hellman maps (Q2426464)

Let \(p\) b an odd prime and \(\mathbb{F}_q\) the finite field of characteristic \(p\) with \(q\) elements, \(E\) an elliptic curve defined over \(\mathbb{F}_q\), \(\ell\) a prime different from \(p\) dividing the order \(|E(\mathbb{F}_q)|\), \(P\in E(\mathbb{F}_q)\) a point of order \(\ell\) and \(m\) the order of \(q\) (modulo \(\ell\)). The bilinear Diffie-Hellman problem is the bilinear map \[ \begin{aligned} \text{BDH}:\langle P\rangle\times\langle P\rangle\times \langle P\rangle&\to \mu_\ell(\mathbb{F}_{q_m})\\ (aP,bP,cP)&\mapsto e(P,P)^{abc} \end{aligned} \] (where \(\mu_\ell(\mathbb{F}_{q^m})\) denotes the group of \(\ell\)th roots of unity in \(\mathbb{F}_{q^m}\)) and finds many applications in cryptography. In analogy to the so-called Diffie-Hellman map, the authors consider the ``diagonal'' case of the above map: \[ \begin{aligned} \text{BDH}_3: \langle P\rangle&\to \mu_\ell(\mathbb{F}_{q_m}),\\ nP&\mapsto e(P, P)^{n^3} \end{aligned} \] and prove that BDH is equivalent to \(\text{BDH}_3\). Various lower bounds on the degree of any polynomial that interpolates the diagonal map \(\text{BDH}_3\) are found that shows that such an interpolation will involve a polynomial of large degree, relative to the size of the set on which it interpolates.