2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note that the discrete logarithm problem can be defined for arbitrary groups, ie sets with a binary operation that satisfy certain properties. It just so happens that a) we can't reverse this efficiently for modular integers with multiplications and for EC points with addition and b) these two are efficiently computable / easily understandable. $\endgroup$ – SEJPM Jan 14 '18 at 20:48
  • 1
    $\begingroup$ @MarquisDeSitruce If you have two accounts that you would like to join together, please sign into either account, visit the contact form and select ‘I need to merge user profiles’. After you contact us, the Stack Exchange Team will reach out to verify that you own both accounts. If we can confirm your ownership, we will initiate a merge. $\endgroup$ – e-sushi Jan 15 '18 at 4:28
4
$\begingroup$

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.

Challenges

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)))$.

  • Failing to fulfill this property implies the ability of an adversary to recover the private key

The second is that the public keys must not be usable to reach the shared secret.

  • I.e. if $share_{secret} = pub_1 * pub_2$, then recovery of the private key is not necessary to break the system

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.

  • Without an algebraic shortcut, computing a public key is computationally intractable.

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)

  • If there is no generator, you cannot generate group elements, and hence no key agreement can occur

Edit in response to further questions/comments

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$.

Side note about $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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jan 15 '18 at 4:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.