【Paper Reading】BatchCrypt: Efficient Homomorphic Encryption for Cross-Silo Federated Learning

Advanced Homomorphic Encryption Mechanism: A Distributed Learning Framework with Cross-Island Data Participation

High-Efficiency Homomorphic Encryption Aimed at Cross-Silo Federated Learning.

文章目录

• • BatchCrypt: 该文提出了一种高效的安全多方计算方案用于跨岛联邦学习。

• 0. 摘要

• 1. 引言

• 2. 背景及相关研究

• • 2.1 跨岛联邦学习

• 2.2 联邦学习中的隐私解决方案

• • 安全多方计算(Secure Multi-Party Computation, MPC)

• 差分隐私(Differential Privacy, DP)

• 安全聚合(Secure Aggregation)

• 同态加密(Homomorphic Encryption, HE)

• 总结

  复制代码

  * 2.3 Cross-Silo FL Platform with HE

• 3. 表征性能瓶颈

• • 3.1 表征结果
    ** 加密与通信开销**
    深入探讨
    ** 为什么HE如此昂贵**
    总结

• 3.2 Various Solutions and the Challenges They Present

  • • HW Accelerator * Minimizing Communication Overhead

• 4. 加密批次处理方案

  • • 4.1 加密联邦学习中批次化为何存在问题
      • 为何量化成为联邦学习中的必要手段

  • 当前存在的量化方案

    • 4.2 HE Batching for Gradients
    • • Gradient Quantization

  • BatchCrypt

    • 4.3 dACIQ: Analytical Clipping for FL
    • • Gaussian Fitting

  • Advance Scaling

    • 4.4 BatchCrypt：Putting It All Together

  • 5. Implementation

  • • Overview
    • Model Placement

  • 6. Evaluation

  • • 6.1 Methodology
    • • Setting

  • Benchmarking Models

• 6.2 Impact of BatchQuantization on BatchCrypt's Performance

• Comprehensive Analysis of BatchCrypt's Performance and Efficiency Gains in Machine Learning Models

• Comparative Study Between Batch Cryptography and FATE Frameworks for Secure Data Processing

• Comparative Analysis Between Batch Cryptography and Plaintext Learning Techniques in Privacy-Preserving Machine Learning Tasks

• Training to Convergence: A Comprehensive Look into the End-to-End Machine Learning Pipeline Dynamics for Optimal Model Performance Achievements.

  复制代码

  * 6.4 Batching Efficiency
  * 6.5 Cost Benifits

7. 讨论

* 8\. Concluding Remark

欢迎大家访问我的GitHub博客

https://lunan0320.cn

0. Abstract

Cross-silo federated learning (FL) 通过聚合本地梯度更新的方法在一些领域如金融或医疗领域实现了一个机器学习模型。

mask local gradient updates : additively homomorphic encryption (HE)

问题

BatchCrypt, a system solution for cross-silo FL

不是单独进行 encrypt 操作, 而是将一组 quantized gradient batches 编码成一个 single integer, 并一次完成加密过程

使用 gradient clipping technique, 可以允许 gradient-wise aggregation

implementation : BatchCrypt 作为 FATE的一个插件

在几何分布的 datacenters EC2 clients, 训练速度提高了2393，通宵开销减小了66101

1. Introduction

数据共享在 data privacy 和 confidentiality情况下是被禁止的

通过 Cross-silo 联邦学习（FL）机制，我们可以克服数据孤岛，并将每个节点计算出的本地模型梯度更新传输至中央ised server 进行共同训练全球模型

针对聚合过程中的隐私问题，在数据处理过程中可能会遇到挑战。该系统被认为是解决这些问题的最佳选择，在交叉数据孤岛设置中表现优异，并且能够在不显著影响学习准确率的情况下提供强大的隐私保护。

在HE 情况下, gradient aggregation 可以直接在 ciphertexts 下操作

The process begins with the HE key-pair being encrypted across all clients via a secure channel.

During training :

1. The client encodes the local gradient updates with a public key and sends the ciphertexts to the central server.
2. The server accumulates the encrypted gradients and transmits the aggregated results to all clients.
3. The client deciphers the aggregated gradients with a private key and updates its local model.

实验表明 ：

(1) more than 80% of training time is spent on encryption/decryption.

(2) encryption yields larger ciphertexts.

HE in encryption and communication is expensive.

WeBank is unable to utilize encrypted gradients in scenarios that are restricted to less privacyminded contexts.

Solution: a simple batch encryption technique.

The client applies quantization to convert gradient values into low-bit integer representations and performs encryption as a single operation.

与独立于直接加密机制的梯度值相比而言,batch encryption 减少了约O(\log N)倍的encapsulation overhead和O(1)倍的数据传输量。

batch encryption key challenges:

通过将两个 batches 的密文相加处理，解密后得到的结果与其在采用明文方式完成 gradient-wise aggregation on two batches 时的效果一致。

提出一种定制化的量化方案用于将梯度值转换为在对称范围内均匀分布的有符号整数。

该编码方案基于两个符号位的量化值补码表示法进行了创新性设计

​ 使用padding 和 advance scaling to avoid overflow in addition.

(2) gradients values are unbounded, be clipped before quantization

提出分析模型为 dACIQ, 基于扩展的ACIQ方法（基于剪切技术在集中式数据上的应用）用于跨ilo联邦学习在去中心化数据场景中的应用。

​ dACIQ 可以选择 optimal clipping thresholds.

There are nine active participants geographically distributed across five AWS EC2 datacenters.

协同训练三个模型：

A three-layer fully connected neural network architecture is based on the FMNIST dataset.
AlexNet was trained using data from the CIFAR-10 dataset.
The text-generative LSTM model is capable of generating text from the Shakespeare dataset.

与FATE 相比，达到23、71、93倍的加速，通信开销减小66、71、101倍

BatchCrypt 精度损失不到1%（可忽略不计）

在cross-silo FL框架下开发出首个低计算资源消耗的高效HE方案

2. Background and Related Work

2.1 Cross-Silo Federated Learning

根据应用场景的不同，federated learning 可以分为：

cross-device FL

客户群体由大量移动或物联网设备组成,这些设备具有有限的计算能力,并且通信连接不可靠.

cross-silo FL

客户群体是一个有限数量的组织（包括但不限于金融与医疗行业），他们具备充足的计算资源储备以及可靠的通信渠道。

与 cross-device 联邦学习相比，cross-silo 联邦学习在隐私和性能方面特别关注着

该 system 应当仅限于特定团队内部使用。任何非内部参与者、包括 central server 等外部实体均不得直接访问 trained application.

（2）强隐私保护强度不应该是以牺牲 learning accuracy 为代价

（3）作为新的范式， cross-silo FL 在 algorithm 和 systems 都有快速的创新

2.2 Privacy Solutions in Federated Learning

Secure Multi-Party Computation (MPC)

multiple entities interactively engage in computing an agreed function. Each participant, apart from exchanging input and output data, does not learn any additional information (non-trivial zero-knowledge property).

MPC 在 clients之间精心设计 computation and synchronous protocols.

协议可以保证 privacy，但是牺牲了 effiency

开发人员精心设计了机器学习算法，并在可能适度降低隐私的前提下，将计算任务划分为不同参与方之间进行处理。

Differential Privacy (DP)

injecting noises 来保证 sample 的privacy

existing studies : selection\ of\ parameters is conducted to balance between data privacy and learning accuracy.

DP具有很高的应用潜力，在聚合过程中直接向中心服务器传递这些 plain gradients。

Secure Aggregation

The server does not learn individual updates from any client, only aggregated updates.

该安全机制适用于跨设备联邦学习（FL）。然而，在跨数据孤岛式的FL出现故障时，则存在以下原因：
（1）central server能够访问聚合梯度（aggregated gradients），基于此，在运行central server的公共云等外部实体中能够获取训练后的模型参数信息。

在每次迭代过程中，clients需同步密钥和zero-sum masks，并对其同步训练的需求较为严格。

Homomorphic Encryption (HE)

computation directly on ciphertexts

additively HE schemes, notably Paillier ：

每个 client transfer transmits encrypted data packets containing localized modifications to the server, which then directly aggregates these localized modifications.

result is sent back to the client for local decryption.

HE meets 3 requirements of cross-silo FL:

（1）保护了训练模型不会被任何的额外的 party learned (server也是)

（2）no learning accuracy loss (no noise)

（3）directly apply to the existing learning systems

cons： HE incurs notable overhead in computational tasks and data exchanges.

Summary

MPC: 提供了强的隐私保证，但是需要重新设计现有的 ML algorithms

DP: 当应用时, 该方法显得straightforward and effectively, 但其在privacy guarantee方面显得less stringent, 同时可能会带来possible accuracy loss

服务器聚合：在跨设备联邦学习中是一种有效的方法（实现），然而带来了较高的同步成本（问题）。

2.3 Cross-Silo FL Platform with HE

如图，是一个典型的 cross-silo FL system.

aggregator 是一个服务器，并协调客户以收集加密后的梯度（具有诚实但好奇的特性）。

​

在 parties 之间的 communication 是由密码协议（SSL / TLS）确保安全

不会有第三方会获取到传输时候的 messages

Overview :

when training begins, the aggregator randomly selects a client to become the leader and creates an HE key pair, synchronizing it to all clients.

并且由 leader 初始化 ML model， sends model weights to others.

Upon receiving the HE key-pair and initial weights, multiple entities will initiate the training process immediately.

在每次迭代中, 每个客户端计算本地的梯度更新, 并使用公共密钥进行加密后发送给aggregator

Aggregator等待所有客户端发送更新信息，并在收集完这些信息后整合它们，并将整合后的结果传递给所有客户端

client decrypted the aggregated gradients, update its local model.

该架构 adheres to the classic distributed SGD pattern. 基于此, 现有的理论与优化算法中包含了同步机制与局部更新SGD。

此外，在客户端实现明文梯度后可采用当前最先进的一阶优化器如Adam算法以加速收敛速度。

3. Characterizing Performance Bottlenecks

探讨cross-silo联邦学习在真实场景中对深度学习模型性能的影响。具体而言,该方法涵盖了数据分布不均衡性、数据隐私保护需求以及分布式系统扩展性三个方面的问题。通过实证分析表明,在上述三个关键指标上,该方法展现出卓越的表现。本文的研究工作不仅推动了理论研究的发展,也为实际应用提供了有益的参考价值

加密（ encryption）和通信（ communication）是两大关键性能瓶颈（bottlenecks），阻碍了联邦学习（FL）在组织间难以实现应用

3.1 Characterization Results

Cross-silo FL 用于 多个 geo-distributed datacenters.

实验研究：基于九个基于EC2的客户端，在五个地理分布的数据中心进行协同训练过程分析，并训练了三个机器学习模型包括FMNIST、CIFAR和LSTM等

(除非特别强调，否则都是 synchronous training)

实验在FATE基础上开展，使用了内置的 Paillier cryptosystem.

Encryption and Communication Overhead

比较两个FL scenarios, 有没有 HE

使用HE会导致训练时间和数据传输明显提高，并在未采用HE的情况下导致迭代时间分别提升了96倍、135倍和154倍

总的来说，HE 的使用 training time 和网络占用都增加了两个数量级。

（这对于更复杂的models，开销是更大的）

Deep Dive

取样测试影响 HE overhead 的方面，

Client : HE-related operations dominate the training time.

60％的时间用于梯度加密。

有20％的时间分配在解密过程上。

数据传输以及等待梯度聚合返回的过程占据了20％的时间。

计算梯度的时间仅占总时间的不到0.5％。

Aggregator :

70% of the duration is spent idling while waiting for a client to transmit encrypted gradients.

The system collects gradient data from all clients.

The aggregated gradient information is then dispatched to each party, noting that clients are geographically distributed.

< Only 10% of the computational effort is dedicated to aggregating gradients.

Why is HE So Expensive

以加法HE 为例，Paillier 在 encryption 和 decryption 上：

1. 采用了高精度指数 和 大规模模数 的多重模乘法与幂运算技术（通常采用超过512bits）。
2. 经过加密处理后生成的密文长度显著增加（对数据传输造成了更高的计算开销）。

Benchmark ：

The computational burden of the Paillier scheme under different key size configurations is notable, and the enlargement of ciphertext volumes becomes increasingly significant as the key size varies.

key size 越大，意味着 higher security.

computation overhead and ciphertexts size 都是线性增长

Summary

部署高端硬件设备（GPUs and TPUs）并非必要性所在；这种做法是一种资源浪费行为。

（2）在geographically distributed data centers中 extremely high network traffics resulted in significantly expensive network data charges, making cross-silo federated learning economically unfeasible.

实际上，对于安全性需求不严格的场景，会选择性关闭 HE

3.2 Potential Solutions and Their Inefficiency

Hardware-Accelerated HE

现有的大多数HE加密方案（如Paillier）都存在一定的限制性独立操作，在这种情况下单独加速一个HE操作仍会遇到困难（FPGA实现仅能提升3倍加速效果）。

（2）仅对于 encryption 自身进行加速是无法减少 communication overhead.

Reducing Communication Overhead

数据膨胀现象主要源于明文与密文长度不一致的直接原因

intuitive idea ：

aggregating gradients across multiple iterations can maximize the number of combined components, generating a comprehensive plaintext sequence.

这样可以显著减少加密的次数

挑战在于在执行分批操作后维持HE的加法特性（这不会影响ML算法和学习准确率）

没有工作系统地介绍 batching, SIMD 可以加速 lattice-based HE schemes.

招致了更多的 computational complexity for lattice-based HE.

现有的加速只能加速 integer cryptographic.

4. BatchCrypt

（1）batching 需要 gradient quantization

​ 通用的 quantization 缺少 flexibility and efficiency

（2） an efficient clipping method to prevent model degradation.

4.1 Why is HE Batching for FL a Problem

batching 技术已经被用于加速 queries 在 Paillier-secured database.

但该技术只适用于 non-negative integers

为了支持浮点数, values 需要被 recorded and grouped by their exponents.

SIMD技术受限于 lattice-based cryptosystems.

目的是开发一个适用于所有加性同态密码系统的统一批次方法。

Why Quantization is Needed

gradients are signed-point numbers, and they must be ordered according to the model's weights rather than being reordered based on exponents.

可行方法：在批处理中使用梯度的整数表示，这需要 quantization.

Existing Quantization Schemes

假设 gradient g 被量化到一个 8-bit 的无符号整数

quantized value of g:
Q(g) = [255*(g-min)/(max-min)]
(max = 1, min = -1)

假设 n 个量化的 gradients 被求和，结果表示为 q_n

dequantized value of q_n:
Q^{-1}(q_n) = q_n*(max-min)/255+n*min

overview :

gradients of a client (floating numbers) are first quantized.

batch joined into a large integer.

aggregate the gradients of two clients.

dequantize them to obtain the aggregated results.

limitations :

为了实现去量化（dequantize）的成功操作, 必须明确aggregated data的总量, 并这对系统的灵活性和同步性造成了影响.

（2）在 aggregation 时候很容易 overflow, values 都被量化为 正整数

​ 解决方法： batched ciphertexts 必须在添加一些内容后解密，并再次加密

（3）不区分正数和负数的溢出

4.2 HE Batching for Gradients

针对现有量化技术已无法满足需求的情况，在梯度优化过程中引入并行化机制以提高效率。

The properties are as follows :

（1）保留 HE 的加法特性

（2）可区分 positive overflows from negative ones.

（3）适用于现有的ML 算法和优化技术

（4）足够灵活来 dequantize values，不需要知道额外的信息(eg. 聚合的数量)

Gradient Quantization

现有技术：通过 gradient compression 技术来减少网络流量

（这些方法主要是在传输过程中 compress values 或者加速 inference）

这些方法并非专为梯度聚合而设计，在处理压缩梯度时其效率有限。

Quantization requirements:

Signed Integers

梯度需被量化为有符号整数，在聚合过程中正值与负值相互抵消，从而降低了溢出的可能性

Symmetric Range

量化范围必须是对称的，否则会导致聚合结果的不正确

Uniform Quantization

梯度呈非均匀分布特征，在量化过程中同样呈现非均匀分布特征的情况下可以获得更高的压缩效率。然而，在这种情况下由于无法直接提取加法信息而限制了进一步的优化。

BatchCrypt

quantize a gradient in [-\alpha,\alpha] into an r-bit integer

uniformly map [-\alpha,0] and [0,\alpha], to [-(2^r-1),0] and [0,2^r-1]

(0 是以两种codes映射的)

使用 two’s complement representation (两位补码)

符号位可以参与加法运算，使用两个符号位来区分 正溢出 和 负溢出

4.3 dACIQ: Analytical Clipping for FL

在现实中， gradients 可能是无界的，并且需要在量化之前的阶段进行截断处理

gradients 在不同的 layers 有不同的分布

同一层的 gradients 有一个类似 Gaussian 的 bell-shaped distribution.

此特性可以用来高效进行 gradient compression.

找到一个 optimal clipping thresholds unclear.

clipping 裁剪 是将梯度饱和到一个阈值为\alpha的过程

两种方法设置 clipping threshold:
（1）profiling-based clipping

​ 选择一个 sample dataset，获得一个样本梯度分布

​ 使用 KL divergence and convergence rate.

​ 但是在FL中不切实际

（2）analytical modeling

Quantization noise 在 clipping 范围内产生的误差

Clipping noise 是超过裁剪阈值的饱和范围

为了探讨 noise 的影响, 最近提出的 ACIQ 最新剪切技术假设量化和剪切过程均遵循 Gaussian 分布

但是 ACIQ 不可直接用于 BatchCrypt:

（1）采用了非对称量化

（2）在 FL 中无法使用明文梯度

accumulated error in BatchCrypt :

前面两个属于剪切噪声，在第三项中采用随机四舍五入噪声；当已知σ的情况下即可获得最佳阈值α。

Gaussian Fitting

传统方法是使用最大似然估计和贝叶斯推理 （对于 FL 大规模参数不适用）

dACIQ 方法：只需要观测集的大小和 max and min

Advance Scaling

假设 m 个clients

将 quantization range 设置为 clipping range 的m倍，则可确保 sum of gradients 不会溢出

4.4 BatchCrypt：Putting It All Together

Initialization

aggregator 随机挑选一个客户端作为领导节点, 通过该领导节点创建HE密钥对, 并设置模型权重参数; 随后将这些密钥对和权重参数同步至其他客户端工人中

Training

此处，leader与其他 workers 没有区别

clients 计算 gradient，并发送到aggregator

该聚合器能够同时完成对高斯参数的计算和每层剪切边界值的确定。

quantization is applied to gradient values, with the scaling factor being the total number of clients, and these quantized values are encrypted using BatchCrypt.

quantization is applied to gradient values, with the scaling factor being the total number of clients, and these quantized values are encrypted using BatchCrypt.

aggregator summed up the encrypted gradients, 并返回给 clients.

5. Implementation

Overview

most of efforts are made on client side.

clients 的架构如下：

consists of dACIQ, Quantizer, two’s Compliments Codec, and Batch Manager.

dACIQ: Gaussian fitting and clipping threshold calculation.

Quantizer: takes threshold to Advance Scaler and dequantization.

Two’s Compliments: 量化值的转换 encode， Numba enables Parallel

BatchManager 负责处理 batch 和 unbatch 操作中的梯度计算，并通过 joblib 实现并行化的计算过程

Model Placement

传统 PS 架构，model wights 保存在 server side.

BatchCrypt: 将 weights 放在worker side

传统方法：

​ clients 使用HE加密初始化的weights，并发送给 aggregator

aggregator接收到来自各方经过加密处理后的梯度数据，并将其应用于同一HE密钥下的权重参数

Drawbacks:

(1) 将weights放在 aggregator 需要 re-encryption

(2) 应用加密的梯度，无法使用复杂 ML optimizers

6. Evaluation

6.1 Methodology

Setting

a geo-distributed FL scenario

9 clients in five AWS EC2 datacenters.

不适用GPU，因为计算不是 bottleneck.

Benchmarking Models

• 3-layer fully-connected neural network on FMNIST dataset.

​ (batch size = 128, adopt Adam optimizer)

• AlexNet on CIFAR10 dataset

​ (batch size = 128, RMSprop optimizer with 10^{-6} dacay.)

• LSTM model on Shakespeare dataset

​ (batch size = 64, adopt Adam optimizer)

6.2 Impact of BatchCrypt’s Quantization

查看 quantization bit 是多少会影响 model quality.

对 9 个 clients 使用 BatchCrypt’s scheme including dACIQ clipping.

以 plain training 作为 baseline，quantization bit width 8,16,32.

FMNIST ：

plain baseline: acc 88.62% 40epochs

8-bit: acc 88.67% 122epochs

16-bit: acc 88.37% 68epochs

32-bit: acc 88.58% 32epochs

CIFAR :

plain baseline: acc 73.97% 285epochs

8-bit: acc 71.47% 234epochs

16-bit: acc74.04% 279epochs

32-bit: acc73.91% 280epochs

LSTM :

在基础/plain模式下（plain baseline），模型的损失值为0.0357，并于第20轮次达到稳定状态；采用8位量化策略时（8-bit），损失值上升至0.1359，并在第29轮次稳定下来；采用16位量化策略时（16-bit），模型表现得到显著提升，在第23轮次达到最佳效果；最后，在采用高精度的32位量化方法（即高精度计算配置）下（即设置为y= x的情况），模型最终达到了最低的损失水平，并在训练过程中始终保持稳定的收敛趋势。

Conclusion:

当采用适当设置的量化位数时，在此情况下 BatchCrypt 的量化对其性能的影响可视为微乎其微（其中当 epoch 数较大时，其影响可通过 BatchCrypt 加速处理来显著缓解）。

注意：longer bit width 并不一定意味着更高模型质量

量化训练可被视为一种正则化技术（regularization technique），通过mitigate overfitting（减轻过拟合）来提升模型的一般化能力（improve generalization），其架构与dropout层（dropout layer）相似。

Summary :

在适当宽度下进行梯度量化处理对于训练后的模型质量没有带来负面的影响效果

采用BatchCrypt时不需要考虑量化引起的错误

6.3 Effectiveness of BatchCrypt

BatchCrypt vs. FATE

quantization bit width to 16

batch size to 100

iterations to 50

communication time （idle in worker and transfer in aggregator）显著减少

BatchCrypt 大大减小了网络占用 66、70.5、101.2倍

BatchCrypt 在 larger model 上效果更好：

（1）more encryption-related operations for BatchCrypt

（2）higher chances of forming long batches.

BatchCrypt 加速达到了两个数量级，这完全可以抵消量化带来的开销。

BatchCrypt vs. Plaintext Learning

encryption remains the major bottleneck

迭代时间和网络占用：

Training to Convergence

• 与 FATE stock 相比，BatchCrypt减少训练时间13.76、72.32、80.65倍

​ network footprints shrink by 37.96、72.01、87.23

• 与 Plain learning 相比，BatchCrypt 仅慢了1.78、2.84、7.55倍（plain 是不需要加密的）

6.4 Batching Efficiency

BatchCrypt 可以有效处理量化值，不考虑 quantization bit width.

A lower quantization bit width is enabled by a larger batch size, resulting in reduced training time.

HE操作在较大batch size的情况下效果降低较多,因此16-bit到32-bit的提升效果不如8-bit到16-bit显著。

BatchCrypt的批量处理方案随着批处理大小的增加而呈现线性递减的趋势，并且有效降低计算资源消耗和通信开销。

6.5 Cost Benifits

BatchCrypt降低了97.4%，98.6%、98.8%的网络成本

7. Discussion

Local-update SGD & Model Averaging

only additional operations involved, BatchCrypt can be easily adopted.

Split Model Inference

BatchCrypt可用于加速中间推理结果的加密和传输。

Flexible Synchronization

our design enables it to make full use of the flexible synchronization methods

Potential on Large Models

某些模型即使使用1位或2位量化也能收敛

Applicability in Vertical FL

批处理这种计算超出了BatchCrypt当前的能力

8. Concluding Remark

系统地利用HE实现安全的 cross-silo FL

BatchCrypt:一组梯度以长整数进行编码，并接受加密处理,显著降低了计算资源消耗以及密文规模

相较于现有技术方案FATE，在本方案中实现了计算效率的提升81倍的同时，在通信开销上也达到了显著优化效果。具体而言，在部署于云计算环境下可使系统运行成本降低至原来的1%。此外，在网络资源消耗方面也实现了降本增效的目标。