安全多方计算之七：门限密码系统-Toy模板网

这篇具有很好参考价值的文章主要介绍了安全多方计算之七：门限密码系统。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 定义

门限密码系统由分布式密钥生成算法、加密算法、门限解密算法三部分构成，定义如下：

（1）分布式密钥生成：这是一个由参与者共同生成公钥 $y$ 的协议，协议运行结束后，每个参与者将获得一个关于私钥 $x$ 的碎片、对应于该碎片的公钥密钥 $y_i$ ，以及与私钥 $x$ 相对应的公钥 $y$ 。

（2）加密算法：该算法的输入为公钥 $y$ 和待加密的消息 $m$ ，其输出为在公钥 $y$ 下明文 $m$ 对应的密文 $c$ 。

（3）门限解密: 这是一个由任意 $t$ 个参与者 $P_{i_1^{\prime}}, P_{i_2^{\prime}}, \ldots, P_{i_{t}}$ 运行的协议, 对于给定输人密文 $c$ 、 $t$ 个公开验证密钥 $h_{i_1^{\prime}},h_{i_2^{\prime}}, \ldots, h_{i_{t}}$ 以及 $t$ 个碎片 $x_{i_1^{\prime}} x_{i_2^{\prime}}, \ldots, x_{i_{t}}$ , 协议运行结束后将输出密文 $c$ 和对应的明文 $m$ 。

2. 分布式ElGamal加密

系统参数: $p 、 q$ 是大素数, 且 $q / p - 1$ , 满足 $Z_{p}$ 中离散对数问题是难解的, $g$ 是 $Z_{p}^{*}$ 的本原元, $M$ 为明文消息。

$n$ 个参与者 $P_{1}, P_{2}, \ldots, P_{n}$ 分别选取一个随机数 $x_{i} \in Z_{p},i=1,2, \ldots, n$ 计算 $y_{i}= g^{x_{i}} \bmod p$ 并公布。

私钥: $x=\sum_{i=1}^{n} x_{i} \bmod p$ 公钥: $y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p$

加密: 选取随机数 $\in Z_{p}$ , 计算 $E(M)=(\alpha, \beta) = (g^{r} \bmod p, y^{r} M \bmod p)$ 解密: $n$ 个参与者首先分别计算 $\alpha^{x_{i}}\bmod p$ 并公布, 然后共同计算出 $\prod_{i=1}^{n} \alpha^{x^{i}}$ , 从而解出 $M$ : $M=\frac{\beta}{\prod_{i=1}^{n} \alpha^{x^{i}}} \bmod p =\frac{\beta}{\alpha^{\sum_{i=1}^{n} x^{i}}} \bmod p =\frac{\beta}{\alpha^x} \bmod p$

推广

令消息 $M=M_{1} M_{2} \cdots M_{n}$ , $n$ 个参与者 $P_{1}, P_{2}, \ldots, P_{n}$ 分别对消息 $M_{1}, M_{2}, \ldots, M_{n}$ 加密。

系统参数: $p 、 q$ 是大素数, 且 $q / p - 1$ , 满足 $Z_{p}$ 中离散对数问题是难解的, $g$ 是 $Z_{p}^{*}$ 的本原元, $M$ 为明文消息。

利用分布式 ElGamal 加密方式产生私钥/公钥对： $n$ 个参与者分别选取一个随机数 $x_{i}\in Z_{p},i=1,2, \ldots,n$ 计算 $y_{i}=g^{x_{i}} \bmod p$ 并公布。

私钥: $x=\sum_{i=1}^{n} x_{i} \bmod p$ 公钥: $y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p$

加密: $n$ 个参与者分别选取随机数 $r_{1}, r_{2}, \ldots, r_{n} \in Z_{p}$ , 对消息 $M_{i}$ 加密 $E\left(M_{i}\right)= \left(\alpha_i ,\beta_i\right) =(g^{r_{i}} \bmod p, y^{r_{i}} M_{i} \bmod p)$

根据同态性计算 $E(M)=E\left(M_{1} M_{2} \cdots M_{n}\right)= E(M_{1})E(M_{2}) \cdots E(M_{n})= (\alpha, \beta)$ 其中， $\alpha=\prod_{i=1}^{n} \alpha_{i}=g^{\sum_{i=1}^{n} r_{i}} \bmod p,\beta = \prod_{i=1}^{n} \beta_{i}=y^{\sum_{i=1}^{n} r_{i}} M \bmod p$

解密: $n$ 个参与者首先分别计算 $\alpha^{x_{i}} \bmod p$ 并公布, 来共同计算出 $\prod_{i=1}^{n} \alpha^{x_{i}}$ , 从而解出 $M$ : $\quad M=\frac{\beta}{\prod_{i=1}^{n} \alpha^{x_{i}}} \bmod p \frac{\beta}{\alpha^{\sum_{i=1}^{n} x_{i}}} \bmod p=\frac{\beta}{\alpha^x} \bmod p$

3.有可信中心的门限ElGamal密码

(1) 分布式密钥生成

可信中心产生一个密钥 $x$ , 对应的公钥为 $y=g^{x} \bmod p$ ，使用 $(t, n)$ 门限方案在协议参与者中分享私钥 $x$ : 选择随机多项式 $f(u)=a_{t-1} u^{t-1}+\ldots+a_{2} u^{2}+ a_{1} u+a_{0} \in G F(q)[u]$ $P_{i}$ 得到 $x_{i}=f\left(u_{i}\right), i=1,2, \ldots, n$ 。

(2) 加密

选取随机数 $\in Z_{p}$ 计算： $E(M)=(\alpha, \beta)= (g^{k} \bmod p, y^{k} M \bmod p)$

(3) 解密

$P_{i}$ 计算 $\alpha_{i}=\alpha^{x_{i}}$ 并公布, 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择 $t$ 个 $\alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}$ , 则 $M=\frac{\beta}{\alpha^{x}}=\frac{\beta}{\prod_{s=1}^{t} \alpha_{i_s}^{\lambda_{i_s}}}$ $\lambda_{i_s}$ 为 Lagrange 揷值系数, 满足 $x=\lambda_{i_1} x_{i_1}+\cdots+\lambda_{i_t} x_{i_t}$ .

有可信中的门限ElGamal密码不能算严格意义上的门限密码，存在第三方可心中，参加密钥分享的用户必须完全信任分发者，相信其不会对加密数据执行解密操作。

4. 无可信中心的门限ElGamal密码

（1）分布式密钥生成

每个参与者 $P_{i}$ 选择择随机数 $x_{i}$ 作为私钥, 计算 $y_{i}=g^{x_{i}} \bmod p$ , 并公布;
每个参与者收到广播的值后, 计算公钥: $y=\prod_{i=1}^{n} y_{i} \bmod p=g^{\sum_{i=1}^{n} x_{i}} \bmod p = g^x \bmod p$ 每个参与者 $P_{i}$ 以秘密分发者身份执行 Feldman 的 VSS 方案, 在 $P_{1}, P_{2}, \ldots, P_{n}$ 之间分享秘密 $x_{i}$ : 选择 $t - 1$ 次随机多项式, $f_{i}(u)=a_{i, t-1} u^{t-1}+\ldots+a_{i 2} u^{2}+a_{i 1} u+a_{i o} \in G F(q)[u]$ 其中 $x_{i}=a_{i 0}=f_{i}(0)$

$P_{i}$ 计算 $x_{i j}=f_{i}\left(u_{j}\right)$ , 发送给 $P_{j}, j=1,2 \ldots, n$ ; $P_{j}$ 收到其他参与者的值 $x_{i j}=f_{i}\left(u_{j}\right), i=1,2 \ldots, n$ , 计算 $s_{j}=\sum_{i=1}^{n} x_{i j}=\sum_{i=1}^{n} f_{i}\left(u_{j}\right)$ 作为自己最终分享得到的关于私钥 $x$ 的秘密碎片, 其验证公钥为 $y_{j}=g^{s_{j}} \bmod p=g^{\sum_{i=1}^{n} x_{i j}} \bmod p$ (2) 加密

选取随机数 $\in Z_{p}$ ,计算 $E(M)=(\alpha, \beta) =(g^{k} \bmod p, y^{k} M \bmod p)$ (3) 门限解密

每个参与者 $P_{i}$ 计算 $\alpha_{i}=\alpha^{s_{i}}$ , 并公布. 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择 $t$ 个 $\alpha_{i_1}, \alpha_{i_2}, \ldots, \alpha_{i_t}$ , 则 $M=\frac{\beta}{\alpha^{x}}=\frac{\beta}{\prod_{s=1}^{t} \alpha_{i_s}^{\lambda_{i_s}}}$ $\lambda_{i_s}$ 为 Lagrange 揷值系数, 满足 $x=\lambda_{i_1} s_{i_1}+\cdots+\lambda_{i_t} s_{i_t}$ .文章来源地址https://www.toymoban.com/news/detail-805117.html