Single Party Encryption, Multi Party Decryption

Question

I am looking for an adequate protocol for public key decryption, which would allow $n$ parties to jointly decrypt a cipher text. The usage scenario for such a protocol would be a mixnet that wouldn't require the sender to know all mixes in advance. The requirements are:

• There is a single externally known long term public key $Y$. Each decryptor $D_i$ has a long term private key $x_i$ and the decryptors do not reveal their respective private keys to each other.
• When decrypting a cipher text, it is done in sequence by the decryptors. Let the incoming cipher text be $c = c_0$. $D_i$ decrypts $c_{i-1}$ to $c_i$ and forwards it to the next decryptor.
• The order in which the decryptors decrypt the cipher text must be arbitrary, i.e. the encryptor does not have to know in which order the cipher text will be decrypted by the decryptors, or even how the private key is split up between the decryptors.
• The pair $(c_{i-1},c_i)$ must be indistinguishable from $(c_{i-1},u)$ for everyone except $D_i$, where $u$ is selected uniformly at random (from the set of intermediate cipher texts).

---

First question: I am correct that the above requirements might be met using the following protocol based on ElGamal:

• Let each $Y_i = g^{x_i} \pmod p$ be known by all decryptors and let $Y = \Pi_{i=1}^nY_i \pmod p$
• Let $m$ be the plain text and $c = (Y_0,r_0,e_0) = (Y,g^k \pmod p,Y^kPad(m) \pmod p)$, where $k$ is selected uniformly at random by the encryptor.
• $Y_i = Y_{i-1}g^{-x_i} \pmod p$
• $r_i = r_{i-1}g^{k_i} \pmod p$, where $k_i$ is selected uniformly at random
• $e_i = e_{i-1}r_{i-1}^{-x_i}Y_i^{k_i} \pmod p$
• If $Y_i = 1$ then $m = Unpad(e_i)$ else $c_i = (Y_i,r_i,e_i)$.

Note: This is a fragile scheme in many ways, but in particular because it might allow the first and last decryptor to collude. If $D_1$ multiply $e_1$ by a small integer, most $Unpad$ functions (such as PKCS#1 v1.5 and PKCS#1 v2.1) will fail, unless $D_n$ first divides $e_n$ by the same small integer. If this small integer is an identifier for the sender of the message, the scheme is broken.

---

Second question: Does there exist any similar protocol e.g. based on secret sharing that still meets all of the above requirements, but in addition:

• Allows $t \lt n$ of the $n$ decryptors to decrypt the cipher text?
• Allows the decryption to be performed in any order not necessarily agreed upon in advance, but still in a finite number of steps bounded by $poly(n)$?
• Features robustness, i.e. if a small numbers of decryptors (less than $n-t$) are compromised and participate in the decryption, $t$ remaining decryptors will still be able to eventually decrypt the message?

Answer 1

Check out Pedersen's scheme for threshold ElGamal (link). Also, check out (this) for an application to electronic voting.

Basically, the scheme works like this. There are $n$ parties, out of which at least $t$ must be reliable or else the scheme collapses. They choose a prime $p = 2q + 1$ where $q$ is also prime, i.e.: $p$ is a safe prime. Additionally, they choose a generator $g$ of the $p$-order subgroup.

Every participant $i$ chooses a polynomial $f_i(x) \in \mathbb{Z}_q[x]$ of degree $t-1$ and privately distributes the points $f_i(j)$ to each participant $j$. Each participant $j$ adds together all the points he received: $f(j) = \sum_if_i(j) \mod q$. The participants have now shared a global polynomial $f(x) = \sum_if_i(x) \mod q$ which is uniquely defined by $t$ points. The secret is located in $f(0)$.

In order to make the scheme verifiable, each of these private shares $f_i(j)$ is accompanied by a public commit value $g^{f_i(j)}$. Each participant is commited to his share $f(j)$ in the global polynomial as $g^{f(j)} = \prod_ig^{f_i(j)} \mod p$ is publicly known.

In order to raise a value $h$ to the power $f(0)$, the participants do the following. Each participant raises $h$ to the power of his own share. They publish $h^{f(i)}$ along with a Chaum-Pedersen proof (link) that the exponent in this value with respect to base $h$ is the same as the exponent in the commit value $g^{f(i)}$ with respect to base $g$.

Anyone can now combine the shares and calculate using Lagrange interpolation $g^{f(0)} = g^{\sum_if(i)\prod_{j \ne i}{-j \over i-j}} = \prod_i(g^{f(i)})^{\prod_{j\ne{}i}{-j \over i-j}} \mod p$.

The indexes $i$ and $j$ run over any set of at least $t$ trustworthy participants. This exponentiation procedure is used once for key generation and once for ciphertext decryption. Note that this allows an arbitrary order of contributions from the participants, so long as at least $t$ participants remain uncorrupted. For the rest we follow the regular ElGamal cryptosystem.