**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.

**Category / Keywords: **Static Diffie-Hellman problem, elliptic curves.

**Publication Info: **To be published at ASIACRYPT 2010

**Date: **received 2 Apr 2010, last revised 13 Sep 2010

**Contact author: **rgranger at computing dcu ie

**Available format(s): **PDF | BibTeX Citation

**Note: **Final version

**Version: **20100913:145308 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]