# SM2协同签名的隐私外包计算(Outsourcing Computation)
参与方：
- 协同签名服务器
- 协同签名客户端
- **（协同签名客户端）外包服务器**

其中，协同签名服务端与常规的一致，并且它并不能感知协同签名的客户端是否使用了外包计算。

外包计算一般应用在协同签名客户端为弱计算环境下，如小程序，浏览器等-当然也可以是APP或PC端。它将协同签名客户端的计算外包给外包服务器。并且外包服务器不能获取所计算的内容的信息。

## Paillier加密
Paillier密钥为：
- $p$,$q$为素数，$n=pq$.
- $\lambda = \mathrm{LCM}(p-1, q-1)$.

公钥：$n$.

私钥：$n, \lambda$


记$\mathrm{Enc}，\mathrm{Dec}$为Paillier加密。满足加同态：
若
$$
c_1 = Enc(m_1),\\
c_2 = Enc(m_2)
$$
则
$$
c_1\cdot c_2 = Enc(m_1 + m_2 \mod n^2)
$$


## 签名密钥生成
> 原始的协同签名服务端和客户端密钥分别为$d_s,d_c$,并且和实际密钥$d$满足
> $$d_s*d_c*(1+d) = 1 \mod N$$

- 客户端
选取
$$
d_{c1} \leftarrow [1, N-1],
$$
计算$A_1= \mathrm{Enc}(d_{c1}),A_2 =\mathrm{Enc}(d_{c1}^{-1})$,并发送$A_1,A_2$给外包服务器；
- 外包服务器
选取
$$
d_{c2} \leftarrow [1, N-1],
$$
计算
$$
\begin{array}{rcl}
P &=& [d_{c2}^{-1}]G \\
B_1 &=& \mathrm{Enc}(d_{c1})^{d_{c2}}= \mathrm{Enc}(d_{c1}d_{c2}) = \mathrm{Enc}(d_{c})\\
B_2&=&\mathrm{Enc}(d_{c2}^{-1})^{d_{c2}^{-1}} = \mathrm{Enc}(d_{c1}^{-1}d_{c2}^{-1})=\mathrm{Enc}(d_{c}^{-1})
\end{array}
$$

外包服务器保存$B_1, B_2$, 把$P$，发给客户端
- 客户端
计算
$$
Q = [d_{c1}^{-1}]P = [d_{c}^{-1}]G,
$$
发送$Q$给协同签名服务端。

- 协同签名服务器计算$R = [d_s^{-1}]G$
- 客户端计算公钥$S = [d_{c1}^{-1}]R= [d_{c1}^{-1}d_s^{-1}]G$, 把$(R,S)$发给外包服务器
- 外包服务器计算$T_1 = [d_{c2}^{-1}]R, T_2 = [d_{c2}^{-1}]S$, $PK =T_2-G=[d_{c2}^{-1}d_{c1}^{-1}d_s^{-1}-1]G = [d]G$, 把$T_1, PK$
- 客户端计算$PK' = [d_{c1}^{-1}]T_1-G$, 并与外包服务器发送的$PK$对比若一致则公钥生成成功。 

```mermaid
sequenceDiagram;
客户端 ->> 外包服务器: A1,A2;
外包服务器 ->> 外包服务器: 计算B1,B2并保存;
外包服务器 ->> 客户端: P;
客户端  ->> 协同签名服务器: Q;
协同签名服务器->>客户端: R;
客户端 ->> 外包服务器: R,S;
外包服务器 ->> 客户端: T1, PK
客户端 ->> 客户端: PK;
```

> 1.上述流程中，客户端部分密钥$d_c$未出现，并且客户端参与生成。
> 2.客户端与外包服务间应使用HTTPS/TLCP连接防止中间人攻击。
> 3.密钥生成后可以通过计算签名验证密钥生成成功。
> 4.一种简单的实现是客户端先按常规生成dc，把加密后的dc注册并放到OS上。



## 签名流程
**前提条件：**

- 协同签名服务器: $d_s$
- 协同签名客户端: Paillier私钥$\lambda$
- 外包服务器: Paillier公钥$n$
  

**签名流程:**

- 客户端
计算e，向外包服务器发起请求
- 外包服务器
选择随机数$k_1'$, 计算$P' = [k_1']G$，发送$P'$给客户端
- 客户端
选择随机数$k_1''$, 计算$P = [k_1'']P'=[k_1'k_1'']G$. 
将$(e,P)$发送给协同签名服务器.
> $k_1''$可以取1
- 协同签名服务器
选择随机数$k_2,k_3$并计算
$$
\begin{array}{rcl}
Q &=& [k_2]P + [k_3]G\\
r &=& e + x_Q\\
s_1 &=& d_sk_2\\
s_2 &=& (k_3 + r)d_s
\end{array}
$$
将$r,s_1,s_2$发送给客户端
- 客户端
将$r,k_1''s_1,s_2$发送给外包服务器
- 外包服务器
计算
$$
\begin{array}{rcl}
s' &=& k_1'k_1''s_1+s_2 \mod N\\
u &=& Enc(d_c)^{s'} = Enc(d_cs')
\end{array}
$$
选择随机数$k_4 \in [1,N-1]$,计算
$$
\begin{array}{rcl}
v &=& Enc(k_4N)\\
w &=& uv = Enc(d_cs' + k_4N)
\end{array}
$$
将$w$发给客户端
- 客户端
计算
$$
s = Dec(w) - r  \equiv d_cs' - r\mod N
$$
输出签名值$(r,s)$.
```mermaid
sequenceDiagram;
客户端 ->> 外包服务器: 请求;
外包服务器 ->> 外包服务器: k1',P';
外包服务器 ->> 客户端: P';
客户端 ->> 客户端: k1'', P=[k1'']P';
客户端  ->> 协同签名服务器: (e,P);
协同签名服务器->>协同签名服务器: 计算r,s1,s2 ;
协同签名服务器 ->> 客户端: (r,s1,s2)
客户端 ->> 外包服务器: (r,k1s1,s2);
外包服务器 ->> 客户端: w = Enc(·);
客户端 ->> 客户端: 解密w;
客户端 ->> 客户端: 输出签名(r,s);
```

## 使用签名密钥解密加密密钥保护结构
**前提条件：**

- 协同签名客户端外包服务器持有Enc($d_c^{-1}$).


> SM2密文$(C_1,C_3,C_2)$,解密只需要协同计算$[d]C_1 = [d_s^{-1}]\cdot[d_c^{-1}]C_1 - C1$。

**解密流程:**

- 客户端
把$C_1$发送给外包服务器；
- 外包服务器
选取随机数$k_1, k_2 \in [1, N-1]$, 计算
$$
E = \mathrm{Enc}(d_c^{-1})^{k_1} \cdot \mathrm{Enc}(k_2N) = \mathrm{Enc}(d_c^{-1}k_1+k_2N)
$$
和
$$
F = [k_1^{-1}]C_1
$$
把$E,F$发给客户端。
- 客户端
计算
$$
\begin{array}{rcl}
e &=& \mathrm{Dec}(E) \mod N \equiv d_c^{-1}k_1\\
H &=& [e]F = [d_c^{-1}]C_1
\end{array}
$$
- 客户端
发送$H$给协同签名服务器
- 协同签名服务器
计算
$$
I = [d_s^{-1}]H = [d_s^{-1}d_c^{-1}]G
$$
发送$I$给客户端
- 客户端
计算
$$
J=[d_s^{-1}]\cdot[d_c^{-1}]C_1 - C_1 = [d]C_1
$$
- 客户端
解密得到加密密钥$d_e$(加密密钥明文)。选取随机数$k\in [1,N-1]$,计算
$$
K = \mathrm{Enc}(d_e)\\
L = K^k = \mathrm{Enc}(d_ek)
$$
$d_{es} = k^{-1} \mod N$. 并将$d_{es}$作为协同签名服务端密钥分量发给服务端，$L$为加密的协同签名客户端密钥分量发给外包服务器。

```mermaid
sequenceDiagram;
客户端 ->> 外包服务器: C1;
外包服务器 ->> 外包服务器: 计算E,F;
外包服务器 ->> 客户端: E,F;
客户端 ->> 客户端: e = Dec(E), H;
客户端  ->> 协同签名服务器: H;
协同签名服务器->>协同签名服务器: 计算I;
协同签名服务器 ->> 客户端: I
客户端 ->> 客户端:计算并得到加密密钥明文;
客户端 ->> 客户端:拆分加密密钥;
客户端 ->> 协同签名服务器: 服务端部分加密密钥;
客户端 ->> 外包服务器: 加密的客户端部分密钥
```
## 协同解密
略，此部分类似使用签名密钥解密流程

## 口令派生Paillier密钥
口令派生出1024bit的字节数组，并转为整数$p'$. $p$为大于$p'$的(满足安全条件)的最小素数。
同样派生出$q$（不同的迭代次数）并根据服务端公钥验证。