基于高效同态加密的Cross-silo联邦学习

Background

回顾联邦学习（federated learning，FL）的发展，目前目前主要有Cross-Silo的模式和Cross-device模式。前者面向机构，后者则是针对终端。其次，也有许多工作研究FL中梯度更新带来的隐私泄露。针对隐私泄露，目前主要通过安全聚合（e.g., 求和/平均）来实现保护隐私的目的。现在主要的安全聚合方案，主要有基于秘密分享、基于成对加性掩码、基于差分隐私，和基于同态加密（Homomorphic Encryption，HE）的方案。各种方案各有利弊。 本文主要针对Cross-Silo场景下，加速基于HE的安全聚合方案，并减少通信开销。 Main Contributions: 本文主要提出了一种梯度量化的方法，并对量化梯度进行batch encoding。进一步，在batch encoding的梯度上进行HE 操作。

Process

前人的量化方案：将一个 \(y \in \left [ -1, 1 \right]\)的梯度量化为一个8-Bit的无符号整数，量化函数和解量化函数如下：

，其中 是就近取整函数（rounding function）; ，其中 是 个量化梯度之和。

但是上述量化方法存在一定的问题：

1. 要正确计算 ，必须事先预知 。因此，每次加入新的用户，需要手动检验调整 的取值；
2. 容易溢出。因为所有的正负梯度都编码为无符号整数，多个用户的累加值容易导致溢出；
3. 不能区分正溢出和负溢出。

本篇文章进行了一定的改善，主要解决了以下几个问题：

\1. 有符号量化：梯度被量化为有符号的整数，这样一来正负值相互抵消有助于解决溢出问题； \2. 关于原点对称的量化区间：为了保证相反符号数能够正确的抵消，量化区间必须关于原点对称。否则，假设将 量化到 ，那么 ，结果错误； \3. 均匀量化。这是为了保证量化数值的加同态性质需要满足的性质。

粗略来说便是将 量化到 ，将 量化到 。；公式化表示如下： ，其中 和 分别是向上取整和向下取整函数； ； 进一步，实用2-bits 表示符号位（sign-bits）。如此， 便有了两种编码方式。

Performance

实验的最终表现也是体现出\(BatchCrypt\)和\(stock\)相比在通信和计算上都有着很大的提升，但是和\(Plaintext Learning\)相比还是有很大的进步空间。