Exploiting Unstructured Sparsity in Fully Homomorphic Encrypted DNNs

📄 arXiv: 2503.09184v2 📥 PDF

作者: Aidan Ferguson, Perry Gibson, Lara D'Agata, Parker McLeod, Ferhat Yaman, Amitabh Das, Ian Colbert, José Cano

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

发布日期: 2025-03-12 (更新: 2025-04-03)

备注: Accepted to 5th Workshop on Machine Learning and Systems (EuroMLSys) co-located with EuroSys '25

💡 一句话要点

针对全同态加密DNN，提出利用非结构化稀疏性加速矩阵乘法方案

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

关键词: 全同态加密 深度神经网络 稀疏矩阵 矩阵乘法 隐私保护 性能优化 非结构化稀疏性

📋 核心要点

  1. 全同态加密DNN计算开销巨大，限制了其在隐私敏感场景的应用。
  2. 利用非结构化稀疏性，在FHE矩阵乘法中降低计算负担，同时保持模型精度。
  3. 提出的稀疏方案在50%稀疏度下平均性能提升2.5倍，多线程方案提升32.5倍。

📝 摘要（中文）

在隐私敏感环境中部署深度神经网络（DNN）受到全同态加密（FHE）计算开销的限制。本文探索了FHE矩阵乘法方案中非结构化稀疏性，旨在降低计算负担并维持模型精度。研究表明，稀疏性可在任意矩阵乘法中利用，与朴素算法相比，在所有稀疏度下均能提供运行时优势。这与明文域形成鲜明对比，后者需要在稀疏性和稀疏乘法算法的开销之间进行权衡。此外，本文提出了三种基于常见明文稀疏编码的FHE稀疏乘法方案。实验表明，性能提升与方案无关；然而，某些稀疏方案在较高稀疏度下能显著降低加密矩阵的内存存储需求。所提出的稀疏方案在50%非结构化稀疏度下平均性能提升2.5倍，而多线程方案在使用64核时，相比等效的单线程稀疏计算，性能提升32.5倍。

🔬 方法详解

问题定义：在全同态加密（FHE）的深度神经网络（DNN）中，矩阵乘法是计算瓶颈。现有的FHE方案计算开销大，难以满足实际应用需求。即使在明文域中广泛使用的稀疏矩阵乘法优化方法，在FHE中也面临额外的复杂性和开销，导致收益不明显甚至适得其反。

核心思路：本文的核心思路是探索在FHE加密域中利用非结构化稀疏性来加速矩阵乘法。与明文域不同，FHE中的稀疏性利用可以避免额外的开销，从而实现性能提升。通过设计特定的稀疏矩阵编码和乘法方案，可以在保证安全性的前提下，显著降低计算复杂度和内存占用。

技术框架：本文提出了三种基于常见明文稀疏编码的FHE稀疏乘法方案。整体流程包括：1) 对明文矩阵进行稀疏化处理；2) 根据选定的稀疏编码方案对稀疏矩阵进行编码；3) 对编码后的矩阵进行FHE加密；4) 在加密域中执行稀疏矩阵乘法；5) 对结果进行解密和解码。

关键创新：本文的关键创新在于证明了在FHE中利用非结构化稀疏性进行矩阵乘法可以始终带来性能提升，这与明文域存在权衡不同。此外，针对FHE环境设计了特定的稀疏矩阵编码和乘法方案，并分析了不同方案的性能和内存占用。

关键设计：论文提出了三种稀疏乘法方案，具体细节未知。关键在于如何在FHE加密域高效地执行稀疏矩阵乘法，以及如何选择合适的稀疏编码方案以最小化内存占用和计算复杂度。多线程方案的实现细节也未知，但其显著的性能提升表明了并行计算在FHE稀疏矩阵乘法中的潜力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的稀疏方案在50%非结构化稀疏度下平均性能提升2.5倍。更重要的是，多线程方案在使用64核时，相比等效的单线程稀疏计算，性能提升高达32.5倍。这表明了在FHE中利用稀疏性和并行计算的巨大潜力，为构建高效的隐私保护AI系统提供了新的思路。

🎯 应用场景

该研究成果可应用于隐私保护的深度学习推理服务，例如在医疗、金融等敏感数据领域。通过利用稀疏性加速FHE计算，可以在保护用户数据隐私的同时，实现高效的DNN模型部署和推理。未来，该技术有望推动FHE在更广泛的AI应用场景中的落地。

📄 摘要（原文）

The deployment of deep neural networks (DNNs) in privacy-sensitive environments is constrained by computational overheads in fully homomorphic encryption (FHE). This paper explores unstructured sparsity in FHE matrix multiplication schemes as a means of reducing this burden while maintaining model accuracy requirements. We demonstrate that sparsity can be exploited in arbitrary matrix multiplication, providing runtime benefits compared to a baseline naive algorithm at all sparsity levels. This is a notable departure from the plaintext domain, where there is a trade-off between sparsity and the overhead of the sparse multiplication algorithm. In addition, we propose three sparse multiplication schemes in FHE based on common plaintext sparse encodings. We demonstrate the performance gain is scheme-invariant; however, some sparse schemes vastly reduce the memory storage requirements of the encrypted matrix at high sparsity values. Our proposed sparse schemes yield an average performance gain of 2.5x at 50% unstructured sparsity, with our multi-threading scheme providing a 32.5x performance increase over the equivalent single-threaded sparse computation when utilizing 64 cores.