2010 | OriginalPaper | Buchkapitel
On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
verfasst von : Robert Granger
Erschienen in: Advances in Cryptology - ASIACRYPT 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show that for any elliptic curve
$E(\mathbb{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
→ ∞ the adversary can solve
any
further instance of the Static DHP in
heuristic
time
$\tilde{O}(q^{1-\frac{1}{n+1}})$
. Our proposal also solves the
Delayed Target DHP
as defined by Freeman, and naturally extends to provide algorithms for solving the
Delayed Target DLP
, the
One-More DHP
and
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
any
group in which index calculus can be effectively applied, the above problems have a natural relationship, and will
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
$\mathbb{F}_{p^2}$
and
$\mathbb{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.