# Single Party Encryption, Multi Party Decryption

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?

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.

• I am missing your thoughts on how, exactly, this might be applied to a mixnet scheme. Dec 23 '13 at 0:20
• Check out Benaloh's voting scheme (link) which uses precisely this threshold scheme for mixnet-based electronic voting. The clue is this: mixing and decryption are separate things. In fact, mixing can be performed by anyone, as long as they have knowledge of the public key. This is done as follows: homomorphically multiply all the ciphertexts with an encryptions of 1 and change the order randomly. No computationally bounded adversary can link the incoming ciphertexts with the outgoing ciphertexts.
– Alan
Dec 23 '13 at 9:32
• Benaloh's scheme seems to be exactly what I am asking for, yes. On the negative side, though, the scheme uses commitments that induce an overhead for the mixes by a factor greater than 100 (with the parameter values recommended in the paper). It is obvious that there would be a risk for integrity if only two commitments were used by each mix, but would it lead to a risk of compromised anonymity? Dec 23 '13 at 18:28
• Anonymity is protected by the number of honest mix servers in the pipeline. The proofs of correct mix do not protect anonymity; they allow an observer to verify that the mix was performed correctly (without leaking the links between incoming and outgoing messages). If the requirements of these proofs are less stringent, it will be easier for mix servers to cheat but it will have no effect on anonymity.
– Alan
Dec 24 '13 at 12:43