安全多方计算之七：门限密码系统

admin • 2023-05-21 19:23 • 区块链

门限密码系统

1. 定义
2. 分布式ElGamal加密
- 推广
3.有可信中心的门限ElGamal密码
4. 无可信中心的门限ElGamal密码

1. 定义

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

（1）分布式密钥生成：这是一个由参与者共同生成公钥

$y$ 的协议，协议运行结束后，每个参与者将获得一个关于私钥

$x$ 的碎片、对应于该碎片的公钥密钥

y_i

$y_{i}$ ，以及与私钥

$x$ 相对应的公钥

$y$ 。

（2）加密算法：该算法的输入为公钥

$y$ 和待加密的消息

$m$ ，其输出为在公钥

$y$ 下明文

$m$ 对应的密文

$c$ 。

（3）门限解密: 这是一个由任意

$t$ 个参与者

′

…

P_{i_1^{prime}}, P_{i_2^{prime}}, ldots, P_{i_{t}}

$P_{i_{1'}}, P_{i_{2'}}, \dots, P_{i_{t}}$ 运行的协议, 对于给定输人密文

$c$ 、

$t$ 个公开验证密钥

′

…

h_{i_1^{prime}},h_{i_2^{prime}}, ldots, h_{i_{t}}

$h_{i_{1'}}, h_{i_{2'}}, \dots, h_{i_{t}}$ 以及

$t$ 个碎片

′

…

x_{i_1^{prime}} x_{i_2^{prime}}, ldots, x_{i_{t}}

$x_{i_{1'}} x_{i_{2'}}, \dots, x_{i_{t}}$ , 协议运行结束后将输出密文

$c$ 和对应的明文

$m$ 。

2. 分布式ElGamal加密

系统参数:

、

p、q

$p 、 q$ 是大素数, 且

−

q / p-1

$q / p - 1$ , 满足

Z_{p}

$Z_{p}$ 中离散对数问题是难解的,

$g$ 是

∗

Z_{p}^{*}

$Z_{p *}$ 的本原元,

$M$ 为明文消息。

$n$ 个参与者

…

P_{1}, P_{2}, ldots, P_{n}

$P_{1}, P_{2}, \dots, P_{n}$ 分别选取一个随机数

∈

…

x_{i} in Z_{p},i=1,2, ldots, n

$x_{i} \in Z_{p}, i = 1, 2, \dots, n$ 计算

y_{i}= g^{x_{i}} bmod p

$y_{i} = g^{x_{i}} mod p$ 并公布。

私钥:

∑

x=sum_{i=1}^{n} x_{i} bmod p

$x = i = 1 \sum n x_{i} mod p$ 公钥:

∏

∑

y=prod_{i=1}^{n} y_{i} bmod p=g^{sum_{i=1}^{n} x_{i}} bmod p = g^x bmod p

$y = i = 1 \prod n y_{i} mod p = g^{\sum_{i = 1 n} x_{i}} mod p = g^{x} mod p$

加密: 选取随机数

∈

r in Z_{p}

$r \in Z_{p}$ , 计算

(

)

(

)

(

)

E(M)=(alpha, beta) = (g^{r} bmod p, y^{r} M bmod p)

$E (M) = (α, β) = (g^{r} mod p, y^{r} M mod p)$ 解密:

$n$ 个参与者首先分别计算

alpha^{x_{i}}bmod p

$α^{x_{i}} mod p$ 并公布, 然后共同计算出

∏

prod_{i=1}^{n} alpha^{x^{i}}

$\prod_{i = 1 n} α^{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 = \frac{β}{\prod _{i = 1 n} α ^{x^{i}}} mod p = \frac{β}{α ^{\sum_{i = 1 n} x^{i}}} mod p = \frac{β}{α ^{x}} mod p$

推广

令消息

⋯

M=M_{1} M_{2} cdots M_{n}

$M = M_{1} M_{2} \dots M_{n}$ ,

$n$ 个参与者

…

P_{1}, P_{2}, ldots, P_{n}

$P_{1}, P_{2}, \dots, P_{n}$ 分别对消息

…

M_{1}, M_{2}, ldots, M_{n}

$M_{1}, M_{2}, \dots, M_{n}$ 加密。

系统参数:

、

p、q

$p 、 q$ 是大素数, 且

−

q / p-1

$q / p - 1$ , 满足

Z_{p}

$Z_{p}$ 中离散对数问题是难解的,

$g$ 是

∗

Z_{p}^{*}

$Z_{p *}$ 的本原元,

$M$ 为明文消息。

利用分布式 ElGamal 加密方式产生私钥/公钥对：

$n$ 个参与者分别选取一个随机数

∈

…

x_{i}in Z_{p},i=1,2, ldots,n

$x_{i} \in Z_{p}, i = 1, 2, \dots, n$ 计算

y_{i}=g^{x_{i}} bmod p

$y_{i} = g^{x_{i}} mod p$ 并公布。

私钥:

∑

x=sum_{i=1}^{n} x_{i} bmod p

$x = i = 1 \sum n x_{i} mod p$ 公钥:

∏

∑

y=prod_{i=1}^{n} y_{i} bmod p=g^{sum_{i=1}^{n} x_{i}} bmod p = g^x bmod p

$y = i = 1 \prod n y_{i} mod p = g^{\sum_{i = 1 n} x_{i}} mod p = g^{x} mod p$

加密:

$n$ 个参与者分别选取随机数

…

∈

r_{1}, r_{2}, ldots, r_{n} in Z_{p}

$r_{1}, r_{2}, \dots, r_{n} \in Z_{p}$ , 对消息

M_{i}

$M_{i}$ 加密

(

)

(

)

(

)

Eleft(M_{i}right)= left(alpha_i ,beta_iright) =(g^{r_{i}} bmod p, y^{r_{i}} M_{i} bmod p)

$E (M_{i}) = (α_{i}, β_{i}) = (g^{r_{i}} mod p, y^{r_{i}} M_{i} mod p)$

根据同态性计算

(

)

(

⋯

)

(

)

(

)

⋯

(

)

(

)

E(M)=Eleft(M_{1} M_{2} cdots M_{n}right)= E(M_{1})E(M_{2}) cdots E(M_{n})= (alpha, beta)

$E (M) = E (M_{1} M_{2} \dots M_{n}) = E (M_{1}) E (M_{2}) \dots E (M_{n}) = (α, β)$ 其中，

∏

∑

∏

∑

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

$α = i = 1 \prod n α_{i} = g^{\sum_{i = 1 n} r_{i}} mod p, β = i = 1 \prod n β_{i} = y^{\sum_{i = 1 n} r_{i}} M mod p$

解密:

$n$ 个参与者首先分别计算

alpha^{x_{i}} bmod p

$α^{x_{i}} mod p$ 并公布, 来共同计算出

∏

prod_{i=1}^{n} alpha^{x_{i}}

$\prod_{i = 1 n} α^{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

$M = \frac{β}{\prod _{i = 1 n} α ^{x_{i}}} mod p \frac{β}{α ^{\sum_{i = 1 n} x_{i}}} mod p = \frac{β}{α ^{x}} mod p$

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

(1) 分布式密钥生成

可信中心产生一个密钥

$x$ , 对应的公钥为

y=g^{x} bmod p

$y = g^{x} mod p$ ，使用

(

)

(t, n)

$(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]

$f (u) = a_{t - 1} u^{t - 1} + \dots + a_{2} u^{2} + a_{1} u + a_{0} \in GF (q) [u]$

P_{i}

$P_{i}$ 得到

(

)

…

x_{i}=fleft(u_{i}right), i=1,2, ldots, n

$x_{i} = f (u_{i}), i = 1, 2, \dots, n$ 。

(2) 加密

选取随机数

∈

k in Z_{p}

$k \in Z_{p}$ 计算：

(

)

(

)

(

)

E(M)=(alpha, beta)= (g^{k} bmod p, y^{k} M bmod p)

$E (M) = (α, β) = (g^{k} mod p, y^{k} M mod p)$

(3) 解密

P_{i}

$P_{i}$ 计算

alpha_{i}=alpha^{x_{i}}

$α_{i} = α^{x_{i}}$ 并公布, 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择

$t$ 个

…

alpha_{i_1}, alpha_{i_2}, ldots, alpha_{i_t}

$α_{i_{1}}, α_{i_{2}}, \dots, α_{i_{t}}$ , 则

∏

M=frac{beta}{alpha^{x}}=frac{beta}{prod_{s=1}^{t} alpha_{i_s}^{lambda_{i_s}}}

$M = \frac{β}{α ^{x}} = \frac{β}{\prod _{s = 1 t} α _{i_{s} λ_{i_{s}}}}$

lambda_{i_s}

$λ_{i_{s}}$ 为 Lagrange 揷值系数, 满足

⋯

x=lambda_{i_1} x_{i_1}+cdots+lambda_{i_t} x_{i_t}

$x = λ_{i_{1}} x_{i_{1}} + \dots + λ_{i_{t}} x_{i_{t}}$ .

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

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

（1）分布式密钥生成

每个参与者

P_{i}

$P_{i}$ 选择择随机数

x_{i}

$x_{i}$ 作为私钥, 计算

y_{i}=g^{x_{i}} bmod p

$y_{i} = g^{x_{i}} mod p$ , 并公布;
每个参与者收到广播的值后, 计算公钥:

∏

∑

y=prod_{i=1}^{n} y_{i} bmod p=g^{sum_{i=1}^{n} x_{i}} bmod p = g^x bmod p

$y = i = 1 \prod n y_{i} mod p = g^{\sum_{i = 1 n} x_{i}} mod p = g^{x} mod p$ 每个参与者

P_{i}

$P_{i}$ 以秘密分发者身份执行 Feldman 的 VSS 方案, 在

…

P_{1}, P_{2}, ldots, P_{n}

$P_{1}, P_{2}, \dots, P_{n}$ 之间分享秘密

x_{i}

$x_{i}$ : 选择

−

t-1

$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]

$f_{i} (u) = a_{i, t - 1} u^{t - 1} + \dots + a_{i 2} u^{2} + a_{i 1} u + a_{i o} \in GF (q) [u]$ 其中

(

)

x_{i}=a_{i 0}=f_{i}(0)

$x_{i} = a_{i 0} = f_{i} (0)$

P_{i}

$P_{i}$ 计算

(

)

x_{i j}=f_{i}left(u_{j}right)

$x_{ij} = f_{i} (u_{j})$ , 发送给

…

P_{j}, j=1,2 ldots, n

$P_{j}, j = 1, 2 \dots, n$ ;

P_{j}

$P_{j}$ 收到其他参与者的值

(

)

…

x_{i j}=f_{i}left(u_{j}right), i=1,2 ldots, n

$x_{ij} = f_{i} (u_{j}), i = 1, 2 \dots, n$ , 计算

∑

(

)

s_{j}=sum_{i=1}^{n} x_{i j}=sum_{i=1}^{n} f_{i}left(u_{j}right)

$s_{j} = \sum_{i = 1 n} x_{ij} = \sum_{i = 1 n} f_{i} (u_{j})$ 作为自己最终分享得到的关于私钥

$x$ 的秘密碎片, 其验证公钥为

∑

y_{j}=g^{s_{j}} bmod p=g^{sum_{i=1}^{n} x_{i j}} bmod p

$y_{j} = g^{s_{j}} mod p = g^{\sum_{i = 1 n} x_{ij}} mod p$ (2) 加密

选取随机数

∈

k in Z_{p}

$k \in Z_{p}$ ,计算

(

)

(

)

(

)

E(M)=(alpha, beta) =(g^{k} bmod p, y^{k} M bmod p)

$E (M) = (α, β) = (g^{k} mod p, y^{k} M mod p)$ (3) 门限解密

每个参与者

P_{i}

$P_{i}$ 计算

alpha_{i}=alpha^{s_{i}}

$α_{i} = α^{s_{i}}$ , 并公布. 同时公布一个零知识证明以证明其计算的正确性;
每个协议参与者从公布的计算结果中选择

$t$ 个

…

alpha_{i_1}, alpha_{i_2}, ldots, alpha_{i_t}

$α_{i_{1}}, α_{i_{2}}, \dots, α_{i_{t}}$ , 则

∏

M=frac{beta}{alpha^{x}}=frac{beta}{prod_{s=1}^{t} alpha_{i_s}^{lambda_{i_s}}}

$M = \frac{β}{α ^{x}} = \frac{β}{\prod _{s = 1 t} α _{i_{s} λ_{i_{s}}}}$

lambda_{i_s}

$λ_{i_{s}}$ 为 Lagrange 揷值系数, 满足

⋯

x=lambda_{i_1} s_{i_1}+cdots+lambda_{i_t} s_{i_t}

$x = λ_{i_{1}} s_{i_{1}} + \dots + λ_{i_{t}} s_{i_{t}}$ .

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

# 安全多方计算信息安全区块链安全网络安全

二维码

哈希函数在区块链中的应用

< <上一篇

Solidity之abi.encode各编码方法使用

下一篇>>

搜索内容

安全多方计算之七：门限密码系统

门限密码系统

1. 定义

2. 分布式ElGamal加密

推广

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

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

最新文章

分类

标签云