In RSA, given only $(n,e)$, where $n =pq$ and $e$ is the public exponent, it is hard to find $p$ and $q$. It also seems hard to find $d$. So we came up the RSA conjecture that is RSA defines a trapdoor one-way permutation. Namely, given, $N,e$ defining $f,x \mapsto f(x)$ is easy; $y \mapsto f^{-1}(y)$ is hard; but $f^{-1}$ is easy given $p,q$ (or $d$).

In their lecture notes Goldwasser and Bellare, claims that;

Note that this trapdoor is a property the discrete logarithm problem did not have.

They have a trapdoor ( actually backdoor), at least since 92' the Gordon's work;

Designing and Detecting Trapdoors for Discrete Log Cryptosystems. The abstract;

Using a number field sieve, discrete logarithms modulo primes of special forms can be found faster than standard primes. This has raised concerns about trapdoors in discrete log cryptosystems, such as the Digital Signature Standard. This paper discusses the practical impact of these trapdoors, and how to avoid them.

and many, some listed in Is it possible to generate backdoored DH parameters?

So the question is

  • Is there proof of Goldwasser and Bellare's claim that discrete logarithms cannot have trapdoor permutations?
  • if not, the lecture notes are written in 2008, is there any advancement on this?
  • 6
    $\begingroup$ The meaning of "trapdoor" is not the same in both citations. In the second one, that's more a backdoor, which existence is hidden. That's not the case with the RSA trapdoor, which existence is public knowledge, even if its key is not. The question remains interesting: can we make a trapdoor permutation with the DLP, or prove that can't be done? $\endgroup$ – fgrieu Oct 9 at 18:06
  • 2
    $\begingroup$ The only known one-way permutations are based on factoring or indistinguishability obfuscation. See crypto.stackexchange.com/questions/66388/… $\endgroup$ – Gee Law Oct 12 at 12:28
  • 3
    $\begingroup$ Well, there is a mixture of two (factoring and discrete log) - Paillier cryptosystem, which you can see as being a trapdoor to discrete log (as decrypting a message involves solving a discrete log). $\endgroup$ – Fractalic Oct 15 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.