Threshold decryption in multi-key homomorphic encryption

Question

I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably I misunderstood something.

MKHE allows multiple clients to encrypt their inputs $x_i$ with their private keys, which is joined into a common ciphertext $C$. An arbitrary function $f$ can then be used on $C$ to produce an encryption $C_f$ of $f(x_1,\ldots, x_k)$. Finally (and most importantly for this question), each client creates a partial decryption of $C_f$, which is joined to obtain $f(x_1,\ldots, x_k)$.

I will explain how this is done in this paper based on BFV FHE scheme (RLWE), since I think it is maybe the most simple. There are other approaches with similar ideas like this first paper, this paper ,...

For simplicity I will consider just a simple operation of addition. Say we have three clients, each encrypting $x_i$ and at the end we want to get $f(x_1,x_2,x_3) = x_1 + x_2 + x_3$. The scheme is based on RLWE problem, so let $R$ be a ring and $D_{\sigma}$ a distribution for which RLWE problem is hard. Let $q$ be the modulus of $R$ and $t$ the modulus of plaintext. Define $\Delta = \lfloor q/t \rceil$.

Setup: Let $a \in R$ be a uniformly random element.

Key-gen: Each client samples a secret and noise $s_i, e_i$ with $D_{\sigma}$ and set $b_i = -as_i + e_i$. Then $(s_i, b_i)$ is his key.

Encrypt: Each client encrypts $x_i$ by sampling $r_i, e_i^1, e_i^2$ with $D_{\sigma}$ setting $(c_i^0, c_i^1) = (b_ir_i + e_i^1 + \Delta x_i, a_ir_i + e_i^2)$

Eval: Ciphertexts $(c_i^0, c_i^1)$ are evaluated into an encryption of $f(x_1,x_2,x_3)$ by defining: $C_{f} = (c_0, c_1, c_2, c_3)$ where $c_0 = c_1^0 + c_2^0 + c_3^0$, $c_1 = c_1^1$, $c_2 = c_2^1$, $c_3 = c_3^1$.

PartDec: Each client samples so called "smudging noise" $e_i^{sm}$ and sends: $\mu_i = c_i^1s_i + e_i^{sm}$

MergeDec: Everyone can calculate $\mu = c_0 + \mu_1 + \mu_2 + \mu_3$ from which corresponds to $\Delta(x_1 + x_2 + x_3) + \text{noise}$ so the result can be extracted.

QUESTION: The reason for the security of the partial decryption is that the "smudging noise" should hide the secrets. But if I use the partial decryption $\mu_i$ of a client together with his partial ciphertext: $$c_i^0 + \mu_i = (b_ir_i + e_i^1 + \Delta x_i) + (c_i^1s_i + e_i^{sm}) = ((-as_i + e_i)r_i + e_i^1 + \Delta x_i) + ((a_ir_i + e_i^2)s_i + e_i^{sm}) = e_ir_i + e_i^1 + e_i^2s_i + e_i^{sm} + \Delta x_i$$ But this means that one can get $x_i$ which is not ok. One can hide $x_i$ only if $e_i^{sm}$ would be big enough to hide it. But then also $\mu$ would be flooded with noise. What am I missing?

Answer 1

Everything you write looks correct. However, you may be expecting the distributed decryption protocol to have a security property that it does not (and was not intended to, and really cannot in your example) have.

Specifically, the Mukherjee-Wichs paper you linked defines security to say (roughly) that, given the evaluated ciphertext, its underlying plaintext, and the secret keys for all but one of the parties, we can statistically simulate that party’s partial decryption. This corresponds to all but one of the parties being semi-honest, and protecting the privacy of the remaining honest party’s input (as far as is possible).

In your example, the evaluation function just sums the three inputs. Because all but one of the parties is semi-honest, the adversary knows all their inputs. It is also entitled to the output sum of all the parties’ inputs. This means it can trivially compute the honest party’s input! So, there is actually no “security violation” arising from the fact that the decryption protocol implicitly reveals the honest party’s input, because that input is implicitly revealed by the function itself.

If you consider a different evaluation function that doesn’t implicitly reveal the honest party’s input, then I think you should see why the “smudging” noise works as intended.