Paper 2010/177
On the Static DiffieHellman Problem on Elliptic Curves over Extension Fields
Robert Granger
Abstract
We show that for any elliptic curve $E(\F_{q^n})$, if an adversary has access to a Static DiffieHellman Problem (Static DHP) oracle, then by making $O(q^{1\frac{1}{n+1}})$ Static DHP oracle queries during an initial learning phase, for fixed $n>1$ and $q \rightarrow \infty$ the adversary can solve {\em any} further instance of the Static DHP in {\em heuristic} time $\tilde{O}(q^{1\frac{1}{n+1}})$. Our proposal also solves the {\em Delayed Target DHP} as defined by Freeman, and naturally extends to provide algorithms for solving the {\em Delayed Target DLP}, the {\em OneMore DHP} and {\em OneMore DLP}, as studied by Koblitz and Menezes in the context of Jacobians of hyperelliptic curves of small genus. We also argue that for {\em any} group in which index calculus can be effectively applied, the above problems have a natural relationship, and will {\em always} be easier than the DLP. While practical only for very small $n$, our algorithm reduces the security provided by the elliptic curves defined over $\F_{p^2}$ and $\F_{p^4}$ proposed by Galbraith, Lin and Scott at EUROCRYPT 2009, should they be used in any protocol where a user can be made to act as a proxy Static DHP oracle, or if used in protocols whose security is related to any of the above problems.
Note: Final version
Metadata
 Available format(s)
 Publication info
 Published elsewhere. To be published at ASIACRYPT 2010
 Keywords
 Static DiffieHellman problemelliptic curves.
 Contact author(s)
 rgranger @ computing dcu ie
 History
 20100913: last of 3 revisions
 20100404: received
 See all versions
 Short URL
 https://ia.cr/2010/177
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/177, author = {Robert Granger}, title = {On the Static DiffieHellman Problem on Elliptic Curves over Extension Fields}, howpublished = {Cryptology ePrint Archive, Paper 2010/177}, year = {2010}, note = {\url{https://eprint.iacr.org/2010/177}}, url = {https://eprint.iacr.org/2010/177} }