New answers tagged

2

The question is referring to Nigel P. Smart's The Discrete Logarithm Problem on Elliptic Curves of Trace One, in Journal of Cryptology (1999) (earlier version). Quoting the intro: (…) we describe an elementary technique which leads to a linear algorithm for solving the discrete logarithm problem on elliptic curves of trace one. In practice, the method ...


8

Let's call the problem Square Diffie-Hellman (SDH). SDH is at least as hard as CDH in groups of known order and the reduction goes as follows.$^*$ Given an adversary $\mathsf{A}$ that breaks SDH, our goal is to construct an adversary $\mathsf{A}'$ that breaks CDH. Given the CDH challenge $(g,g^x,g^y)$, $\mathsf{A}'$ runs $\mathsf{A}$ thrice -- first on $(g,g^...


6

This problem is equivalent to the CDH problem: Here is how to solve CDH given an Oracle that solves this problem: Given $g, g^x$, we can compute $g^{x^{-1}}$ (which is equivalent to the CDH problem) by doing the following: Call the Oracle with $g, g^x$; the Oracle gives us a pair $g^{y}, xy$ We compute $(g^{y})^{(xy)^{-1}} = g^{x^{-1}}$, hence showing one ...


Top 50 recent answers are included