Paper Info
Title
Nonuniform Polynomial Time Algorithm to Solve Decisional Diffie-Hellman Problem in Finite Fields under Conjecture
Abstract
In this paper, we show that curves which are defined over a number field of small degree but have a large torsion group over the number field have considerable cryptographic significance. If those curves exist and the heights of torsions are small, they can serve as a bridge for prime shifting, which results a nonuniform polynomial time algorithm to solve DDH on finite fields and a nonuniform subexpontial time algorithm to solve elliptic curve discrete logarithm problem. At this time we are unable to prove the existence of those curves. To the best of our knowledge, this is the first attempt to apply the ideas related to the Uniform Boundedness Theorem(UBT), formerly known as Uniform Boundedness Conjecture, in cryptography.
Year
DOI
Venue
2002
10.1007/3-540-45760-7_20
CT-RSA
Keywords
Field
DocType
nonuniform polynomial time algorithm,elliptic curve,uniform boundedness theorem,finite fields,finite field,solve decisional diffie-hellman problem,considerable cryptographic significance,uniform boundedness conjecture,nonuniform subexpontial time algorithm,number field,small degree,discrete logarithm problem
Discrete mathematics,Finite field,Uniform boundedness,Algorithm,Algebraic number field,Time complexity,Conjecture,Counting points on elliptic curves,Elliptic curve,Mathematics,Discrete logarithm
Conference
ISBN
Citations 
PageRank 
3-540-43224-8
1
0.65
References 
Authors
8
2
Name
Order
Citations
PageRank
Qi Cheng144863.05
Shigenori Uchiyama237140.90