Threshold encryption

Is there any (k,n)-threshold encryption scheme, such that the decryption process is non-interactive, i.e., the decryption can be processed "in a line" where each party "in the middle of the line" receives a partially decrypted ciphertext, perform partially decryption itself, and then pass it on to some other party?

It can be assumed that the key generation is interactive.

• For a public key encryption system based on DH key agreement with the secret scalar split using shamir secret sharing this is pretty trivial. If the parties know ahead of time which set of k of them will participate, the k such participants re-construct the distributed key, multiply the ephemeral public key by their re-constructed share and add the resulting points however they like to obtain the final shared secret. If you want this to be a line, it can be a line, possibly enforced by having each participant send the in-progress sum encrypted to the next participant. Jul 12, 2023 at 12:31
• Let me clarify my question. In the part of non-interactiveness, I meant that they don't know ahead of time who the k participants are, ahead of time. By saying "line" I meant that each party performs a computation once and then sends the output to some other party (which can be freely selected by the party, after completing the partial decryption). Jul 12, 2023 at 13:28
• Given that Shamir Secret Sharing involves using f(x)=y polynomial points to find f(0) and that reconstruction is linear in the y values, participants could compute and share Z=y*E where y is their polynomial scalar and E is the ephemeral public key point. The result is a list of (x,Z) points that can be re-assembled using Lagrange basis polynomials in much the same way as (x,y) points can. So participants create a list of k such (x,Z) points and then someone does the reconstruction but of the shared DH secret in the EC point domain rather than the distributed key. Jul 12, 2023 at 14:00
• I guess that you refer to a process where the parties engage in a DH key exchange, where the ciphertext is $Z*m$ for some plaintext $m$, so that parties can reconstruct $Z=\sum_{i\in [n]}Z_i*L_i(X))$ (where $L_i$ is the Lagrange term). But is there a way to keep the secret key not being leaked to any of the parties? Jul 12, 2023 at 16:19
• That's exactly what I had in mind. Reconstructing the DH shared secret is obviously possible and then whoever has the Z[i] terms from all k participants can just do that. Presumably this is the last person in the hypothetical line. Ensuring no individual has access to the final Z would require distributing and combining the post-decryption computation with the decryption itself. So what happens to the plaintext afterwards? If it gets delivered to someone, you can just deliver the Z[i] shares and have them do the reconstruction and decryption obviously. Presumably it's more complicated? Jul 12, 2023 at 17:01

One can build such schemes from lattices, though there is a great deal of nuance that must be taken.

The high-level idea of the construction is as follows. The following is true for essentially all lattice-based schemes (all I know, which is quite a few), namely for a (matrix) ciphertext $$C$$, there is an appropriate (vector) secret key $$s$$ such that

$$C^ts = \mathsf{error\_correct}(m) + e$$

where $$m$$ is the message, $$e$$ is the error. Here, $$\mathsf{error\_correct}(m)$$ is some procedure that allows one to recover $$m$$ from the (noisly encoded) message $$\mathsf{error\_correct}(m)+e$$. The most common way is to write $$\mathsf{error\_correct}(m) = (q/2)m$$, and then divide by $$(q/2)$$ and round to the nearest integer. There are other techniques possible though.

One can replace "matrix" and "vector" with other algebracially structured things, i.e. module elements over some ring. I won't bother. This "linear decryption" structure is the basis of all of the homomorphic properties that lattice-based schemes have (though it isn't sufficient by itself --- code-based schemes can often have a similar structure, but we can't build FHE from them).

Anyway, it can also be used to build threshold encryption. The idea is to use some linear secret-sharing of $$s$$, say $$s = \sum_i a_i s_i$$. We then can write

$$C^ts = C^t(\sum_i a_i s_i) = \sum_i (a_i C)^ts_i.$$

I.e. each participant computes (local) decryptions of $$a_i C$$, where $$a_i$$ are the coefficients determined by the linear secret-sharing scheme. One can then sum the resulting "partial decryptions" to get the full decryption.

There are two nuances to take care of here though

1. Computing $$a_i C$$ increases the error from $$e$$ to $$a_i e$$. This might overwhelm the error-correction. This can be fixed by using secret-sharing with small (say $$\{0,1\}$$) coefficients, or appealing to lattice-based schemes that admit efficient multiplication by large scalars.

2. The partial decryptions $$\lfloor a_iC^ts / (q/2)\rceil$$ may leak information about the error $$e$$, which can cause security issues. This can also be fixed in several ways, the simplest is to add additional error $$e_{\mathsf{large}}$$ (often called "smudging" or "flooding" error) such that $$e_{\mathsf{large}}+e$$ is hard to distinguish from $$e_{\mathsf{large}}$$, i.e. it "hides" the sensitive error $$e$$.

After fixing things in the above way

1. decryption is non-interactive, and
2. can be processed "in-line" as you want. Namely, the $$i$$th party takes the currently being processed decryption $$c$$, and sends $$c + (a_i C^t s_i + e_{\mathsf{large}})$$ to the next party. The final party then computes $$c\mapsto \lfloor c / (q/2)\rceil$$.
• That's an interesting approach. If I understand you correctly, nobody (even the last party) does get to know $s$ because of the accumulative error. Is that correct? Jul 13, 2023 at 16:33
• Yes. Note that this is a requirement for any threshold decryption, even ones without your "in-line processing" requirement. Jul 13, 2023 at 16:50