Silent Threshold Encryption Simplified

# Silent Threshold Encryption Simplified *Special thanks to Arka Rai Choudhuri, Sanjam Garg, Dimitris Kolonelos, Abhiram Kothapalli, and Mingyuan Wang for their feedback.* ## Backstory About a year ago, we put out a [threshold encryption scheme](https://eprint.iacr.org/2024/263) ([blogpost](https://hackmd.io/@guruvamsi-policharla/new-threshold-schemes)) with *silent setup*. Initially, we thought it was a nice improvement on threshold encryption by avoiding a distributed key generation. But it has since found applications in [timelock encryption](https://hackmd.io/@guruvamsi-policharla/new-threshold-schemes), [encrypted mempools](https://eprint.iacr.org/2025/1419), [proposer builder-separation](https://www.paradigm.xyz/2024/10/removing-the-relays), [distributed key generation](https://eprint.iacr.org/2024/2098) (funnily enough, it helped the very thing we tried to eliminate), [traitor tracing](https://eprint.iacr.org/2025/342), and [federated learning](https://eprint.iacr.org/2025/1579). Follow up work [[WW25]](https://www.cs.utexas.edu/~dwu4/silent-threshold.html) showed that you can get smaller ciphertexts and support more general access policies. So it's clear that "advanced" encryption schemes with nice properties like silent setup are useful. Other examples include [Batched Threshold Encryption](https://eprint.iacr.org/2024/669), [Distributed Broadcast Encryption](https://eprint.iacr.org/2023/874), [Registration Based Encryption](https://eprint.iacr.org/2018/1030), [Registered Attribute Based Encryption](https://eprint.iacr.org/2022/1500), and [Registered Functional Encryption](https://eprint.iacr.org/2023/395). But if you open one of these papers and stare at the construction, it seems like an arbitrary collection of group elements + randomness (at least to me). We would really like to bring some order to the chaos and find a nice framework to a) study these primitives and b) extend them in interesting ways, all without having to worry about the low-level details. Similar to how you can write ZK circuits while remaining oblivous to the details of the underlying proof system. ### It's all Witness Encryption If you zoom out enough, you'll realize that these advanced encryption schemes can be viewed as a witness encryption[^third] for some *specific* language. You might be thinking -- well that's obvious... but also kind of pointless because we don't have any efficient constructions for witness encryption. It's true that we don't have efficient witness encryption for all NP languages BUT we can have efficient constructions for *specific* relations that may not be NP complete. Starting from this observation, we designed a [framework](https://eprint.iacr.org/2025/1364) to build (concretely efficient) witness encryption schemes. We then use our framework to: - Recover previously known "advanced" encryption schemes - Establish new feasibility results - Improve best known results In this blogpost I'll revisit silent threshold encryption [[GKPW24]](https://eprint.iacr.org/2024/263), through the lens of our framework. As we'll see shortly, it allows for a much more intuitive explanation of everything that's happening.[^second] >[!Tip] I've set up this post with little exercises, so grab a scratchpad to work things out. ## Our Framework for WE If you've ever implemented circuits for zero-knowledge proofs using a DSL like Circom/Noir, you probably didn't implement everything from scratch yourself. Instead, you might have used "gadgets" written by experts for commonly used primitives like hashing/signatures and combined them in clever ways to build your final circuit. Now imagine being able to do this but for witness encryption. That's our framework. We provide you with "gadgets" -- witness encryption for small but powerful relations -- and you can compose them in non-trivial ways to build a witness encryption for a larger relation. You can also extend the framework with new gadgets! The following graphic is a good mental image to have: ![blog-fig](https://hackmd.io/_uploads/S1jv02u5ll.gif) There are statement variables $(x_1,x_2,x_3)$, and witness variables $(w_1,w_2,w_3)$ and gadgets that can be applied on any subset of statement-witness tuples to enforce a "constraint". We can additionally enforce logical relations on the output of gadgets such that the ciphertext can be decrypted only if `(Gadget 1 AND Gadget 2) OR Gadget 3` is satisfied. The rest of the blogpost is focused on building silent threshold encryption. There are two main steps: 1. Suppose for a moment that you had witness encryption for all languages in NP. Identify a relation that would be sufficient to build your application. 2. Next, express the relation of interest in terms of gadgets and let our compiler takeover to build the witness encryption. More often than not, you'll need to tweak and introduce some structure into your relation that will allow you to actually reduce to the gadgets. We'll see an example shortly. The methodology outlined above is quite general and will be broadly applicable to build any advanced encryption scheme. ## WE $\rightarrow$ Silent Threshold Encryption Let's dive in and build Silent Threshold Encryption. To quickly recall, Silent Threshold Encryption allows you to encrypt a message to $n$ parties such that: * Any $t$-out-of-$n$ can decrypt *non-interactively* viz. parties can locally compute a *partial decryption* of the ciphertext and broadcast it. Given $t$ partial decryptions, anyone can aggregate the partial decryptions to recover the message. * Ciphertext size $O(1)$ does not depend on number of parties * Parties do not interact, except for announcing their public key (Silent Setup) >[!note] Throughout this post, variables in blue are part of the statement (what you encrypt to) and variables in red are part of the witness (the key to decrypt the ciphertext). ## Step 1: Identify an interesting relation Let's start by identifying some relation, such that if we had a *succinct* witness encryption for it, then we can actually build Silent Threshold Encryption. As it turns out, this one will be sufficient: > You can decrypt my ciphertext if and only if you known signatures $\{\sigma_i\}_{i \in S}$ on a string $\mathsf{tg}$ from a subset $S$ of public keys $S$ $\subset$ $(\mathsf{pk}_1, \dots, \mathsf{pk}_n)$, where $S$ $\geq$ $t$ That looks like a mouthful, but all it's really saying is you can encrypt to a set of (signature) public keys, and signatures on $\mathsf{tg}$ are the key to decrypt: * $\mathsf{Enc}\big(m;$$(\mathsf{pk}_1, \dots, \mathsf{pk}_n), \mathsf{tg}, t$$\big) \to \mathsf{ct}$ * $\mathsf{Dec}\big(\mathsf{ct};$ $\{\sigma_i\}_{i \in S}$ $\big) \to m$ Do you see why this is sufficient to build Silent Threshold Encryption? It's worth taking to moment to figure out why. :::spoiler Answer Here's a protocol for Silent Threshold Encryption, given the above WE: * $\mathsf{KeyGen}$: Typically, this is an interactive procedure between the $n$ different parties. At the end of which, they establish a shamir secret sharing of a random sampled secret key. Instead, here we will simply have all parties sample a signing key pair $(\mathsf{pk}, \mathsf{sk})$ (locally) and publish $\mathsf{pk}$. No interaction needed. * $\mathsf{Encrypt}$: To encrypt a message to the $n$ parties, simply run the witness encryption's encrypt algorithm using the desired set of public keys, threshold, and a randomly chosen string $\mathsf{tg} \leftarrow \{0,1\}^{\lambda}$ * $\mathsf{Decrypt}$: To compute a partial decryption, each party will sign the string $\mathsf{tg}$. * $\mathsf{Aggregate}$: Given $t$ signatures (partial decryptions), anyone can run the witness encryption's decrypt algorithm to recover the message $m$. ::: :::info 💡 Looking ahead, we will actually build the above WE for [BLS signatures](https://www.iacr.org/archive/asiacrypt2001/22480516.pdf), the same one used for consensus on pretty much every blockchain! This enables interesting applications like [Removing Relays in PBS](https://www.paradigm.xyz/2024/10/removing-the-relays). ::: On the face of it, building a witness encryption for the relation above sounds like a daunting task. Especially if we want an $O(1)$ sized ciphertext. The first step is to make life a little easier by leveraging aggregate signatures. ### Aggregate Signatures BLS signatures have a very attractive property of [*aggregate* verification](https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html). The premise is simple. Suppose you wanted to verify that some $t$-out-of-$n$ different parties signed the same message. Naively, you would individually verify each signature under the corresponding public key. But BLS aggregate signatures allow you to do something more clever. Let $S \subseteq [n]$ be the set of signers. Very loosely: >[!Important] >Instead of demanding $t$ signatures $\{\sigma_i\}_{i \in S}$ under $\{\mathsf{pk}_i\}_{i \in S}$, we can demand a single signature $\sigma$ under an aggregate public key[^seventh] $\mathsf{apk} = \prod_{i \in S} \mathsf{pk}_i$. The aggregate signature is unique and one can compute it given $\{\sigma_i\}_{i \in S}$ as $\sigma = \prod_{i \in S} \sigma_i$. >[!Note] > In fact, we can use any linear combination for aggregation i.e. demand a signature under $\mathsf{apk} = \prod_{i \in S} \mathsf{pk}_i^{\alpha_i}$ for some $\{\alpha_i \neq 0\}_{i \in S}$. The signature would then be computed using the same linear combination $\sigma = \prod_{i \in S} \sigma_i^{\alpha_i}$. Looking ahead, this felxibility will be important. With this observation, we can instead focus on building a witness encryption for the following (somewhat) simpler relation: > You can decrypt my ciphertext if and only if you known a signature $\sigma$ on a string $\mathsf{tg}$ under an aggregate public key $\mathsf{apk}$, which is a "valid aggregation" of at least $t$ public keys from $(\mathsf{pk}_1, \dots, \mathsf{pk}_n)$. The witness encryption "circuit" now only needs to check one signature, and a public key aggregation (which is just an MSM). This begins to feels a lot more feasible now.  ## Gadgets To build the above witness encryption scheme, we will use our framework. We start by introduce three gadgets along with some nice self-contained applications. Let $e:\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ be an efficiently computable bilinear pairing, and let $\mathbb{F}$ be the underlying scalar field.[^fourth] ### Signature Gadget Let's start with something familiar that you've probably seen before. Witness encryption for signatures. Turns out [BLS signatures](https://www.iacr.org/cryptodb/data/paper.php?pubkey=150) support a witness encryption of the form: > You can decrypt my ciphertext if and only if you know a BLS signature $\sigma$ $\in \mathbb{G}_1$ on a string $\mathsf{tg}$ $\in \{0,1\}^*$ under some public key $\mathsf{pk}$ $\in \mathbb{G}_1$ >[!Note] > Note that the signature $\sigma$ and public key $\mathsf{pk}$ are both part of the witness. As is, it is quite easy to find a satifying witness for this statement. Sample a BLS signing key pair and sign $\mathsf{tg}$ with it. But when combined with other gadgets which enforce other constraints, the larger relation may be non-trivial. In all of our gadgets, **any witness element can be converted to a statement element**. This means we also have a witness encryption for: > You can decrypt my ciphertext if and only if you know a BLS signature $\sigma$ $\in \mathbb{G}_1$ on a string $\mathsf{tg}$ $\in \{0,1\}^*$ under a chosen public key $\mathsf{pk}$ $\in \mathbb{G}_1$ Things get a lot more interesting now because if you specify both a public key and string that needs to be signed, it can actually be hard to find a valid signature. This enables some very nice applications: - If we set $\mathsf{tg}$ to be the identity of users such as emails or phone numbers, then we get [Identity-Based Encryption](https://eprint.iacr.org/2001/090), where the master secret key is the signing key. - If we set $\mathsf{tg}$ to be the block height, and sign at every block height, then we get time-lock encryption. See [McFly](https://eprint.iacr.org/2022/433) for more details. This has also been deployed by [drand](https://www.drand.love) among other places. >[!Tip] > There's a variant of BLS signatures that allow group elements to be signed, and one can build a gadget for the same. If you set this group element to be the [KZG](https://www.iacr.org/cryptodb/data/paper.php?pubkey=23846) commitment, then you can actually build [Batched Threshold Encryption](https://eprint.iacr.org/2024/1516) and [Batched Identity-Based Encryption](https://eprint.iacr.org/2024/1575). I plan to write a separate blogpost about this. ### Inner Product Gadget The inner-product gadget allows us to enforce a "linear" constraint on a set of group elements as follows:  > You can decrypt my ciphertext if and only if you known a linear combination $(w_1,\dots,w_n)$ $\in \mathbb{F}^n$ of elements $(u_1, \dots, u_n)$$\in \mathbb{G}_1^n$ such that $\prod_{i=1}^n$ $u_i$$^{w_i}$ $=$ $v$ Again, just like the signature gadget, the above WE is easy to find a witness given any statement. But things get interesting when you make some witness elements a part of the statement or when you add other gadgets into the mix. >[!Note] > The above gadget has an $O(1)$ ciphertext size. Importantly, it does *not* grow with the size of the statement/witness $O(n)$. The inner-product gadget is surprisingly powerful and will be at the heart of most "compression" that we will see. In fact, this gadget is sufficient to build Silent Threshold Encryption in the special case where $t=1$ i.e. any party in the entire committee can decrypt locally.[^fifth] Do you see why? :::spoiler Hint 1 Choose $v$ to be a part of the statement with $v$ $=$ $g$, the generator of the group. ::: :::spoiler Hint 2 Set elements $(u_1, \dots, u_n)$ to be the public keys of parties. What would an honest party use as their witness? What happens if an adversary "outside the committee" finds a valid witness? ::: :::spoiler Answer Section 2.1 of the [framework paper](https://eprint.iacr.org/2025/1364). ::: ### Degree Check Gadget This degree-check gadget might sound a little contrived but it will make sense in second. > You can decrypt my ciphertext if and only if you known a vector $(w_1,\dots,w_n)$ $\in \mathbb{F}^n$ such that they are the evaluations of a *low-degree* ($\leq n-$$t$) polynomial on some canonically chosen domain.[^sixth] **Observation:** From the funddamental theorem of algebra, there can be at most $n-$$t$ zeros, which implies 1. there must be at least $t$ non-zero entries in $(w_1,\dots,w_n)$, or 2. $(w_1,\dots,w_n)$ are all $0$ Thus, if $(w_1,\dots,w_n)$ are non-zero, then there must be at least $t$ nonzero entries. So we can effectively use the degree-check gadget as a "non-zero" gadget. >[!Note] > Just like the inner-product gadget, the degree check gadget has an $O(1)$ ciphertext size. Importantly, it does *not* grow with the size of the statement/witness $O(n)$. Turns out, you can use one of the previous gadgets that we've seen to enforce the nonzero condition. Do you see it? :::spoiler Hint Use the inner-product gadget on $(w_1,\dots,w_n)$ where the linear combination enforces that there is at least one non-zero entry. :::  ## Step 2: Building the WE We are now equipped with all the gadgets needed to build the desired witness encryption: > You can decrypt my ciphertext if and only if you known a signature $\sigma$ on a string $\mathsf{tg}$ under an aggregate public key $\mathsf{apk}$, which is a "valid aggregation" of at least $t$ public keys from $(\mathsf{pk}_1, \dots, \mathsf{pk}_n)$. Worth pausing here to try and do it yourself. :::spoiler Inner-Product Gadget ![ip](https://hackmd.io/_uploads/SkiJZgtcxl.gif) ::: :::spoiler Degree Check ![deg-check](https://hackmd.io/_uploads/BJ-gblK9eg.gif) ::: :::spoiler Almost Answer This is almost the final construction but there's one missing constraint :). **Hint:** You need to prevent $\vec{w}$ $=0$ ![ste-we](https://hackmd.io/_uploads/SyaenJYcle.gif) :::  Combining the signature, inner-product and degree-check gadgets, we have a witness encryption for the following relation > You know a signature signature $\sigma$ on a string $\mathsf{tg}$ under an aggregate public key $\mathsf{apk}$, such that $\mathsf{apk}$ $= \prod_{i \in [n]}$ $\mathsf{pk}_i$$^{w_i}$ and the polynomial $f(X)$ such that $\{$$f(i)$ $=$ $w_i$$\}_{i \in [n]}$ has degree at most $n-$$t$, and $f(X)$ is not the zero polynomial. All of the gadgets produce a constant sized WE, which results in the overall witness encryption also having a constant size (see the [paper](https://eprint.iacr.org/2025/1364) for more details). In the application of Silent Threshold Encryption, given signatures $\{$$\sigma_i$$\}_{i \in S}$ on on $\mathsf{tg}$ from any $t$-sized subset $S$ $\subseteq[n]$, an honest party can produce a valid witness as follows: * compute $f(X)$$=\prod_{i \notin S} (X-i)$ and set $\{$$w_i$ $=$ $f(i)$$\}_{i \in [n]}$ * set $\sigma$ $=$ $\prod_{i \in S}$ $\sigma_i$$^{w_i}$ Security against malicious parties can be argued from the unforgeability of the BLS signature scheme and extractable security of the witness encryption scheme.[^eighth] [^second]: In fact, at the time of writing the [original blogpost](https://hackmd.io/@guruvamsi-policharla/new-threshold-schemes), I tried (and failed) to provide intuition for the construction, especially without introducing a bunch of math. Our new found understanding with the framework really allowed us to do this. [^third]: Consider an NP relation $\mathcal{R} \subset \{0,1\}^* \times \{0,1\}^*$. (Extractable) Witness encryption allows a user to encrypt a message to an NP statement $x$ such that the ciphertext can be decrypted if and only if you know a valid witness $w$ such that $(x,w) \in \mathcal{R}$. [^fourth]: The exact hardness assumption we need will depend on the gadget and how it's instantiated. For convenience, we can work in the Generic Group Model, where pretty much any "reasonable" assumption is hard. [^fifth]: Silent threshold encryption with $t=1$ has been previously studied under the name of [Distribtued Broadcast Encryption](https://eprint.iacr.org/2023/874). Interestingly enough, DBE was first coined in [BZ14](https://eprint.iacr.org/2013/642) who used $\mathcal{iO}$ to build it. Later, [KMW23](https://eprint.iacr.org/2023/874) built a concretely efficient version from pairings. But there was actually a paper in 2010 [WQZD10](https://dl.acm.org/doi/10.1145/1866307.1866416) that also had a pairing based construction and called it Ad Hoc Broadcast Encryption. This paper lacked a formal security proof and had a bug in the construction which was fixed by [KMW23](https://eprint.iacr.org/2023/874). Lore. [^sixth]: In practice, one may use the $n$-th roots of unity for fast interpolation/evaluation. [^seventh]: There are [subtle issues](https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html) that arise when a malicious party picks their public key based on other honest party public keys. We handle this by demanding a proof of knowledge of secret keys. [^eighth]: I haven't shown you how to enforce $f(X)$ $\neq 0$. When you do this, it's possible you may need to update how the witness is computed.