Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
If discrete logarithm is based on the fact that finding $x$ for $a^x$ is difficult, wouldn't it be difficult to find $n$ such that if $f(x_1) = x_2$ then $f(x_2) = x_3 ... = x_n$ if $x$ is a generator with the equation for a group $N$?
I'm just confused as to why there seem to be only two discrete logarithm problems, EC scalar multiplication and exponentiation.
Applying a function successively as you indicate does indeed form a group - Each time the function is applied, it is effectively equivalent to incrementing the group value by 1. This allows for an indirect way to compute an addition operation, by enumerating the number of times that the function has been applied.
You can actually instantiate Diffie-Hellman with an arbitrary deterministic function $f$ - correctness is guaranteed, but security is not.
Effectively, your DH private key is the number of times that the function has been applied. In classic DH, the function $f$ is simple multiplication by the generator $g$.
It is easy to see that when you apply the function $x$ times, and then apply the function $y$ more times, then the function has been applied in total $x + y$ times. Provided that both parties use the same $f$ and initial starting value (the generator $g$), both parties will arrive at the same value.
An example with small numbers:
$priv_1 \leftarrow 4\\ priv_2 \leftarrow 3\\ pub_1 \leftarrow F(F(F(F(g))))\\ pub_2 \leftarrow F(F(F(g)))\\ share_1 \leftarrow F(F(F(F(F(F(F(g)))))))\\ share_2 \leftarrow F(F(F(F(F(F(F(g)))))))$
Clearly, $share_1$ and $share_2$ yield the same output, as the function has been applied the same number of times. Thus correctness is guaranteed.
There are three challenges that I have encountered to create a DH protocol this way.
The first is finding some $f$ that is difficult to recover the number of times that $f$ has been applied, given some output $F(F(F....(g)))$.
The second is that the public keys must not be usable to reach the shared secret.
The third requirement is that the function must offer an algebraic shortcut that allows you to compute the $N_{th}$ term without actually invoking $f$ $N$ times. For example, you can instantiate a DH like protocol using a standard cryptographic hash function such as sh256 - but there is no way to shortcut such a function. For security, a private key is a number that is at least 128 bits in size; Using sha256 for DH would imply the need for on the order of $2^{128}$ invocations of the function.
There is a actually fourth requirement that may or may not be trivial to fulfill: Finding a generator for the group must be "easy". (thank you to MarquisDeSitruce for pointing this out)
Since $f$ can be an arbitrary function, some are indeed trivial to recover the private key from, others are not; The exact way to violate that requirement depends on the exact ff that you use. Clearly if ff is $x+1$, then recovering the private key from the public key is trivial. There must exist no algorithm that can recover the private key in less time than guessing it; It does not have to be an otherwise convenient/trivial algorithm i.e. LLL could probably break $mx+b$.
Actually, I have experimented with that particular function $mx + b$. It provides a shortcut (involving modular exponentiation and a geometric series); Unfortunately, it is broken. I don't usually bother to write up attacks, I tend to perform them live in the python interpreter. I don't remember the attack offhand, if I recall correctly it was algebraic, breaking the system in negligible time/space.
