同态加密

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

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

1. 参数设置:

   1. 选择两个大素数$p,q$，计算 $N=pq$
   2. 计算 $\phi(N)=(p-1)(q-1)$，$\phi(N^2)=N \cdot \phi(N)$，$\because \phi(N^m) = N^m \cdot (1-\frac{1}{a}) \cdot (1-\frac{1}{b}) \cdots = N^{m-1} \cdot (a-1)(b-1) \cdots$
   3. 由二项式定理易知：$(1+N)^a \in \mathbb{Z^*}_{N^2} \; mod \; N^2 \equiv (1+aN)$，易知 $ind(1+N) \in \mathbb{Z^*}_{N^2} = N \because (1+N)^{N} \; mod \; N^2 \equiv 1$
   4. 对于一个映射 $f(a,b) = (1+N)^a \cdot b^N \; mod \; 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 \; mod \; N^2$，则 $(1+N)^{a_1-a_2} \equiv (b_2 b_1^{-1})^N \; mod \; N^2$，设 $a_1-a_2=k$，则 $(1+N)^k \equiv (b_2 b_1^{-1})^N \; mod \; N^2$，如果$k \neq 0$，则$(1+N)^k = 1+kN$，而$(b_2 b_1^{-1})^N \equiv 1 \; mod \; N$，则$kN \equiv 0 \; mod \; N$恒成立，但是对于模$N^2$而言，如果$k \neq 0$，则$kN < N^2$，故不成立，所以$k=0$，即$a_1=a_2$，从而$b_1=b_2$。证毕。

   5. $f(a_1,b_1) \cdot f(a_2,b_2) \rightarrow f(a_1+a_2,b_1b_2)$ 是一个同态
   6. 公钥为 $N$, 私钥为 $\phi(N)$，既$(p-1)(q-1)$

2. 加密

   1. 选择随机数$r \in \mathbb{Z^*}_N$
   2. 明文$m \in \mathbb{Z}_N$
   3. 密文计算：$c = Enc(m,r) = (1+N)^m \cdot r^N = (1+m \cdot N) \cdot r^N \; mod \; N^2$

3. 解密

   1. 计算 $c^{\phi(N)} \; mod \; N^2$，则 $c^{\phi(N)} \equiv ((1+N)^m \cdot r^N)^{\phi(N)} \; mod \; N^2 \equiv (1+N)^{m \cdot \phi(N)} \; mod \; N^2$，\because gcd(r,N^2) = 1 \And \phi(N^2) = N\phi(N) \rightarrow r^{N\phi(N)} \equiv 1 \; mod \; N^2
   2. 计算 $\frac{(1+N)^{m \cdot \phi(N)} -1}{N} \equiv \frac{1+m \cdot \phi(N) N - 1}{N} \equiv m \cdot \phi(N) \; mod \; N$ (参数设置中的3)
   3. 解得 $m \equiv m \cdot \phi(N) \cdot \phi(N)^{-1} \; mod \; N$

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

4. 同态加

   1. 设有两个密文 $c_1 = Enc(m_1,r_1)$，$c_2 = Enc(m_2,r_2)$
   2. 则 $c_1 \cdot c_2 \; mod \; N^2 = (1+N)^{m_1} \cdot r_1^N \cdot (1+N)^{m_2} \cdot r_2^N \; mod \; N^2$ $= (1+N)^{m_1+m_2} \cdot (r_1 r_2)^N \; mod \; N^2 = Enc(m_1+m_2, r_1 r_2)$

5. 标量乘

   1. 设有密文 $c = Enc(m,r)$，标量$k \in \mathbb{Z}$
   2. 则 $c^k \; mod \; N^2 = ((1+N)^m \cdot r^N)^k \; mod \; N^2$ $= (1+N)^{km} \cdot (r^k)^N \; mod \; N^2 = Enc(km, r^k)$

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

配对的一些性质： 乘法同态： e(u1·u2, v) = e(u1, v) · e(u2, v) e(u, v1·v2) = e(u, v1) · e(u, v2) 指数可提到映射外： e(u^a, v) = e(u, v)^a，e(u, v^b) = e(u, v)^b 合起来：$e(u^a, v^b) = e(u, v)^{ab}$

1. 密钥生成

   1. 选择两个大素数$p,q$，计算 $N=pq$
   2. 准备双线性映射 $e: G \times G \rightarrow G_T$，生成元 $g \in G$，生成元 $h \in G_T$，$ind(G) = ind(G_T) = N$
   3. 公钥为 $(n,g,h,e,G,G_T)$，私钥为 $(p,q)$

2. 加密 计算 $c = g^m \cdot h^r$，其中$m \in \mathbb{Z}_N$为明文，$r \in \mathbb{Z}_N$为随机数

3. 解密

   1. 计算 $c^p = (g^m \cdot h^r)^p = (g^p)^m$
   2. 然后对其进行离散对数求解，得到$m$

4. 同态加 $Enc(m_1) \oplus Enc(m_2) = g^m_1 h^r_1 \cdot g^m_2 h^m_2 \cdot h^r$ $= g^{m_1+m_2} \cdot h^{r_1+r_2+r}$ $= Enc(m_1+m_2)$

5. 同态乘

   1. $c_1 = Enc(m_1) = g^m_1 h^r_1$，$c_2 = Enc(m_2) = g^m_2 h^r_2$
   2. denote $g_1 = e(g,g)$，$h_1 = e(g,h)$
   3. $Enc(m_1) \otimes Enc(m_2) = e(g^{m_1} h^{r_1}, g^{m_2} h^{r_2})$ $= 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}$ $= g_1^{m_1 m_2} \cdot h_1^{m_1 r_2 + r_1 m_2} \cdot e(h,h)^{r_1 r_2}$ $= Enc(m_1 \otimes m_2)$