1
$\begingroup$

The Wikipedia article on Discrete Logarithm just states without source:

In some cases (e.g. large prime order subgroups of groups ($\mathbb{Z}_p)^×$) there is not only no efficient algorithm known for the worst case, but the average-case complexity can be shown to be about as hard as the worst case using random self-reducibility.

To my understanding "large prime order subgroups of groups ($\mathbb{Z}_p)^×$" are also known as Schnorr groups. But apparently not everybody calls them that (?).

So where would I find a (citable) proof that the discrete logarithm problem is (assumed to be) hard for elements of a Schnorr group?

This is probably related to Why does Schnorr's Digital Signature scheme necessitate two prime numbers?, which would be my next question. The answer given there may be correct but also without a citable source...

$\endgroup$
1
$\begingroup$

I do not know an exact citable source.

However the rationale is roughly the following:

The Decisional Diffie-Hellman Problem (DDHP) is not hard in $\mathbb{Z}_p^*$ since the Legendre symbol leaks the parity of the discrete log (DLOG) [1 section 5.1.2, 2]. You can use this fact to build an efficient algorithm to distinguish between Diffie-Hellman and non Diffie Hellman tuples [3 section 6.6]. Another reason is the existence of the Pohlig - Hellman Algorithm [1].

Note that the semantic security of the ElGamal cryptosystem rests on the DDHP problem, which is believed to be easier than the DLOG problem.

References:

[1]Cryptography: Theory and Practice by Douglas Stinson

[2] Finding $x$'s parity in the discrete log problem

[3] https://crypto.di.uoa.gr/class/Kryptographia/Semeioseis_files/Cryptograph_Primitives_and_Protocols.pdf

$\endgroup$
  • $\begingroup$ But why does the order need to be prime? What is the problem if the order of the group was not prime? $\endgroup$ – Linus Aug 30 '19 at 8:56
  • 1
    $\begingroup$ Because if it is not prime, then the chinese remainder theorem through the Pohlig Hellman algorithm will effectively reduce it to (smaller) prime order subgroups. So I guess with prime orders you can estimate exactly the difficulty. $\endgroup$ – Panagiotis Grontas Aug 30 '19 at 13:53
  • $\begingroup$ Thanks for helping me out! This is really appreciated. $\endgroup$ – Linus Aug 30 '19 at 17:08

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.