同态加密

Paillier加密: 任意次同态加与标量乘

支持无限次的加法同态以及明文k与密文的乘法同态（ $k \cdot E n c (m)$ ），这里先讲g优化为n+1后的Paillier加密。

参数设置:
1. 选择两个大素数 $p, q$ ，计算 $N = p q$
2. 计算 $ϕ (N) = (p - 1) (q - 1)$ ， $ϕ (N^{2}) = N \cdot ϕ (N)$ ， $∵ ϕ (N^{m}) = N^{m} \cdot (1 - \frac{1}{a}) \cdot (1 - \frac{1}{b}) \dots = N^{m - 1} \cdot (a - 1) (b - 1) \dots$ ，其中 $a, b, \dots$ 为 $N$ 的不同质因数
3. 由二项式定理易知： $(1 + N)^{a} \in {Z^{*}}_{N^{2}} m o d N^{2} \equiv (1 + a N)$ ， $∴ (1 + N)^{N} m o d N^{2} \equiv 1$ ，易知： $i n d (1 + N) \in {Z^{*}}_{N^{2}} = N$
4. 对于一个映射 $f (a, b) = (1 + N)^{a} \cdot b^{N} m o d N^{2}$ 是单射
证明
设 $f (a_{1}, b_{1}) = f (a_{2}, b_{2})$ ，则 $(1 + N)^{a_{1}} \cdot b_{1}^{N} \equiv (1 + N)^{a_{2}} \cdot b_{2}^{N} m o d N^{2}$ ，则 $(1 + N)^{a_{1} - a_{2}} \equiv (b_{2} b_{1}^{- 1})^{N} m o d N^{2}$ ，设 $a_{1} - a_{2} = k$ ，则 $(1 + N)^{k} \equiv (b_{2} b_{1}^{- 1})^{N} m o d N^{2}$ ，如果 $k \neq 0$ ，则 $(1 + N)^{k} = 1 + k N$ ，而 $(b_{2} b_{1}^{- 1})^{N} \equiv 1 m o d N$ ，则 $k N \equiv 0 m o d N$ 恒成立，但是对于模 $N^{2}$ 而言，如果 $k \neq 0$ ，则 $k N < N^{2}$ ，故不成立，所以 $k = 0$ ，即 $a_{1} = a_{2}$ ，从而 $b_{1} = b_{2}$ 。证毕。
1. $f (a_{1}, b_{1}) \cdot f (a_{2}, b_{2}) \to f (a_{1} + a_{2}, b_{1} b_{2})$ 是一个同态
2. 公钥为 $N$ , 私钥为 $ϕ (N)$ ，既 $(p - 1) (q - 1)$
3. 记 $L (x) = \frac{x - 1}{N}$
加密
1. 选择随机数 $r \in {Z^{*}}_{N}$
2. 明文 $m \in Z_{N}$
3. 密文计算： $c = E n c (m, r) = (1 + N)^{m} \cdot r^{N} = (1 + m \cdot N) \cdot r^{N} m o d N^{2}$
解密
1. 计算 $c^{ϕ (N)} m o d N^{2}$ ，则 $c^{ϕ (N)} \equiv ((1 + N)^{m} \cdot r^{N})^{ϕ (N)} m o d N^{2} \equiv (1 + N)^{m \cdot ϕ (N)} m o d N^{2}$ ， $∵ g c d (r, N^{2}) = 1 and ϕ (N^{2}) = N ϕ (N) \to r^{N ϕ (N)} \equiv 1 m o d N^{2}$
2. 计算 $\frac{(1 + N)^{m \cdot ϕ (N)} - 1}{N} \equiv \frac{1 + m \cdot ϕ (N) N - 1}{N} \equiv m \cdot ϕ (N) m o d N$ (参数设置中的3)
3. 解得 $m \equiv m \cdot ϕ (N) \cdot ϕ (N)^{- 1} m o d N$

原始版本：把 $1 + N$ 换成生成元 $g$ ，则加密为 $c = g^{m} \cdot r^{N} m o d N^{2}$ ，跟优化后的比多了一次幂运算。

同态加
1. 设有两个密文 $c_{1} = E n c (m_{1}, r_{1})$ ， $c_{2} = E n c (m_{2}, r_{2})$
2. 则 $c_{1} \cdot c_{2} m o d N^{2} = (1 + N)^{m_{1}} \cdot r_{1}^{N} \cdot (1 + N)^{m_{2}} \cdot r_{2}^{N} m o d N^{2}$ $= (1 + N)^{m_{1} + m_{2}} \cdot (r_{1} r_{2})^{N} m o d N^{2} = E n c (m_{1} + m_{2}, r_{1} r_{2})$
标量乘
1. 设有密文 $c = E n c (m, r)$ ，标量 $k \in Z$
2. 则 $c^{k} m o d N^{2} = ((1 + N)^{m} \cdot r^{N})^{k} m o d N^{2}$ $= (1 + N)^{k m} \cdot (r^{k})^{N} m o d N^{2} = E n c (k m, r^{k})$

BGN加密: 任意次同态加与一次同态乘

配对的一些性质：

乘法同态：

$e (u 1 \cdot u 2, v) = e (u 1, v) \cdot e (u 2, v)$

$e (u, v 1 \cdot v 2) = e (u, v 1) \cdot e (u, v 2)$

指数可提到映射外： $e (u^{a}, v) = e (u, v)^{a} ， e (u, v^{b}) = e (u, v)^{b}$

合起来： $e (u^{a}, v^{b}) = e (u, v)^{a b}$

密钥生成
1. 选择两个大素数 $p, q$ ，计算 $N = p q$
2. 准备双线性映射 $e : G \times G \to G_{T}$ ，生成元 $g \in G$ ，生成元 $h \in G_{T}$ ， $i n d (G) = i n d (G_{T}) = N$
3. 公钥为 $(n, g, h, e, G, G_{T})$ ，私钥为 $(p, q)$
加密计算 $c = g^{m} \cdot h^{r}$ ，其中 $m \in Z_{N}$ 为明文， $r \in Z_{N}$ 为随机数
解密
1. 计算 $c^{p} = (g^{m} \cdot h^{r})^{p} = (g^{p})^{m}$
2. 然后对其进行离散对数求解，得到 $m$
同态加 $E n c (m_{1}) \oplus E n c (m_{2}) = g_{1}^{m} h_{1}^{r} \cdot c \cdot h^{r}$ $= g^{m_{1} + m_{2}} \cdot h^{r_{1} + r_{2} + r}$ $= E n c (m_{1} + m_{2})$
同态乘
1. $c_{1} = E n c (m_{1}) = g^{m_{1}} h^{r_{1}}$ ， $c_{2} = E n c (m_{2}) = g^{m_{2}} h^{r_{2}}$
2. denote $g_{1} = e (g, g)$ ， $h_{1} = e (g, h)$ ，有 $i n d (g_{1}) = n$ ， $i n d (h_{1}) = p$
3. $\begin{aligned} E n c (m_{1}) \otimes E n c (m_{2}) & = \\ = e (c_{1}, c_{2}) h_{1}^{r} \\ = e (g^{m_{1}} h^{r_{1}}, g^{m_{2}} h^{r_{2}}) h_{1}^{r} \\ = e (g^{m_{1}}, g^{m_{2}} h^{r_{2}}) \cdot e (h^{r_{1}}, g^{m_{2}} h^{r_{2}}) h_{1}^{r} \\ = e (g^{m_{1}}, g^{m_{2}}) \cdot e (g^{m_{1}}, h^{r_{2}}) \cdot e (h^{r_{1}}, g^{m_{2}}) \cdot e (h^{r_{1}}, h^{r_{2}}) \cdot h_{1}^{r} \\ = e (g, g)^{m_{1} m_{2}} \cdot e (g, h)^{m_{1} r_{2}} \cdot e (h, g)^{r_{1} m_{2}} \cdot e (h, h)^{r_{1} r_{2}} \cdot h_{1}^{r} \\ = g_{1}^{m_{1} m_{2}} \cdot h_{1}^{m_{1} r_{2} + r_{1} m_{2} + \dots + r} \\ = g_{1}^{m_{1} m_{2}} \cdot h_{1}^{\tilde{r}} \\ = E n c (m_{1} m_{2}) \end{aligned}$

同态加密 ​

Paillier加密: 任意次同态加与标量乘 ​

BGN加密: 任意次同态加与一次同态乘 ​

同态加密

Paillier加密: 任意次同态加与标量乘

BGN加密: 任意次同态加与一次同态乘