联邦学习与密码学

2020/08/16 密码学

联邦学习(Federated Learning)是一种分布式机器技术(框架),最早由Google在2016年提出解决安卓手机终端在本地更新算法模型的问题。现在联邦学习框架解决的问题是协助多个机构间在满足数据隐私安全、合法合规的前提下对数据进行联合学习建模,即参与方在不泄露自身数据前提下完成联合建模。

联邦学习

联邦学习分为3大类,分别是

  • 横向联邦学习(Horizontal Federated Learning)
  • 纵向联邦学习(Vertical Federated Learning)
  • 联邦迁移学习(Federated Transfer Learning)

当两个数据集合的用户特征重叠比较大,而用户样本重叠比较小时,使用横向联邦学习。例如微众银行在深圳的业务与网商银行在杭州的业务,这两个数据集合的用户样本重叠比较小(深圳与杭州的物理距离),但是用户特征重叠比较大(都属于银行业务),可以使用横向联邦学习来构建联合模型

当两个数据集合的用户特征重叠比较小,而用户样本重叠比较大时,使用纵向联邦学习。例如网商银行在杭州的业务与网易云音乐在杭州的业务,这两个数据集合的用户样本重叠比较大(同一个城市的用户),但是用户特征重叠比较小(分别是银行业务与娱乐业务),可以使用纵向联邦学习来构建联合模型。

当两个数据集合的用户特征和用户样本重叠都比较小时,使用联邦迁移学习。例如网商银行在杭州的业务与TikTok在纽约州的业务,这两个数据集的用户样本和用户特征重叠都非常小,适用联邦迁移学习。通过引入迁移学习来解决单边数据规模小、标签样本少的问题[2]。

联邦学习商用落地

目前在联邦学习领域代码开源的有微众银行FATE、百度PaddleFL安全计算项目、谷歌的TensorFlow Federated框架,非开源的有蚂蚁金服Morse摩斯计算平台、平安科技的蜂巢等等[3]。其中FATE和Morse完成产品落地并获得信通院的安全计算证书。

联邦学习与联邦数据库的区别

从上面的描述中,我们会发现联邦学习与联邦数据库有相似的地方。联邦数据库系统对多个独立的数据库或者数据仓库进行CRUD数据库基础操作,这些数据库的数据可能是异构的,并且以分布式储存,例如有MySQL、ODPS、OceanBase、SLS等等。联邦数据库系统抽象了底层数据源的存储类型,统一以SQL语言来完成对数据源的操作。联邦学习与联邦数据库系统的区别在于,后者与各个数据库交互的过程中不涉及到任何隐私保护机制,数据对于联邦管理系统而言是可见的,存在数据安全风险[4]。

联邦学习与密码学

联邦学习需要解决如何在不泄露数据隐私的情况下完成联合计算,其中的核心是密码学上的加解密算法。本文的重点不是机器学习的内容,而是联邦学习中使用的密码学相关技术,因此下文主要围绕密码学展开。

目前实现联邦学习主要有两大技术路线[8],分别是基于硬件可信执行环境(Trusted Execution Environment, TEE)技术的可信计算,以及基于密码学的安全多方计算(Secure Multi-party Computation, MPC)。

TEE方案上比较核心的技术是intel SGX(Software Guard Extensions)。开发者可以把应用程序划分到受保护的私有内存区域encalve中,确保应用程序的机密性和完整性。

MPC是密码学中的一个子领域,它允许数据所有者在不泄露原始数据的前提下进行协同计算,输出计算结果,确保参与计算的每一方都无法获取除了计算结果以外的其他信息。MPC方案中比较核心的技术点有秘密分享(Secret Sharing)、同态加密(Homomorphic Encryption)以及混淆电路(Garbled Circuit)。下面以微众银行FATE中使用到的同态加密计算为切入点展开讨论。

微众银行 FATE

什么是数据孤岛?数据孤岛是指不同组织机构之间或者企业不同部门之间的数据无法流动、连接。打破数据孤岛面临的阻碍是数据的隐私问题。如何在保护数据隐私安全同时满足数据共享的需求是目前机器学习应用场景下的一个热点问题。腾讯微众银行提出了一个满足隐私保护和数据安全的解决方案,FATE。

FATE使用的密码学技术

下图是FATE的主要系统模块,我们重点关注MPC层。

从FATE在Github的开源代码中[5]可以发现FATE使用的几种密码学技术:

  • Paillier Encryption 加法同态加密算法
  • Affine Homomorphic Encryption 仿射同态加密算法,加法同态
  • IterativeAffine Homomorphic Encryption 变换仿射同态加密算法,加法同态
  • RSA
  • Diffne Hellman Key Exchange (DHKE)
  • SecretShare MPC Protocol (SPDZ) 秘密共享安全多方计算协议

同态加密的作用是允许对加密的密文进行函数操作,最常见的函数操作是同态加法和同态乘法。同态加密技术根据对数据的处理方式不同主要分为三类,分别是:

  • Fully Homomorphic Encryption (FHE),全同态加密算法,支持任意的、无限次数的密文函数操作。
  • Somewhat Homomorphic Encryption (SHE),有限同态加密算法,支持任意的、有限次数的密文函数操作。
  • Partially Homomorphic Encryption (PHE),部分同态加密算法,支持无限次调用同态加法或同态乘法操作。

其中FATE里使用到的同态加密算法里,Paillier、Affine、IterativeAffine Homomorphic Encryption均是PHE,支持加法同态,而RSA是支持乘法同态的PHE(在FATE里RSA仅作为公钥密码算法),SPDZ[6]是基于SHE实现的安全多方计算协议。下面我们展开其中Paillier算法的几个细节。

Paillier同态加密算法由Paillier在1999年的欧密上提出[7]。Paillier的同态方案主要涉及到3个操作,分别是密钥生成、加密、解密。

  • Key Generation

    • 随机独立选择两个大素数\(p,q\),并且满足\(gcd(pq,(p-1)(q-1)) = 1\)。
    • 计算出\(n=pq, \lambda=lcm(p-1,q-1)\)。
    • 随机独立选择一个整数\(g\),其中满足\(g \in Z^{*}_{n^2}\)。
    • 计算出\(\mu = (L(g^{\lambda}\bmod n^2))^{-1}\bmod n\),其中\(L(x)=\frac{x-1}{n}\)。
    • 得出公钥\(pk=(n,g)\),私钥\(sk=(\lambda,\mu)\)。
  • Encrypt

    • 假设要加密的消息为\(m\)(消息被映射到有限域上),满足\(0<m<n\)。
    • 随机独立选择一个整数\(r\),满足\(0<r<n\),显然有\(gcd(r,n)=1\)。
    • 计算出密文\(c=g^m \cdot r^n \bmod n^2\)。
  • Decrypt

    • 需要解密的密文为\(c \in Z^{*}_{n^2}\)。
    • 计算出明文\(m=L(c^{\lambda} \bmod n^2) \cdot \mu \bmod n\)。
    • 上面的明文公式也可以展开为\(m=\frac{L(c^{\lambda} \bmod n^2)}{L(g^{\lambda} \bmod n^2)} \bmod n\)。

Paillier同态加密算法的安全性可以归约到一个数学难题:给定整数\(n,z\),求出满足\(z \equiv y^n \bmod n^2\)的\(y\)值是困难的。下面是Paillier满足的加法同态性质,它不支持乘法同态。

\[D(E(m_1, r_1) \cdot E(m_2,r_2) \bmod n^2) = m_1 + m_2 \bmod n\] \[D(E(m_1, r_1) \cdot g^{m_2} \bmod n^2) = m_1 + m_2 \bmod n\]

我在阅读FATE的Paillier的代码实现时发现了两个细节。

细节1:FATE的Paillier加密函数部分,随机数\(g\)的取值是\(n+1\),这样可以减少加密函数的幂运算的次数。

class PaillierPublicKey(object):
    """Contains a public key and associated encryption methods.
    """
    def __init__(self, n):
        self.g = n + 1
        self.n = n
        self.nsquare = n * n
        self.max_int = n // 3 - 1
    
    """
    """

    def apply_obfuscator(self, ciphertext, random_value=None):
        r = random_value or random.SystemRandom().randrange(1, self.n)
        obfuscator = gmpy_math.powmod(r, self.n, self.nsquare)
        return (ciphertext * obfuscator) % self.nsquare
    
    def raw_encrypt(self, plaintext, random_value=None):
        if not isinstance(plaintext, int):
            raise TypeError("plaintext should be int, but got: %s" %
                            type(plaintext))
        if plaintext >= (self.n - self.max_int) and plaintext < self.n:
            # Very large plaintext, take a sneaky shortcut using inverses
            neg_plaintext = self.n - plaintext  # = abs(plaintext - nsquare)
            neg_ciphertext = (self.n * neg_plaintext + 1) % self.nsquare
            ciphertext = gmpy_math.invert(neg_ciphertext, self.nsquare)
        else:
            ciphertext = (self.n * plaintext + 1) % self.nsquare
        ciphertext = self.apply_obfuscator(ciphertext, random_value)
        return ciphertext

为什么这样做是可行的呢?下面给出正确性证明:

  • 假设\(g=n+1\)
  • 那么有\(c=g^m \cdot r^n \bmod n^2 = (n+1)^m \cdot r^n \bmod n^2 = (1+mn) \cdot r^n \bmod n^2\)

这使得原本加密函数中的\(m\)次幂运算降低到0次幂运算以及有限域上各1次的加法和乘法。上面的公式化简过程中涉及到一个二项定理:

\[(1+n)^x=\sum_{k=0}^x \begin{pmatrix} x\\ k \end{pmatrix} n^k = 1 + nx + \begin{pmatrix} x\\ 2 \end{pmatrix} n^2 + ... \text{higher powers of n}.\]

因此有

\[(1+n)^x \equiv (1+nx) \bmod n^2\]

细节2:FATE的Paillier解密算法中使用了中国剩余定理来提高解密的速度。

class PaillierPrivateKey(object):
    """Contains a private key and associated decryption method.
    """

    def h_func(self, x, xsquare):
        """Computes the h-function as defined in Paillier's paper page.
        """
        return gmpy_math.invert(self.l_func(gmpy_math.powmod(self.public_key.g, x - 1, xsquare), x), x)

    def l_func(self, x, p):
        """computes the L function as defined in Paillier's paper.
        """
        return (x - 1) // p

    def crt(self, mp, mq):
        """the Chinese Remainder Theorem as needed for decryption.
           return the solution modulo n=pq.
        """
        u = (mp - mq) * self.q_inverse % self.p
        x = (mq + (u * self.q)) % self.public_key.n
        return x
    
    def raw_decrypt(self, ciphertext):
        """return raw plaintext.
        """
        if not isinstance(ciphertext, int):
            raise TypeError("ciphertext should be an int, not: %s" % type(ciphertext))
        mp = self.l_func(gmpy_math.powmod(ciphertext, self.p-1, self.psquare), self.p) * self.hp % self.p
        mq = self.l_func(gmpy_math.powmod(ciphertext, self.q-1, self.qsquare), self.q) * self.hq % self.q
        return self.crt(mp, mq)

上面的代码逻辑如下,其中\(CRT\)是中国剩余定理函数。

\[L_p(x)=\frac{x-1}{p},L_q(x)=\frac{x-1}{q}\] \[h_p = L_p(g^{p-1} \bmod p^2)^{-1} \bmod p\] \[h_q = L_q(g^{q-1} \bmod q^2)^{-1} \bmod q\] \[m_p = L_p(c^{p-1} \bmod p^2) \cdot h_p \bmod p\] \[m_q = L_q(c^{q-1} \bmod q^2) \cdot h_q \bmod q\] \[m = CRT(m_p, m_q) \bmod pq\]

受限于篇幅,至于仿射同态和仿射变换同态算法就不展开描述了。

网商银行 Morse

根据官网上的描述,Morse的定位是:

大规模多方安全计算商用平台,基于多方安全计算、隐私保护、区块链等技术,实现数据可用不可见,解决企业数据协同计算过程中的数据安全和隐私保护问题,助力机构安全高效地完成联合风控、联合营销、联合科研等跨机构数据合作任务,驱动业务增长。

Morse分别使用了TEE和MPC方案来实现联邦学习(蚂蚁将其边界拓宽,称为共享学习),由于Morse没有开源,目前搜集到的资料还比较少,关于Morse在MPC方案上的细节我还不是很清楚。建议阅读这篇文章:共享学习: 比联邦学习更强大的数据孤岛解决方案

总结

本文首先抛出了关于联邦学习的定义以及目前的一些商用产品,然后以同态加密(MPC方案)为切入点展开讨论了联邦学习中比较核心的密码学基础。总结以下几点内容:

  1. 联邦学习允许参与方在满足数据隐私安全、合法合规要求前提下进行联合机器学习来解决数据孤岛问题。
  2. 联邦学习主要有两种技术方案,分别是TEE可信执行环境和MPC安全多方计算。
  3. 联邦学习的未来研究方向重心是数据安全性与密码学算法的效率问题。

参考资料

  1. Federated Machine Learning: Concept and Applications
  2. 知乎专栏-什么是联邦学习 https://zhuanlan.zhihu.com/p/100688371
  3. 知乎专栏-银行数字化“开放”与“自主”如何兼得 联邦学习商用观察 https://zhuanlan.zhihu.com/p/152321522
  4. 联邦学习白皮书-2.0 https://aisp-1251170195.cos.ap-hongkong.myqcloud.com/wp-content/uploads/pdf/%E8%81%94%E9%82%A6%E5%AD%A6%E4%B9%A0%E7%99%BD%E7%9A%AE%E4%B9%A6_v2.0.pdf
  5. FATE https://github.com/FederatedAI/FATE
  6. Overdrive: Making SPDZ Great Again https://eprint.iacr.org/2017/1230.pdf
  7. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf
  8. 共享学习: 比联邦学习更强大的数据孤岛解决方案 https://blog.csdn.net/weixin_44326589/article/details/99817811

Search

    Table of Contents