5 ms·
No, because in elliptic curve Diffie-Hellman, the private key isn't used to invert anything, as opposed to RSA (a true example of a trapdoor), where it is.
by agwa 11y ago
No, because in elliptic curve Diffie-Hellman, the private key isn't used to invert anything, as opposed to RSA (a true example of a trapdoor), where it is.
- markc 11y agoThanks for this. I was unclear on this point. So looking at the discrete log problem vs a trapdoor function: Discrete log: for f(x) = y - Easy: given f and x find y. - Hard: given f and y find x. Trapdoor: for f(x) = y - Easy: given f and y find x, given a secret, e.g. (p-1)(q-1) in RSA. - Hard: given f and y find x, without possesion of the secret. Is that accurate, or have I misstated the essential difference somehow?
- agwa 11y agoYes, that's essentially the difference between a one-way function and a trapdoor function. I'm sure you knew this already, but for completeness, another property of the trapdoor function is: - Easy: given f and x find y.
- ecesena 11y agoWell... 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.
- pbsd 11y agoWhile 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.