A note on the interpolation of the Diffie-Hellman mapping (Q2777722)

Let \(q\) be a prime power, \(F_q\) the finite field of order \(q\) and \(\gamma\) an element of order \(d\mid q-1\). The Diffie-Hellman problem in \(F_q\) is, given \({\gamma}^x\), \({\gamma}^y\) find \({\gamma}^{xy}\). Define the mapping NEWLINE\[NEWLINEf({\gamma}^x, {\gamma}^y) = {\gamma}^{xy} NEWLINE\]NEWLINE and note that the polynomial NEWLINE\[NEWLINE f(X,Y) = d^{-1} \sum_{i,j = 0}^{d-1} {\gamma}^{-ij} X^i Y^j NEWLINE\]NEWLINE satisfies the map, where \(d^{-1}\) is the inverse of \(d\) modulo the characteristic of \(F_q\). To break Diffie-Hellman it would be sufficient to satisfy the first equation above for all pairs \((x,y) \in {\mathcal W} \subseteq [0,d-1]^2\) for a sufficiently large set \({\mathcal W}\). The main result of the paper is NEWLINENEWLINENEWLINETheorem: Let \(q\) be a prime power, \({\gamma}\) a nonzero element of order \(d\mid q-1\) and \(N\) an integer. Let \({\mathcal U}\) be a set of distinct integers modulo \(d\) and \({\mathcal V} \subseteq \{ N+1, \cdots , N+H \}\) with \(|{\mathcal V}|= H-s\) and \(1 \leq H < d\). Let \(f(X,Y) \in F_q [ X,Y]\) be a polynomial satisfying NEWLINE\[NEWLINE f({\gamma}^x , {\gamma}^y) = {\gamma}^{xy},\quad \text{for all } (x,y)\in {\mathcal U}\times {\mathcal V} . NEWLINE\]NEWLINE Then we have the following lower bound on the total degree of \(f(X,Y)\): NEWLINE\[NEWLINE \deg (f) \geq \min \left( |{\mathcal U}|, \left\lceil {{H-s} \over {s+1}} \right\rceil \right) -1.NEWLINE\]