代理重加密

Proxy Re-encryption(PRE)

假设Sender原本有一个信息是加密给 Alice 的，但是这时 A 不在，A 可以告诉一个代理 Proxy，让其把这个信息重新加密给 Bob，而 Proxy 并不知道这个信息的内容。对于 P 来说，他只知道 RKEY (Re-encryption Key)，而不知道 A 和 B 的私钥。

基于Elgamal的双向代理重加密 - 1

双向代理，既可以从 A 重加密给 B，也可以从 B 重加密给 A。

这个方案是多跳的，既可以经过多次的代理重加密。

Set-up

• 生成安全素数 $p=2q+1$, 在子群 ${\mathbb{Z}}_q$ 中选取生成元 $g$

Keygen

• 选取随机数 $a,b\in {\mathbb{Z}}_q$ 作为 A 和 B 的私钥
• 计算公钥 $p{k}_A=g^{a}modp$ 和 $p{k}_B=g^{b}modp$

Re-keygen

• 入参有两个，既A和B的私钥
• 对于从 A 到 B 的重加密，计算 $r{k}_{A\to B}=b{a}^{-1}modp$
• 同样的，对于从 B 到 A 的重加密，计算 $r{k}_{B\to A}=a{b}^{-1}modp$

Enc

和ElGamal一致

• 选取随机数 $k\in {\mathbb{Z}}_q$
• 对于明文 $m\in {\mathbb{Z}}_p$
• 假设现在要加密给 A
• 计算密文 $C=(C_1,C_2)=(g^{k}modp,m\ast p{k}_A^{k}modp)$
• 既 $C=(g^{k}modp,m\ast g^{ak}modp)$

对于A, Dec和ElGamal一致，故而不在此赘述

Re-Enc

• Proxy 拿到密文 $C=(C_1,C_2)$ 和重加密密钥 $r{k}_{A\to B}$

• 计算新的密文 $C^{\prime }=(C_1^{\prime },C_2^{\prime })=(C_1,C_2^{r{k}_{A\to B}}modp)$

• 既：$(g^{k}modp,m\ast p{k}_A^{k\ast b{a}^{-1}}modp)=(g^{k}modp,m\ast p{k}_B^{k}modp)$

• $(g^a{)}^{k\ast b{a}^{-1}}=g^{bk}$

• 此时显然，B 可以使用自己的私钥 $b$ 来解密新的密文 $C^{\prime }$

基于Elgamal的双向代理重加密 - 2

但是显然，在pratical上，上面这种rkeygen的方式显然是有问题的，故而有下面这种变换

Re-keygen

• 对于 A, 要生成 $r{k}_{A\to B}$
• $rk=s{k}_a/H(p{k}_B^{s{k}_a})modq$, 既 $rk=\frac{a}{H(g^{ba})}$
• 发送$rk$给Proxy

Re-Enc

• 计算 $C^{\prime }=(C_1^{\prime },C_2^{\prime })=(C_1^{rk},C_2)$
• 既： $(g^{k\ast \frac{a}{H(g^{ba})}},m\ast g^{ak})$

Dec

• 对于 B 来说，显然只需知道A的公钥和自己的私钥，即可计算出 $H(p{k}_A^{s{k}_b})=H(g^{ab})$
• 然后计算: $m=C_2/C_1^{H(p{k}_A^{s{k}_b})}modp$ 即可得到消息 $m$

基于配对的单向代理重加密

对于一个传统的Elgamal密文：$(g^r,g^{ar}\ast m)$，我们其实很自然的可以想到将密文转换一下形式，将A的公钥和信息解绑：

$$(g^{ar},g^r\ast m)$$

这样，A仍然可以使用自己的私钥 $a$ 来解密这个密文，只需计算 $(g^{ar}{)}^{\frac{1}{a}}$ 即可

再结合一下配对，就有了如下方案

Set-up

• 选取群 ${\mathbb{Z}}_r,\mathbb{G},{\mathbb{G}}_T$，以及双线性映射 $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$
• 选取生成元 $g\in \mathbb{G}$，生成元 $g_T=e(g,g)$

Keygen

• 对于A，选取随机数 $a\in {\mathbb{Z}}_r$ 作为私钥，计算公钥 $p{k}_A=g^a$
• 对于B，选取随机数 $b\in {\mathbb{Z}}_r$ 作为私钥，计算公钥 $p{k}_B=g^b$

Enc

依旧是先加密给 A

• 选取随机数 $r\in {\mathbb{Z}}_r$
• 计算 $C_1=p{k}_A^r=g^{ar}$
• 计算 $C_2=g_T^r\ast m=e(g,g{)}^r\ast m$, $m\in {\mathbb{G}}_T$
• 发送密文 $C=(C_1,C_2)$

Dec

对于A来说，显然：

• 计算 $g^r=C_1^{\frac{1}{a}}$
• 再计算 $e(g,g^r)=e(g,g{)}^r$ 即可

Re-keygen

• 计算 $r{k}_{A\to B}=g^{b/a}=p{k}_B^{1/a}$

• In pratical: 先计算 $inv=g^{-a}$, 再计算 $r{k}_{A\to B}=in{v}^b$

Re-Enc

• $C_2$ 保持不变
• 计算 $C_1^{\prime }=e(C_1,r{k}_{A\to B})=e(g^{ar},g^{b/a})=e(g,g{)}^{br}$
• 发送新的密文 $C^{\prime }=(C_1^{\prime },C_2)$

Dec2

对于B来说，显然：

• 计算 $e(g,g{)}^r=(C_1^{\prime }{)}^{\frac{1}{b}}=e(g,g{)}^{br\ast \frac{1}{b}}$
• 再计算 $m=C_2/e(g,g{)}^r$ 即可