智东西|54页PPT全解联邦学习中的同态运算与密文传输【附PPT下载】( 五 )
文章图片
针对联邦学习的第二个挑战 ， 我们的主要通过平方乘算法+蒙哥马利算法来解决模幂运算代价大的问题 。 我们解决的具体问题是如何高效的计算模幂运算 ， 模幂运算公式是上图中最上面的公式 ， 这里面a,b,c均为N比特大整数 ， 一般N都是1024或2048的常比特的一个整数 。 首先想到的是朴素算法 ， 先计算出a的b次方的值 ， 然后将这个计算结果对c取模 。 它的缺点是计算复杂度非常高 ， 高达O(2N) ， 并且中间层级的结果非常大 ， 在GPU里面根本就无法保存 。
我们做的第一个优化就是做平方乘算法 ， 平方乘算法的原理非常简单 ， 若我们想求a的k次方的值 ， 不需要让a乘上k次 ， 可以先求a的二分之k次方 ， 再平方 。 以此类推 ， 若算a的二分之k次方的值 ， 要先求a的4分之k次方的值 ， 然后再平方 ， 通过这种方法可以将计算次序降低到log(K)次 。 有了这个方法就可以将模幂运算里的b表示成二进制数 ， 通过log(b)次的乘法 ， 就能算出模幂的值 。
平方乘算法的优点是将整个计算的复杂度下降到O(N)并且中间计算结果都不超过c 。 但它的缺点是仍然要进行2N次的取模运算 ， 对GPU来说 ， 取模代价是很高的 。
为了解决取模运算代价高的问题 ， 我们进一步引入蒙哥马利模乘算法 。 它最大的特点是能够在不进行取模运算的这个前提下 ， 就算出模乘的值 ， 这样就完全避免了代价高昂的取模运算 。
接下来 ， 我讲下如何解决联邦学习需要缓存大量中间计算结果的问题 ， 我们的主要解决方案就是使用中国剩余定理 。
文章图片
首先 ， 先讲下联邦学习的解密计算公式 ， 上面是联邦学习解密运算的完整的公式 。 通过观察整个公式会发现 ， 联邦学习解密计算出来的明文m其实是一个长度为N比特的值 ， 但是它中间一部分的计算结果其实是2N比特 ， 意味着在计算中需要两倍的显存进行存储 ， 这对计算效率的影响还是挺大的 。
文章图片
接下来我会讲解如何用中国剩余定理来减少解密计算里的中间计算结果 ， 首先 ， 简单介绍下中国剩余定理 。 中国剩余定理指给定一组两两互质的整数n1、n2……nk以及任一组整数a1、a2……ak ， 类似于上面的统一方程组 ， 它一定有解 ， 并且解一定同余于N ， N指的是n1、n2……nk相乘的值 。
文章图片
利用中国剩余定理就可以避免直接去计算解密公式来求解明文m ， 首先会构造两个子项mp以及mq ， 通过mp跟mq两个子项 ， 构造一个同余方程组 ， 因为这个p与q都是大质数 ， 它们一定是互质的 ， 一定满足中国剩余定理的条件 ， 所以这是一个满足中国剩余定理的统一方程组 。 我们用CRT(mp ， mq)表示方程组的解 。 在数学上可以证明 ， 同余方程组的解modpq的值等价于上面联邦学习解密计算公式得出的值 。 也就是说如果求解联邦学习解密计算 ， 我们不一定要根据上面表达式来计算 ， 也可以用下面的表达式来替代 。 下面的表达式计算主要涉及图中紫色框框出的三个部分的计算 ， 这三个部分的计算有两个特点 ， 第一个是三部分的中间计算结果都不超过N比特 ， 因此避免使用更大的显存来缓存中间结果；另外是从2N比特数的模幂运算简化成N比特数的模幂运算 ， 计算量是大幅度减少 。
最后来看下使用上面三种方法以后 ， GPU加速联邦学习计算的一个评测结果 。 对比的bassline是14核2.2Ghz的CPU ， 用的GPU是TeslaV100 ， 我们主要对比了四种联邦学习涉及的密态计算 ， 包括同态加密、同态解密、密态乘法及密态加法 。 对于计算比较复杂的同态加密和同态解密 ， 差不多有6倍左右的加速 ， 对于计算相对简单的密态乘法及密态加法 ， 实现了几十倍和几百倍的加速 。 这其实只是一个初步的结果 ， 我们相信使用GPU加速联邦学习计算其实还有更大的空间 ， 值得大家一起来探索 。
推荐阅读
- 智东西|占美国门店25%以上，疫情使苹果再关美国30家门店
- 科技报道|用了十几年了，哪些东西觉得贵的值得？网友：充电十分钟用一个月
- AI科技报|很可能又是一款PPT手机，小米mix将首发120W快充？综合分析
- 车东西|可辅助车辆完成分米级定位，日本研制出新型惯性传感器
- 小暖男石头哥|讲透中、美、德三国智能制造战略，清华大学68页PPT
- 「美国」什么东西掠过中国上空？NASA公布一消息，大量数据已传回美国
- 早爆娱闻|打造高绩效团队好东西，揪头发、照镜子、闻味道：21页阿里三板斧
- 车东西|后者融资已超70亿，亚马逊或砸10亿美元收购自动驾驶创企Zoox
- 次等大叔|却在网上特别的火？是信息差干的好事，为什么有些东西明明是假的
- CPU@华为Mate30Pro，除了强劲的处理器，你该知道这些东西！