BGV KeyGen-- Can a maliciously-generated secret-shared key break security (e.g. SPDZ)?

Question

I was (re)reading the paper "Practical Covertly Secure MPC for Dishonest Majority–or: Breaking the SPDZ Limits".

One of the key points in this paper is that they present a covertly secure BGV key generation protocol (Protocol B1, p15). The public key is revealed, but the secret key is full-threshold secret-shared among the parties.

They achieve covert security by generating multiple keys, and then opening all-but-one (provably) at random and checking that the parameters were generated correctly.

I understand why this is necessary with the $\epsilon_{i, j}$. If the error parameters are too small, then the underlying lattice problem is not hard enough. But it seems this could be fixed by each party adding an error that is large enough for the lattice problem to be hard. Then the security would be satisfied even if $n-1$ parties submit 0 as their error value. And in the honest case the error would be more than necessary, but definitely within the tolerable amount since BGV supports a lot of (homomorphic) ciphertext additions without the ciphertexts stopping to be decryptable.

Why is it necessary to check the $s_{i, j}$ and $b_{i,j}$? Is there an attack that an adversary controlling up to $n-1$ parties could do where they pick bad $s_{i, j}$ or incorrectly compute $b_{i, j}$ such that they can decrypt ciphertexts without collaborating with the honest players? Or in other words, why is this protocol not secure against malicious adversaries?

Answer 1

Short answer: I don't know of any practical attack that exploits a malicious key generation protocol to, say, learn something about an encrypted message. However, I imagine this is highly context-dependent (e.g. it seems hard to attack SPDZ this way, there may be other applications that are vulnerable) and there is no proof that no such attack exists.

Longer answer: A malformed public key can potentially lead to decryption errors, where the probability of an error depends on some secret information (such as a private key). This allows for selective failure attacks, where the adversary observes whether an error occurs or not to try and learn something about the secret, and makes it difficult to prove the protocol secure.

In general, these kinds of attacks can be very concerning, although in this case it appears harder to exploit.

Consider a malformed public key $pk = (a, \hat b:= b + \hat e) \in R_q^2$, where $(a,b)$ is a correct key and $\hat e$ is some maliciously chosen, large error.

The first component of an honestly generated ciphertext $(c_0,c_1) = Enc_{pk}(m)$ has the form $$c_0 = \hat b\cdot v + p\cdot e_0 + m$$

where $v$ comes from the ring-LWE secret distribution, and $e_0$ is a noise term (both sampled during encryption).

The malicious $pk$ introduces an additional error $\hat e \cdot v$ into $c_0$. When decrypting the ciphertext, decryption will likely be correct if $\|\hat e \cdot v\|_\infty < q/p$, but otherwise an error will occur.

Now, if decryption succeeds, the adversary will learn one bit of information on the secret $v$, namely that $\|\hat e \cdot v\|_\infty < q/p$. This means we can no longer use the standard technique of showing ciphertexts are pseudorandom under ring-LWE. That's because the proof requires $v$ to be distributed like a ring-LWE secret and completely unknown to $n-1$ parties, so that $(c_0,c_1)$ looks like a valid ring-LWE sample.

Finally, note that it seems very hard to exploit this leakage in a practical attack, particularly since the $v$ value is different with every ciphertext, so the leakage can't be reused. I'd speculate that it might even be possible to prove this secure for SPDZ under some variant of ring-LWE with leaky secrets.