Paper 2025/443

Homomorphic Signature-based Witness Encryption and Applications

Abstract

Signature-based witness encryption (SWE) schemes recently emerged as a viable alternative to instantiate timed-release cryptography in the honest majority setting. In particular, assuming threshold trust in a set of parties that release signatures at a specified time, one can ``encrypt to the future'' using an SWE scheme. It offers stateless decryption, where parties producing the signatures do not need to know the ciphertexts in advance to perform decryption. This statelessness makes SWE vastly superior to regular threshold encryption for decentralized blockchain applications such as sealed-bid auctions and voting. However, the lack of homomorphism in existing SWE schemes severely bottlenecks their throughput and limits their deployment. In this work, we formally introduce Homomorphic SWE (HSWE) to resolve these limitations. We present a systematic suite of HSWE constructions designed to scale across varying message spaces without sacrificing statelessness. We first establish foundational HSWE schemes for binary messages using Cocks IBE and standard Learning With Errors (LWE). To support polynomially-sized message spaces, we construct a pairing-based scheme that features an efficient multi-pairing optimization for cross-tag aggregation. For exponentially large message spaces, we transition to a Ring-LWE construction that achieves high-throughput polynomial packing with post-quantum security. Moreover, we address the inherent privacy limitation of public stateless aggregation by proposing a framework that perfectly hides individual plaintexts and only reveals the final aggregated result. We also present an empirical performance evaluation in Rust to highlight the impact of homomorphism in practical deployments.