Paper 2010/177

On the Static Diffie-Hellman 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 Diffie-Hellman 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 One-More DHP} and {\em One-More 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)
PDF
Publication info
Published elsewhere. To be published at ASIACRYPT 2010
Keywords
Static Diffie-Hellman problemelliptic curves.
Contact author(s)
rgranger @ computing dcu ie
History
2010-09-13: last of 3 revisions
2010-04-04: received
See all versions
Short URL
https://ia.cr/2010/177
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/177,
      author = {Robert Granger},
      title = {On the Static Diffie-Hellman 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.