Public key generation in homomorphic encryption schemes

Question

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.

Answer 1

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!

Answer 2

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.