Polynomial representations of the Diffie-Hellman mapping
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 \[ f(g^x,g^y)=g^{xy} \quad \text{ for }1\leq x,y\leq q-1 \] 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\). The 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)]: Let \({\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 \[ f(g^x,g^y)=g^{xy} \quad \text{ for all } (x,y)\in {\mathcal W}. \] If \(|{\mathcal W}|\geq 10 H^{8/5}\) then we have \[ \deg(f)\geq \frac{|{\mathcal W}|^2}{128H^3}. \] 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\). Reviewer'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}\).
- A note on the interpolation of the Diffie-Hellman mapping
- On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping
- Polynomial interpolation of the generalized Diffie-Hellman and Naor-Reingold functions
- scientific article; zbMATH DE number 1792665
- scientific article; zbMATH DE number 1982615
- A polynomial representation of the Diffie-Hellman mapping
- scientific article; zbMATH DE number 1303541
- scientific article; zbMATH DE number 4027620
- On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.
- Cryptanalysis of ``\(2R\) schemes
- Cryptography. Theory and practice
- Number theoretic methods in cryptography. Complexity lower bounds
- On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.
- The Diffie-Hellman protocol
- The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
- Security of polynomial transformations of the Diffie-Hellman key.
- Polynomial interpolation of the generalized Diffie-Hellman and Naor-Reingold functions
- On the complexity of the discrete logarithm and Diffie-Hellman problems
- A polynomial representation of the Diffie-Hellman mapping
- On the index of the Diffie-Hellman mapping
- Polynomial interpolation of the Naor-Reingold pseudo-random function
- Polynomial approximation of bilinear Diffie-Hellman maps
- Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem
- Polynomial representations of the Lucas logarithm
- A note on the interpolation of the Diffie-Hellman mapping
- Transformations of cryptographic schemes through interpolation techniques
- Interpolation of the Double Discrete Logarithm
- On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping
- A key exchange protocol relying on polynomial maps
- Studying the performance of artificial neural networks on problems related to cryptography
This page was built for publication: Polynomial representations of the Diffie-Hellman mapping
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2730746)
