同态加密

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

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

1. 参数设置:

   1. 选择两个大素数$p,q$，计算 $N=pq$
   2. 计算 $\varphi (N)=(p-1)(q-1)$，$\varphi (N^2)=N\cdot \varphi (N)$，$\because \varphi (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}}^{\mathbb{\ast }}}_{N^2}mod{N}^2\equiv (1+aN)$，易知 $ind(1+N)\in {{\mathbb{Z}}^{\mathbb{\ast }}}_{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\ne 0$，则$(1+N{)}^k=1+kN$，而$(b_2{b}_1^{-1}{)}^N\equiv 1modN$，则$kN\equiv 0modN$恒成立，但是对于模$N^2$而言，如果$k\ne 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)\to f(a_1+a_2,b_1{b}_2)$ 是一个同态
   6. 公钥为 $N$, 私钥为 $\varphi (N)$，既$(p-1)(q-1)$
   7. 记 $L(x)=\frac{x-1}{N}$

2. 加密

   1. 选择随机数$r\in {{\mathbb{Z}}^{\mathbb{\ast }}}_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^{\varphi (N)}mod{N}^2$，则 $c^{\varphi (N)}\equiv ((1+N{)}^m\cdot r^N{)}^{\varphi (N)}mod{N}^2\equiv (1+N{)}^{m\cdot \varphi (N)}mod{N}^2$，$\because gcd(r,N^2)=1\text{and}\varphi (N^2)=N\varphi (N)\to r^{N\varphi (N)}\equiv 1mod{N}^2$
   2. 计算 $\frac{(1+N{)}^{m\cdot \varphi (N)}-1}{N}\equiv \frac{1+m\cdot \varphi (N)N-1}{N}\equiv m\cdot \varphi (N)modN$ (参数设置中的3)
   3. 解得 $m\equiv m\cdot \varphi (N)\cdot \varphi (N{)}^{-1}modN$

原始版本：把 $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\to 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_1^m{h}_1^r\cdot g_2^m{h}_2^m\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_1^m{h}_1^r$，$c_2=Enc(m_2)=g_2^m{h}_2^r$
   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)$