Suppose one is implementing a cryptographic scheme over a group where one needs the discrete logarithm to be hard - what is the recommended group to use? I'm looking for a group where calculations are simple but it doesn't need to be extremely efficient. I would therefore prefer some type of multiplicative group mod n. It seems different "diffie-hellmann" like schemes employ different groups. So here's some possibilities - I would ideally like them "ranked" in terms of security wrt. the discrete log problem (or any comments if some of them are terrible/insecure choices)

1) Generate a random, big prime "p" and use (Z_p)* as the group (i.e. the multiplicative group modulo a prime p) - the group will have order p-1.

2) Generate a random big integer "n" and use (Z_n)* as the group (i.e. the group will have order phi(n)).

3) Generate a large prime "p" and find a large prime-sized subgroup of (Z_p)*.

4) Generate a large number (not prime) "n" and find a large prime-sized subgroup of (Z_n)*.

(My guess of a ranking - in increasing level of security - would be 2, 1, 3/4).

Some articles seem to call for #3-#4. But are the benefits and are 1+2 inherently secure (I would guess #2 might be depending on factorization of n)? Also, what is the best way to generate a group like #3/#4 (depending on which one is better) Are there other even better choices for groups than 1-4? Also, does it matter what generator one uses? For instance, is the security of #1 intact if one uses the base g = 2?

Thank you in advance!

  • 2
    $\begingroup$ Check NIST and ANSI standards for discrete log-based crypto, they discuss parameter generation. $\endgroup$
    – pg1989
    Nov 26, 2013 at 20:57
  • 1
    $\begingroup$ Note that Decisional Diffie-Hellman will be easy for #1 and #2. $\;$ $\endgroup$
    – user991
    Nov 26, 2013 at 21:58
  • 1
    $\begingroup$ If you only want to rely on the discrete log problem and no additional assumptions such as factoring, choices #1 and #3 are suitable. In the former case you have to avoid choosing smooth group orders, i.e., that $p-1$ has only small factors. You can avoid this by choice #3 which is typically done by choosing $p$ to be a safe prime and then you also avoid that the DDH is easy (as Ricky mentioned for #1). As @pg1989 mentioned you can find strategies in NIST standards. And no, it doesn't matter which generator you choose - the smaller the better the efficiency. $\endgroup$
    – DrLecter
    Nov 26, 2013 at 22:00
  • $\begingroup$ @RickyDemer why #2 is easy? $\endgroup$
    – curious
    Nov 10, 2014 at 13:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.