On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping
Eike Kiltz, Arne Winterhof · Bulletin of the Australian Mathematical Society · 2004
We obtain lower bounds on degree and weight of bivariate polynomials representing the Diffie-Hellman mapping for finite fields and the Diffie-Hellman mapping for elliptic curves over finite fields. This complements and improves several earlier results. We also consider some closely related bivariate mappings called P-Diffie-Hellman mappings introduced by the first author. We show that the existence of a low degree polynomial representing a P-Diffie-Hellman mapping would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on weight and degree of such interpolation polynomials, as well.