Paper 2025/2115

Weighted Batched Threshold Encryption with Applications to Mempool Privacy

Abstract

A Batched Threshold Encryption (BTE) scheme enables a committee of servers to perform a lightweight (in terms of communication and computation) threshold decryption of an arbitrary batch of ciphertexts from a larger pool, while ensuring the privacy of ciphertexts that are outside the batch. Such a primitive has a direct application in designing encrypted mempools for MEV protection in modern blockchains. Bormet et al. (USENIX 2025) recently proposed a BTE scheme called “BEAT-MEV” which is concretely efficient for small to moderate batch sizes. In this work, we improve and extend the BEAT-MEV scheme in multiple ways. First, we improve the computational cost from quadratic to quasilinear in the batch size, thus making it practical for large batch sizes. This improvement is achieved by substituting the key-homomorphic punctured PRF used in BEAT-MEV with an FFT-friendly alternative. Second, we extend the ideas in their scheme to the weighted setting, where each server in the committee has an associated 'weight' value (e.g., stake weight of validators in PoS blockchains), while crucially ensuring that the communication cost remains independent of the weights. In contrast, BEAT-MEV with naive virtualization would incur communication cost linear in the total weight. Third, for handling the small failure rate inherent in BEAT-MEV scheme due to index collisions across different clients at the time of encryption, we propose a generalization of their suggested approach which offers an option to trade off between ciphertext size and server communication for a given failure rate. We implement and evaluate our scheme and compare it with BEAT-MEV to demonstrate our concrete improvement. In the unweighted setting, we improve the computational cost (without increasing the communication cost) by ≈ 6× for a batch size of 512 ciphertexts. In the weighted setting, we improve the communication cost (without compromising computation time), over BEAT-MEV with naive virtualization, by ≈ 50× for 100 validators with total stake weight 5000 distributed as per the latest Solana stake distribution.