We Had It All In 1992

About three years ago, my coauthors and I introduced batched threshold encryption to build practical encrypted mempools. More than 20 papers later, every practical construction still relies on pairings. We now have a pairing-free scheme, and it’s 5–10× faster.

Why not just use threshold encryption? You can, but the communication to decrypt a block of transactions is much larger than the block itself. Specifically, decrypting B transactions requires O(nB) communication when there are n validators. In contrast, Batched Threshold Encryption demands that B ciphertexts be decrypted with sub-linear communication in the batch size, per party. Almost all BTE schemes do it with O(1) communication per party.

In the early days, constructions had these strange caveats like “your transaction can only be included in this specific view number” or “it must be included at a specific position in the batch” which could potentially result in conflicts. Then we found ways of getting around these issues, but at the cost of a more expensive setup. Last week we finally found a clean construction that only needs a DKG. So we have good pairing-based BTE schemes now.

Stepping Back. But recall that the whole point of BTE was to build encrypted mempools for blockchains. And virtually all of them run consensus protocols where the number of validators n \geq 3f+1 in order to tolerate f corrupt parties. So far, all BTE schemes allow the adversary to corrupt any number of parties f\leq t-1 up to the reconstruction threshold t. While this is the strongest security guarantee one can achieve, and valuable to study, it’s unnecessary for encrypted mempools. So what if we relax our requirements?

As it turns out, in the ramp setting where there exists a gap between the corruption threshold f and reconstruction threshold t, you can avoid pairings entirely. In fact, we had all the building blocks in 1992.

Packed Secret Sharing. Franklin and Yung (also Blakley and Meadows) observed that in the ramp setting, secrets can be packed more efficiently than with Shamir secret sharing. Concretely, one can pack \ell secrets into n shares, with reconstruction from any f+\ell of them, as follows:

• Choose two non-intersecting domains, D of size \ell and D_s of size n. We use D=[\ell]=\{1,\dots,\ell\} and D_s=[n^{-}]=\{-1,\dots,-n\}
• Sample a random polynomial S(X) of degree at most f+\ell-1 which evaluates to (s_1,\dots,s_\ell) on D
• The packed secret sharing is \{S(-i)\}_{i\in[n]}

Any f shares are independent of the secrets, and any f+\ell shares determine S. It is linearly homomorphic, and multiplying two sharings pointwise gives a sharing of the Hadamard product of the secrets.

Threshold ElGamal. Recall threshold ElGamal in a group with generator g. The committee holds shares \mathsf{sk}_i of a secret key \mathsf{sk}, the public key is \mathsf{pk}=g^{\mathsf{sk}}, and a ciphertext is

\mathsf{ct} = (c_1, c_2) = \left(g^{r},\; \mathsf{pk}^{r}\cdot M\right)

To decrypt, party i publishes c_1^{\mathsf{sk}_i}, and by interpolating t partial decryptions in the exponent, anyone can recover the mask \mathsf{pk}^r.

Pairing-Free BTE

This is all you need to build Batched Threshold Encryption. It’s a fun exercise to build it yourself (hints below).

Hint 1

Keep the ciphertexts exactly as they are in threshold ElGamal. Change how the committee shares \mathsf{sk} so that each party publishes a single group element that decrypts a whole batch of \ell ciphertexts at once. How large can \ell be?

Hint 2

Give the committee a packed sharing of \ell copies of \mathsf{sk}.

Hint 3

The randomness r_1,\dots,r_\ell of the batch also defines a polynomial R(X). Multiply it with the secret key.

Appendix A of the updated paper has the full construction, including how to handle malicious parties. Given that packed secret sharing is used extensively in secure multiparty computation to reduce communication/computation complexity, it is not surprising that these techniques extend to BTE. Threshold decryption is, after all, just a special-purpose multi-party computation protocol.

How does the DDH construction compare?

Simple BTE and DKG Is All You Need use the ramp-setting optimizations from Remark 2 and Appendix B of the updated paper.

Partial decryptions are bigger in the pairing-free scheme but not THAT much bigger. The total communication to decrypt ciphertexts is still O(B). While this may be larger than pairing-based schemes, which only require O(n), it is still concretely comparable to the block size:

• with n=3f+1 and t=2f+1: |\mathsf{pd}| \approx 6B/n~\mathbb{G} + 2\mathbb{F}
• with n=5f+1 and t=4f+1: |\mathsf{pd}| \approx 3.33 B/n~\mathbb{G} + 2\mathbb{F}

Amortized per transaction, the ciphertext + partial decryption overhead is:

• \approx 288 + 64n/B bytes at n=3f+1
• \approx 203 + 64n/B bytes at n=5f+1
• 112 + 48n/B bytes for Simple BTE
• 192 + 48n/B bytes for “DKG Is All You Need”

Benchmarks of total decryption time with a committee of n=128, run on an M5 MacBook Pro (single-threaded). Both schemes are measured with a quorum of t=85 partial decryptions. The pairing-free scheme uses f=42 and \ell=22, and packed Simple BTE uses \ell=16. A prototype of the pairing-free BTE on the Pallas curve is compared against a packed prototype of Simple BTE.

What it loses in communication, it makes up for in speed and simplicity.

---

1. The construction in the current version of the paper also attaches a NIZK to each ciphertext, which adds 2\mathbb{F}. This can be avoided in the random oracle model (paper will be updated soon).↩︎

2. Although a large part of the Simple BTE decryption work can be pipelined and done before partial decryptions arrive, it cannot be avoided. The time to verify partial decryptions is ignored for both schemes, but the pairing-free version is expected to have faster verification. We note that both implementations are prototypes with room for optimization.↩︎