Paper 2026/1186

Butterfly Effect: Multi-Key FHE from Ring-LWR

Abstract

The Learning with Errors (LWE) problem is a fundamental hardness assumption underlying most fully homomorphic encryption (FHE) schemes. Given the close relationship between the Learning with Rounding (LWR) and LWE problems, several cryptographic constructions have also been developed based on LWR. In particular, LWR-based schemes often benefit from simpler and more efficient implementations, as they eliminate the need for explicit Gaussian error sampling. Despite these advantages, relatively few FHE constructions in the literature are based on the LWR assumption. At AsiaCCS 2025, Goyal and Gangopadhyay proposed a multi-key FHE (MKFHE) scheme based on LWR that adopts a public-key extension mechanism rather than the conventional ciphertext-extension paradigm. The authors also identified the development of a ring-based analogue as an open future direction. In this work, we present two Ring-LWR-based MKFHE constructions that can be viewed as ring analogues of the LWR-based MKFHE scheme of Goyal and Gangopadhyay. To the best of our knowledge, these are the first MKFHE schemes based on the Ring-LWR assumption. Compared with existing Ring-LWE-based multi-key constructions, our schemes achieve improved compactness in terms of storage and communication costs. We provide concrete parameterizations supporting circuits of varying multiplicative depths and present a proof-of-concept implementation to validate our claims.