【密码学】Pailler半同态加密方案

近期，看到铜锁里面一个半同态加密算法还挺有意思，然后呢，想着，顺道看一下吧，正好好久也没写文章了，这不，水文章的素材就来了。

前言

简单的介绍一下，什么是半同态加密，这个概念，如果说完全没了解过这个东西的话，不要被这个名词给吓住，虽然我知道，文章当中出现的数学元素越多，可能看完的概率就越低，所以呢，争取，文章当中少用点数学公式。

我们先来看一下官方的定义，具体定义来自于维基百科。

❝

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it.

❞

用一个场景来举例说明一下，假设，你有一些数据需要进行一系列的运算，其中运算包括加法和乘法，但是呢，你这本地的算力有限，如果要完成这一系列的运算，需要耗费大量的计算资源，如果本地搭建这么一个计算平台的话，消耗的资源实在是太大了。于是呢，你就想到要把这个计算放到云计算平台上来实现，通过租赁云计算平台的算力，来实现这个运算过程，这样成本就在可控制的范围之内了。

那么问题又来了，这些数据呢，对于你来说，是非常重要的数据，你不希望把原始的数据提交给云服务，那么依靠原有的密码学知识，似乎就没办法实现这个过程了。

小孩子才做选择，那么成年人当然是选择两个都要了，同态加密呢，就是既能将数据加密，又能在加密之后保持原有的运算性质，那么上面这个场景就迎刃而解了。

由于全同态加密实现起来难度比较大，本文呢，来介绍一种半同态的方案，那么问题又来了，什么是半同态呢，我们上面提到了，运算其中有加法和乘法运算，但是同时实现加法和乘法运算比较困难，如果单独支持一种，比如只支持加法运算或者只支持乘法运算，那么实现起来就比较简单，前面铺垫了这么多，接下来就来看一下本文要介绍的一个半同态加密方案Paillier方案的具体过程。

预备知识

在介绍这个算法过程之前呢，需要用到一点点的数学知识，这里先简单介绍一下。

复合剩余类问题

若，其中p和q都为素数，如果存在整数，使得，那么我们称z为模的n阶剩余类。其中判定整数z是不是模的n阶剩余类是困难的。

Carmichael Function

介绍这个函数之前呢，我们简单来回顾一下之前介绍过的欧拉函数。之前介绍rsa的时候，我们提到过一个定理，那便是欧拉定理。

任意n和a互素，那么我们有

有关于欧拉定理的证明，这里就不展开了，相信读者应该会自己证明欧拉定理吧。

然后呢，我们思考是不是欧拉函数是最小的x使得下面的等式成立呢

显然不是，我们来看一个例子。比如说数字8，我们很容易计算它的欧拉函数，比如手算，当然，也有公式可以计算出来，对于忘记公式的读者呢，我这里给一下公式吧。

我们知道，比如说和8互素的元素7，我们知道，显然欧拉函数是成立的，然后呢，我们来计算一下下面的一系列数字。

• ...

显然，我们可以找打一个比4更小的数字，使得这个成立，因此呢。欧拉函数，明显就不是最小的，我们定义，Carmichael函数。

其中为使得上面的式子成立的最小正整数，然后我们给出他的计算方法吧。

其中lcm是最小公倍数。具体的证明这里就不给出了有需要的读者，可以翻一翻数论的相关知识。

Paillier算法

密钥生成

我们先来看一下，密钥生成的过程，整个过程可以分为4步，具体如下

• 首先选择两个素数p和q，这里p和q要取的大一些
• 计算p和q的乘积n，以及
• 选取一个随机整数g，其中
• 令计算

然后，公钥为(n, g)，私钥为

加密过程

假设需要加密的内容为m，具体加密过程可以分为两步

• 选择随机数r，其中
• 计算密文

解密过程

解密过程，只需要计算一步

• 计算明文

密文加法

因为，这是一个半同态加密的算法，除了加密，我们需要定义运算，这里实现了加法和标量乘法的运算，首先来看一下加法运算

• 给定密文和
• 加法运算的结果

密文减法

对于减法，实际上是加法的逆运算，我们来看一下减法的运算

• 给定密文和
• 减法运算的结果

标量乘法

对于标量乘法，实际上可以看做连续加法的运算，我们来看一下标量乘法的运算

• 给定密文和明文标量
• 标量乘法

证明

咱也简单的证明一下，拿出我刚学的数论的知识，我们来一起证明一下，首先来看一下解密过程的正确性。

根据Carmichael Function，我们知道

因此

然后，我们可以得到

然后，我们应用L函数，可以得到

好了，这就证明完成了。

接下来，我们来证明一下加法的同态性，

因此

解密过程

加法的同态性可得。

总结

现在AI技术在不断发展，大模型的出现，的的确确在影响着我们的生活，说实话，AI在某些情况下写的代码比我写的好的太多，但是呢，一般人的电脑是支撑不了本地运行大模型的，而且有的大模型本身就是闭源的，那么我们想要享受大模型带来的福利，必然需要上传数据到云端进行计算，那么如何来保证上传这些数据的安全性呢，有没有一种可能通过密码学手段，上传密文的数据，得到结果，然后在本地解密拿到明文呢？这是我的一个猜想，因为我也不知道能不能实现，因为我实在太菜，如果这个可以做到，个人感觉大模型的应用应该会更加广泛，好了，今天的闲聊就到这里，感谢各位读者的观看，咱们下期再见，下期，咱们看一下铜锁当中的另一个基于椭圆曲线离散对数问题的半同态加密。

参考资料

• https://www.yuque.com/tsdoc/misc/rdibad
• https://zhuanlan.zhihu.com/p/580291259
• Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[J]. Lecture Notes in Computer Science, 1999, 547(1):223-238.
• R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, 1978.(https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/RAD78.pdf)
• https://en.wikipedia.org/wiki/Homomorphic_encryption
• https://github.com/ZenGo-X/rust-paillier/tree/master
• https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2015/[20150707][carmichael].pdf
• https://en.wikipedia.org/wiki/Carmichael_function
• https://www.cnblogs.com/pam-sh/p/14950746.html