Welcome to the resource topic for 2010/177
Title:
On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
Authors: 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.
ePrint: https://eprint.iacr.org/2010/177
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .