1
$\begingroup$

Im following these slides from "An Introduction to the Theory of Elliptic Curves" http://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf, but I'm having some difficulty understanding how the ECDLP can be solved in anomalous curves.

On the slides it says: "If #E(Fp) = p, then there is a “p-adic logarithm map” that gives an easily computed homomorphism logp-adic : E(Fp) -> Z/pZ. It is easy to solve the discrete logarithm problem in Z/pZ, so if #E(Fp) = p, then we can solve ECDLP in time O(log p)."

But I'm having trouble understanding some concepts. I understand that there exists an homomorphism between the elliptic curve E(Fp) and the ring of integers Z/pZ. I might be wrong but from what I understand this homomorphism is map phi that satisfies this properties

  • phi(O) = 0
  • phi(P + Q) = phi(P) + phi(Q)
  • phi(kP) = k.phi(P)

What I don't understand is why is it easy to solve the discrete logarithm problem in Z/pZ. Isn't the Diffie Hellman key exchange based on the difficulty of computing discrete logarithms?

But even assuming that it is easy do solve the DLP in Z/pZ, how could I get to the solution to the ECDLP assuming I have the solution to the DLP?

Finally, does anyone know any books or papers where I can read more about this? I tried looking but didnt find anything

Improve this question
$\endgroup$
2
  • $\begingroup$ Related: math.stackexchange.com/questions/3021935/… $\endgroup$
    – kodlu
    Mar 1 at 5:51
  • $\begingroup$ The solution process is very simple as noted on slides 3 and 53, we can compute inverses mod $p$ using the extended Euclidean algorithm and then note that $k\equiv\phi(kP)\phi(P)^{-1}\pmod p$. My favourite introduction to anomalous curves is Elliptic Tales by Ash and Gross chapter 9 section 3. It provides a nice step-by-step example computation of the map. $\endgroup$
    – Daniel S
    Mar 1 at 7:29

1 Answer 1

Reset to default
1
$\begingroup$

What I don't understand is why is it easy to solve the discrete logarithm problem in $\mathbb{Z}/p\mathbb{Z}$. Isn't the Diffie Hellman key exchange based on the difficulty of computing discrete logarithms?

In the additive group $\mathbb{Z}/p\mathbb{Z}$, DLOG is equivalent to computing a modular inverse, which is efficient. I highly suspect the target of the $p$-adic logarithm is this additive group, as

  • the slides use different notation for multiplicative groups,
  • you are right --- if it were a multiplicative group DLOG wouldn't be easy, and
  • logarithms convert multiplication into addition, so the group operation in the codomain of a logarithm should really be addition.

But even assuming that it is easy do solve the DLP in $\mathbb{Z}/p\mathbb{Z}$, how could I get to the solution to the ECDLP assuming I have the solution to the DLP?

In general, given an efficiently computable injective homomorphism $\phi: G\to G'$, if DLOG is easy in $G'$, then it is easy in $G$. This is because, given $t = g^a$, one can

  1. compute $\phi(t) = \phi(g^a) = \phi(g)^a$
  2. compute the discrete logarithm of $\phi(t)$ to recover $a$.

If $\phi$ isn't an injection you might run into some issues/have to do some more work, but the existence of such a homomorphism is good for attackers generically. I think pairing-based cryptography has more examples of such things if you're interested in other examples, but don't know details myself.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.