6 ms·

Wouldn't the "special information" be the private key in this case?

ColinWright 11y ago
It's more complicated than that. Consider RSA. Choose p, q, and let n=pq Note: phi(n) = (p-1)(q-1) Choose e Compute d such that de = 1 (mod phi(n)) The number d is your private key. Given a message M, E(M) = M^e (mod n) Given an encrypted message E, D = E^d (mod n). Magically, D=M. Now multiplying the numbers p and q is a one-way function, because there is no effective way to factor n (if p and q are chosen suitably.) The exponentiation M^e is a trap-door function because normally you can't undo it, but with any of the extra knowledge p, q, or d, then you can undo it. There are nuances, and time and time again I meet people who think lots of things are the same when in fact they are different, and the differences matter. A one-way function is not necessarily a trap-door function. In this case many things are equivalent in the sense that one can easily be computed given another, but the details actually matter. The point, though, is that there are on-way functions that do not have trap-doors and hence are not trap-door functions. The definition as given in the blog post seems to conflate the two, when in fact the difference is important. PKCs are often made by starting with a provably one-way function and trying to find a way of inserting a trap-door without weakening it. (Sorry if this is a little incoherent, it's late here, and I need to do some stuff before going to bed, and I have an early start tomorrow.)
- nightcracker 11y ago
  Perhaps a better example of a one-way function vs. a trap door is with symmetric cryptography? Let's look at two examples of a 2^128 -> 2^128 function f(n): - The first 128 bits of SHA2(n). It should be computationally infeasible to find n from the output. - AES128(n, k). It should be computationally infeasible to find n from the output, unless you know k.
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 ago
  Thanks 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 ago
    Yes, 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 ago
  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.
  - pbsd 11y ago
    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.

It's more complicated than that. Consider RSA. Choose p, q, and let n=pq Note: phi(n) = (p-1)(q-1) Choose e Compute d such that de = 1 (mod phi(n)) The number d is your private key. Given a message M, E(M) = M^e (mod n) Given an encrypted message E, D = E^d (mod n). Magically, D=M. Now multiplying the numbers p and q is a one-way function, because there is no effective way to factor n (if p and q are chosen suitably.) The exponentiation M^e is a trap-door function because normally you can't undo it, but with any of the extra knowledge p, q, or d, then you can undo it. There are nuances, and time and time again I meet people who think lots of things are the same when in fact they are different, and the differences matter. A one-way function is not necessarily a trap-door function. In this case many things are equivalent in the sense that one can easily be computed given another, but the details actually matter. The point, though, is that there are on-way functions that do not have trap-doors and hence are not trap-door functions. The definition as given in the blog post seems to conflate the two, when in fact the difference is important. PKCs are often made by starting with a provably one-way function and trying to find a way of inserting a trap-door without weakening it. (Sorry if this is a little incoherent, it's late here, and I need to do some stuff before going to bed, and I have an early start tomorrow.)

nightcracker 11y ago
Perhaps a better example of a one-way function vs. a trap door is with symmetric cryptography? Let's look at two examples of a 2^128 -> 2^128 function f(n): - The first 128 bits of SHA2(n). It should be computationally infeasible to find n from the output. - AES128(n, k). It should be computationally infeasible to find n from the output, unless you know k.

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 ago
Thanks 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 ago
  Yes, 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 ago
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.
- pbsd 11y ago
  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.