Relect: Single Secret Leader Election via FHE with Reduced Computation and Communication and Transparent Setup

Haofei Liang, Zeyu Liu, Yunhao Wang, Xiang Xie, Yu Yu, Fan Zhang

ACM CCS'26

Abstract

In a single secret leader election (SSLE) protocol, all parties collectively and obliviously elect one leader. Parties other than the selected leader should not be able to learn the identity of the leader unless it is revealed by the leader itself. The problem is first formalized by Boneh et al. (AFT 2020), and the first concretely feasible lattice-based SSLE with proof-of-concept implementations, Qelect, was recently introduced by Wang and Zhang (USENIX 2025).

In this work, we present Relect, an efficient SSLE protocol, based on the Ring Learning with Error assumption. We build it by leveraging the algebraic structure of the underlying threshold Fully Homomorphic Encryption (FHE) and by designing tailored homomorphic circuits. Compared to prior works, Relect (1) achieves substantially higher efficiency and (2) removes the strong environment assumption in Qelect (a trusted setup), and thereby also allows a dynamic leader selection for each round.

Concretely, for 32–2048 parties, our local FHE computation runtime achieves 5.25–37.6× faster than Qelect, which is the major efficiency bottleneck of the entire SSLE procedure. Furthermore, we show that for the same parameters, our communication cost is also 1.14–2× smaller. As mentioned, this is achieved while removing the trusted setup.

In terms of end-to-end runtime, following Qelect, we tested 2–128 parties. We show that under the LAN setting, Relect is 2.73–225× faster than Qelect per round. Under the WAN setting, Relect is 1.93 to 16.8× faster than Qelect. Note that these performance gains are all achieved while removing the trusted assumption and achieving dynamic leader selection for each round.