University of Surrey

Test tubes in the lab Research in the ATI Dance Research

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

Granger, Robert (2010) On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields In: The 16th International Conference on the Theory and Application of Cryptology and Information Security - Advances in Cryptology (ASIACRYPT 2010), 05-09 Dec 2010, Singapore.

Full text not available from this repository.


We show that for any elliptic curve E(Fqn ), if an adversary has access to a Static Diffie-Hellman Problem (Static DHP) oracle, then by making O(q1− 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 O˜(q1− 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 Fp2 and Fp4 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.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Date : 5 December 2010
DOI : 10.1007/978-3-642-17373-8_17
Copyright Disclaimer : © International Association for Cryptologic Research 2010
Uncontrolled Keywords : Elliptic Curve; Elliptic Curf; Discrete Logarithm; Hyperelliptic Curve; Discrete Logarithm Problem
Depositing User : Clive Harris
Date Deposited : 07 Feb 2019 14:15
Last Modified : 07 Feb 2019 14:15

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800