DLP based crypto systems with multiple independent generators

Question

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:

1. 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.
2. 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.
3. 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.
4. 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.

Answer 1

It's not impractical. Choosing a random generator $g$ is easy and can be done efficiently. It's efficient enough that it wouldn't be a problem to generate a random generator when you generate your keypair. I think your premise (your assumption that this is a problem or that it should be discomforting) is not valid. Consequently, I don't see the relevance of the question.

Let me elaborate a bit. There are two kinds of values that might be floating around:

• Domain parameters are parameters that are shared by many users. For instance, in a discrete-log based cryptosystem, if the modulus $p$ is shared by everyone, then it is a domain parameter.

• Individual parameters (to coin a term) are values that are used by a single party, and are generated by the same party who uses/relies upon them. For instance, a user's private key is an individual parameter, since it is generated by that user and only used by that user.

These two different kinds of values have different security and verifiability requirements:

• Domain parameters are critical and particularly sensitive, since they're generated by one person (e.g., a CA or trusted authority) but used and relied upon by everyone else. If the CA secretly and dishonestly constructs a domain parameter in a way that introduces a backdoor (rather than following the algorithm they were supposed to use), everyone loses. That's very bad. The standard mitigation is to provide everyone a way to verify that the CA generated the domain parameter honestly.

  In summary, domain parameters must be verifiable.

• Individual parameters don't have this problem. There's no reason for Alice to secretly embed a backdoor in her private key, since the only person's security who is harmed is Alice's (at worst others may obtain the ability to eavesdrop on messages encrypted to Alice, but a malicious Alice could always have achieved a similar effect simply by publishing all the messages she receives, and there's no way for others to verify Alice hasn't done that). There's no way for Bob to verify that Alice has kept the messages he sends her secret. Therefore, there's no reason why Bob would need to verify that Alice generated her private key honestly. For instance, we don't require that RSA provide a way for Bob to verify that Alice generated her RSA secret key using the algorithm she was supposed to use; if she does something different, we say it is her tough luck. There's no point in trying to prohibit what you can't prevent.

  In summary, individual parameters do not need to be verifiable, and there's no clear value to verifiability.

This means that your question is based upon a faulty premise. Your premise is that there's something wrong with a cryptosystem if the public key (an individual parameter) is not verifiable. This premise is not accurate; actually, there's nothing wrong with a cryptosystem where the public and private keys are not verifiable by third parties. We use cryptosystems like that all the time. Therefore, the best answer to the question is to un-ask the question.

I am making numerous assumptions about what you are asking. I confess I might not have understood what you really wanted to know, and what problem you are trying to solve; if so, my apologies.