# Best group if one wants the discrete log problem to be hard?

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!

-
Check NIST and ANSI standards for discrete log-based crypto, they discuss parameter generation. –  pg1989 Nov 26 '13 at 20:57
Note that Decisional Diffie-Hellman will be easy for #1 and #2. $\;$ –  Ricky Demer Nov 26 '13 at 21:58
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. –  DrLecter Nov 26 '13 at 22:00
Great, thanks - good answers! –  Morty Nov 27 '13 at 8:28
@RickyDemer why #2 is easy? –  curious Nov 10 '14 at 13:29