admin管理员组文章数量:1528307
1. commitment scheme
commitment scheme是密码学中必不可少的primitive,存在2个角色——committer和receiver:
committer 将a value put in a locked box,将该locked box给receiver,因此除committer外无人知道具体的value值(即hiding属性),由于locked box已在receiver手上,该committer不能open出2个不同的value值for the same commitment(即binding属性)。
同时,可以在不泄露具体value值的情况下,证明relations between committed values。
通常,a non-interactive commitment scheme中包含3个基本算法:
- S e t u p ( 1 k ) Setup(1^k) Setup(1k):输入为security parameter k k k,输出为系统需要的public parameters。
- C o m m i t ( m , r ) Commit(m,r) Commit(m,r):输入为待commit的message m m m,随机值 r r r,输出为commitment c c c和an opening value d d d。
- V e r i f y ( c , m , d ) Verify(c,m,d) Verify(c,m,d):输入为commitment c c c、message m m m 和 an opening value d d d,输出为yes or no,即表示验证是否通过。
其中,commitment c c c is sent to the receiver at the commit time,而opening value d d d is sent together with the message m m m at the opening time to allow verification。
- hiding 属性:是指commitment c c c不会泄露 m m m (either perfect secrecy, or computational indistinguishability)。
- binding 属性:是指no adversary (either powerful or computationally bounded) can generate c , m ≠ m ′ , d , d ′ c,m\neq m',d,d' c,m=m′,d,d′使得 V e r i f y ( c , m , d ) Verify(c,m,d) Verify(c,m,d)和 V e r i f y ( c , m ′ , d ′ ) Verify(c,m',d') Verify(c,m′,d′)都成立。
接下来将介绍2个简单的commitment schemes,二者具有互补特性,可结合使用形成powerful commitment scheme:
- Pedersen Commitment
- EIGamal Commitment
2. Pedersen commitment
考虑
G
=
<
g
>
\mathbb{G}=<g>
G=<g> 为a cyclic group of prime order
q
q
q,2个随机generators
g
,
h
∈
G
g,h\in\mathbb{G}
g,h∈G。
Pedersen commitment允许commit to scalar elements from
Z
q
\mathbb{Z}_q
Zq:
-
Commitment:
为了commit to a scalar m ∈ Z q m\in\mathbb{Z}_q m∈Zq,one 选择a random r ← Z q r \leftarrow \mathbb{Z}_q r←Zq,设置 c ← g m h r c\leftarrow g^mh^r c←gmhr,相应的opening value为 r r r。 -
Opening:
为了open a commitment c ∈ G c\in\mathbb{G} c∈G,one reveal the pair ( m , r ) (m,r) (m,r)。若 c = g m h r c=g^mh^r c=gmhr成立,则receiver accepts the opening to m m m,否则拒绝。
Q-1: Pedersen commitment具有perfectly hiding属性——even a powerful adversary cannot have any idea about the committed value。
Q-2: Pedersen commitment具有computationally binding属性——除非one can break a problem (to be specified), 否则 adversary can not open a commitment in two different ways。
Q-3: Pedersen commitment 是equivocal 模棱两可的:simulator 使用a trapdoor (仅simulator本人知道) 来生成 parameters
(
g
,
h
)
(g,h)
(g,h)时(与Setup
算法无法区分),该simulator可生成a commitment
c
∈
G
c\in\mathbb{G}
c∈G,然后open成任意的值。【其实应该就是指若simulator知道
g
a
=
h
g^a=h
ga=h,其中
a
a
a为trapdoor,则该simulator可生成a commitment
c
c
c,并将其open为任意值。】
Q-4: 何时可在a security proof中使用Pedersen commitment的binding属性 和 equivocality 模棱两可?
Q-5: 何时可在a security proof中使用Pedersen commitment的hiding属性 和 equivocality 模棱两可?
3. EIGamal commitment
考虑
G
=
<
g
>
\mathbb{G}=<g>
G=<g> 为a cyclic group of prime order
q
q
q,2个随机generators
g
,
h
∈
G
g,h\in\mathbb{G}
g,h∈G。
EIGamal commitment允许commit to group elements from
G
\mathbb{G}
G:
- Commitment:
为了commit to a group element M ∈ G M\in\mathbb{G} M∈G,one 选择a random r ← Z q r\leftarrow \mathbb{Z}_q r←Zq,设置 c ← ( c 0 = g r , c 1 = M h r ) c\leftarrow (c_0=g^r,c_1=Mh^r) c←(c0=gr,c1=Mhr),相应的opening value为 r r r。 - Opening:
为了open a commitment c ∈ G c\in\mathbb{G} c∈G,one reveal the pair ( M , r ) (M,r) (M,r)。若 c = ( g r , M h r ) c=(g^r, Mh^r) c=(gr,Mhr)成立,则receiver accepts the opening to M M M,否则拒绝。
Q-6: EIGamal commitment具有perfectly binding属性——even a powerful adversary cannot open a commitment in two different ways。【对于group order
q
q
q,若存在
r
≠
r
′
m
o
d
q
r\neq r'\mod q
r=r′modq,则
g
r
≠
g
r
′
g^r\neq g^{r'}
gr=gr′,对应的
x
=
r
′
−
r
m
o
d
q
x=r'-r\mod q
x=r′−rmodq,
x
x
x为non-zero modulo
q
q
q。因此有
g
r
′
=
g
r
+
x
=
g
r
⋅
g
x
g^{r'}=g^{r+x}=g^r\cdot g^x
gr′=gr+x=gr⋅gx,若
x
x
x为not zero or a multiple of the group order,则不存在
r
≠
r
′
m
o
d
q
r\neq r'\mod q
r=r′modq,使得
g
r
=
g
r
′
g^r=g^{r'}
gr=gr′成立。因此,EIGamal具有perfectly binding属性。】
Q-7: EIGamal commitment具有computationally hiding属性——除非one can break a problem (to be specified), 否则 adversary can not distinguish commitments to
M
0
M_0
M0 or
M
1
M_1
M1 of its choice。【即an unbounded adversary can simply try all possible
r
∈
Z
q
r\in\mathbb{Z}_q
r∈Zq till it matches
g
r
g^r
gr,然后根据已知的
r
r
r 可找到
M
∈
G
M\in\mathbb{G}
M∈G matches
M
h
r
Mh^r
Mhr。】
Q-8: EIGamal commitment 是extractable可提取的:simulator 使用a trapdoor (仅simulator本人知道) 来生成 parameters
(
g
,
h
)
(g,h)
(g,h)时(与Setup
算法无法区分),则该simulator可extract the committed value in any
c
∈
G
c\in\mathbb{G}
c∈G。【其实应该就是指若simulator知道
g
a
=
h
g^a=h
ga=h,其中
a
a
a为trapdoor,则该simulator可extract
M
=
B
/
A
a
M=B/A^a
M=B/Aa。】
Q-9: 何时可在a security proof中使用EIGamal commitment的binding属性 和 extractability可提取?
Q-10: 何时可在a security proof中使用EIGamal commitment的hiding属性 和 extractability可提取?
Q-11: EIGamal commitment之所以称为”EIGamal” commitment,是因为这其实就是EIGamal encryption。(具体可参见博客 EIGamal encryption VS Pairing encryption)
How one could make the hiding property and the extractability compatible without any limitation?
4. Non-interactive commitments (Pedersen commitment + EIGamal commitment)
Pedersen commitment:
- perfectly hiding
- computationally binding
EIGamal commitment:
- computationally hiding
- perfectly binding
Q-12: 由此可知,a non-interactive commitment 不可能同时具有perfectly hiding和perfectly binding属性。(which would mean both hiding and binding against powerful adversaries。)
an efficient construction in the random oracle model为:
c
=
C
o
m
m
i
t
(
m
,
r
)
=
H
(
m
,
r
)
c=Commit(m,r)=H(m,r)
c=Commit(m,r)=H(m,r)
其中
H
H
H为hash函数
H
:
{
0
,
1
}
∗
→
{
0
,
1
}
2
k
H: \{0,1\}^*\rightarrow \{0,1\}^{2k}
H:{0,1}∗→{0,1}2k,on the message
m
∈
{
0
,
1
}
∗
m\in\{0,1\}^*
m∈{0,1}∗ to commit, with random coins
r
∈
{
0
,
1
,
}
3
k
r\in\{0,1,\}^{3k}
r∈{0,1,}3k,for security parameter
k
k
k,相应的opening value为
r
r
r。
Q-13: 以上random oracle model下的构建确实是a non-interactive commitment scheme (具有hiding和binding属性),and say under which assumptions (some limit or not on the number of queries to the random oracle)。
Q-14: Show that it is also extractable and equivocal for a simulator that can access the list of query-answer pairs and that can program the random oracle in an indistinguishable way。
为了在standard model(而不是random oracle model)情况下,实现类似以上的具有equivocal和extractable的commitment scheme,具体的构建思路为:
- an equivocal bit-commitment scheme C o m m i t e q ( b , r ) Commit_{eq}(b,r) Commiteq(b,r),for a bit b ∈ { 0 , 1 } b\in\{0,1\} b∈{0,1} and random coins r r r,输出为a commitment c c c,和 opening value d ∈ { 0 , 1 } 2 k d\in\{0,1\}^{2k} d∈{0,1}2k。(可参见博客 水银承诺mercurial commitment 中的chameleon hash function。其本质可为Pedersen commitment。)
- an extractable commitment scheme C o m m i t e x t ( D , r ′ ) Commit_{ext}(D,r') Commitext(D,r′), for a bitstring D ∈ { 0 , 1 } 2 k D\in \{0,1\}^{2k} D∈{0,1}2k 安定random coins r ′ r' r′,输出为commitment c ′ c' c′和opening value O O O。
注意以上两种commitment scheme中, C o m m i t e q Commit_{eq} Commiteq的输出opening value d d d 为 C o m m i t e x t Commit_{ext} Commitext 的输入 D D D,两者都在the same space { 0 , 1 } 2 k \{0,1\}^{2k} {0,1}2k
On a message m = ( m 1 , ⋯ , m l ) ∈ { 0 , 1 } l m=(m_1,\cdots,m_l)\in\{0,1\}^l m=(m1,⋯,ml)∈{0,1}l ,整个commitment 算法 C o m m i t ( m , ( ( r i ) i , ( D i ′ ) i , ( r i , b ′ ) i , b ) ) Commit(m, ((r_i)_i, (D'_i)_i, (r'_{i,b})_{i,b})) Commit(m,((ri)i,(Di′)i,(ri,b′)i,b))流程为:
- for random coins r i r_i ri for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l,设置 ( c i , D i ) ← C o m m i t e q ( m i , r i ) (c_i,D_i)\leftarrow Commit_{eq}(m_i,r_i) (ci,Di)←Commiteq(mi,ri);
- for random coins D i ′ ← { 0 , 1 } 2 k D'_i \leftarrow \{0,1\}^{2k} Di′←{0,1}2k,设置 d i , m i ← D i , d i , 1 − m i ← D i ′ d_{i,m_i}\leftarrow D_i,d_{i,1-m_i}\leftarrow D'_i di,mi←Di,di,1−mi←Di′ for i = 1 , ⋯ , l i=1,\cdots, l i=1,⋯,l;
- for random coins r i , b ′ r'_{i,b} ri,b′,设置 ( c i , b ′ , O i , b ) ← C o m m i t e x t ( d i , b , r i , b ′ ) (c'_{i,b},O_{i,b})\leftarrow Commit_{ext}(d_{i,b}, r'_{i,b}) (ci,b′,Oi,b)←Commitext(di,b,ri,b′) for i = 1 , ⋯ , l i=1,\cdots,l i=1,⋯,l and b = 0 , 1 b=0,1 b=0,1;
- output the commitment ( c i , ( c i , b ′ ) b ) i (c_i, (c'_{i,b})_b)_i (ci,(ci,b′)b)i,opening value ( d i , m , O i , m i ) i (d_{i,m}, O_{i,m_i})_i (di,m,Oi,mi)i。
Q-15: Explain how works the Verify
算法。
Q-16: Show this is indeed a commitment scheme: with both hiding and binding properties。
Q-17: Show this commitment scheme is also both equivocal and extractable。
参考资料:
[1] Difference between Pedersen commitment and commitment based on ElGamal
[2] David Pointcheval 的课件Commiments Schemes
[3] Why is the El Gamal commitment scheme information theoretically binding?
本文标签: PedersencommitmentEIGamal
版权声明:本文标题:Pedersen commitment 还是 EIGamal commitment ? 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1726644987a1079895.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论