# Is there an effective way for public key generation in homomorphic encryption schemes?

Is there any way to effectively generate valid distributed public key in schemes like ElGamal or Benaloh for a number of participants? There's no need in private keys since there's no intent to decrypt messages at all, only to encrypt them securely.

As far as I know, there's no effective way to generate distributed key pair in Benaloh.

-
As far as the ElGamal scheme, have a look at the following link. Not sure if that's what you're after, though. – user476 Sep 23 '11 at 9:11
@Bill - thanks a lot. I'll take a look. – Andrei Petrenko Sep 23 '11 at 9:50
I'm having a hard time understanding the question. What exactly do you want to accomplish? The standard specification of El Gamal already describes how each participant can generate their own keypair. What more do you need? What is wrong with the answer "run the standard procedure to generate a keypair, and keep the public key"? – D.W. Sep 26 '11 at 4:16
@D.W. Distributed key generation requires pretty much work. I wonder, if it is assumed that we don't need public key, will it facilitate the process. – Andrei Petrenko Sep 27 '11 at 7:22
@Andrei, thanks! It helps to hear that you are talking about distributed key generation. I presume this means that you want $n$ parties to work together to generate a single public/private keypair, so that any $n$ of them can jointly decrypt, but no $n-1$ of them are able to decrypt. But, I'm still confused: the original question says you don't need the private key, but your comment says you don't need the public key. Which is it? Actually, I'm a bit puzzled how you wouldn't need either. You're going to encrypt message but there is no way to ever decrypt: can that possibly be right? – D.W. Sep 27 '11 at 7:41

I must confess to not fully understanding your question but hopefully this will assist.

To generate a public key in Elgamal, you need a group (e.g., subgroup $\mathbb{G}_q$ of $\mathbb{Z}_p$ for large primes $p,q$) and a generator ($g$ where $\mathrm{order}(g)=q$).

A secret key is chosen from $x \in_r \mathbb{Z}_q$ and the public key is computed as $y=g^x$.

• If you want to generate a public key $y$ without caring about $x$, you can use any element of $\mathbb{G}_q$.
• If you want to ensure that no one knows $x$ for a given $y$, you could compute $y_i=\mathcal{H}(g)+i$ for $i=\{0,1,2,\ldots\}$ until you find a $y_i \in \mathbb{G}_q$.

For Benaloh (or Paillier), the first point is the same, the second is more complicated if you want to additionally ensure that no one knows the factorization of $n=pq$ (however there are techniques to do this).

Finally, I do not see any applications of encrypting without requiring decryption. If you simply want to obfuscate a value, there are more efficient primitives you can use. If you don't need decryption (per se) but do want to do things like plaintext equality tests, these require a decryption key!

-
Thanks a lot for your help again, Jeremy. – Andrei Petrenko Sep 23 '11 at 15:47

As far as the ElGamal scheme, I have given it some thought. With all due respect to the paper that I provided that appears to select different private-public key pairs for each participant/entity, I believe another way to set up an encryption system for multiple participants using the same private key (if that's what you desire), is to use different generators of the primary field/group, $G_{q}$, that you select.

As a simple example, take the cyclic (multiplicative) group $\mathbb{Z}^{*}_{13} = \mathbb{Z}_{13} \setminus \{0\}$. The generators of this group are $g=2$, $g=6$, $g=7$ and $g=11$. That is, order$(2)=12$, order$(6)=12$, etc. To generate a public key, select a random $x$ from $\{0,...,11\}$. Then, for each generator, $g_{i}$, compute $h_{i} = g_{i}^x$. That is, $h_{1} = 2^{x}$, $h_{2} = 6^{x}$, etc. Clearly, no matter the value for $x$, each participant will have a different public key denoted by $(\mathbb{Z}^{*}_{13}, 13, g_{i}, h_{i})$.

Encryption works by participant $i$ choosing a random $y$ for every message from $\{0,...,11\}$, then calculating $c_{1} = g_{i}^y$. Participant $i$ also calculates the shared key (called the ephemeral key) by $s_{i} = h_{i}^{y}$. Finally, participant $i$ then converts the message $m$ into $m' \in \mathbb{Z}_{13}^*$, and calculates $c_{2} = m' \cdot s_{i}$. Participant $i$ then sends the cipher text $(c_{1},c_{2}) = (g_{i}^{y}, m' \cdot h_{i}^{y}) = (g_{i}^{y}, m' \cdot (g_{i}^{x})^{y})$.

Decryption of the cipher text $(c_{1},c_{2})$ works by calculating the shared secret $s_{i} = c_{1}^{x}$ using the same private key $x$, and then computing $m' = c_{2} \cdot s_{i}^{-1}$. The message $m'$ is then converted back to the plain text message, $m$.

The decryption step produces the intended message since

$c_{2} \cdot s_{i}^{-1} = m' \cdot h^{y} \cdot (g_{i}^{xy})^{-1} = m' \cdot g_{i}^{xy} \cdot g_{i}^{-xy} = m'$

For the scheme to be secure, the user will have to select $q > 2^{2000}$ (with current technology). Note, however, that if one participant's security is compromised, then all participants' securities are compromised. This is probably why it would pay to have a different pair of public-private keys for each participant.

-