Smuche: Scalar-Multiplicative Caching in Homomorphic Encryption

📄 arXiv: 2312.16352v1 📥 PDF

作者: Dongfang Zhao

分类: cs.CR, cs.LG, cs.PF

发布日期: 2023-12-26

💡 一句话要点

提出Smuche以解决同态加密中的缓存效率问题

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: 同态加密 缓存技术 标量乘法 性能优化 机器学习 隐私保护 联邦学习

📋 核心要点

  1. 现有的同态加密缓存技术如Rache在处理大规模数据时存在性能开销过大的问题，难以满足实际应用需求。
  2. 本文提出了一种名为Smuche的常数时间缓存技术，通过标量乘法和新随机性的引入，独立于任何参数，优化了缓存性能。
  3. 实验结果显示，Smuche在性能上优于Rache和CKKS，能够有效提升同态加密的实际应用效率。

📝 摘要（中文）

在不可信环境中部署机器学习系统时，平衡安全性与效率是一个关键问题。优化全同态加密（HE）的性能是一种有效策略。尽管现有的高级缓存技术如Rache在提升HE性能方面表现良好，但其性能开销受限于明文模型的特征，尤其在处理大规模数据时显得不够实用。本文提出了一种新颖的常数时间缓存技术Smuche，通过对单个缓存密文应用标量乘法，并引入全新的常数时间随机性，显著优化了HE的性能。实验结果表明，Smuche在解决现有方法的局限性方面表现出色。

🔬 方法详解

问题定义：本文旨在解决现有同态加密缓存技术在处理大规模数据时的性能开销问题，尤其是Rache在明文模型特征影响下的时间复杂度为$ ext{O}(N)$。

核心思路：Smuche的核心思想是通过对单个缓存密文进行标量乘法，并引入常数时间的随机性，从而实现常数时间的缓存效率，避免了对明文模型特征的依赖。

技术框架：Smuche的整体架构包括缓存密文的标量乘法模块和随机性引入模块，两个模块协同工作以实现高效的缓存性能。

关键创新：Smuche的主要创新在于其常数时间的缓存机制，这与现有方法的性能受限于明文特征的设计本质上有所不同，显著降低了缓存开销。

关键设计：在实现过程中，Smuche的设计不依赖于特定的参数设置，确保了其在不同应用场景下的通用性和灵活性。

📊 实验亮点

实验结果表明，Smuche在性能上显著优于基线方案Rache和CKKS，具体提升幅度未知，展示了其在实际应用中的有效性和优势。

🎯 应用场景

Smuche技术在需要高效同态加密的场景中具有广泛的应用潜力，如联邦学习、隐私保护的数据分析和安全多方计算等领域。其优化的性能能够促进更多机器学习系统在不可信环境中的安全部署，推动相关技术的发展。

📄 摘要（原文）

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.