ICP密钥重分享协议

ICP（Internet Computer Protocol）由多个子网（subnet）构成，每个子网上是一个区块链网络。为了实现ICP子网节点动态管理以及子网与子网之间消息认证，Jens Groth提出一种基于BLS签名的非交互分布式密钥生成及密钥重分享协议，主要实现以下功能:

采用BLS签名，公钥加密和零知识证明技术，实现公开可验证的秘密分享协议；
能够在保证子网公钥不变的情况下，实现密钥的再分享，可以有效解决子网中节点动态加入或退出的密钥管理问题。

Shair 密钥分享

密钥分享主要是将秘密 $s$ 创建多个份额： $s_1, \cdots, s_n$ ，其中任w意 $t$ 个可以构建秘密 $s$ , 而 $t-1$ 不会泄露任何 $t$ 的信息。

Shamir 秘密分享：随机选取 $(t-1)$ 次多项式 $a(x)$ , 其中 $a(0)=s$ , $s_1 = a(1), s_2=a(2),\cdots, s_n=a(n)$ . 任意 $t$ 个点可以构造多项式 $a(x)$ , 得到 $s=a(0)$ 。

可以采用Lagrange 插值描述Shamir 秘密分享：给定索引集合 $I=\{i_1, \cdots, i_t\}$ , 对于 $i_j\in I$ , 定义Lagrange多项式：
$L_{i_j}^I(x)=\prod_{i\in I / \{i_j\}} \frac{x-i}{i_j-i} mod\ p$
所有的Lagrange多项式次数都是 $t-1$ , 并满足 $L_{i_j}^I(i_k)=1, k=j$ 和 $L_{i_j}^I(i_k)=0, k\neq j$ . 因此对于 $a(x)$ 上的点 $((i_1, a(i_1)), \cdots, (i_t, a(i_t)))$ ，可以得到：
$a(x)=\sum_{i_j\in I}L_{i_j}^I(x)s_{i_j} mod\ p$
对于秘密分享 $s_{i_1}=a(i_1), \cdots, s_{i_t}=a(i_t)$ , 可以构建 $s=a(0)$ 为：
$s=\sum_{i_j\in I}L_{i_j}^I(0)s_{i_j} mod\ p$
因此 $(n,t)$ 密钥分享方案为：

$\bf{Share}(n,t,s)\rightarrow (s_1, \dots, s_n)$ ：给定 $s\in S$ , 设定 $a_0:= s$ , 选择 $a_1,\cdots, a_{t_1}\leftarrow \mathbb{Z}_p$ , 定义 $a(x) = \sum_{k=0}^{t-1}a_kx^k$ , 得到： $(s_1,\cdots, s_n):=(a(1),\cdots, a(n))$

$\bf{Reconstruct}(I,s_{i_1},\cdots,s_{i_t})$ : 给定 $I$ 中的索引 $1\leq i_i < \cdots < i_t \leq n$ 和分享 $s_{i_1},\cdots, s_{i_t}\in \mathbb{Z}_p$ ，返回:
$s:=\sum_{i_j\in I}L_{i_j}^I(0)s_{i_j} mod\ p$
为了验证分享的正确性，Feldman提出了可验证的秘密分享(VSS)，需要公开参数： $A_0=g^{a_0}, \cdots, A_{t-1}=g^{a_{t-1}}$ , 对于每个分享 $s_i=a(i)$ , 可以验证其正确性：
$g^{s_i}=g^{a(i)}=g^{\sum_{k=0}^{t-1}a_k i^k}=\prod_{k=0}^{t-1}A_k^{i^k}$
但是这种情况下只有接收者可以验证，需要一个交互过程。可以构造公开可验证的秘密分享（PVSS）方案, 使任何人都可以开公验证。

Resharing

对于密钥为 $s$ 的 $(n,t)$ Shamir秘密分享方案可以转化为 $(n', t')$ 的Shamir 秘密分享方案， $s$ 保持不变。对于分享 $(s_1, \cdots, s_n)$ , $\bf Resharing$ 过程如下：

$\bf Reshare(n',t',s_i)$ ：返回 $(s_{i,1},\cdots, s_{i,n})\leftarrow Share(n',t',s_i)$ .

$\bf Combine(I, s_{i_1,j},\cdots,s_{i_t,j})$ : 返回 $s'_j\leftarrow Reconstruct(I,s_{i_1,j},\cdots,s_{i_t,j})$

上式成立的条件在于Lagrange插值的线性性质，即对于 $I\subset [1..n]$ 和 $J\subset [1..n']$ ，可以计算下式：
$\begin{align} s' & = \sum_{j_l\in J}L_{j_l}^J(0)s'_{j_l} \\ &=\sum_{j_l\in J}L_{j_l}^J(0)(\sum_{i_k\in I}L_{i_k}^I(0)s_{i_k,j_l}) \\ &=\sum_{i_k\in I}L_{i_k}^I(0)(\sum_{j_l\in J}L_{j_l}^J(0)s_{i_k,j_l}) \\ &=\sum_{i_k\in I} L_{i_k}^I(0)s_{i_k} \\ &=s \end{align}$

BLS 签名

$\bf Setup$ : 选择双线性对 $e:(G_1, G_2)\rightarrow G_{T}$ , Hash函数： $H_{G_1}:\{0,1\}^*\rightarrow G_1$ .

$\bf KGen$ ：选择 $sk\leftarrow \mathbb{Z}_q$ ，设置 $vk:=g_2^{sk}$ , 返回 $(vk,sk)$

$\bf Sign(sk, m)$ : 计算签名 $\sigma := H_{G_1}(m)^{sk}$

$\bf SigVfy(vk,m,\sigma)$ : 若 $vk\in G_2, \sigma \in G_1$ , 验证：
$e(H_{G_1}(m), vk)=e(\sigma,g_2)$
BLS签名满足惟一性。

门限签名

$(n,t)$ 门限签名主要指对于参与者人数大于或等于 $t$ 时，可以构建一个有效的签名。分布式门限签名方案主要包括几个算法：

$VKVfy(t,vk,shvk_1,\cdots, shvk_n)\rightarrow b$ ：确定性算法，用于验证阈值 $t$ , 验证密钥 $vk$ , 验证密钥share： $shvk_1, \cdots, shvk_n$ 是否有效。

$SKVfy(sk, shvk) \rightarrow \bot$ : 确定性算法，用以验证私钥share $sk$ 和验证公钥share $shvk$ 是否有效。

$SigShare(sk, m)\rightarrow sh$ ：确定性或随机的算法，利用私钥share $sk$ 对消息 $m\in \{0,1\}^*$ 产生签名share: $sh$

$SigShVfy(shvk,m,sh)\rightarrow b$ : 确定性算法，对于验证公钥share $shvk$ 对 $m$ 和签名share $sh$ 进行验证。

$SigShCombine(I, sh_1, \cdots, sh_n)\rightarrow \sigma$ : 确定性算法，对于 $t$ 个签名share: $sh_1, \cdots, sh_t$ , 将其组合成一个签名： $\sigma$

$SigVfy(vk, m, \sigma)\rightarrow b$ : 确定性算法，给定验证公钥 $vk$ , 消息 $m\in \{0,1\}^*$ 和签名 $\sigma$ , 验证签名是否有效。

BLS门限签名

$\bf Setup$ : 设置阶为 $p$ 的群 $\mathbb{G_1}, \mathbb{G_2}, \mathbb{G_T}$ , 双线性对函数 $e:(\mathbb{G_1}\times \mathbb{G_2})\rightarrow \mathbb{G_T}$ ， $g_1, g_2$ 分别为 $\mathbb{G_1}, \mathbb{G_2}$ 的生成元，Hash函数： $H_{\mathbb{G_1}: \{0,1\}^*}\rightarrow \mathbb{G_1}$

$\bf VKVfy(t,vk,shvk_1,\cdots, shvk_n)$ : 验证 $t\in [1..n]$ , $vk, shvk_1, \cdots, shvk_n \in G_2$ . 设定 $shvk_0:=vk$ , $I=\{0,\cdots,t-1\}$ ，对于 $j=t,\cdots,n$ ，验证：
$shvk_j=\prod_{i\in I}shvk_i^{L_i^I(j)}$
若验证通过，返回 $\top$ , 否则返回 $\bot$ .

$\bf SKVfy(sk,shvk)$ : 若 $sk\in \mathbb{Z}_p, shvk=g_2^{sk}$ , 则返回 $\top$ , 否则返回 $\bot$

$\bf SigShare(sk, m)$ : 计算 $sk:=H_{\mathbb{G_1}}^{sk}$

$\bf SigShareVfy(shvk,m,sh)$ : 若 $shvk\in \mathbb{G_2}, sh\in \mathbb{G_1}$ , 验证：
$e(H_{\mathbb{G_1}}(m),shvk)=e(sh,g_2)$
$\bf SigShCombine(I, sh_{i_1},\cdots, sh_{i_t})$ : 解析 $I$ 为多个索引 $i_1<\cdots<i_t$ ， $sh_{i_1},\cdots, sh_{i_t} \in \mathbb{G_1}$ ，得到聚合签名：
$\sigma:=\prod_{i\in I} sh_i^{L_i^I(0)}$
$\bf SigVfy(vk,m,\sigma)$ : 验证 $vk \in G_2, \sigma\in \mathbb{G_1}$ ，验证：
$e(H_{\mathbb{G_1}}(m),vk)=e(\sigma, g_2)$

前向安全的公钥加密方案

本节将介绍CCA安全的多接收者的公钥加密方案，基于双线性对构造，具有前向安全性。

二叉树加密

设二叉树高度为 $\lambda$ , 每个叶子节为一个加密的密文，每个节点都有一个对应的私钥，拥有根节点私钥可以解密所有的密文，拥有中间节点可以解密其对应子树的密文。

BTE(Binary Tree Encryption) 加密方案主要有以下几个算法：

$\bf Setup$ : 参数包括消息空间 $M$ , 二叉树高度 $\lambda$ , 节点的路径为： $\tau_1,\cdots, \tau_l$ , 其中 $l\leq \lambda$ . 即根节点为空路径： $l=0$ , 叶子节点 $l=\lambda$

$\bf KGen\rightarrow (pk, dk)$ : 随机的密钥生成算法，生成二叉树根节点的公钥和私钥。

$\bf KVfy(pk)\rightarrow b$ : 确定性算法，以验证公钥的有效性。

$\bf Derive(dk_{\tau_1,\cdots,\tau_{l-1}}, \tau_l)\rightarrow dk_{\tau_1,\cdots,\tau_{l}}$ : 随机的更新算法，给定节点 $\tau_1,\cdots,\tau_{l-1}$ 的解密密钥和 $\tau_l$ , 得到节点 $\tau_1,\cdots,\tau_{l}$ 的解密密钥，其中 $l\leq \lambda, \tau_l\in \{0,1\}$

$\bf Enc(pk,m,\tau_1,\dots,\tau_{\lambda})$ : 随机的加密算法，给定公钥，加密的消息，和叶子节点，返回加密的密文。

$\bf Dec(dk_{\tau_1,\cdots,\tau_{l}},c)\rightarrow m$ : 确定性的算法，

方案构造

$\bf Setup$ : 对于阶为 $p$ 的双线性对群： $\mathbb{G_1}, \mathbb{G_2},\mathbb{G_T}$ ，消息空间 $\mathcal{M}=[-R..S]\subset \mathbb{Z_p}$ , 消息空间足够小，可通过穷举攻击获取，群元素 $f_0, f_1,\cdots, f_{\lambda}, h\in \mathbb{G_2}$ , 树的高度为 $\lambda$

$\bf KGen \rightarrow (y,dk)$ : 选择 $x\leftarrow \mathbb{Z_p}$ , 计算 $y:=g_1^x$ . 选择 $\rho \leftarrow \mathbb{Z_p}$ , 则 $dk:=(g_1^{\rho},g_2^x, f_0^{\rho},\cdots,f_{\lambda}^{\rho},h^{\rho})$ , 返回： $(y,dk)$

$\bf KVfy(pk)\rightarrow b$ : 若 $pk=y \in \mathbb{G_1}$ , 返加 $\top$ , 否则返回 $\bot$

$\bf Derive(dk_{\tau_1,\cdots,\tau_{l-1}}, \tau_l)\rightarrow dk_{\tau_1,\cdots,\tau_{l}}$ : 给定
$dk_{\tau_1\cdots\tau_{l-1}}=(\tau_1\cdots\tau_{l-1},a,b,d_l,\dots, d_{\lambda},e)\in \{0,1\}^{l-1}\times\mathbb{G_1}\times \mathbb{G_2}^{\lambda-l+2}$
$\tau_l \in \{0,1\}$ , 选择 $\delta \leftarrow \mathbb{Z}_p$ , 返回：
$dk_{\tau_1\cdots\tau_{l}}=(\tau_1\cdots\tau_{l},a\cdot g_1^{\delta},b\cdot d_l^{\tau_l}\cdot (f_0\prod_{i=1}^l f_i^{\tau_i})^{\delta},d_{l+1}\cdot f_{l+1}^{\delta},\dots, d_{\lambda}\cdot f_{\lambda}^{\delta},e\cdot h^{\delta})$
$\bf Enc(y,m,\tau_1\cdots\tau_{\lambda})\rightarrow c$ : 给定 $y\in \mathbb{G_1}, m\in \mathcal{M}, \tau_1\cdots\tau_{\lambda}\in \{0,1\}^{\lambda}$ , 选择 $r,s\leftarrow \mathbb{Z}_p$ , 返回：
$c:=\lgroup y^rg_1^m, g_1^r,g_1^s,(f_0\prod_{i=1}^{\lambda}f_i^{\tau_i})^r h^s \rgroup$
$\bf Dec(dk_{\tau_1\cdots\tau_{\lambda}},c)\rightarrow m$ : 解析
$dk_{\tau_1\cdots\tau_{\lambda}}=(\tau_1\cdots\tau_{\lambda},a,b,e)\in \{0,1\}^{\lambda}\times \mathbb{G_1}\times \mathbb{G_2^2}$
对于 $c=(C,R,S,Z)\in \mathbb{G_1^3}\times \mathbb{G_2}$ , 判定 $e(R,f_0\prod_{i=1}^{\lambda}f_i^{\tau_i})\cdot e(S,h)=e(g_1,Z)$

计算：
$M:=e(C,g_2)\cdot e(R,b)^{-1}\cdot e(a,Z)\cdot e(S,e)^{-1}$
搜索 $m\in \mathcal{M}$ , 使得 $M=e(g_1,g_2)^m$

多接收者二叉树加密

发送者有多个密文给多个接收者，可以直接用单接收者的二叉树加密方案，但是效率比较低，通过复用随机数，可以使加密方案更加高效，多接收者的二叉树加密方案主要有以下算法：

$\bf Setup$ : 指消息密文空间 $\mathcal{M}$ , 高度为 $\lambda$ 的二叉树有 $2^{\lambda}$ 个叶子节点，节点的路径为 $\tau_1\cdots\tau_l, l\leq \lambda$ , 对于叶子节点 $l=\lambda$

$\bf KGen\rightarrow(pk,dk)$ : 随机的密钥生成算法，生成根节点公钥和私钥；

$\bf KVfy(pk)\rightarrow b$ : 确定性算法，验证公钥的有效性；

$\bf Derive(dk_{\tau_1\cdots\tau_{l-1},\tau_l}) \rightarrow dk_{\tau_1\cdots\tau_{l}}$ : 随机的更新算法，给定节点 $\tau_1\cdots\tau_{l-1}$ 的解密私钥，得到节点 $\tau_1\cdots\tau_{l}$ 的解密私钥。

$\bf Enc(pk_1,m_1,\cdots,pk_n,m_n,\tau_1,\cdots,\tau_{\lambda})\rightarrow c$ : 随机的加密方案，给定公钥和消息，得到相应节点的密文。

$\bf Dec(i,dk_{\tau_1\cdots\tau_{\lambda}},c)\rightarrow m$ : 确定性解密算法，给定密文，索引 $i$ , 和解密密钥，得到 $m\in \mathcal{M}$

方案构造

构造基本上和单接收者二叉树加密方案类似，但使用相同的随机数 $r,s$ .

$\bf KGen \rightarrow (y,dk)$ : 选择 $x\leftarrow \mathbb{Z_p}$ , 计算 $y:=g_1^x$ . 生成关于 $x$ 的离散对数零知识证明 $\pi\leftarrow Prove_{dlog}(y;x)$ , 令 $pk:=(y,\pi)$ . 选择 $\rho \leftarrow \mathbb{Z_p}$ , 则 $dk:=(g_1^{\rho},g_2^x, f_0^{\rho},\cdots,f_{\lambda}^{\rho},h^{\rho})$ , 得到： $(pk,dk)$

$\bf KVfy(pk)\rightarrow b$ : 若 $pk=y \in \mathbb{G_1}$ , 返加 $\top$ , 否则返回 $\bot$

$\bf Derive(dk_{\tau_1,\cdots,\tau_{l-1}}, \tau_l)\rightarrow dk_{\tau_1,\cdots,\tau_{l}}$ : 给定
$dk_{\tau_1\cdots\tau_{l-1}}=(\tau_1\cdots\tau_{l-1},a,b,d_l,\dots, d_{\lambda},e)\in \{0,1\}^{l-1}\times\mathbb{G_1}\times \mathbb{G_2}^{\lambda-l+2}$
$\tau_l \in \{0,1\}$ , 选择 $\delta \leftarrow \mathbb{Z}_p$ , 返回：
$dk_{\tau_1\cdots\tau_{l}}=(\tau_1\cdots\tau_{l},a\cdot g_1^{\delta},b\cdot d_l^{\tau_l}\cdot (f_0\prod_{i=1}^l f_i^{\tau_i})^{\delta},d_{l+1}\cdot f_{l+1}^{\delta},\dots, d_{\lambda}\cdot f_{\lambda}^{\delta},e\cdot h^{\delta})$
$\bf Enc(pk_1,m_1,\cdots, pk_n,m_n, \tau_1\cdots\tau_{\lambda})\rightarrow c$ : 给定 $pk_i=(y_i,\pi_i), y_i\in \mathbb{G_1}, m_i\in \mathcal{M}, \tau_1\cdots\tau_{\lambda}\in \{0,1\}^{\lambda}$ , 选择 $r,s\leftarrow \mathbb{Z}_p$ , 返回：
$c:=\lgroup y_1^rg_1^{m_1},\cdots, y_n^rg_1^{m_n}, g_1^r,g_1^s,(f_0\prod_{i=1}^{\lambda}f_i^{\tau_i})^r h^s \rgroup$

$\bf Dec(i, dk_{\tau_1\cdots\tau_{\lambda}},c)\rightarrow m$ : 解析
$dk_{\tau_1\cdots\tau_{\lambda}}=(\tau_1\cdots\tau_{\lambda},a,b,e)\in \{0,1\}^{\lambda}\times \mathbb{G_1}\times \mathbb{G_2^2}$
对于 $c=(C_1,\cdots, C_n,R,S,Z)\in \mathbb{G_1^{n+2}}\times \mathbb{G_2}$ , 判定 $e(R,f_0\prod_{i=1}^{\lambda}f_i^{\tau_i})\cdot e(S,h)=e(g_1,Z)$

对于 $i\in [1..n]$ , 计算：
$M:=e(C_i,g_2)\cdot e(R,b)^{-1}\cdot e(a,Z)\cdot e(S,e)^{-1}$
搜索 $m\in \mathcal{M}$ , 使得 $M=e(g_1,g_2)^m$

扩展明文空间

对于 $m\in \mathbb{Z}_p$ , 难以计算其离散对数 $M=e(g_1,g_2)^m$ . 可以采用chunked encryption 实现，即将 $m$ 写作 $m=\sum_{j=1}^mm_jB^{j-1}$ , 其中 $m_j\in [0..B-1]$ , 限定 $B$ 足够小，可以穷举搜索出来。对于消息空间为 $\mathbb{Z}_p$ 的多接收者二叉树加密方案描述如下：

$\bf Setup$ : 设定正整数 $B$ , $m$ , 使得 $[0..B-1]\subset \mathcal{M}, p< B^m$ , 其中 $\mathcal{M}=[-R..S]$

$\bf KGen'\rightarrow (pk,dk)$ : 得到 $(pk,dk)\leftarrow KGen$

$\bf KVfy'(pk)\rightarrow b$ : 返回 $KVfy(pk)$

$\bf Derive'(dk_{\tau_1\cdots\tau_{l-1},\tau_l}) \rightarrow dk'$ : 得到 $\bf Derive(dk_{\tau_1\cdots\tau_{l-1},\tau_l}) \rightarrow dk_{\tau_1\cdots\tau_{l}}$

$\bf Enc'(pk_1,m_1,\cdots, pk_n,m_n, \tau_1\cdots\tau_{\lambda})\rightarrow c'$ : 给定 $m_1, \cdots, m_n \in \mathbb{Z_p}$ , 分别将其分成小块 $m_{i,j}\in [0..B-1]$ , 因此 $m_i =\sum_{j=1}^m m_{i,j}B^{j-1}$ . 对于 $j=1,\cdots,m$ , 设定 $c_j\leftarrow Enc(pk_1,m_{1,j},\cdots,pk_n,m_{n,j}, \tau_1, \cdots,\tau_{\lambda})$ ，返回 $c':=(c_1,\cdots,c_m)$

$\bf Dec'(i,dk_{\tau_1,\cdots,\tau_{\lambda}},c')\rightarrow m'$ : 解析 $c'=(c_1,\cdots,c_m)$ , 对于 $j=1,\cdots,m$ , 计算 $m_{i,j}\leftarrow Dec(i,dk_{\tau_1\cdots \tau_{\lambda}}, c_j)$ , 最终得到 $m':=\sum_{j=1}^m m_{i,j}B^{j-1}$

注：采用 Baby-step Giant-ste算法可以加快搜索速度。

方案造构

$\bf Enc(pk_1,m_1,\cdots,pk_n,m_n, \tau_1\cdots\tau_n)\rightarrow c = (c_1,c_n)$ : 选择 $r_1,s_1,\cdots,r_m,s_m \leftarrow \mathbb{Z}_p$ , 计算 $c_1:=Enc_1(pk_1,m_1,\cdots,pk_n,m_n; r_1,s_1,\cdots, r_m,s_m)$ 和 $c_2:=Enc_2(\tau_1,\cdots, \tau_{\lambda};r_1,s_1,\cdots,r_m,s_m)$ ，其中：

$Enc_1(pk_1,m_1,\cdots,pk_n,m_n; r_1,s_1,\cdots, r_m,s_m)$ : 首先解析 $pk_1,\cdots, pk_n$ 为 $pk_i=(y_i,\pi_i)$ , $y_i\in \mathbb{G_1}$ . 然后将 $m_1, \cdots, m_n \in \mathbb{Z}_p$ 分成小块, $m_i=\sum_{j=1}^m m_{i,j}B^{j-1}$ , 其中 $m_{i,j}\in [0..B-1]$ .

返回值为： $c_1:=(C_{1,1},\cdots, C_{n,m}, R_1,S_1,\cdots,R_m,S_m)\in \mathbb{G_1}^{n(m+2)}$ , 其中：
$C_{i,j}:=y_i^{r_j}g_1^{m_{i,j}}, R_j:=g_1^{r_j}, S_{j}:=g_1^{s_j}$
$Enc_2(\tau_1,\cdots, \tau_{\lambda};r_1,s_1,\cdots,r_m,s_m)$ : 对于 $\tau_1,\cdots, \tau_{\lambda} \in \{0,1\}$ , 返回 $c_2:=(Z_1, \cdots, Z_m)\in \mathbb{G_2^m}$ , 其中：
$Z_j:=(f_0\prod_{i=1}^{\lambda}f_i^{\tau_i})^{r_j}h^{s_j}$
返回值为： $c:=(c_1, c_2)$

$\bf Dec(i,dk_{\tau_1,\cdots,\tau_{\lambda}},c)\rightarrow m$ : 解析 $c=(c_1,c_2)$ , $c_1=(C_{1,1},\cdots,C_{n,m}, R_1, S_1,\cdots,R_m,S_m) \in \mathbb{G_1}^{n(m+2)}$ , $c_2=(Z_1,\cdots, Z_m)$ . 对于 $j=1,\cdots, m$ , 验证：
$e(g_1,Z_j)=e(R_j,f_0\prod_{i=1}^{\lambda}f_i^{\tau_i})\cdot e(S_j,h)$
对于 $1\leq i\leq n$ , 解析 $dk_{\tau_1,\cdots,\tau_{\lambda}}=(\tau_1\cdots\tau_{\lambda}, a,b,e) \in \{0,1\}^{\lambda}\times \mathbb{G_1}\times \mathbb{G_2^2}$ 。

对于 $j=1,\cdots,m$ , 计算：
$M_j：=e(C_{i,j},g_2)\cdot(R_j,b)^{-1}\cdot e(a,Z_j)\cdot e(S_j,e)^{-1}$
搜索 $m_j\in \mathcal{M}$ , 使得 $M_j=e(g_1, g_2)^{m_j}$ . 最终得到消息 $m:=\sum_{j=1}^m m_jB^{j-1}$

前向安全的CCA公钥加密方案

$\bf Setup$ : 给定消息空间 $\mathcal{M}$ 和最大周期数 $T=2^{\lambda_T}$ .

$\bf KGen\rightarrow (pk,dk_0)$ : 随机的密钥生成算法，生成一个公钥和周期为 $\tau =0$ 的私钥。

$\bf KVfy(pk)\rightarrow b$ : 确定性算法，验证 $pk$ 的准确性。

$\bf KUpd(dk_{\tau}) \rightarrow dk_{\tau+1}$ : 随机的密钥更新算法，给定周期 $\tau$ 的解密密钥，返回周期为 $\tau +1$ 的解密密钥。若 $\tau + 1 = T$ ，返回 $\bot$ .

$\bf Enc(pk_1, m_1, \cdots, pk_n,m_n, \tau)\rightarrow c$ : 随机的加密算法，给定 $n$ 个公钥，相应的消息及周期，返回一个密文。

$\bf Dec(i, dk_{\tau'},c,\tau)\rightarrow m$ : 确定性解密算法，给定解密密钥 $dk_{\tau}$ ，索引为 $i$ , 周期为 $\tau$ , 返回明文 $m \in \mathcal{M}$ . 若 $\tau \notin [\tau'..T-1]$

方案构造

本部分将构造一个多接收者的CCA安全的加密方案，明文空间为 $\mathbb{Z}_p$ ，

$\bf Setup$ : 明文消息空间为 $\mathbb{Z}_P$ , 最大周期数为 $T=2^{\lambda_T}$ , hash函数: $H:\{0,1\}^*\rightarrow \{0,1\}^{\lambda_H}$

初始设置包括群元素 $f_0, \cdots, f_{\lambda}, h\in \mathbb{G}_2$ , 其中 $\lambda = \lambda_T + \lambda_H$ .

$\bf KGen\rightarrow (pk, dk_0)$ : 选择 $x \leftarrow \mathbb{Z}_p$ , 计算 $y:=g_1^x$ , 生成证明 $\pi \leftarrow Prove_{dlog}(y,x)$ , 设定公钥为 $pk:=(x, \pi)$ , 选择随机数 $\rho = \mathbb{Z}_p$ ， $dk:= (g_1^{\rho}, g_2^x, f_0^{\rho}, f_1^{\rho},\cdots,f_{\lambda}^{\rho}, h^{\rho})$ ，令 $dk_0:=(0, \{dk\})$ ，返回 $(pk, dk_0)$

$\bf KVfy(pk) \rightarrow b$ ：解析公钥为 $pk=(y, \pi)$ , 若 $y \in \mathbb{G}_1$ , 且 $PVfy_{dlog}(y, \pi)$ 验证通过，返回 $\top$ , 否则 $\bot$

$\bf KUpd(dk_{\tau}, \tau') \rightarrow dk_{\tau'}$ : 若 $\tau'\notin [\tau + 1\cdots T-1]$ . 解析 $\tau = \tau_1\cdots\tau_{\lambda_T}$ , $dk_{\tau}=(\tau, \{dk_{\tau_1\cdots\tau_l}\}_{\tau_1\cdots\tau_l \in \mathcal{T}_{\tau} })$ ，其中 $\mathcal{T}_{\tau}$ 是涵盖 $[\tau\cdots T-1]$ 所有叶子节点的最小子集， $\mathcal{T}_{\tau'}$ 是涵盖 $[\tau'\cdots T-1]$ 所有叶子节点的最小子集，对于所有的 $\tau_1 \cdots \tau_l \in \mathcal{T}_{\tau'} / \mathcal{T}_{\tau}$ 得到子密钥 $dk_{\tau_1\cdots\tau_l}$ ,得到：
$dk_{\tau'}=(\tau',\{dk_{\tau_l\cdots\tau_l}\}_{\tau_1\cdots\tau_l}\in \mathcal{T}_{\tau'})$
$\bf Enc(pk_1,m_1,\cdots,pk_n,m_n,\tau)\rightarrow c$ : 分析 $\tau = \tau_1\cdots\tau_{\lambda_T}$ 的二进制形式，选择 $r_1, s_1, \cdots, r_m, s_m \leftarrow \mathbb{Z}_p$ ，计算：
$c_1 := Enc_1(pk_1,m_1,\cdots, pk_n, m_n; r_1,s_1,\cdots, r_m, s_m)$
计算 $\tau_{\lambda_{T}+1}\cdots \tau_{\lambda} := H(pk_1,m_1,\cdots,pk_n,m_n; r_1,s_1,\cdots, r_m, s_m)$
$c_2:=Enc_2(\tau_1,\cdots,\tau_{\lambda};r_1,s_1,\cdots,r_m,s_m)$
返回加密的密文： $c:=(c_1,c_2)$

$\bf Dec(i, dk_{\tau'},c,\tau)\rightarrow m$ : 解析 $c=(c_1, c_2)$ , $\tau = \tau_1\cdots\tau_{\lambda_T}$ , 计算 $\tau_{\lambda_T +1}\cdots\tau_{\lambda} := H(pk_1,\cdots, pk_n,c_1,\tau)$ ，假定 $\tau \in [\tau'\cdots T-1]$ , 得到 $dk_{\tau_1\cdots\tau_{\lambda}}$ , 返回 $Dec(i, dk_{\tau_1\cdots\tau_{\lambda}},c)$

非交互式零知识证明

离散对数证明

$\bf Setup$ : 设定群 $\mathbb{G_1}$ , 素数阶为 $p$ , 生成元为 $g_1$ . Oracle $\mathcal{O}$ 采用Hash函数 $H_{\mathbb{Z}_p}$ 实现。

$\bf Instance$ : $y\in \mathbb{G}_1$

$\bf Statement$ : 证明 $y$ 的离散对数

$\bf Witness$ : $x \in \mathbb{Z}_p$ , 使得 $y = g_1^x$

$\bf Prove^{\mathcal{O}}(instance, witness)$ :

选择 $r\leftarrow \mathbb{Z}_p$ , 计算 $a:= g_1^r$ ;
计算 $e:= \mathcal{O}(y,a)$
计算 $z:=ex+ r\ mod\ p$
生成的证明为： $\pi = (a, z)\in \mathbb{G_1} \times \mathbb{Z}_p$

$\bf PVfy^{\mathcal{O}}(instance, \pi)$ :

验证 $y, a\in \mathbb{G}_1$ , 域元素 $z \in \mathbb{Z}_p$
计算 $e:= \mathcal{O}(y, a)$
若 $y^e a = g_1^z$ 验证通过，则返回 $\top$ ，否则 $\bot$

密钥分享证明

$\bf Setup$ : 设定群 $\mathbb{G_1}, \mathbb{G_2},\mathbb{G}_T$ , 阶为 $p$ , 双线性对： $e:\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ , 生成元为： $g_1, g_2, e(g_1,g_2)$ . 群元素 $h \in \mathbb{G}_2/ \{1\}$ . Oracle $\mathcal{O}$ 采用 Hash函数 $H_{\mathbb{Z}_p}$ .

$\bf Instance$ : $y_1, \cdots, y_n \in \mathbb{G}_1$ ， $A_0 = g_2^{a_0},\cdots,A_{t-1}=g_2^{a_{t-1}}$

                                   $R=g_1^r, C_1 = y_1^rg_1^{s_1},\cdots, C_n = y_n^r\cdot g_1^{s_n}$

$\bf Statement$ : 实例中离散对数满足： $i=1,\cdots,n$ 满足下述关系：
$s_i = \sum_{k=0}^{t-1} a_k i^k mod\ p$
$\bf Witness$ : 对于 $r, s_1, \cdots, s_n \in \mathbb{Z}_p$ 满足 $s_i = a(i)$ , 其中 $a(i)=\sum_{k=0}^{t-1} a_k i^k\ mod\ p$

$\bf Prove^{\mathcal{O}}(instance,witness)$ :

计算 $x:= \mathcal{O}(intance)$
生成随机数： $\alpha,\rho \leftarrow \mathbb{Z}_p$ , 计算：
$F= g_1^{\rho}, A = g_2^{\alpha}, Y=(\prod_{i=1}^n y_i^{x^i})^{\rho} \cdot g_1^{\alpha}$
计算 $x':= \mathcal{O}(x,F, A， Y)$

计算：

       $z_r = rx' + \rho\ mod\  p$ ,    $z_a = x'\sum_{i=1}^n s_i x^i + \alpha\ mod\ p $

生成的证明为： $\pi = (F,A,Y,z_r, z_a) \in \mathbb{G}_1 \times \mathbb{G}_2 \times \mathbb{G}_1 \times \mathbb{Z}_p^2$

$\bf PVfy^{\mathcal{O}}(intance, \pi)$ :

验证 $y_1,\dots, y_n, R，C_1, \cdots,C_n, F, Y \in \mathbb{G}_1, A_0, \cdots, A_{t-1}, A\in \mathbb{G}_2$ , 域元素 $z_r, z_a \in \mathbb{Z}_p$
计算 $x:= \mathcal{O}(instance), x'= \mathcal{O}(x,F,A,Y)$
验证：
$R^{x'} \cdot F =g_1^{z_r},\ \ \ (\prod_{k=0}^{t-1} A_k^{\sum_{i=1}^ni^kx^i})^{x'}\cdot A = g_2^{z_a}$
和
$(\prod_{i=1}^n C_i^{x^i})^{x'}\cdot Y = \prod_{i=1}^n(y_i^{x^i})^{z_r} \cdot g_1^{z_a}$
若验证通过返回 $\top$ , 否则返回 $\bot$

Chunking 零知识证明

$\bf Setup$ : 指定参数为阶为 $p$ , 生成元 $g_1$ 的群 $\mathbb{G}_1$ , 参数包括安全参数 $\lambda$ , 正整数 $n,m,l, B, E, S, Z$ , 使得 $E= 2^{\lceil \lambda/l\rceil}, S = nm(B-1)(E-1), 2lS\leq Z < p2^{-\lambda/l}$

$\bf Instance$ : $\mathbb{G}_1$ 中的群元素有：
$y_1,\cdots, y_n, R_1 = g_1^{r_1}, \cdots, R_m = g_1^{r_m}, C_{1,1}=y_1^{r_1}g_1^{s_{1,1}},\cdots, C_{n,m} = y_n^{r_m}g_1^{s_{n,m}}$
$\bf Statement$ : 实例的离散对数满足 $i=1,\cdots, n, j=1,\cdots,m$ , 使得 $\bigtriangleup_{i,j} \in [1;E-1]$ , 使得：
$\bigtriangleup_{i,j}s_{i,j} \in [1-Z..Z-1]$
$\bf Witness$ : 离散对数 $r_1,\cdots, r_m, s_{1,1},\cdots,s_{n,m}\in \mathbb{Z}_p$ 满足约束 $s_{i,j}\in [0..B-1]$

$\bf Prove^{\mathcal{O}}(instance,witness)$ :

选择 $y_0 \leftarrow \mathbb{G}_1, \sigma_1,\cdots, \sigma_l \leftarrow [-S; Z-1], \beta_1, \cdots, \beta_l \leftarrow \mathbb{Z}_p$
计算
$B_1 = g_1^{B_1}, \ C_1 = y_0^{\beta_1} g_1^{\sigma_1}, \cdots, B_l = g_1^{\beta_l}, C_l = y_0^{\beta_l}g_1^{\sigma_l}$
查询 $\mathcal{O}(instance, y_0, B_1, C_1,\cdots,B_l, C_l;\lambda_e)$ , 解析输出为： $e_{1,1,1},\cdots,e_{m,n,l}\in [0..E-1]$
计算：

$z_{s,1}= \sum_{i=1}^n\sum_{j=1}^me_{i,j,1}s_{i,j} + \sigma_1, \cdots, z_{s,l}= \sum_{i=1}^n\sum_{j=1}^me_{i,j,l}s_{i,j} +\sigma_l$

检查其在 $[0..Z-1]$ 范围内。

计算：
$D_0 = g_1^{\delta_0}, \cdots, D_n = g_1^{\delta_n}, Y = \prod_{i=0}^n y_i^{\delta_i}$
查询 $\mathcal{O}(e_{1,1,1},\cdots,e_{n,m,l}, z_{s,1},\cdots,z_{s,l}, D_0，\cdots, D_n, Y)$ ，得到 $x \in \{0,1\}^{\lambda}$
计算

$z_{r,1}=\sum_{j=1}^m\sum_{k=1}^l e_{1,j,k} r_jx^k + \delta_1, \cdots, z_{r,n} = \sum_{j=1}^m\sum_{k=1}^le_{n,j,k}r_jx^k+\delta_n, z_{\beta} = \sum_{k=1}^l\beta_kx^k+\delta_0$

生成的证明为： $\pi = (y_0, B_1,C_1, \cdots, B_l,C_l, D_0,\cdots, D_n, z_{s,1},\cdots,z_{s,l},z_{r,1},\cdots, z_{r,n}, z_\beta)$

$\bf PVfy^{\mathcal{O}}(instance, \pi)$ :

验证实例属于 $\mathbb{G_1}^{n+m+nm}$ , 解析 $\pi = (y_0,\cdots, z_\beta) \in \mathbb{G}_1^{2l+n+2} \times \mathbb{Z}_p^{l+n+1}$
验证 $z_{s,1},\cdots, z_{s,l}\in [0..Z-1]$
计算 $e_{1，1，1}，\cdots, e_{n,m,l}$ , 查询 $\mathcal{O}$ 得到 $x$
验证：

$\prod_{j=1}^m R_j^{\sum_{k=1}^l e_{1,j,,k}x^k} \cdot D_1 = g_1^{z_{r,1}}, \cdots, \prod_{j=1}^m R_j^{\sum_{k=1}^l e_{n,j,k}x^k}\cdot D_n = g_1^{z_{r,n}}, \prod_{k=1}^lB_k^{x^k}\cdot D_0 = g_1^{z_{\beta}}$
```
和
```

$\prod_{k=1}^l(\prod_{i=1}^n\prod_{j=1}^m C_{i,j}^{e{i,j,k}})^{x^k} \cdot \prod_{k=1}^lC_k^{x^k}\cdot Y = \prod_{i=1}^ny_i^{z_{r,i}}\cdot y_0^{z_\beta}\cdot g_1^{\sum_{k=1}^l z_{s,k}x^k}$

前向安全的分布式密钥生成和密钥重分享协议

$\bf Setup$ : 参数索引范围为 $[1..N]$ , 最大周期数为： $T$

$\bf KGen \rightarrow (pk, dk_0)$ : 随机化的密钥生成算法，得到一个公钥，和一个私钥，初始周期为 $\tau =0$

$\bf KVfy(pk)\rightarrow b$ : 确定性算法，验证公钥的有效性。

$\bf KUpd(dk_{\tau})\rightarrow dk_{\tau +1}$ : 对于周期为 $\tau$ 的解密密钥，升级到周期 $\tau + 1$ .

$\bf Deal(?sk, t, pk_1,\cdots, pk_n，\tau)\rightarrow d$ : 随机的 dealing 算法，给定门限值，和多个公钥 $n\leq N$ , 生成给定周期的 dealing. 私钥sk 为可选的输入。

$\bf DVfy(?shvk,t,pk_1,\cdots, pk_n, \tau, d)\rightarrow b$ : 确定性 dealing 验证算法，若dealing 有效，则返回 $\top$ , 否则返回 $\bot$ , $shvk$ 为可选的验证公钥。

$\bf VKCombine(t,n,I,d_1,\cdots, d_l)\rightarrow (vk, shvk_1, \cdots, shvk_n)$ : 确定性算法，给定索引 $I$ , 不同的索 $i_1< \cdots < i_l$ ，返回验证公钥 $vk$ , 秘密分享的验证公钥 $shvk_1, \cdots, shvk_n$

$\bf VKVfy（t, vk, shvk_1,\cdots, shvk_n）\rightarrow b$ : 确定性算法，给定门限 $t$ 和验证密钥，若有效，则返加 $\bot$

$\bf SKRetrieve(j, dk_{\tau'}, I, d_1,\cdots, d_l, \tau) \rightarrow sk$ ：确定性算法，给定解密密钥，大小于 $l$ 的集合 $I$ , 周期 $\tau$ 的 $dealings$ : $d_1, \cdots, d_l$ , 返回 $j$ 的私钥。