#StackBounty: #rsa #discrete-logarithm #trapdoor RSA like trapdoor permutations in Discrete logarithm

Bounty: 50

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 is discrete logarithms cannot have trapdoor permutations?
  • if not, the lecture notes are written in 2008, is there any advancement on this?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.