0


安全多方计算之四:比特承诺

比特承诺

1. 简介

比特承诺方案是密码协议的重要成分,广泛应用于电子拍卖、商业谈判、电子投票、电子现金和在线游戏等领域,还可以用于零知识证明、身份认证和安全多方计算协议等。

比特承诺方案(Bit Commitment Scheme)解决这样的问题:Alice向Bob承诺一个预测(比特值),直到一段时间之后才揭示着预测(比特值);在这期间,Alice不能改变自己的预测(比特值)。

比特承诺的一个直观例子:Alice 把消息

     M 
    
   
  
    M 
   
  
M(承诺)放在一个箱子里(只有Alice有钥匙)并将它锁住送给Bob,等到 Alice 决定向 Bob证实消息 
 
  
   
   
     M 
    
   
  
    M 
   
  
M时,Alice把消息 
 
  
   
   
     M 
    
   
  
    M 
   
  
M及钥匙给 Bob,Bob 能够打开箱子并验证箱子里的消息同 Alice出示的消息是否相同,且Bob 确信箱子里的消息在他保管期间没有被篡改。

比特承诺包括两个阶段:

  • 承诺阶段:Alice选择一个要承诺的比特或比特序列 b b b,并把能表示该比特的消息 c c c发送至Bob。
  • 打开阶段:Alice把打开承诺的消息 d d d与承诺 b b b,发送至Bob;Bob用 d d d打开消息 c c c,验证 b b b是否为A承诺的比特。

一个安全的比特承诺方案需满足以下两个性质:

  • 隐藏性:承诺阶段,接收方Bob不能得到发送方Alice承诺的比特值。一个承诺方案是完善隐蔽的,如果接收方不能从发送的消息中得到关于承诺的任何消息。
  • 绑定性:给定承诺阶段的交互信息,接收者只能接受一个合法的承诺。即发送方不能在打开承诺的阶段改变自己承诺的比特。

常见的比特承诺方案有基于对称密码算法的,基于单向函数的以及基于数学难解问题的,包括基于大数分解的与基于离散对数的等。

2. 基于对称密码算法的比特承诺方案

承诺者Alice要向检验者Bob承诺

     b 
    
   
  
    b 
   
  
b,基于对称密码算法的比特承诺方案如下:

Alice 和 Bob 共同选定某种对称加密算法

     E 
    
   
  
    E 
   
  
E

承诺阶段

  • Bob产生一个随机比特串 r r r并发送给 Alice
  • Alice 随机选择一个密钥 k k k,利用对称加密算法 E E E对 r r r和需承诺的比特 b b b加密得 c = E ( r , b ) c=E(r,b) c=E(r,b),最后将加密后的结果 c c c发送给验证者 Bob

打开阶段

  • 当需要 Alice 公开承诺时,她将密钥 k k k和承诺的比特 b b b发送给 Bob
  • Bob利用密钥 k k k解密 c c c,并利用他的随机串 r r r检验比特 b b b的有效性。

3. 基于单向函数的比特承诺方案

承诺者Alice要向检验者Bob承诺

     b 
    
   
  
    b 
   
  
b,基于单向函数的比特承诺方案如下:

Alice和Bob共同选定一个单向函数

     H 
    
   
     ( 
    
   
     ⋅ 
    
   
     ) 
    
   
  
    H(·) 
   
  
H(⋅),如Hash函数

承诺阶段

  • Alice生成两个随机数 r 1 , r 2 r_1,r_2 r1​,r2​,计算单向函数值 h = H ( r 1 , r 2 , M ) h=H(r_1,r_2,M) h=H(r1​,r2​,M),并将散列结果 h h h和其中一个随机数,如 r 1 r_1 r1​发送给Bob

打开阶段

  • 当Alice向Bob出示承诺 b b b时,把承诺 b b b和另一个随机数 r 2 r_2 r2​一起发送给Bob
  • Bob计算 H ( r 1 , r 2 , M ) H(r_1,r_2,M) H(r1​,r2​,M)的值,并与第(2)步收到的 h h h值做比较,验证承诺 b b b的有效性。

Alice通过发送随机数

      r 
     
    
      1 
     
    
   
  
    r_1 
   
  
r1​对 
 
  
   
   
     b 
    
   
  
    b 
   
  
b做出承诺,也就是说散列值 
 
  
   
   
     h 
    
   
  
    h 
   
  
h和随机数 
 
  
   
    
    
      r 
     
    
      1 
     
    
   
  
    r_1 
   
  
r1​构成了Alice向Bob承诺的证据。

该协议的优点是Bob不必发送任何消息。

4. Pederson承诺协议

承诺者Alice要向检验者Bob承诺

     m 
    
   
  
    m 
   
  
m,Pederson的比特承诺方案如下:

系统参数:

     p 
    
   
     、 
    
   
     q 
    
   
  
    p、q 
   
  
p、q是大素数,且 
 
  
   
   
     q 
    
   
     / 
    
   
     p 
    
   
     − 
    
   
     1 
    
   
  
    q/p-1 
   
  
q/p−1 , 满足 
 
  
   
    
    
      Z 
     
    
      p 
     
    
   
  
    Z_{p} 
   
  
Zp​中离散对数问题是难解的,  
 
  
   
   
     g 
    
   
  
    g 
   
  
g 是 
 
  
   
    
    
      Z 
     
    
      p 
     
    
      ∗ 
     
    
   
  
    Z_{p}^{*} 
   
  
Zp∗​ 的 本原元,随机数 
 
  
   
   
     y 
    
   
     ∈ 
    
    
    
      Z 
     
    
      p 
     
    
      ∗ 
     
    
   
  
    y \in Z_{p}^{*} 
   
  
y∈Zp∗​

承诺阶段:

Alice 选择需要承诺的消息比特串

     m 
    
   
     ∈ 
    
    
    
      Z 
     
    
      q 
     
    
   
  
    m \in Z_{q} 
   
  
m∈Zq​, 并生成随机数 
 
  
   
   
     r 
    
   
     ∈ 
    
    
    
      Z 
     
    
      q 
     
    
      ∗ 
     
    
   
  
    r \in Z_{q}^{*} 
   
  
r∈Zq∗​; 计算 
 
  
   
   
     c 
    
   
     = 
    
    
    
      g 
     
    
      r 
     
    
    
    
      y 
     
    
      m 
     
     
    
     
     
       m 
      
     
       o 
      
     
       d 
      
     
     
   
     p 
    
   
  
    c= g^{r} y^{m} \bmod p 
   
  
c=grymmodp 作为对消息 
 
  
   
   
     m 
    
   
  
    m 
   
  
m的承诺,将 
 
  
   
   
     c 
    
   
  
    c 
   
  
c发送至 Bob。

打开阶段

Alice将

     m 
    
   
  
    m 
   
  
m与 
 
  
   
   
     r 
    
   
  
    r 
   
  
r发送至Bob;Bob通过收到的 
 
  
   
   
     r 
    
   
  
    r 
   
  
r打开承诺,验证 
 
  
   
   
     c 
    
   
  
    c 
   
  
c的计算是否与收到的承诺一致。如果一致,则认为承诺有效,否则无效。

本文转载自: https://blog.csdn.net/apr15/article/details/128448977
版权归原作者 机器学习Zero 所有, 如有侵权,请联系我们删除。

“安全多方计算之四:比特承诺”的评论:

还没有评论