Polynomial representations of the Diffie-Hellman mapping (Q2730746)

Let \(q\) be a prime power, \(\mathbb{F}_q\) be the finite field of order \(q\), and \(g\) be primitive element of \(\mathbb{F}_q\). The Diffie-Hellman key exchange is based on the fact that no easy representation of the Diffie-Hellman mapping NEWLINE\[NEWLINEf(g^x,g^y)=g^{xy} \quad \text{ for }1\leq x,y\leq q-1NEWLINE\]NEWLINE is known. For breaking the Diffie-Hellman cryptosystem it would be sufficient to have an easy polynomial satisfying \(f(g^x,g^y)=g^{xy}\) for all pairs \((x,y)\in {\mathcal W}\) of a large subset \({\mathcal W}\subseteq [1,q-1]^2\). NEWLINENEWLINENEWLINEThe authors obtain the following result extending the technique in \textit{D. Coppersmith} and \textit{I. Shparlinski} [J. Cryptology 13, 339-360 (2000; Zbl 1038.94007)]: NEWLINENEWLINENEWLINELet \({\mathcal W}\subseteq [N+1,N+H]^2\) with \(2\leq H\leq q-1\) and let \(f(X,Y)\in \mathbb{F}_q[X,Y]\) be a polynomial such that NEWLINE\[NEWLINEf(g^x,g^y)=g^{xy} \quad \text{ for all } (x,y)\in {\mathcal W}.NEWLINE\]NEWLINE If \(|{\mathcal W}|\geq 10 H^{8/5}\) then we have NEWLINE\[NEWLINE\deg(f)\geq \frac{|{\mathcal W}|^2}{128H^3}.NEWLINE\]NEWLINE They obtain also results on the degree of polynomials \(F(X,Y,Z)\) over \(\mathbb{F}_q\) satisfying \(F(g^x,g^y,g^{xy})=0\), where \((x,y)\) runs through a certain subset of \([1,q-1]^2\).NEWLINENEWLINENEWLINEReviewer's remark: The authors' first result and the reviewer's result in [Bull. Aust. Math. Soc. 64, 475-477 (2001)] complement each other. In particular, the latter paper contains nontrivial results for certain subsets \({\mathcal W}\) of cardinality smaller than \(10H^{8/5}\).