【全同态加密】基于AGCD的全同态加密方案

最近翻，全同态加密的时候，找到了一个有趣的方案[8]，为啥有趣呢，因为这个方案，应该算是比较好理解的全同态加密方案了，里面，基本上不涉及太多其他的数学问题，也就用到了，小学二年级学过的带余除法的知识就可以理解了，不像其他的基于LWE的方案，还要先理解LWE，因此，这里，就来水一篇文章，一起来看一下这一个方案。

背景知识

首先，我们来回顾一下，大家非常熟悉的一个概念，也就是最大公约数，相信大家应该对于这个概念并不陌生。

最大公约数

对于给定两个整数a和b，如果存在一个整数d满足如下条件

• d是a的约数，也就是
• d是b的约数，也就是
• 对于所有的整数k, 如果k是a和b的任意共同的约数，那么

我们称d是a和b的最大公约数，通常记作。

对于，任意两个数字呢，我们求解他的最大公约数，是有一个非常快的计算方法的，也就是大家熟知的欧几里得算法，这里就不展开描述了，相信各位读者应该都不陌生，并且，这个算法，在密码学当中出现的频率还是相当的高的，因为只要对于一个求逆元，基本上都要用到这个算法，

近似最大公约数算法(AGCD)

那么，问题来了，之前，其实我们了解过LWE, 添加一个噪声之后，便使得寻找原来的变得困难，那么我们针对于求解最大公约数，同样添加一个噪声呢，其实他也会变得困难。

我们，来描述一下这个问题，这里，我们采用决策的版本，来描述，因为密码学当中，很大概率，用的决策版本要更多一些。我们令

其中，我们要求，然后和随机数，其中，是不可区分的。

来一个简单的例子，比如说，

x_0: 7511762267097296623597571
x_1: 5260835876212355262978089
x_2: 5842439417310392827016873
x_3: 6606621472862031178881592
x_4: 5622848897659131949830271
x_5: 5010155935571121541192303
x_6: 7651322429600266269118566
x_7: 6820107589954534396675715
x_8: 6993791646691857523759409
x_9: 7233764524898512417362422

这里，里面p是固定值，然后其中有一个是随机数，能区分出来，哪个是随机数吗？

对于，这个问题如何分析呢，以及他是如何做的规约，这里就不展开描述了，有兴趣的可以看一下参考资料[2]当中的相关讨论。

基于AGCD的密码学协议

这里，我们先来看一个简单的基于AGCD设计的，加密算法，这里还是分为老三步了。

首先，生成一个私钥p, 这里，我们要求p是一个奇数，注意，不要求是素数。然后对于公钥，我们给定一个参数，这个表示，公钥当中元素的数量，然后最终的公钥为

其中都是在指定的范围内，随机均匀获取。

这个算法呢，只能加密一个比特，也就是消息，我们从公钥当中，随机挑选个元素，构成集合，对于密文，计算规则如下

解密算法，就比较容易了，这里，我们只需要模p在模2，就可以得到结果

这里，简单的分析一下，这个算法的正确性吧，我们有

于是乎，我们可以发现，后面的部分，一定是一个偶数，因此，在模2之后，我们就可以还原出来，原始的消息m。

这里，我们简单的用Python来实现一下这个逻辑，这个应该是比较好理解的。

import math
import random


def random_int(x):
    return random.randint(2 ** (x - 1), 2 ** x)


class Encryptor:
    def __init__(self):
        self._lambda = 16
        self._tau = 10
        self._kappa = 5

    def key_gen(self):
        p = random_int_odd(self._lambda + int(math.log2(self._lambda)))
        pk = []
        for i in range(self._tau):
            q = random_int(self._lambda * int(math.log2(self._lambda)))
            r = random_int(self._lambda)
            pk.append(p * q + 2 * r)
        return p, pk

    def encrypt(self, pk, m):
        return sum(random.sample(pk, self._kappa)) + m

    def decrypt(self, p, c):
        return c % p % 2


if __name__ == '__main__':
    encryptor = Encryptor()
    p, pk = encryptor.key_gen()
    c = encryptor.encrypt(pk, 0)
    print(encryptor.decrypt(p, c))

基于AGCD的同态加密算法

然后，我们来看一下，如何把上面的算法，调整一下，改成一个全同态加密的算法。

这里，我们假设，明文是，然后，对于他的密文，我们可以写作

然后，我们这里，可以实现，对应的加法运算，也就是

那么，为什么他们是相等的呢，这里，我们来看

因此，在实现解密过程，我们模p再模2之后，得到的就是的结果，这样，我们就完成了加法同态，当然，这个加法是在之下的。

然后，对于乘法呢，我们有

同样的，我们来看

在同样的操作之下，我们便可以得到对应的乘积。

这么做呢，看起来，似乎是非常的nice，但是呢，如果说，我们运算次数，足够的多，那么就会出现一个问题，就是，比如在加法运算当中，这么就会导致，在模p的时候，消息产生了影响，从而导致结果不再正确，这里对于加法增长的速度还是不咋地快的，但是，对于乘法来说，这个增长速度就很快了，因为它是错误的乘积。

这里，我们来简化的推算一下，我们只考虑，乘法的误差，因为乘法增长的要远远大于加法。

然后，我们知道，错误的层级有如下的关系

也就是，我们其实，只完成了L层深度的同态加密计算。接下来，有意思的事情就来了，那么，我们在完成了这个有限深度的全同态加密计算之后，我们怎么能够来给搞成一个全同态加密的系统呢？

自举(Bootstrapping)

具体，这个词的翻译呢，参考了一些资料[3,4]，应该是能翻译成为自举的吧，如果翻译错了，也欢迎读者和我交流，这几句是废话，那么，后面，我们还是用不翻译了，翻译出来，感觉怪怪的，不得劲。

书接上文，我们提到了一个有限层级的全同态加密方案，也就是我们支持最多对数层深度的全同态加法和乘法运算，当然，这些运算，还是在下面的，然后呢，这里Gentry，在2009年[5]，首次提出了Bootstrapping技术，这个方案呢，使得有限层的全同态加密方案呢，可以通过一系列的操作，转换成为一个无限层级的全同态加密方案。

这里，我们在运行一些操作之后，这里，我们的误差，会达到一个临界值，在执行一次运算，我们的误差，就会超过这个临界值，导致解密失败，然后我们可以这么来做，我们对于私钥，也进行加密，之后，我们得到加密之后的私钥，因为这个操作是全同态的，因此，我们可以实现一个全同态的解密运算，然后，这里，运行解密运算的操作的误差层级，是要小于最大误差深度的，并且，还要预留出来，可以继续运算的空间。

这里，因为，我们用我们的全同态算法，实现了解密的运算，因此，这里是不会去leak其他的信息的，然后，这里因为经过了全同态的解密，因此，这里的误差，就会回落到一个比较低的水平，这样，我们每次到临界值，也就是误差快要爆掉的时候，我们都来这么一下子，那么我们就可以实现一个无限次数的全同态加密的方案了。这个思想，其实还是比较好理解的，但是，如果我想，我肯定想不到，从09年Gentry提出这个方案之后，后续全同态也都采用了这个方案。

本文，提到的全同态方案呢，其实就是Gentry的第一代方案，只不过，在本文当中，我做了一定程度的简化，有兴趣的读者，可以自行的看下资料[8]。

代码实现

这个代码呢，我相信，肯定是有大佬写过的，具体参见资料[7]，当然，这个代码是用rust来写的，整体阅读起来，还是比较容易的，我们来看一下结果吧。

可以发现，这个代码，确实是对的，有兴趣的读者，可以自行阅读一下相关源码，注意，这个代码第一次编译时间，可能老长，耐心等待。

总结

简单总结下，本文呢，实际上是第一代全同态方案，这里基于的困难问题是AGCD问题，这个算法，其实，效率还是不咋地高的，读者，运行下具体[7]中的代码，就能体验到了，然后，后续的方案，其实都是基于LWE的了，因为LWE吧，他的加速，确实是多，毕竟NIST发布的3个抗量子算法当中，就有俩是基于LWE来做的，好了，其他的全同态加密方案，我们有机会再来聊，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/
2. https://crypto.stackexchange.com/questions/62823/why-is-approximate-gcd-a-hard-problem
3. https://en.wikipedia.org/wiki/Bootstrapping
4. https://www.investopedia.com/terms/b/bootstrapping.asp
5. Fully Homomorphic Encryption Using Ideal Lattices, Craig Gentry, 2009
6. https://eprint.iacr.org/2016/215.pdf
7. https://github.com/DeviousCilantro/fhe-int
8. https://eprint.iacr.org/2009/616.pdf