Paillier同态加密算法

Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，即密文相乘等于明文相加，即：

$D(E(m_1)\cdot E(m_2))=m_1+m_2$

标量乘法同态，即标量k乘以

$D(k*E(m1)) = k*m1$

1. Paillier方案描述

原版Paillier方案于论文[1]中提出，下面对方案进行描述：

1.1 密钥生成

选两个大素数 $p, q$ , 需要满足条件 $gcd(pq, (p-1)(q-1))=1$ , 不满足就重新选择随机数；
计算 $n = pq, \lambda = lcm(p-1,q-1)$ ，这里 $lcm$ 表示最小公倍数（Least Common Multiple）；
定义 $L(x)= \left \lfloor \frac{x-1}{n} \right \rfloor$ , 这里除法后向下取整；
随机选取一个小于 $n^2$ 的正整数 $g$ ，并且存在 $u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n$ ，如果不存在这样的 $u$ ，则要重新选择 $g$ ，或者从第1步重新开始。

得到的公钥为 $(n, g)$ , 私钥为 $(\lambda, u)$

快速生成私钥

如果素数 $p, q$ 长度相等，则可以采用一种简化的方式来生成Paillier的公钥和私钥，第3、4步改为：

$g=n+1, \ \lambda = \phi(n), \ u=(\phi(n)-1）mod\ n$

其中 $\phi(n)$ 为欧拉函数，即 $\phi(n) = (p-1)*(q-1)$ 。

1.2 加密

明文为 $m, 0 < m < n$ ;
随机选择 $r$ , 满足 $0<r<n$ 且 $r \in Z_{n^2}^*$ , $r$ 和 $n$ 互质；
计算密文： $c=g^mr^n \ mod \ n^2$

1.3 解密

计算明文 $m=L(c^{\lambda} \ mod \ n^2)*u \ mod \ n$

2. Paillier加解密实例

生成密钥对：

随机选择素数 $p=13, q=17$
计算 $n=13*17=221$
$\lambda = lcm(p-1, q-1) = lcm(12, 16) = 48$
随机选择小于 $n^2 = 221^2$ 的正整数 $g=4886$
计算 $u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n = (L(4886^{48}mod\ 48841))^{-1} \ mod\ 221 =159$

则公钥为 $(n,g)=(221, 4886)$ ，私钥为 $(\lambda , u)=(48, 159)$ 。

假设要对消息 $m=123$ 进行加密，则加密过程：

随机选择 $r=666$ ，且 $r$ 和 $n$ 互素
计算加密结果 $c=g^m r^n mod n^2 = 4886^{123} * 666^{221} \ mod \ 48841 = 25889$

解密过程：

$m = L(c^{ \lambda } mod n^2) * u \ mod \ n=L(25889^{48} \ mod \ 48841) * 159 \ mod \ 221 = 123$

3. Paillier的设计思路

下面介绍一下 Paillier 加密方案的设计思路。

根据 Binomial theorem ，有：

$(1+n)^x = \sum_{k=0}^x {x \choose k} n^k = 1 + nx + {x \choose 2}n^2 + {\text{higher powers of }}n$

这意味着：

$(1+n)^x = 1 + nx \pmod {n^2}$

如果定义：

$y = (1+n)^x \pmod {n^2}$

那么：

$x = \frac{y-1}{n} \pmod {n^2}$

从而有：

$L((1+n)^x \bmod n^2) = x \pmod n$

这里 $L(x)= \left \lfloor \frac{x-1}{n} \right \rfloor$

4. Paillier具备“加同态”性质

加法同态

Paillier加密的两个密文消息相乘的结果解密后得到两个消息相加的结果。

对于两个密文 $c_1 \equiv g^{m_1}.r_1^n \bmod n^2 和 c_2 \equiv g^{m_2}.r_2^n \bmod n^2$

$c_1c_2 \equiv g^{m_1}.g^{m_2}.r_1^n.r_2^n \bmod n^2 \\ \Rightarrow c_1c_2 \equiv g^{m_1}.g^{m_2}.r_1^n.r_2^n \equiv g^{m_1+m_2}.(r_1.r_2)^n \bmod n^2$

其中 $r_1$ 和 $r_2$ 都是 $Z_{n^2}^*$ 中的元素，因此 $r_1r_2$ 也属于 $Z_{n^2}^*$ , 并具有相同的性质，所以 $c_1c_2$ 可以看作是 $m=m_1+m_2$ 加密的密文， $c_1*c_2$ 的解密结果为 $m$ 。

同态标量乘法

对于密文 $c_1$ 和标量 $k$ ，计算 $c = c_1^k \bmod n^2$

需要说明的是，对于 Paillier 加密方案，给出公钥和两个加密后的消息 $E(m_1)$ 和 $E(m_2)$ ，无法计算出 $m_1 * m_2$ 的密文。也就是说 Paillier 没有“乘同态”性质。

4.1 具备“乘同态”性质的加密方案（Unpadded RSA，ElGamal）

Unpadded RSA，ElGamal 加密方案都具备“乘同态”性质。

下面以 RSA 为例，介绍一下它的“乘同态”性质。我们知道对于 RSA，加密算法为 $E(m) = m^e \bmod n$ ，从而可以推出它的“乘同态”性质:

$\begin{aligned} E(m_1) \cdot E(m_2) & = m_1^e \cdot m_2^e \bmod n\\ &= (m_1 \cdot m_2)^e \bmod n \\ &= E(m_1 \cdot m_2) \end{aligned}$

总结

常见的同态加密算法中，Paillier算法和Benaloh算法仅满足加法同态，RSA算法和ElGamal算法只满足乘法同态，而Gentry算法则是全同态的。

参考

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 199,393评论 5赞 467
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 83,790评论 2赞 376
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 146,391评论 0赞 330
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 53,703评论 1赞 270
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 62,613评论 5赞 359
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,003评论 1赞 275
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,507评论 3赞 390
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,158评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,300评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,256评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,274评论 1赞 328
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,984评论 3赞 316
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,569评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,662评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,899评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,268评论 2赞 345
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,840评论 2赞 339