更新:由于这篇文章的内容大部分是我的脑洞,所以我不能确保正确性,目前我已经把文章设为隐藏状态,如果你碰巧访问到这篇文章,请自行辨识内容的正确性。
PS:关于非交互承诺方案的一些更严谨的内容目前被写在了我的硕士论文中,在我大论文完成后我也会公开这些内容,所以,别急(
以下是正文:
事情是这样的,上次 写的笔记内容被我用在某个期末作业上了,由于是写作业上的所以表述会正规一点,而且写的时候也加了新东西,所以可以再水一篇贴了。
承诺方案(Commitment Scheme)如其名,就是在模拟一个“作出承诺”和“兑现承诺”的过程,但和现实的承诺不同,密码学中的承诺通常是在承诺发送者不会改变某个值,然后在兑现承诺的时候把这个值发送给接收者,接收者收到后验证这个值是否真的没被改变。
承诺(Commitment)的概念最早由[B83]提出,而较正式的承诺方案则在[BCC88]提出,[BCC88]提出的是单比特的承诺方案(Bit Commitment Scheme),目前承诺方案被广泛应用于抛币协议、零知识证明、安全多方计算等协议中,在[C01]提出通用可组合框架(Universally Composable,下简称UC)以后,这些协议相继提出了UC模型下的版本,承诺方案也不例外,最先提出UC模型下承诺方案的是[CF01],目前(我所了解的)被认为最快的且在UC模型下、不使用Random Oracle的、可承诺任意比特的承诺方案是[Lin11]提出的承诺方案。
承诺方案有两个参与者:发送方(Sender)和接收方(Receiver);承诺方案还有两个阶段:承诺(Commit)和打开(Open)。
在承诺阶段中,发送方承诺某个不会改变的值m m m ,利用m m m 和随机性r r r 计算并发送承诺值c c c 给接收方。在打开阶段中,发送方须发送值m m m 和一个用于辅助打开承诺的打开值(Opening Value)d d d 给接收方,接收方利用收到的m m m 、d d d 和c c c 验证(Verify)m m m 是否没被发送方或其他攻击者更改,若验证通过则接受(Accept),否则拒绝(Reject)。大概过程见下图:
C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r C o m ( m , r ) → ( c , d ) ⟶ c ⋮ ⟶ m , d V e r i f y ( c , m , d ) → Accept/Reject \begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \rm{Open: }
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
\rm{Com}(m, r) \rightarrow (c, d)
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{l}
\rm{Verify(c, m, d)} \rightarrow \text{Accept/Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
Commit : Open : Sender ( m ) Com ( m , r ) → ( c , d ) ⋮ ⟶ c ⟶ m , d Receiver Verify ( c , m , d ) → Accept/Reject
作为一个协议,首先要拥有正确性,一个是取值范围的问题:假设消息的取值范围是M \mathcal{M} M 、随机数的取值范围是R \mathcal{R} R 、承诺值的范围是C \mathcal{C} C 、打开值得范围是D \mathcal{D} D ,“← $ \overset{\$}{\leftarrow} ← $ ”表示随机选取,则会有:
m ∈ M ; r ∈ R ; C o m ( m , r ) → ( c , d ) ⇒ c ∈ C ; d ∈ D ; \begin{array}{ccc}
\begin{array}{l}
m \in \mathcal{M} \rm{;} \ \ \
r \in \mathcal{R} \rm{;} \\
\rm{Com}(m, r) \rightarrow (c, d)
\end{array}
& \Rightarrow &
\begin{array}{l}
c \in \mathcal{C} \rm{;} \ \ \
d \in \mathcal{D} \rm{;} \\
\end{array}
\end{array}
m ∈ M ; r ∈ R ; Com ( m , r ) → ( c , d ) ⇒ c ∈ C ; d ∈ D ;
另一个是,若承诺值和打开值是按正确流程生成的,则一定会通过验证:
m ∈ M ; r ∈ R ; C o m ( m , r ) → ( c , d ) ⇒ V e r i f y ( c , m , d ) = Accept \begin{array}{ccc}
\begin{array}{l}
m \in \mathcal{M} \rm{;} \ \ \
r \in \mathcal{R} \rm{;} \\
\rm{Com}(m, r) \rightarrow (c, d)
\end{array}
& \Rightarrow &
\begin{array}{l}
\rm{Verify(c, m, d)} = \text{Accept}
\end{array}
\end{array}
m ∈ M ; r ∈ R ; Com ( m , r ) → ( c , d ) ⇒ Verify ( c , m , d ) = Accept
安全属性·
除了上面的流程,承诺方案还需要满足两个安全属性:绑定(Binding)和隐藏(Hiding),很遗憾在我目前看到的论文里都没有这两个安全属性的形式化定义,大多论文都选择使用自然语言去定义,目前看到最多的定义如下:
绑定属性 :定义一:承诺方不能用两个不同的m ≠ m ′ m \ne m' m = m ′ 承诺出同样的承诺值c c c ;定义二:承诺方生成的承诺值c c c 在打开时不能被两个不同的m ≠ m ′ m \ne m' m = m ′ 通过验证。
隐藏属性 :接收方不能根据接收到的承诺值c c c 恢复出m m m 。
显然,绑定针对的是不诚实的承诺方,隐藏则是不诚实的接收方。
对绑定属性的一点看法·
绑定属性的定义会有点歧义,在目前的论文里,定义一和定义二都有出现,但在我看来,定义二会更准确,因为定义一的安全性并不用考虑打开阶段。而且根据承诺方案的正确性,若有两个不同的m ≠ m ′ m \ne m' m = m ′ 承诺出同样的承诺值c c c ,那么c c c 也应该要被m m m 和m ′ m' m ′ 通过验证,也即其逆否命题也成立:若一个承诺值c c c 不能被两个不同的m ≠ m ′ m \ne m' m = m ′ 通过验证,则不会有两个不同的m ≠ m ′ m \ne m' m = m ′ 承诺出同样的承诺值c c c ,符合定义二可推出符合定义一(② ⇒ ① ② \Rightarrow ① ② ⇒ ① )。
另外,感觉上如果只按照定义一实现绑定的话,可以在打开阶段设置后门,而达到设计虽符合了安全定义但是却不安全的协议。举个较极端的例子,假设我设计一个符合上述绑定属性定义一和隐藏属性的承诺方案(简单地用一个加密函数或者单向函数作C o m \rm{Com} Com 即可符合),但是在打开阶段的验证函数无论输入是什么都输出接受,即V e r i f y ( c , m , d ) → always Accept \rm{Verify(c, m, d)} \overset{\text{always}}{\rightarrow} \text{Accept} Verify ( c , m , d ) → always Accept ,根据加密函数或者单向函数性质,这个承诺方案都满足绑定属性的定义一和隐藏属性的定义,但显然这不是一个可以使用的承诺方案,因为无论承诺方承诺什么,接收方都只能接受。
上述的绑定属性定义一的出现,我认为是历史原因导致的。以往的承诺方案其实并不复杂,通常是发送方使用加密函数或者单向函数对信息m m m 进行加密或映射,在打开时接收方使用接收到的m m m 进行重加密或重映射,然后对比得到的结果是否跟c c c 一致,若一致则接受,否则拒绝。在这样的构造下,承诺阶段的操作与打开阶段的几乎一样,没有有两个不同的信息承诺出相同的承诺值的话自然也不会有一个承诺值可以被两个不同的信息通过验证,换句话说,在这种情况下 ,符合定义一可以推出符合定义二(② ⇔ ① ② \Leftrightarrow ① ② ⇔ ① )。
形式化定义的尝试·
上面说了,目前我所看的论文里都没有出现绑定和隐藏这两个安全属性的形式化定义,但是根据自然语言的定义给出形式化定义其实是可行的,所以下面我就进行一番尝试,给出针对这两个安全属性的攻击者的优势(Advantage),可以理解为攻击者攻击成功的概率。假设消息的取值范围是M \mathcal{M} M 、随机数的取值范围是R \mathcal{R} R 、承诺值的范围是C \mathcal{C} C 、打开值得范围是D \mathcal{D} D ,“ ← $ \overset{\$}{\leftarrow} ← $ ”表示随机选取。
不诚实得发送者A S \text{A}_\text{S} A S 攻破绑定属性的优势可以表示为:
Adv Binding ( A S ) = Pr [ V e r i f y ( c , m , d ) = Accept V e r i f y ( c , m ′ , d ′ ) = Accept : ( c , m , m ′ , d , d ′ ) ← A S ; m , m ′ ∈ M ; m ≠ m ′ ; d , d ′ ∈ D ; c ∈ C ] \text{Adv}_\text{Binding}(A_S) = \text{Pr}\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
\rm{Verify(c, m, d)} = \text{Accept} \\
\rm{Verify(c, m', d')} = \text{Accept}
\end{array}
& \rm{:} &
\begin{array}{l}
(c, m, m', d, d') \leftarrow \text{A}_\text{S} \rm{;} \\
m, m' \in \mathcal{M} \rm{;} \ \ \
m \ne m' \rm{;} \\
d, d' \in \mathcal{D} \rm{;} \ \
c \in \mathcal{C}
\end{array}
\end{array}
\end{bmatrix}
Adv Binding ( A S ) = Pr ⎣ ⎡ Verify ( c , m , d ) = Accept Verify ( c , m ′ , d ′ ) = Accept : ( c , m , m ′ , d , d ′ ) ← A S ; m , m ′ ∈ M ; m = m ′ ; d , d ′ ∈ D ; c ∈ C ⎦ ⎤
不诚实的接收者A R \text{A}_\text{R} A R 攻破隐藏属性的优势可以表示为:
Adv Hiding ( A R ) = Pr [ m = m ′ : m ← $ M ; r ← $ R ; ( c , d ) ← C o m ( m , r ) ; m ′ ← A R ( c ) ] \text{Adv}_\text{Hiding}(\text{A}_\text{R}) = \text{Pr}\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
m = m'
\end{array}
& \rm{:} &
\begin{array}{l}
m \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \
r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\
(c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\
m' \leftarrow \text{A}_\text{R}(c)
\end{array}
\end{array}
\end{bmatrix}
Adv Hiding ( A R ) = Pr ⎣ ⎡ m = m ′ : m ← $ M ; r ← $ R ; ( c , d ) ← Com ( m , r ) ; m ′ ← A R ( c ) ⎦ ⎤
除了上述我编的定义,记c m , r c_{m, r} c m , r 为C o m ( m , r ) \rm{Com}(m, r) Com ( m , r ) 得到的承诺值,目前还流传着其他的定义,常见的如(这里为了与上面的表述相一致,在不改变意思的情况下做了修改):
绑定属性(定义一):∀ m , m ′ ∈ M , ∀ r , r ′ ∈ R , m ′ ≠ m ⇒ c m , r ≠ c m ′ , r ′ \forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'} ∀ m , m ′ ∈ M , ∀ r , r ′ ∈ R , m ′ = m ⇒ c m , r = c m ′ , r ′ 。按我的理解,还可以被写作:
Adv Binding ′ ( ) = Pr [ c = c ′ : m ≠ m ′ ← $ M ; r , r ′ ← $ R ; ( c , d ) ← C o m ( m , r ) ; ( c ′ , d ′ ) ← C o m ( m ′ , r ′ ) ] \text{Adv}^{'}_\text{Binding}() = \text{Pr}\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
c = c'
\end{array}
& \rm{:} &
\begin{array}{l}
m \ne m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ \
r, r' \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\
(c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\
(c', d') \leftarrow \rm{Com}(m', r')
\end{array}
\end{array}
\end{bmatrix}
Adv Binding ′ ( ) = Pr ⎣ ⎡ c = c ′ : m = m ′ ← $ M ; r , r ′ ← $ R ; ( c , d ) ← Com ( m , r ) ; ( c ′ , d ′ ) ← Com ( m ′ , r ′ ) ⎦ ⎤
隐藏属性:通常会被简化表述为∀ m , m ′ ∈ M , { c m , R } = { c m ′ , R } \forall m,m' \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \{c_{m', \mathcal{R}}\} ∀ m , m ′ ∈ M , { c m , R } = { c m ′ , R } 。按我的理解,还可以被写作(在Adv Hiding ( A R ) = 0 \text{Adv}_\text{Hiding}(\text{A}_\text{R})=0 Adv Hiding ( A R ) = 0 时等号成立):
Adv Hiding ( A R ) ≤ Adv Hiding ′ ( ) = Pr [ C m ≠ C m ′ : m ≠ m ′ ← $ M ; C m = { c ∣ ( c , d ) ← C o m ( m , r ) ; r ∈ R } C m ′ = { c ′ ∣ ( c ′ , d ′ ) ← C o m ( m ′ , r ′ ) ; r ′ ∈ R } ] \text{Adv}_\text{Hiding}(\text{A}_\text{R}) \le \text{Adv}^{'}_\text{Hiding}() = \text{Pr}\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
\mathcal{C}_m \ne \mathcal{C}_{m'}
\end{array}
& \rm{:} &
\begin{array}{l}
m \ne m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\
\mathcal{C}_m = \{c\ |\ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ r \in \mathcal{R} \} \\
\mathcal{C}_{m'} = \{c'\ |\ (c', d') \leftarrow \rm{Com}(m', r')\rm{;}\ r' \in \mathcal{R} \}
\end{array}
\end{array}
\end{bmatrix}
Adv Hiding ( A R ) ≤ Adv Hiding ′ ( ) = Pr ⎣ ⎡ C m = C m ′ : m = m ′ ← $ M ; C m = { c ∣ ( c , d ) ← Com ( m , r ) ; r ∈ R } C m ′ = { c ′ ∣ ( c ′ , d ′ ) ← Com ( m ′ , r ′ ) ; r ′ ∈ R } ⎦ ⎤
这两个定义的好处是并不用考虑攻击者,即只要构造符合某种属性的C o m \rm{Com} Com 就可以构造出安全的承诺方案,而且使用在各种证明中都会更简洁,但遗憾的是目前并没有找到绑定属性中定义二的类似表述。Adv Binding ′ ( ) \text{Adv}^{'}_\text{Binding}() Adv Binding ′ ( ) 的表述很直观,几乎只是大白话的翻译。Adv Hiding ′ ( ) \text{Adv}^{'}_\text{Hiding}() Adv Hiding ′ ( ) 的大概意思是,若攻击者可以找到m ≠ m ′ m \ne m' m = m ′ 使得C m ≠ C m ′ \mathcal{C}_m \ne \mathcal{C}_{m'} C m = C m ′ ,那么就会存在r , r ′ ∈ R r, r' \in \mathcal{R} r , r ′ ∈ R ,使得c m , r c_{m, r} c m , r 、c m ′ , r ′ c_{m', r'} c m ′ , r ′ 可以区分m m m 、m ′ m' m ′ 。Adv Hiding ′ ( ) = 0 \text{Adv}^{'}_\text{Hiding}()=0 Adv Hiding ′ ( ) = 0 时,M \mathcal{M} M 中的每个m m m 承诺出来的承诺值分布都一样,那么攻击者拿到任何一个c ∈ C c \in \mathcal{C} c ∈ C 也不会知道是由哪一个或者哪几个m ∈ M m \in \mathcal{M} m ∈ M 产生的,自然也无法恢复出消息m m m ,也即Adv Hiding ( A R ) = 0 \text{Adv}_\text{Hiding}(\text{A}_\text{R})=0 Adv Hiding ( A R ) = 0 。
也许 还可以写出另一个区分性的版本:
Adv Hiding ( A R ) ≤ Adv Hiding ′ ′ ( A R ) = ∣ P r [ b = b ∗ : m 0 ≠ m 1 ← A R ( ) ; b ∗ ← $ { 0 , 1 } ; r ← $ R ; ( c ∗ , d ) ← C o m ( m b ∗ , r ) ; b ← A R O r a ( ⋅ ) ( c ∗ ) ] − 1 2 ∣ \text{Adv}_\text{Hiding}(\text{A}_\text{R}) \le \text{Adv}^{''}_\text{Hiding}(\text{A}_\text{R}) = \begin{vmatrix}
Pr\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
b = b^*
\end{array}
& \rm{:} &
\begin{array}{l}
m_0 \ne m_1 \leftarrow \text{A}_\text{R}() \rm{;} \\
b^* \overset{\$}{\leftarrow} \{0, 1\} \rm{;} \
r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\
(c^*, d) \leftarrow \rm{Com}(m_{b^*}, r) \rm{;} \\
b \leftarrow \text{A}_\text{R}^{\rm{Ora}(·)}(c^*)
\end{array}
\end{array}
\end{bmatrix}
- \frac{1}{2}
\end{vmatrix}
Adv Hiding ( A R ) ≤ Adv Hiding ′′ ( A R ) = ∣ ∣ P r ⎣ ⎡ b = b ∗ : m 0 = m 1 ← A R ( ) ; b ∗ ← $ { 0 , 1 } ; r ← $ R ; ( c ∗ , d ) ← Com ( m b ∗ , r ) ; b ← A R Ora ( ⋅ ) ( c ∗ ) ⎦ ⎤ − 2 1 ∣ ∣
其中
O r a ( m ) : = { r ← $ R ; ( c , d ) ← C o m ( m , r ) ; Output: ( c , d ) } \rm{Ora}(m) := \begin{Bmatrix}
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \
(c, d) \leftarrow \rm{Com}(m, r) \rm{;} \\
\text{Output: } (c, d)
\end{array}
\end{Bmatrix}
Ora ( m ) := { r ← $ R ; ( c , d ) ← Com ( m , r ) ; Output: ( c , d ) }
完美安全和计算上安全·
上述的绑定和隐藏属性其实还各自分两个安全等级:完美(Perfect)安全和计算上(Computational)安全。所谓完美安全,就是即使是有无限能力(Unbounding)的攻击者也不可能攻破这个安全属性;所谓计算上安全,就是攻击者能攻破该属性的概率可以被忽略,或者说攻击者在多项式时间内不可能攻破。
有了上面的几个定义,这两个安全等级就很好解释了:
完美绑定(Perfectly Binding):Adv Binding ( A S ) = 0 \text{Adv}_\text{Binding}(\text{A}_\text{S}) = 0 Adv Binding ( A S ) = 0 ,或者至少需要Adv Binding ′ ( ) = 0 \text{Adv}^{'}_\text{Binding}() = 0 Adv Binding ′ ( ) = 0 ,因为前面说了定义二 ⇒ 定义一 \rm{定义二} \Rightarrow \rm{定义一} 定义二 ⇒ 定义一 ,定义一是定义二的一个必然条件;
计算上绑定(Computationally Binding):Adv Binding ( A S ) = n e g l \text{Adv}_\text{Binding}(\text{A}_\text{S}) = \rm{negl} Adv Binding ( A S ) = negl ,或者至少需要Adv Binding ′ ( ) = n e g l \text{Adv}^{'}_\text{Binding}() = \rm{negl} Adv Binding ′ ( ) = negl ,其中n e g l \rm{negl} negl 为可忽略(Negligible);
完美隐藏(Perfectly Hiding):Adv Hiding ( A R ) = 0 \text{Adv}_\text{Hiding}(\text{A}_\text{R}) = 0 Adv Hiding ( A R ) = 0 ,或者Adv Hiding ′ ( ) = 0 \text{Adv}^{'}_\text{Hiding}() = 0 Adv Hiding ′ ( ) = 0 ;
计算上隐藏(Computationally Hiding):Adv Hiding ( A R ) = n e g l \text{Adv}_\text{Hiding}(\text{A}_\text{R}) = \rm{negl} Adv Hiding ( A R ) = negl ,或者Adv Hiding ′ ( ) = n e g l \text{Adv}^{'}_\text{Hiding}() = \rm{negl} Adv Hiding ′ ( ) = negl 。
明显,完美安全的安全性比计算上安全的安全性高,但坏消息是,不能同时实现完美绑定和完美隐藏 ,粗略的论证如下:假设Adv Binding ′ ( ) = 0 \text{Adv}^{'}_\text{Binding}() = 0 Adv Binding ′ ( ) = 0 且Adv Hiding ′ ( ) = 0 \text{Adv}^{'}_\text{Hiding}() = 0 Adv Hiding ′ ( ) = 0 ,首先根据Adv Hiding ′ ( ) = 0 \text{Adv}^{'}_\text{Hiding}() = 0 Adv Hiding ′ ( ) = 0 会有:
∀ m ≠ m ′ ∈ M ; { c ∣ ( c , d ) ← C o m ( m , r ) ; r ∈ R } = { c ′ ∣ ( c ′ , d ′ ) ← C o m ( m ′ , r ′ ) ; r ′ ∈ R } \forall m \ne m' \in \mathcal{M} \rm{;} \\
\{c\ |\ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ r \in \mathcal{R} \} =
\{c'\ |\ (c', d') \leftarrow \rm{Com}(m', r')\rm{;}\ r' \in \mathcal{R} \}
∀ m = m ′ ∈ M ; { c ∣ ( c , d ) ← Com ( m , r ) ; r ∈ R } = { c ′ ∣ ( c ′ , d ′ ) ← Com ( m ′ , r ′ ) ; r ′ ∈ R }
由两个集合的相等可以推出:
∀ m ≠ m ′ ∈ M ; ∃ r , r ′ ∈ R ; s . t . c = c ′ ; ( c , d ) ← C o m ( m , r ) ; ( c ′ , d ′ ) ← C o m ( m ′ , r ′ ) \forall m \ne m' \in \mathcal{M} \rm{;} \ \
\exist r, r' \in \mathcal{R} \rm{;} \\
s.t.\ \ c = c' \rm{;}\ \ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ \ (c', d') \leftarrow \rm{Com}(m', r')
∀ m = m ′ ∈ M ; ∃r , r ′ ∈ R ; s.t. c = c ′ ; ( c , d ) ← Com ( m , r ) ; ( c ′ , d ′ ) ← Com ( m ′ , r ′ )
而\rm{Adv}^{'}_\rm{Binding}() = 0会有:
∀ m ≠ m ′ ∈ M ; ∀ r , r ′ ∈ R ; c ≠ c ′ ; ( c , d ) ← C o m ( m , r ) ; ( c ′ , d ′ ) ← C o m ( m ′ , r ′ ) \forall m \ne m' \in \mathcal{M} \rm{;} \ \
\forall r, r' \in \mathcal{R} \rm{;} \\
c \ne c' \rm{;}\ \ (c, d) \leftarrow \rm{Com}(m, r)\rm{;}\ \ (c', d') \leftarrow \rm{Com}(m', r')
∀ m = m ′ ∈ M ; ∀r , r ′ ∈ R ; c = c ′ ; ( c , d ) ← Com ( m , r ) ; ( c ′ , d ′ ) ← Com ( m ′ , r ′ )
两者矛盾,所以Adv Binding ′ ( ) = 0 \text{Adv}^{'}_\text{Binding}() = 0 Adv Binding ′ ( ) = 0 和Adv Hiding ′ ( ) = 0 \text{Adv}^{'}_\text{Hiding}() = 0 Adv Hiding ′ ( ) = 0 不能同时成立,完美绑定和完美隐藏不能同时实现。
所以在构造承诺方案时,通常会选择“完美绑定+计算上隐藏”或者“计算上绑定+完美隐藏”的组合,实在没办法的情况下才会选择“计算上绑定+计算上隐藏”的组合。
模棱两可和提取·
模棱两可和提取是两个后门属性,常用于构造通用可组合(UC)安全的承诺方案:
模棱两可(Equivocality)属性 :指在知道且仅在知道某个后门值时,可以对一个已经对一个消息m m m 做出的承诺在打开时解释为任意不同消息m ′ m' m ′ 的承诺,且不被接收方发现,即根据m ≠ m ′ ∈ M ; m \ne m' \in \mathcal{M}\text{;} m = m ′ ∈ M ; r ∈ R ; r \in \mathcal{R}\text{;} r ∈ R ; ,可以计算出d ′ ∈ D d' \in \mathcal{D} d ′ ∈ D ,使得Verify ( c m , r , m ′ , d ′ ) = Accept \text{Verify}(c_{m, r}, m', d') = \text{Accept} Verify ( c m , r , m ′ , d ′ ) = Accept 。
提取(Extractability)属性 :指在知道且仅在知道某个后门值时,可以仅根据承诺值c m , ⋅ c_{m, ·} c m ,⋅ 提取消息m m m 。
由于后门的存在,构造满足模棱两可或提取的承诺方案通常会使用公钥系统,即会有一个密钥生成函数G e n \rm{Gen} Gen 生成一个公钥和后门的对( p k , t d ) (pk, td) ( p k , t d ) ,在仅知道公钥p k pk p k 的情况下无法(或计算上不能)恢复后门t d td t d ,C o m \rm{Com} Com 操作和V e r i f y \rm{Verify} Verify 操作均需要使用公钥p k pk p k ,记作C o m p k \rm{Com}_{pk} Com pk 和V e r i f y p k \rm{Verify}_{pk} Verify pk 。
下面说一下形式化定义,同样由于在现有文献中没找到详细的定义,于是就按照自己的理解编一个:
密钥生成:( p k , t d ) ← G e n ( 1 κ ) (pk, td) \leftarrow \rm{Gen}(1^\kappa) ( p k , t d ) ← Gen ( 1 κ ) ,其中1 κ 1^\kappa 1 κ 为安全系数;
模棱两可:( c , d ) ← C o m p k ( m , r ) (c, d) \leftarrow \rm{Com}_{pk}(m, r) ( c , d ) ← Com pk ( m , r ) ,m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M ,r ∈ R r \in \mathcal{R} r ∈ R ,( c , d ) ← C o m ( m , r ) (c, d) \leftarrow \rm{Com}(m, r) ( c , d ) ← Com ( m , r ) ,则d ′ ← E q u i v t d ( m , m ′ , d ) d' \leftarrow \rm{Equiv}_{td}(m, m', d) d ′ ← Equiv td ( m , m ′ , d ) ,其中d ′ ∈ D d' \in \mathcal{D} d ′ ∈ D 且V e r i f y p k ( c , m ′ , d ′ ) = Accept \rm{Verify}_{pk}(c, m', d') = \text{Accept} Verify pk ( c , m ′ , d ′ ) = Accept ,由于不能被接收方发现做了假承诺,还需要∃ r ′ ∈ R s . t . C o m p k ( m ′ , r ′ ) = ( c , d ′ ) \exist r' \in \mathcal{R}\ s.t.\ \rm{Com}_{pk}(m', r') = (c, d') ∃ r ′ ∈ R s . t . Com pk ( m ′ , r ′ ) = ( c , d ′ ) (或者说不存在这样的r ′ r' r ′ 的概率可忽略?又或者存在但是接收方能找到的概率可忽略?);
提取:( c , d ) ← C o m p k ( m , r ) (c, d) \leftarrow \rm{Com}_{pk}(m, r) ( c , d ) ← Com pk ( m , r ) ,m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M ,r ∈ R r \in \mathcal{R} r ∈ R ,则m ← E x t r a t d ( c ) m \leftarrow \rm{Extra}_{td}(c) m ← Extra td ( c ) 。
由于在通用可组合框架中,E q u i v t d \rm{Equiv}_{td} Equiv td 和E x t r a t d \rm{Extra}_{td} Extra td 都是由模拟者(Simulator)操作的,结合通用可组合框架中的证明套路,还可以借助模拟者的优势给出定义:
模拟者的模棱两可优势:
Adv Equiv ( S S ) = P r [ V e r i f y p k ( c , m ′ , d ′ ) = Accept : c ← S S ( ) ; c ∈ C ; m ′ ← $ M ; d ′ ← S S t d ( m ′ ) ] ≥ 1 − n e g l \text{Adv}_\text{Equiv}(\text{S}_\text{S}) = Pr\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
\rm{Verify}_{pk}(c, m', d') = \text{Accept}
\end{array}
& \rm{:} &
\begin{array}{l}
c \leftarrow \text{S}_\text{S}() \rm{;} \
c \in \mathcal{C} \rm{;} \\
m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\
d' \leftarrow \text{S}_\text{S}^{td}(m')
\end{array}
\end{array}
\end{bmatrix}
\ge 1 - \rm{negl}
Adv Equiv ( S S ) = P r ⎣ ⎡ Verify pk ( c , m ′ , d ′ ) = Accept : c ← S S ( ) ; c ∈ C ; m ′ ← $ M ; d ′ ← S S t d ( m ′ ) ⎦ ⎤ ≥ 1 − negl
模拟者的提取优势:
Adv Extra ( S R ) = P r [ m = m ′ : m ← $ M ; r ← $ R ; ( c , d ) ← C o m p k ( m , r ) ; m ′ ← S S t d ( c ) ] ≥ 1 − n e g l \text{Adv}_\text{Extra}(\text{S}_\text{R}) = Pr\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
m = m'
\end{array}
& \rm{:} &
\begin{array}{l}
m \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \ \
r \overset{\$}{\leftarrow} \mathcal{R} \rm{;} \\
(c, d) \leftarrow \rm{Com}_{pk}(m, r) \rm{;} \\
m' \leftarrow \text{S}_\text{S}^{td}(c)
\end{array}
\end{array}
\end{bmatrix}
\ge 1 - \rm{negl}
Adv Extra ( S R ) = P r ⎣ ⎡ m = m ′ : m ← $ M ; r ← $ R ; ( c , d ) ← Com pk ( m , r ) ; m ′ ← S S t d ( c ) ⎦ ⎤ ≥ 1 − negl
模棱两可和提取属性的存在直观上好像会分别和前文的绑定属性和隐藏属性相矛盾,从而影响协议的安全性,但其实不然,因为模棱两可和提取均需要知道后门,而在实际的协议设计中,密钥是由一个安全的第三方生成、分发和保管的(如UC框架中的承诺方案),安全第三方并不会泄露后门,而仅知道公钥p k pk p k 的情况下后门无法(或计算上不能)被恢复,所以E q u i v t d \rm{Equiv}_{td} Equiv td 和E x t r a t d \rm{Extra}_{td} Extra td 方法仅有安全第三方可以使用,但这个第三方并不会攻击协议的参与方,所以协议还是安全的。
但是后门的存在会对完美安全属性有影响,结果是,若承诺方案可模棱两可,则不能实现完美绑定;若可提取,则不能实现完美隐藏 。完美安全要求的是“无限能力的攻击者也不可能攻破”,而无限能力的攻击者是可以算出后门的,所以自然地,若协议有模棱两可属性,则无限能力的攻击者可以实现E q u i v t d \rm{Equiv}_{td} Equiv td ,从而可以对不同的消息做出相同的承诺,攻破完美绑定属性;类似地,若协议有提取属性,则无限能力的攻击者可以实现E x t r a t d \rm{Extra}_{td} Extra td ,从而可以根据承诺值恢复消息,攻破完美隐藏属性。
更进一步,直觉上 (其实这里的证明我也不太确定是否正确,所以只是直觉上),只有实现了完美绑定才会有提取属性;只有实现了完美隐藏才会有模棱两可 。首先假设协议拥有提取属性,但是没有完美绑定属性,则会存在m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M 和r , r ′ ∈ R r, r' \in \mathcal{R} r , r ′ ∈ R ,使得c m , r = c m ′ , r ′ c_{m, r} = c_{m', r'} c m , r = c m ′ , r ′ ,那么在提取c m , r c_{m, r} c m , r 或者c m ′ , r ′ c_{m', r'} c m ′ , r ′ 时,就会有m m m 和m ′ m' m ′ 两种可能,攻击者无法分辨哪个才是诚实发送方真正承诺的消息,所以若没有完美绑定属性则没有提取属性;类似地,假设协议拥有模棱两可属性,但是没有隐藏属性,则会存在m , m ′ ∈ M m,m' \in \mathcal{M} m , m ′ ∈ M 使得 { c m , R } ≠ { c m ′ , R } \ \{c_{m, \mathcal{R}}\} \ne \{c_{m', \mathcal{R}}\} { c m , R } = { c m ′ , R } ,也即存在r ∈ R r \in \mathcal{R} r ∈ R ,使得c m , r ∉ { c m ′ , R } c_{m, r} \not\in \{c_{m', \mathcal{R}}\} c m , r ∈ { c m ′ , R } ,则不存在r ′ ∈ R r' \in \mathcal{R} r ′ ∈ R 使得C o m p k ( m ′ , r ′ ) = ( c , d ′ ) \rm{Com}_{pk}(m', r') = (c, d') Com pk ( m ′ , r ′ ) = ( c , d ′ ) ,即如果恰好选择到这样的m m m 和m ′ m' m ′ 时,模棱两可会被接收者发现进而失败,所以若没有完美隐藏属性则没有模棱两可属性。
由于前文论证了“不能同时实现完美绑定和完美隐藏”,所以结合可以推出提取属性和模棱两可属性直觉上也不能同时实现。
从函数性质看安全属性·
下面给出一些可能的非通用可组合框架(Plain Model)下的承诺方案构造思路,这里首先分析完美绑定或者完美隐藏的一些特性。
从单射函数到完美绑定·
复习一下完美绑定的一个必要条件,∀ m , m ′ ∈ M , ∀ r , r ′ ∈ R , m ′ ≠ m ⇒ c m , r ≠ c m ′ , r ′ \forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'} ∀ m , m ′ ∈ M , ∀ r , r ′ ∈ R , m ′ = m ⇒ c m , r = c m ′ , r ′ ,然后对比一下单射函数的定义:
∀ a , b ∈ X , a ≠ b ⇒ f ( a ) ≠ f ( b ) \forall a, b \in \mathcal{X},\ a \ne b \Rightarrow f(a) \ne f(b)
∀ a , b ∈ X , a = b ⇒ f ( a ) = f ( b )
可以看出两者的表述是相似的,也就是说,如果令C o m c ( m , r ) → c m , r \rm{Com}^c(m, r) \rightarrow c_{m, r} Com c ( m , r ) → c m , r ,只有C o m c ( m , r ) \rm{Com}^c(m, r) Com c ( m , r ) 可被构造为一个单射函数,该承诺方案才会拥有完美绑定属性。或者换个说法,令C o m r c ( m ) → c m , r \rm{Com}_{r}^c(m) \rightarrow c_{m, r} Com r c ( m ) → c m , r ,需要符合下面两点:
∀ m , m ′ ∈ M ; ∀ r ∈ R ; m ≠ m ′ ⇒ C o m r c ( m ) ≠ C o m r c ( m ′ ) \forall m, m' \in \mathcal{M}\rm{;}\ \forall r \in \mathcal{R}\rm{;}\ m \ne m' \Rightarrow \rm{Com}_{r}^c(m) \ne \rm{Com}_{r}^c(m') ∀ m , m ′ ∈ M ; ∀r ∈ R ; m = m ′ ⇒ Com r c ( m ) = Com r c ( m ′ ) ;
∀ r , r ′ ∈ R , r ≠ r ′ ⇒ { C o m r c ( M ) } ∩ { C o m r ′ c ( M ) } = ∅ \forall r, r' \in \mathcal{R}, r \ne r' \Rightarrow \{\rm{Com}_{r}^c(\mathcal{M})\} \cap \{\rm{Com}_{r'}^c(\mathcal{M})\} = \empty ∀ r , r ′ ∈ R , r = r ′ ⇒ { Com r c ( M )} ∩ { Com r ′ c ( M )} = ∅ 。
简单论证一下:假设存在m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M 和r , r ′ ∈ R r, r' \in \mathcal{R} r , r ′ ∈ R 使得C o m r c ( m ) = C o m r ′ c ( m ′ ) \rm{Com}_{r}^c(m) = \rm{Com}_{r'}^c(m') Com r c ( m ) = Com r ′ c ( m ′ ) ,由第二点的两集合无交集可得只能r = r ′ r = r' r = r ′ ,即C o m r c ( m ) = C o m r c ( m ′ ) \rm{Com}_{r}^c(m) = \rm{Com}_{r}^c(m') Com r c ( m ) = Com r c ( m ′ ) ,由第一点的单射可得只能m = m ′ m = m' m = m ′ ,与假设矛盾,所以这样不同的m m m 和m ′ m' m ′ 不存在,即推出∀ m , m ′ ∈ M , ∀ r , r ′ ∈ R , m ′ ≠ m ⇒ c m , r ≠ c m ′ , r ′ \forall m,m' \in \mathcal{M},\ \forall r,r' \in \mathcal{R},\ m' \ne m \Rightarrow c_{m, r} \ne c_{m', r'} ∀ m , m ′ ∈ M , ∀ r , r ′ ∈ R , m ′ = m ⇒ c m , r = c m ′ , r ′ 。另外,若令C o m m c ( r ) → c m , r \rm{Com}_{m}^c(r) \rightarrow c_{m, r} Com m c ( r ) → c m , r ,也可以推出类似的条件。
根据以上推出的特性,可以尝试粗略地设计一种完美绑定的承诺方案的通用构造。假设F F F 是一个函数簇,对于所有的r ∈ R r\in \mathcal{R} r ∈ R ,F r : M → F F_r:\mathcal{M} \rightarrow \mathcal{F} F r : M → F ,G : R → G G: \mathcal{R} \rightarrow \mathcal{G} G : R → G 是两个单射的函数,则一种完美绑定的承诺方案可以这样设计:
A Toy Commitment Scheme with Perfectly Binding C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r r ← $ R f = F r ( m ) g = G ( r ) c = ( f , g ) ⟶ c ⋮ d = r ⟶ m , d If f = F d ( m ) and g = G ( d ) → Accept Otherwise → Reject \text{A Toy Commitment Scheme with Perfectly Binding} \\
\begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathcal{R} \\
f = F_r(m) \\
g = G(r) \\
c = (f, g)
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\ \\
\begin{array}{l} d = r \end{array} & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{lll}
\text{If } f = F_d(m) \text{ and } g = G(d) & \rightarrow & \text{Accept} \\
\text{Otherwise} & \rightarrow & \text{Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
A Toy Commitment Scheme with Perfectly Binding Commit : Open : Sender ( m ) r ← $ R f = F r ( m ) g = G ( r ) c = ( f , g ) ⋮ d = r ⟶ c ⟶ m , d Receiver If f = F d ( m ) and g = G ( d ) Otherwise → → Accept Reject
注:以上的构造只能保证完美绑定属性,如果还要计算上隐藏属性的话,还需要F F F 和G G G 拥有其他的性质。
以上完美绑定属性的论证并不难,首先假设攻击者可攻破完美绑定属性,则可以找到一个与m m m 不同的m ′ ∈ M m' \in \mathcal{M} m ′ ∈ M ,使得接收者输出接受;而若接收者输出接受则必须f = F d ( m ) f = F_d(m) f = F d ( m ) 且g = G ( d ) g = G(d) g = G ( d ) ,由于G G G 是单射的且d = r d=r d = r ,即f = F r ( m ) f = F_r(m) f = F r ( m ) ;所以若攻击者可以攻破完美绑定,即可以找到m ′ ≠ m m' \ne m m ′ = m 使得F r ( m ′ ) = f = F r ( m ) F_r(m') = f = F_r(m) F r ( m ′ ) = f = F r ( m ) ,和F r F_r F r 的单射属性相矛盾,所以不存在这样的攻击者。
可以参考实际的例子,ElGamal承诺方案就是利用类似的思路构造的。令G = < g > \mathbb{G} = <g> G =< g > 是一个素数q q q 阶的循环群,h , g ∈ G h, g \in \mathbb{G} h , g ∈ G 是两个随机的生成元,消息m ∈ G m \in \mathbb{G} m ∈ G ,则ElGamal承诺方案可以表示为:
ElGamal Commitment Scheme C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r r ← $ Z q c 0 = m h r c 1 = g r c = ( c 0 , c 1 ) ⟶ c ⋮ d = r ⟶ m , d If c = ( m h r , g r ) → Accept Otherwise → Reject \text{ElGamal Commitment Scheme} \\
\begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathbb{Z}_q \\
c_0 = mh^r \\
c_1 = g^r \\
c = (c_0, c_1)
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\ \\
\begin{array}{l} d = r \end{array} & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{lll}
\text{If } c = (mh^r, g^r) & \rightarrow & \text{Accept} \\
\text{Otherwise} & \rightarrow & \text{Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
ElGamal Commitment Scheme Commit : Open : Sender ( m ) r ← $ Z q c 0 = m h r c 1 = g r c = ( c 0 , c 1 ) ⋮ d = r ⟶ c ⟶ m , d Receiver If c = ( m h r , g r ) Otherwise → → Accept Reject
令F r ( m ) = m h r F_r(m) = mh^r F r ( m ) = m h r 、G ( r ) = g r G(r) = g^r G ( r ) = g r 这就是上面通用构造的一个实例化,显然F r ( m ) F_r(m) F r ( m ) 和G ( r ) G(r) G ( r ) 都是单射函数。
从满射函数到完美隐藏·
先复习一下完美隐藏的定义:∀ m , m ′ ∈ M , { c m , R } = { c m ′ , R } \forall m,m' \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \{c_{m', \mathcal{R}}\} ∀ m , m ′ ∈ M , { c m , R } = { c m ′ , R } ,这里假设C \mathcal{C} C 中不包含多余的承诺值,即C = { c m , r ∣ m ∈ M ; r ∈ R } \mathcal{C} = \{ c_{m, r}\ |\ m \in \mathcal{M}\rm{;}\ r \in \mathcal{R} \} C = { c m , r ∣ m ∈ M ; r ∈ R } ,则可以得到∀ m ∈ M , { c m , R } = C \forall m \in \mathcal{M},\ \{c_{m, \mathcal{R}}\} = \mathcal{C} ∀ m ∈ M , { c m , R } = C ,也即∀ m ∈ M ; ∀ c ∈ C ; \forall m \in \mathcal{M}\rm{;}\ \forall c \in \mathcal{C}\rm{;} ∀ m ∈ M ; ∀c ∈ C ; ∃ r ∈ R \exist r \in \mathcal{R} ∃ r ∈ R s . t . c m , r = c s.t.\ c_{m, r} = c s . t . c m , r = c 。类似地,对比满射的定义,设F : X → Y F: \mathcal{X} \to \mathcal{Y} F : X → Y ,则:
∀ y ∈ Y ; ∃ x ∈ X ; s . t . F ( x ) = y \forall y \in \mathcal{Y}\rm{;}\ \exist x \in \mathcal{X}\rm{;}\ s.t.\ F(x)=y
∀ y ∈ Y ; ∃x ∈ X ; s.t. F ( x ) = y
两个表述是相似的,如果令C o m m c ( r ) → c m , r \rm{Com}_{m}^c(r) \rightarrow c_{m, r} Com m c ( r ) → c m , r ,则当且仅当对所有m ∈ M m \in \mathcal{M} m ∈ M ,C o m m c ( r ) \rm{Com}_{m}^c(r) Com m c ( r ) 满射到C \mathcal{C} C 时,承诺方案拥有完美隐藏属性。
首先论证⇒ \Rightarrow ⇒ 方向:若对所有m ∈ M m \in \mathcal{M} m ∈ M ,C o m m c ( r ) \rm{Com}_{m}^c(r) Com m c ( r ) 满射到C \mathcal{C} C ,则∀ m ∈ M ; ∀ c ∈ C ; ∃ r ∈ R s . t . C o m m c ( r ) = c \forall m \in \mathcal{M}\rm{;}\ \forall c \in \mathcal{C}\rm{;}\ \exist r \in \mathcal{R}\ s.t. \rm{Com}_{m}^c(r)=c ∀ m ∈ M ; ∀c ∈ C ; ∃r ∈ R s.t. Com m c ( r ) = c ,即符合上面的完美隐藏定义推导;
接着论证⇐ \Leftarrow ⇐ 方向:假设存在某个m ∈ M m \in \mathcal{M} m ∈ M 使得C o m m c ( r ) \rm{Com}_{m}^c(r) Com m c ( r ) 不满射到C \mathcal{C} C ,则存在m ′ ∈ M m' \in \mathcal{M} m ′ ∈ M 和r ′ ∈ R r' \in \mathcal{R} r ′ ∈ R ,使得c ′ = C o m m ′ c ( r ′ ) ∉ { C o m m c ( R ) } c' = \rm{Com}_{m'}^c(r') \not\in \{ \rm{Com}_{m}^c(\mathcal{R}) \} c ′ = Com m ′ c ( r ′ ) ∈ { Com m c ( R )} ,可得c ′ ∈ ( { C o m m ′ c ( R ) } − { C o m m c ( R ) } ) ≠ ∅ c' \in (\{ \rm{Com}_{m'}^c(\mathcal{R}) \} - \{ \rm{Com}_{m}^c(\mathcal{R}) \}) \ne \empty c ′ ∈ ({ Com m ′ c ( R )} − { Com m c ( R )}) = ∅ ,即存在m ′ ∈ M m' \in \mathcal{M} m ′ ∈ M 和r ′ ∈ R r' \in \mathcal{R} r ′ ∈ R ,使得{ C o m m ′ c ( R ) } ≠ { C o m m c ( R ) } \{ \rm{Com}_{m'}^c(\mathcal{R}) \} \ne \{ \rm{Com}_{m}^c(\mathcal{R}) \} { Com m ′ c ( R )} = { Com m c ( R )} ,和完美隐藏的定义相悖,所以不存在这样的m m m 。
根据以上推出的特性,下面尝试粗略地设计一种完美隐藏的承诺方案的通用构造。假设F F F 是一个函数簇,对于所有的m ∈ M m\in \mathcal{M} m ∈ M ,F m F_m F m 都能从R \mathcal{R} R 满射到C \mathcal{C} C ,则一种完美隐藏的承诺方案可以这样设计:
A Toy Commitment Scheme with Perfectly Hiding C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r r ← $ R c = F m ( r ) ⟶ c ⋮ d = r ⟶ m , d If c = F m ( d ) → Accept Otherwise → Reject \text{A Toy Commitment Scheme with Perfectly Hiding} \\
\begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathcal{R} \\
c = F_m(r)
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\ \\
\begin{array}{l} d = r \end{array} & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{lll}
\text{If } c = F_m(d) & \rightarrow & \text{Accept} \\
\text{Otherwise} & \rightarrow & \text{Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
A Toy Commitment Scheme with Perfectly Hiding Commit : Open : Sender ( m ) r ← $ R c = F m ( r ) ⋮ d = r ⟶ c ⟶ m , d Receiver If c = F m ( d ) Otherwise → → Accept Reject
注:以上的构造只能保证完美隐藏属性,如果还要计算上隐藏属性的话,还需要F F F 拥有其他的性质。
以上完美隐藏属性的论证也不难,假设攻击者可以攻破完美隐藏属性,则可以仅根据c = F m ( r ) c = F_m(r) c = F m ( r ) 恢复m m m ,但由于∀ m ∗ ∈ M \forall m^* \in \mathcal{M} ∀ m ∗ ∈ M ,F m ∗ F_{m^*} F m ∗ 满射到C \mathcal{C} C ,即对于任意的m ∗ ∈ M m^* \in \mathcal{M} m ∗ ∈ M ,都可能存在r ∗ ∈ R r^* \in \mathcal{R} r ∗ ∈ R 使得F m ∗ ( r ∗ ) = c F_{m^*}(r^*) = c F m ∗ ( r ∗ ) = c ,所以攻击者不可能知道c c c 是由哪个m ∗ m^* m ∗ 选出的函数所映射的。
来个实际的例子,Pedersen承诺方案就是利用类似的思路构造承诺方案的。令G = < g > \mathbb{G} = <g> G =< g > 是一个素数q q q 阶的循环群,h , g ∈ G h, g \in \mathbb{G} h , g ∈ G 是两个随机的生成元,消息m ∈ Z q m \in \mathbb{Z}_q m ∈ Z q ,则Pedersen承诺方案可以表示为:
Pedersen Commitment Scheme C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r r ← $ Z q c = g m h r ⟶ c ⋮ d = r ⟶ m , d If c = g m h d → Accept Otherwise → Reject \text{Pedersen Commitment Scheme} \\
\begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathbb{Z}_q \\
c = g^mh^r
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\ \\
\begin{array}{l} d = r \end{array} & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{lll}
\text{If } c = g^mh^d & \rightarrow & \text{Accept} \\
\text{Otherwise} & \rightarrow & \text{Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
Pedersen Commitment Scheme Commit : Open : Sender ( m ) r ← $ Z q c = g m h r ⋮ d = r ⟶ c ⟶ m , d Receiver If c = g m h d Otherwise → → Accept Reject
令F m ( r ) = g m h r F_m(r) = g^mh^r F m ( r ) = g m h r ,这就是上面构造的一个实例化。显然对于所有m ∈ Z q m \in \mathbb{Z}_q m ∈ Z q ,F m F_m F m 满射到G \mathbb{G} G ,因为∣ Z q ∣ = ∣ G ∣ = q |\mathbb{Z}_q| = |\mathbb{G}| = q ∣ Z q ∣ = ∣ G ∣ = q ,假设存在某个m ∈ G m \in \mathbb{G} m ∈ G 使得F m F_m F m 不满射到G \mathbb{G} G ,则存在r ≠ r ′ ∈ Z q r \ne r' \in \mathbb{Z}_q r = r ′ ∈ Z q ,使得F m ( r ) = F m ( r ′ ) F_m(r) = F_m(r') F m ( r ) = F m ( r ′ ) ,即g m h r ≡ g m h r ′ g^mh^r \equiv g^mh^{r'} g m h r ≡ g m h r ′ ( i n G ) (\rm{in}\ \mathbb{G}) ( in G ) ,也即h r ≡ h r ′ ( i n G ) h^r \equiv h^{r'}\ (\rm{in}\ \mathbb{G}) h r ≡ h r ′ ( in G ) ,由于h h h 是G \mathbb{G} G 的生成元,即当且仅当r = r ′ r = r' r = r ′ 时成立,与假设矛盾。
从单向函数到计算上安全·
计算上安全的构造则没有那么直观,因为计算上安全要求是攻击成功的概率可忽略,就需要把安全性规约到某个难题上,但现有的难题五花八门,很难找到一种“模板”的构造方法。但也许可以用单向函数(One-way Function)做个尝试,首先看一下单向函数的定义:若函数f : X → Y f: \mathcal{X} \to \mathcal{Y} f : X → Y 是单向函数,则任何多项式算法F F F 算出f f f 的伪逆(Pseudo Inverse)的概率可忽略,即
P r [ f ( F ( f ( x ) ) ) = f ( x ) ] ≤ n e g l \rm{Pr}[f(F(f(x))) = f(x)] \le \rm{negl}
Pr [ f ( F ( f ( x ))) = f ( x )] ≤ negl
首先单向函数可以很直观地推出计算上隐藏属性,假设C o m r c ( m ) : M → C \rm{Com}_r^c(m): \mathcal{M} \to \mathcal{C} Com r c ( m ) : M → C 是单向函数,若攻击者A R \text{A}_\text{R} A R 可以在多项式时间内攻破隐藏属性,则会有A R ( C o m r c ( m ) ) = m \text{A}_\text{R}(\rm{Com}_r^c(m)) = m A R ( Com r c ( m )) = m ,即P r [ C o m r c ( A R ( C o m r c ( m ) ) ) = C o m r c ( m ) ] > n e g l \rm{Pr}[\rm{Com}_r^c(\text{A}_\text{R}(\rm{Com}_r^c(m))) = \rm{Com}_r^c(m)] > \rm{negl} Pr [ Com r c ( A R ( Com r c ( m ))) = Com r c ( m )] > negl ,可以调用A R \text{A}_\text{R} A R 攻击C o m r c ( m ) \rm{Com}_r^c(m) Com r c ( m ) 的单向性,即计算上隐藏的安全性可规约到C o m r c ( m ) \rm{Com}_r^c(m) Com r c ( m ) 的单向性。
计算上绑定的规约则每那么直观,可能需要先定义一个更宽松的绑定属性,在Adv Binding \text{Adv}_\text{Binding} Adv Binding 的定义中,攻击者A S \text{A}_\text{S} A S 需要在同一时间给出m m m 和m ′ m' m ′ ,但承诺方案中真正攻击的流程也许并不是这样的,比如在通用可组合框架的证明过程中的模拟者,需要先生成一个承诺值c ∈ C c \in \mathcal{C} c ∈ C ,然后由环境给出消息m ′ ∈ M m' \in \mathcal{M} m ′ ∈ M ,然后再由模拟者生成d ′ d' d ′ 把c c c 打开为m ′ m' m ′ 的承诺。根据这个流程,可以给出以下定义:
Adv Binding lossy ( A S ) = P r [ V e r i f y ( c , m ′ , d ′ ) = Accept : c ← A S ( ) ; c ∈ C ; m ′ ← $ M ; d ′ ← A S m ′ ( c ) ; d ′ ∈ D ; ] \text{Adv}^\text{lossy}_\text{Binding}(\text{A}_\text{S}) = Pr\begin{bmatrix}
\begin{array}{ccc}
\begin{array}{l}
\rm{Verify(c, m', d')} = \text{Accept}
\end{array}
& \rm{:} &
\begin{array}{l}
c \leftarrow \text{A}_\text{S}() \rm{;} \ \
c \in \mathcal{C} \rm{;} \\
m' \overset{\$}{\leftarrow} \mathcal{M} \rm{;} \\
d' \leftarrow \text{A}^{m'}_\text{S}(c) \rm{;} \ \
d' \in \mathcal{D} \rm{;} \\
\end{array}
\end{array}
\end{bmatrix}
Adv Binding lossy ( A S ) = P r ⎣ ⎡ Verify ( c , m ′ , d ′ ) = Accept : c ← A S ( ) ; c ∈ C ; m ′ ← $ M ; d ′ ← A S m ′ ( c ) ; d ′ ∈ D ; ⎦ ⎤
这里由于m ′ m' m ′ 是随机选择而不是让攻击者选择,所以定义变宽松了而且安全性也变弱,但是证明时的可操作空间也更大。现在假设C o m m c ( r ) : R → C \rm{Com}_m^c(r): \mathcal{R} \to \mathcal{C} Com m c ( r ) : R → C 是单向函数,且假设在构造时令d = r d=r d = r (或者使用类似的构造),假设V e r i f y ( c ∗ , m , r ) : = C o m m c ( r ) = ? c \rm{Verify}(c^*, m, r) := \rm{Com}_m^c(r) \overset{?}{=} c Verify ( c ∗ , m , r ) := Com m c ( r ) = ? c 的运算并对比得出的值是否和承诺值c c c 相等。因为A S \text{A}_\text{S} A S 在生成c c c 时并不知道m ′ m' m ′ 的任何信息,所以对于C o m m ′ \rm{Com}_{m'} Com m ′ 来说c c c 是一个完全随机的像,而在选出m ′ m' m ′ 后,若A S \text{A}_\text{S} A S 输出的d ′ d' d ′ 可以通过验证,则C o m m ′ ( d ′ ) = c \rm{Com}_{m'}(d') = c Com m ′ ( d ′ ) = c ,即有P r [ C o m m ′ c ( A S ( c ) ) = c ] > n e g l \rm{Pr}[\rm{Com}_{m'}^c(\text{A}_\text{S}(c)) = c] > \rm{negl} Pr [ Com m ′ c ( A S ( c )) = c ] > negl ,和C o m m c \rm{Com}_m^c Com m c 是单向函数的假设冲突。虽然论证如是说,但由于不能自由控制c c c 的选取,并不能直观地进行规约,所以这里的证明能否通过还需要斟酌。
从陷门置换到后门属性·
由于模棱两可和提取这两个后门属性都需要一个后门值,所以考虑后门属性的构造时,最先想到的会是陷门函数(Trapdoor Function)。陷门函数本身也是一个单向函数,单向函数要求求出伪逆的概率可忽略,而陷门函数则说,如果知道后门的话,则存在可以容易地求出逆(或伪逆)的逆函数,假设F : X → Y F: \mathcal{X} \to \mathcal{Y} F : X → Y 是陷门函数、G e n \rm{Gen} Gen 是密钥生成函数、I n v e r t \rm{Invert} Invert 是逆函数,则:
( p k , t d ) ← G e n ( 1 κ ) (pk, td) \leftarrow \rm{Gen}(1^\kappa) ( p k , t d ) ← Gen ( 1 κ ) ;
x ′ ← I n v e r t t d ( F p k ( x ) ) , F p k ( x ) = F p k ( x ′ ) x' \leftarrow \rm{Invert}_{td}(F_{pk}(x)),\ F_{pk}(x) = F_{pk}(x') x ′ ← Invert td ( F pk ( x )) , F pk ( x ) = F pk ( x ′ ) 。
陷门置换(Trapdoor Permutation)则是双射的陷门函数。
利用陷门置换构造提取属性是直观的,假设C o m p k , r c ( m ) : M → C \rm{Com}_{pk,r}^c(m): \mathcal{M} \to \mathcal{C} Com pk , r c ( m ) : M → C 是一个陷门置换,令
E x t r a t d ( c ) : = I n v e r t t d C o m p k , r c ( c ) \rm{Extra}_{td}(c) := \rm{Invert}^{\rm{Com}_{pk,r}^c}_{td}(c)
Extra td ( c ) := Invert td Com pk , r c ( c )
即可实现提取操作。由于C o m p k , r c ( m ) \rm{Com}_{pk,r}^c(m) Com pk , r c ( m ) 是双射的,即至少是单射的,也即不存在m ′ ≠ m ∈ M m' \ne m \in \mathcal{M} m ′ = m ∈ M 使得C o m p k , r c ( m ′ ) = c \rm{Com}_{pk,r}^c(m')=c Com pk , r c ( m ′ ) = c ,自然E x t r a t d \rm{Extra}_{td} Extra td 提取出m ′ ≠ m m' \ne m m ′ = m ,即提取出来的是真实的逆,不是伪逆。
然后是利用陷门置换构造模棱两可属性,假设C o m p k , m c ( r ) : R → C \rm{Com}_{pk,m}^c(r): \mathcal{R} \to \mathcal{C} Com pk , m c ( r ) : R → C 是陷门置换,且假设在构造时令d = r d=r d = r (或者使用类似的构造),假设V e r i f y p k ( c ∗ , m , r ) : = C o m p k , m c ( r ) = ? c ∗ \rm{Verify}_{pk}(c^*, m, r) := \rm{Com}_{pk, m}^c(r) \overset{?}{=} c^* Verify pk ( c ∗ , m , r ) := Com pk , m c ( r ) = ? c ∗ 的运算并对比得出的值是否和承诺值c c c 相等。令
E q u i v t d ( m , m ′ , r ) : = I n v e r t t d C o m p k , m ′ c ( C o m p k , m c ( r ) ) \rm{Equiv}_{td}(m, m', r) := \rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))
Equiv td ( m , m ′ , r ) := Invert td Com pk , m ′ c ( Com pk , m c ( r ))
即可实现模棱两可操作。由于C o m p k , m c \rm{Com}_{pk,m}^c Com pk , m c 双射到C \mathcal{C} C ,即c = C o m p k , m c ( r ) ∈ C c = \rm{Com}_{pk,m}^c(r) \in \mathcal{C} c = Com pk , m c ( r ) ∈ C ,且存在唯一的r ′ ∈ R r' \in \mathcal{R} r ′ ∈ R 使得C o m p k , m ′ c ( r ′ ) = c \rm{Com}_{pk,m'}^c(r') = c Com pk , m ′ c ( r ′ ) = c ,可得r ′ = E q u i v t d ( m , m ′ , r ) = I n v e r t t d C o m p k , m ′ c ( C o m p k , m c ( r ) ) r' = \rm{Equiv}_{td}(m, m', r) = \rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r)) r ′ = Equiv td ( m , m ′ , r ) = Invert td Com pk , m ′ c ( Com pk , m c ( r )) ,代入V e r i f y p k ( c , m ′ , r ′ ) \rm{Verify}_{pk}(c, m', r') Verify pk ( c , m ′ , r ′ ) ,根据陷门函数的性质可得
C o m p k , m ′ c ( r ′ ) = C o m p k , m ′ c ( I n v e r t t d C o m p k , m ′ c ( C o m p k , m c ( r ) ) ) = C o m p k , m c ( r ) = c \rm{Com}_{pk, m'}^c(r') = \rm{Com}_{pk, m'}^c(\rm{Invert}^{\rm{Com}_{pk,m'}^c}_{td}(\rm{Com}_{pk,m}^c(r))) = \rm{Com}_{pk,m}^c(r) = c
Com pk , m ′ c ( r ′ ) = Com pk , m ′ c ( Invert td Com pk , m ′ c ( Com pk , m c ( r ))) = Com pk , m c ( r ) = c
验证通过。
以下利用上述构造思路构造两种承诺方案,并给出相应的证明。
例子一·
首先尝试构造计算上绑定、完美隐藏且拥有模棱两可属性的承诺方案。假设F : R → F F: \mathcal{R} \to \mathcal{F} F : R → F 是一个陷门置换,公钥为p k pk p k 、后门为t d td t d ;设G G G 是一个置换的簇,由m ∈ M m \in \mathcal{M} m ∈ M 选出一个置换函数G m : F → C G_m: \mathcal{F} \to \mathcal{C} G m : F → C ,且在知道m m m 时存在多项式算法G m − 1 G_m^{-1} G m − 1 计算置换的逆,则该承诺方案可以构造为:
C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r r ← $ R c = G m ( F p k ( r ) ) ⟶ c ⋮ d = r ⟶ m , d If c = G m ( F p k ( d ) ) → Accept Otherwise → Reject \begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathcal{R} \\
c = G_m(F_{pk}(r))
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\ \\
\begin{array}{l} d = r \end{array} & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{lll}
\text{If } c = G_m(F_{pk}(d)) & \rightarrow & \text{Accept} \\
\text{Otherwise} & \rightarrow & \text{Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
Commit : Open : Sender ( m ) r ← $ R c = G m ( F p k ( r )) ⋮ d = r ⟶ c ⟶ m , d Receiver If c = G m ( F p k ( d )) Otherwise → → Accept Reject
下面作简略证明:
计算上绑定:假设多项式时间的攻击者A S \text{A}_\text{S} A S 的Adv Binding ( A S ) \text{Adv}_\text{Binding}(\text{A}_\text{S}) Adv Binding ( A S ) 优势不可忽略,则可以找到m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M 和r , r ′ ∈ R r, r' \in \mathcal{R} r , r ′ ∈ R 使得G m ( F p k ( r ) ) = G m ′ ( F p k ( r ′ ) ) G_m(F_{pk}(r)) = G_{m'}(F_{pk}(r')) G m ( F p k ( r )) = G m ′ ( F p k ( r ′ )) ,则在不知道t d td t d 的情况下有不可忽略的概率可以算出r ’ ∈ R r’ \in \mathcal{R} r ’ ∈ R 使得F p k ( r ′ ) = G m ′ − 1 ( G m ( F p k ( r ) ) ) F_{pk}(r') = G_{m'}^{-1}(G_{m}(F_{pk}(r))) F p k ( r ′ ) = G m ′ − 1 ( G m ( F p k ( r ))) 即,
P r [ F p k ( A S ( F p k ( r ) ) ) = F p k ( r ) ] > n e g l \rm{Pr}[F_{pk}(\text{A}_\text{S}(F_{pk}(r))) = F_{pk}(r)] > \rm{negl}
Pr [ F pk ( A S ( F pk ( r ))) = F pk ( r )] > negl
从而攻破F p k F_{pk} F p k 的单向性。
完美隐藏:由于F p k F_{pk} F p k 和G m G_m G m 都双射,所以对于任意m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M ,
{ G m ( F p k ( R ) ) } = { G m ( F ) } = C = { G m ′ ( F ) } = { G m ′ ( F p k ( R ) ) } \{ G_m(F_{pk}(\mathcal{R})) \} = \{ G_m(\mathcal{F}) \} = \mathcal{C} = \{ G_{m'}(\mathcal{F}) \} = \{ G_{m'}(F_{pk}(\mathcal{R})) \}
{ G m ( F p k ( R ))} = { G m ( F )} = C = { G m ′ ( F )} = { G m ′ ( F p k ( R ))}
Adv Hiding ( A R ) = 0 \text{Adv}_\text{Hiding}(\text{A}_\text{R})=0 Adv Hiding ( A R ) = 0 。
模棱两可:和计算上绑定的证明类似,但知道t d td t d 的情况下可以对F p k F_{pk} F p k 求逆,
E q u i v t d ( m , m ′ , d ) : = I n v e r t t d F ( G m ′ − 1 ( G m ( F p k ( r ) ) ) ) \rm{Equiv}_{td}(m, m', d) := \rm{Invert}_{td}^{F}(G_{m'}^{-1}(G_{m}(F_{pk}(r))))
Equiv td ( m , m ′ , d ) := Invert td F ( G m ′ − 1 ( G m ( F pk ( r ))))
例子二·
接下来尝试构造完美绑定、计算上隐藏且拥有提取属性的承诺方案。假设F F F 是一个函数簇,对于所有的r ∈ R r\in \mathcal{R} r ∈ R ,F r : M → F F_r:\mathcal{M} \rightarrow \mathcal{F} F r : M → F 是单射函数,且在知道m m m 时存在多项式算法I n d e x F ( m ) : = r \rm{Index}^F(m) := r Index F ( m ) := r 计算选择函数的值,在知道r r r 时存在多项式算法F r − 1 F_r^{-1} F r − 1 计算函数的逆;G : R → G G: \mathcal{R} \rightarrow \mathcal{G} G : R → G 是单射的陷门函数,公钥为p k pk p k 、私钥为t d td t d ,则该承诺方案可以构造为:
C o m m i t : O p e n : S e n d e r ( m ) R e c e i v e r r ← $ R f = F r ( m ) g = G p k ( r ) c = ( f , g ) ⟶ c ⋮ d = r ⟶ m , d If f = F d ( m ) and g = G p k ( d ) → Accept Otherwise → Reject \begin{array}{|lc|}
\hline \\
\begin{array}{c}
\rm{Commit: } \\ \\ \\ \\ \\ \\ \\ \rm{Open: } \\ \\ \\ \\
\end{array} &
\begin{array}{lcl}
\mathrm{Sender}(m) & \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Receiver} \\
\begin{array}{l}
r \overset{\$}{\leftarrow} \mathcal{R} \\
f = F_r(m) \\
g = G_{pk}(r) \\
c = (f, g)
\end{array} & & \\
& \overset{c}{\longrightarrow} & \\
\vdots & & \\ \\
\begin{array}{l} d = r \end{array} & & \\
& \overset{m,\ d}{\longrightarrow} & \\
& & \begin{array}{lll}
\text{If } f = F_d(m) \text{ and } g = G_{pk}(d) & \rightarrow & \text{Accept} \\
\text{Otherwise} & \rightarrow & \text{Reject}
\end{array} \\
\end{array} \\
\hline
\end{array}
Commit : Open : Sender ( m ) r ← $ R f = F r ( m ) g = G p k ( r ) c = ( f , g ) ⋮ d = r ⟶ c ⟶ m , d Receiver If f = F d ( m ) and g = G p k ( d ) Otherwise → → Accept Reject
以下作简略证明:
完美绑定:假设Adv Binding ( A S ) ≠ 0 \text{Adv}_\text{Binding}(\text{A}_\text{S})\ne 0 Adv Binding ( A S ) = 0 ,则存在m ≠ m ′ ∈ M m \ne m' \in \mathcal{M} m = m ′ ∈ M 和r , r ′ ∈ R r, r' \in \mathcal{R} r , r ′ ∈ R 使得F r ( m ) = F r ′ ( m ′ ) F_r(m) = F_{r'}(m') F r ( m ) = F r ′ ( m ′ ) 和G p k ( r ) = G p k ( r ′ ) G_{pk}(r) = G_{pk}(r') G p k ( r ) = G p k ( r ′ ) ,由于G p k G_{pk} G p k 是单射函数,所以r = r ′ r = r' r = r ′ ,即F r ( m ) = F r ( m ′ ) F_r(m) = F_{r}(m') F r ( m ) = F r ( m ′ ) ,由于F r F_r F r 也是单射函数,所以m = m ′ m = m' m = m ′ ,与假设矛盾,所以Adv Binding ( A S ) = 0 \text{Adv}_\text{Binding}(\text{A}_\text{S}) = 0 Adv Binding ( A S ) = 0 。
计算上隐藏:假设多项式时间的攻击者A R \text{A}_\text{R} A R 的Adv Hiding ( A R ) \text{Adv}_\text{Hiding}(\text{A}_\text{R}) Adv Hiding ( A R ) 优势不可忽略,则可以在不知道t d td t d 的情况下根据F r ( m ) F_r(m) F r ( m ) 和G p k ( r ) G_{pk}(r) G p k ( r ) 算出m m m ,随即可以算出r = I n d e x F ( m ) r = \rm{Index}^F(m) r = Index F ( m ) ,即
P r [ G p k ( A R ( G p k ( r ) ) ) = G p k ( r ) ] > n e g l \rm{Pr}[G_{pk}(\text{A}_\text{R}(G_{pk}(r))) = G_{pk}(r)] > \rm{negl}
Pr [ G pk ( A R ( G pk ( r ))) = G pk ( r )] > negl
从而攻破G p k G_{pk} G p k 的单向性。
提取:和计算上隐藏的证明类似,但在知道t d td t d 的情况下可以对G p k G_{pk} G p k 求逆:
E x t r a t d ( c ) : = F I n v e r t t d G ( g ) − 1 ( c ) \rm{Extra}_{td}(c) := F^{-1}_{\rm{Invert}_{td}^G(g)}(c)
Extra td ( c ) := F Invert td G ( g ) − 1 ( c )
额外的思路·
例子一中的G G G 函数和例子二的F F F 函数其实都可以利用异或操作构造。
首先,当n ∈ Z + n \in \mathbb{Z^+} n ∈ Z + 、a , b ∈ { 0 , 1 } n a,b \in \{0, 1\}^n a , b ∈ { 0 , 1 } n 时,函数F a ( b ) : = a ⨁ b F_a(b) := a \bigoplus b F a ( b ) := a ⨁ b 是一个{ 0 , 1 } n → { 0 , 1 } n \{0, 1\}^n \to \{0, 1\}^n { 0 , 1 } n → { 0 , 1 } n 的置换:
单射性:假设存在b ≠ b ′ ∈ { 0 , 1 } n b \ne b' \in \{0, 1\}^n b = b ′ ∈ { 0 , 1 } n 使得F a ( b ) = F a ( b ′ ) F_a(b) = F_a(b') F a ( b ) = F a ( b ′ ) ,则a ⨁ b = a ⨁ b ′ a \bigoplus b = a \bigoplus b' a ⨁ b = a ⨁ b ′ ,则b = b ′ b = b' b = b ′ ,矛盾。所以
∀ a ∈ { 0 , 1 } n ; ∀ b , b ′ ∈ { 0 , 1 } n ; b ≠ b ′ ⇒ F a ( b ) ≠ F a ( b ′ ) \forall a \in \{0, 1\}^n \rm{;}\ \forall b, b' \in \{0, 1\}^n \rm{;}\ b \ne b' \Rightarrow F_a(b) \ne F_a(b')
∀ a ∈ { 0 , 1 } n ; ∀b , b ′ ∈ { 0 , 1 } n ; b = b ′ ⇒ F a ( b ) = F a ( b ′ )
满射性:假设存在c ∈ { 0 , 1 } n c \in \{0, 1\}^n c ∈ { 0 , 1 } n 使得∀ b ∈ { 0 , 1 } n , F a ( b ) ≠ c \forall b \in \{0, 1\}^n,\ F_a(b) \ne c ∀ b ∈ { 0 , 1 } n , F a ( b ) = c ,由于F a F_a F a 定义域与值域相同,则∃ b ≠ b ′ s . t . F a ( b ) = F a ( b ′ ) \exist b \ne b'\ s.t.\ F_a(b) = F_a(b') ∃ b = b ′ s . t . F a ( b ) = F a ( b ′ ) ,即∃ b ≠ b ′ s . t . a ⨁ b = a ⨁ b ′ \exist b \ne b'\ s.t.\ a \bigoplus b = a \bigoplus b' ∃ b = b ′ s . t . a ⨁ b = a ⨁ b ′ ,当且仅当∃ b ≠ b ′ s . t . b = b ′ \exist b \ne b'\ s.t.\ b = b' ∃ b = b ′ s . t . b =