Smuche: Scalar-Multiplicative Caching in Homomorphic Encryption
Dongfang Zhao
Addressing the challenge of balancing security and efficiency when deploying
machine learning systems in untrusted environments, such as federated learning,
remains a critical concern. A promising strategy to tackle this issue involves
optimizing the performance of fully homomorphic encryption (HE). Recent
research highlights the efficacy of advanced caching techniques, such as Rache,
in significantly enhancing the performance of HE schemes without compromising
security. However, Rache is constrained by an inherent limitation: its
performance overhead is heavily influenced by the characteristics of plaintext
models, specifically exhibiting a caching time complexity of $\mathcal{O}(N)$,
where $N$ represents the number of cached pivots based on specific radixes.
This caching overhead becomes impractical for handling large-scale data. In
this study, we introduce a novel \textit{constant-time} caching technique that
is independent of any parameters. The core concept involves applying scalar
multiplication to a single cached ciphertext, followed by the introduction of a
completely new and constant-time randomness. Leveraging the inherent
characteristics of constant-time construction, we coin the term ``Smuche'' for
this innovative caching technique, which stands for Scalar-multiplicative
Caching of Homomorphic Encryption. We implemented Smuche from scratch and
conducted comparative evaluations against two baseline schemes, Rache and CKKS.
Our experimental results underscore the effectiveness of Smuche in addressing
the identified limitations and optimizing the performance of homomorphic
encryption in practical scenarios.