Polynomial approximation of bilinear Diffie-Hellman maps

DOI10.1016/J.FFA.2007.03.002MaRDI QIDQ2426464zbMATH OpenOpenAlexFDO

Authors Theo Garefalakis, Ian Blake

Publication date 22 April 2008

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ffa.2007.03.002

zbMATH Keywords

elliptic curvespolynomial interpolationWeil pairing

Mathematics Subject Classification ID

Elliptic curves over global fields (11G05) Curves over finite and local fields (11G20) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1982615
• On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping
• A note on the interpolation of the Diffie-Hellman mapping
• Polynomial representations of the Diffie-Hellman mapping
• Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Cites work

• Advances in Elliptic Curve Cryptography
• Coding and Cryptography
• scientific article; zbMATH DE number 1643939 (Why is no real title available?)
• scientific article; zbMATH DE number 1982615 (Why is no real title available?)
• scientific article; zbMATH DE number 2009971 (Why is no real title available?)
• Identity-Based Encryption from the Weil Pairing
• Information Security and Privacy
• On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.
• On Polynomial Interpolations related to Verheul Homomorphisms
• Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem
• Polynomial representations of the Diffie-Hellman mapping
• Reducing elliptic curve logarithms to logarithms in a finite field
• Simplified pairing computation and security implications
• The Diffie-Hellman protocol
• The generalized Weil pairing and the discrete logarithm problem on elliptic curves
• The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
• The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems

Cited in

(5)

• On the index of the Diffie-Hellman mapping
• Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem
• On Polynomial Interpolations related to Verheul Homomorphisms
• On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping
• Closed formulae for the Weil pairing inversion

This page was built for publication: Polynomial approximation of bilinear Diffie-Hellman maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2426464)