I am implementing a key distribution protocol described by Torben Pedersen in A Threshold Cryptosystem without a Trusted Party (EUROCRYPT'91). In the protocol, the $n$ parties distribute a public key for the ElGamal cryptosystem, where each party ends up with "part of" the private key and can work together to decrypt a message.

In the paper, Pedersen states that the parties all agree on the two primes $p$ and $q$, and the generator $g$ of $\mathbb{G}_{q}$. $h$ is then computed based on the individiual's choice of the private key $x_{i}$ (so that $h_{i} = g^{x_{i}}$ and $h = \prod_{i}^{n} h_{i}$).

If $p$ is sufficiently large, can the public parameters $p$, $q$, and $g$ be reused? It seems to me that if in each round of encryption, each party selects a new $x_{i}$, thus resulting in a new $h$, that the values of $p$, $q$, and $g$ can be persistent.

I ask this because finding a random safe prime of 1024 bits can be slow, and finding a generator of $\mathbb{G}_{q}$ can take a very long time. If these could be agreed upon well in advance and then reused, it makes the protocol more practical.

If $(p, q, g)$ can be reused, is this true for ElGamal in general?


This question probably goes much deeper than what you actually aimed for. Simply speaking: If you use $(p,g,h)$ just a couple of times, where $x$ is not revealed in any way, then yes you can reuse it. If you reuse it very often you might run into trouble. However in a general ElGamal-like encryption system, you can use a single public key as often as you want.

The tricky part in the security proof is, when you have to deal with security under "selective openings", where you consider a larger number of private/public keys, and grant the attacker the ability to open some of them and want to know if the remaining ones are still secure. A paper about this is e.g. "Encryption Schemes Secure under Selective Opening Attack" (Bellare, Yilek, 2009) or "Possibility and impossibility results for encryption and commitment secure under selective opening" (Bellare, Hofheinz, Yilek, 2009)

| improve this answer | |
  • 2
    $\begingroup$ Are you saying there is an attack if you re-use $(p,g,h)$ too many times? Are you saying that existing proofs don't make any promises if you re-use $(p,g,h)$ too many times? Can you give some intuition for what the nature of the alleged trouble is? I find it hard to believe that there is a real problem. It is bog-standard to re-use the public key $(p,g,h)$ in discrete-log-based cryptosystems; is there any reason that Pederson would be different? $\endgroup$ – D.W. Apr 14 '14 at 16:58
  • $\begingroup$ It might be standard to re-use the public key in dlog-based systems, but the problem is that standard security definitions (IND-CPA, IND-CCA) do not consider multiple keys. It's proven, that IND-CPA does not imply security under (simulation-based and full indistinguishability-based) selective opening (actually, there are multiple variants of SO-security, see On definitions of selective opening security (Böhl, Hofheinz, Kraschewski, 2012), see figure in section 1). If you run any kind of scheme with "just" IND-CPA or IND-CCA security with multiple keys, this could potentially apply. $\endgroup$ – tylo Apr 15 '14 at 11:09
  • $\begingroup$ Concerning normal ElGamal: This problem does apply, if you use a fresh private/public key for every new message. And in the question it was stated, that in each round every party chooses a new $x_i$. $\endgroup$ – tylo Apr 15 '14 at 11:11

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.