Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Well... it's used to invert the scalar multiplication and compute the discrete logarithm - with a notation similar to other comments:

  Easy: given int n, point P -> compute Q = nP

  Hard: given points P, Q (known to be nP for some n) -> compute n
This said, similarly as RSA vs factorization, DHP vs DLP (and other problems) are only assumed to be equivalent, meaning that one could find an easy way to break DH without computing the DLP.


While the equivalence between RSA and integer factorization is still an open question, the Rabin (exponent 2) trapdoor permutation is tightly equivalent to factoring.

Furthermore, for most groups the DHP is polynomially equivalent to the DLP. The requirement for this to be true is that there exists an elliptic curve with smooth order modulo the Diffie-Hellman group's order. Such smooth-order curves are hard to actually find for large groups, exponentially so (this is a fine example of the chasm between uniform and nonuniform reductions); but for elliptic curves groups used in practice, it is possible to find them. In other words, an easy way to break the DHP in smallish elliptic curve groups would lead to ECDLP solving with only polynomial overhead.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: