International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields

Authors:
Robert Granger
Download:
URL: http://eprint.iacr.org/2010/177
Search ePrint
Search Google
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}})$. While practical only for very small $n$, our algorithm reduces the security of elliptic curves defined over $\F_{p^2}$ and $\F_{p^4}$ proposed by Galbraith, Lin and Scott at EUROCRYPT 2009, should these curves be used in any protocol where a user can be made to act as a proxy Static DHP oracle. 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. Lastly, we 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.
BibTeX
@misc{eprint-2010-23078,
  title={On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields},
  booktitle={IACR Eprint archive},
  keywords={Static Diffie-Hellman problem, elliptic curves.},
  url={http://eprint.iacr.org/2010/177},
  note={In submission rgranger@computing.dcu.ie 14750 received 2 Apr 2010, last revised 21 May 2010},
  author={Robert Granger},
  year=2010
}