Paper 2026/1428

Highly Efficient Consistent Broadcast Encryption

Abstract

Public Key Encryption for Broadcast ($\mathsf{PKEBC}$) is a multi-recipient encryption primitive that guarantees decryption consistency across all designated recipients. Concretely, if a ciphertext $c$ is encrypted for Bob and Charlie, and Bob’s decryption yields a message $m$, then Charlie’s decryption of $c$ must also succeed and produce the same $m$. This property, though seemingly natural, is essential in secure group messaging, where consistent message delivery is often implicitly assumed. However, no efficient constructions of $\mathsf{PKEBC}$ currently exist: known approaches achieve consistency through Non-Interactive Zero-Knowledge ($\mathsf{NIZK}$) proofs of generic statements. Not only is the complexity of the $\mathsf{NIZK}$ statements already prohibitively expensive, but, in addition, it is not even clear if these can be turned into purely algebraic statements while retaining linear-sized ciphertexts. This is crucial to enable the use of efficient $\mathsf{NIZK}$ constructions. This paper presents new generic $\mathsf{PKEBC}$ constructions along with optimized instantiations of each. Concretely, we introduce $\mathsf{PKEBC}_{\mathsf{SM}}$ and $\mathsf{PKEBC}_{\mathsf{FO}[\mathsf{mPKE}]}$, and prove the security of these constructions in the standard and random oracle models, respectively. – $\mathsf{PKEBC}_{\mathsf{SM}}$ achieves consistency via $\mathsf{NIZK}$ proofs. Crucially, we hand-tuned the $\mathsf{NIZK}$ statements of our instantiation to ensure the $\mathsf{NIZK}$ is only used to prove very simple and carefully optimized purely algebraic statements. – $\mathsf{PKEBC}_{\mathsf{FO}[\mathsf{mPKE}]}$ achieves consistency via the Fujisaki-Okamoto ($\mathsf{FO}$) transform (CRYPTO 1999 and Journal of Cryptology 2013) applied to a Multi-Recipient Public Key Encryption scheme ($\mathsf{mPKE}$). Specifically, $\mathsf{NIZK}$'s ciphertext recomputation during decryption ensures ciphertexts are well-formed, eliminating the need for costly $\mathsf{NIZK}$ proofs. We then give two suitable $\mathsf{mPKE}$ instantiations: one based on Kurosawa’s $\mathsf{mPKE}$ (PKC 2002) and the other from Hash Proof Systems. For all our schemes and their instantiations, ciphertext sizes and encryption and decryption times grow linearly with the number of receivers. Our constructions therefore enable the first practical group messaging applications with consistency guarantees.