One example of a DLP based crypto system (or rather DDH based crypto system) where the public key parameters include two independent generators of the subgroup, is Cramer Shoup. Since the security proof of this scheme is based on DDH, it seems at least one of the two generators has to be uniformly chosen anew for each public key, and made part of the public key, rather than made part of domain parameters that are shared between multiple key pairs.
This seems a bit impractical, assuming you want a crypto system where the public key parameters are shared between multiple key pairs, and the individual public keys contain no more information than necessary. Furthermore it is a bit discomforting that e.g. Cramer Shoup does not include a method for verifying the validity of the generator choices, even though implicit verification is entailed by the trust model - you can e.g. test that the prime parameters are indeed prime, but it is harder to test if the generators have been deliberately chosen to facilitate discrete logarithm calculation.
Does this matter in the case of Cramer Shoup? I don't know, and that's not really my primary question interest. It might be noted that the relation between the two generators $g_1, g_2$ is not retained as part of the private key, and that the owner of the private key at no point in the normal operation of the scheme gets to prove that these generators have been correctly generated, but that might be insignificant. Rather, I am asking whether other schemes exist that also make use of more than one generator, and which might include those generators in domain parameters rather than include them in the individual public key.
Just a crazy idea: Suppose, for instance, you choose a prime $p$ and a prime $q$ such that $p = 2kq + 1$ and such that the calculation of $\log_23 (\mod p)$ and $\log_32 (\mod p)$ is conjectured to be DLP-hard in $Z_p^*$. In such case the generators $g_1 = 2^{2k}(\mod p)$ and $g_2 = 3^{2k}(\mod p)$ might be deterministically generated (which has its own advantages with respect to assurance of validity) and included as part of the system parameters, provided that the security proof for the crypto system is such that it is sufficient that the relation between the generators $g_1$ and $g_2$ is DLP-hard.
Does there exist any public key crypto system for which choosing such public key parameters would make sense, i.e. one that rests on the assumption that $\log_{g_1}g_2$ and $\log_{g_2}g_1$ are DLP-hard, rather than the assumption that the $g_2$ element in $(g_1,g_2)$ is indistinguishable from random?
In order for such a crypto system to exist, the following four criteria have to be met:
- To begin with, the crypto system obviously has to use certain operations, such as modular exponentiation in $Z^*_p$, and have certain parameters, such as use multiple generators for a suitable subgroup.
- Finding $log_23\mod p$ and $log_32\mod p$ have to be hard problems. If $p-1$ e.g. is divisible by a smooth number, they might not be hard problems. There might be other criteria I am not aware of.
- The crypto system has to be based on a hard problem that is reducible to DLP, such as REPRESENTATION. There might be other hard problems that qualify.
- There has to be specific reasons, either practical reasons or security reasons, for using deterministically generated generators instead of random ones (such as storage/time/bandwidth requirements, or inclusion of the generators in domain parameters). As pointed out in one of the answers below, in some cases such reasons do not exist. That doesn't however entail that such reasons can't exist in other cases.