对安全性证明中DH BDH等相关假设的理解（安全）

对安全性证明中DH BDH等相关假设的理解

前言

密码学的安全本质上依赖于数学问题中的未解“难题”。注意，这些“难题”到目前为止还未找到一种多项式的解决算法，至于这种算法是否存在，未来能否被找到则是无法证明的。既然目前不存在一种多项式算法来解决某一难题，那我们就可以假设这个问题很难，在多项式时间内无法被解决。实际上，CDH DDH等假设正是基于这种考虑，就是在假设所对应的CDH DDH问题很难不能在多项式时间内解决。如果你不同意我的假设，你就需要提供存在一种多项式解法（很难的啦）。

为什么要强调多项式时间？因为任何“难题”都只是说没有快速的解法，而非不可解。毕竟在不考虑时间成本时，暴力法是所有问题的通用解法。当然，运气法也可以。

在安全性分析中，当我们想通过某一假设来证明方案的安全性时，我们首先需要将方案的安全性问题归约为对应的问题上。之后，我们可以得出结论：如果假设A成立（引用别人的假设文献作为定理），那么任何攻击者都无法在多项式时间内破解我们的方案，因为任何攻击者都无法在多项式时间内解决问题A。结论是基于假设的，而假设是具有时效性的。例如，如果某一天某个天才破解了问题A，那么上述的推断就不成立了。因此，在未来的某一天，我们现在提出的假设都可能被推翻。

定义

DH假设

DH问题来自于1976年提出的Diffie-Hellman密钥交换协议，其数学定义可以描述为：

给定

      < 
     
    
      g 
     
    
      , 
     
    
      p 
     
    
      , 
     
     
     
       g 
      
     
       a 
      
     
    
        
     
    
      ( 
     
    
      m 
     
    
      o 
     
    
      d 
     
    
        
     
    
      p 
     
    
      ) 
     
    
      , 
     
     
     
       g 
      
     
       b 
      
     
    
        
     
    
      ( 
     
    
      m 
     
    
      o 
     
    
      d 
     
    
        
     
    
      p 
     
    
      ) 
     
    
      > 
     
    
   
     <g,p,g^a\ (mod\ p),g^b\ (mod\ p)> 
    
   
 <g,p,ga (mod p),gb (mod p)>，攻击者能否在多项式时间内计算出 
  
   
    
     
     
       g 
      
      
      
        a 
       
      
        b 
       
      
     
    
        
     
    
      ( 
     
    
      m 
     
    
      o 
     
    
      d 
     
    
        
     
    
      p 
     
    
      ) 
     
    
   
     g^{ab}\ (mod\ p) 
    
   
 gab (mod p)？

该问题依赖的数学难题是离散对数问题（Discrete Logarithm Problem，DLP）。DH假设的就是在说DLP问题很难，因此DH问题也很难。很明显，这是成立的，因为离散对数问题至今仍未被解决。想要推翻这个假设你就得解决DLP问题，总不能拿不出证据又不承认。

CDH假设和DDH假设

CDH假设（Computational Diffie-Hellman Assumption）和DDH假设（Decisional Diffie-Hellman Assumption）是DH假设的变体，将线性离散问题转移到群论离散问题。我们说过，假设都是对应问题的，两者所对应的问题分别为：

Computational Diffie-Hellman Problem（CDHP）：
对于循环群

      G 
     
    
   
     G 
    
   
 G和生成元 
  
   
    
    
      g 
     
    
   
     g 
    
   
 g，给定 
  
   
    
    
      < 
     
    
      G 
     
    
      , 
     
    
      g 
     
    
      , 
     
     
     
       g 
      
     
       a 
      
     
    
      , 
     
     
     
       g 
      
     
       b 
      
     
    
      > 
     
    
   
     <G,g,g^a,g^b> 
    
   
 <G,g,ga,gb>，攻击者能否在多项式时间**计算**出 
  
   
    
     
     
       g 
      
      
      
        a 
       
      
        b 
       
      
     
    
   
     g^{ab} 
    
   
 gab?

Decisional Diffie-Hellman Problem（DDHP）：
对于循环群

      G 
     
    
   
     G 
    
   
 G和生成元 
  
   
    
    
      g 
     
    
   
     g 
    
   
 g，给定 
  
   
    
    
      < 
     
    
      G 
     
    
      , 
     
    
      g 
     
    
      , 
     
     
     
       g 
      
     
       a 
      
     
    
      , 
     
     
     
       g 
      
     
       b 
      
     
    
      , 
     
     
     
       g 
      
     
       c 
      
     
    
      > 
     
    
   
     <G,g,g^a,g^b,g^c> 
    
   
 <G,g,ga,gb,gc>，攻击者能否在多项式时间**判断**出 
  
   
    
     
     
       g 
      
     
       c 
      
     
     
      
       
       
         = 
        
       
      
        ? 
       
      
     
     
     
       g 
      
      
      
        a 
       
      
        b 
       
      
     
    
   
     g^c\overset{\text{?}}{=}g^{ab} 
    
   
 gc=?gab?

类似的，CDH假设就是认为CDHP无多项式时间解，而DDH假设是认为DDHP无多项式时间解。

问题1，CDHP和DDHP的差异在哪？哪个更难解决？从上面的问题定义中可以看出，两者主要差异是对攻击者的要求，前者要求攻击者计算出结果，而后者要求攻击者判断一个结果对不对。那么哪个更难呢？答案是CDHP难于DDHP，因为如果你能解决CDHP，那你就能解决DDHP。试想，你都能算出

      g 
     
     
     
       a 
      
     
       b 
      
     
    
   
  
    g^{ab} 
   
  
gab了，还能不知道 
 
  
   
    
    
      g 
     
    
      c 
     
    
    
     
      
      
        = 
       
      
     
       ? 
      
     
    
    
    
      g 
     
     
     
       a 
      
     
       b 
      
     
    
   
  
    g^c\overset{\text{?}}{=}g^{ab} 
   
  
gc=?gab。但是反过来不行啊，你不能说我知道了 
 
  
   
    
    
      g 
     
    
      c 
     
    
   
     ≠ 
    
    
    
      g 
     
     
     
       a 
      
     
       b 
      
     
    
   
  
    g^c\ne g^{ab} 
   
  
gc=gab我就知道了 
 
  
   
    
    
      g 
     
     
     
       a 
      
     
       b 
      
     
    
   
  
    g^{ab} 
   
  
gab。DDHP可以看作是CDHP的放松版，简单点说就是，你算不出来不要紧，我给你个数，你验证一下是不是正确解就完事了。所以，我们得出：在问题难度方面， 
 
  
   
   
     C 
    
   
     D 
    
   
     H 
    
   
     P 
    
   
     ≥ 
    
   
     D 
    
   
     D 
    
   
     H 
    
   
     P 
    
   
  
    CDHP\ge DDHP 
   
  
CDHP≥DDHP。我们再把DLP也算上。同样的道理，解决了DLP就能解决CDHP，但是解决了CDHP不一定能解决DLP，因此我们可以得出结论：在问题难度方面， 
 
  
   
   
     D 
    
   
     L 
    
   
     P 
    
   
     ≥ 
    
   
     C 
    
   
     D 
    
   
     H 
    
   
     P 
    
   
     ≥ 
    
   
     D 
    
   
     D 
    
   
     H 
    
   
     P 
    
   
  
    DLP\ge CDHP\ge DDHP 
   
  
DLP≥CDHP≥DDHP。

问题2，是否问题越难，所对应的假设越强？答案是否。假设的强度与问题的难度相反，问题越难，假设越弱。注意，这里的强弱是指安全等级，因为假设是用在安全分析上的，不是说假设越弱越容易被推翻，因为所有的假设都是基于离散问题的，都是成立的，都是难解的“难题”，切勿误解。试想一下，如果我们的系统A在数学上满足DDH假设，也就是说没有人能够在多项式时间内解决DDHP。你连最简单的DDHP都解决不了，就更不可能解决CDHP了。就好比你连加法都不会，还想学高等数学？反过来，如果我们的系统B在数学上只满足CDH假设，也就意味着攻击者能够解决DDHP。对比而言，攻击者在B上能做的计算更多，所以我们说A系统强于B系统。因为A系统依赖于DDH假设，B系统依赖于CDH假设，所以，我们说在安全强弱方面：

     D 
    
   
     D 
    
   
     H 
    
   
     ≥ 
    
   
     C 
    
   
     D 
    
   
     H 
    
   
  
    DDH\ge CDH 
   
  
DDH≥CDH。在一般的论文分析中，为了体现设计的方案足够安全，普遍采用的是Decisonal版本的假设，即DDH假设，下面的BDH系列也是。

CBDH假设和DBDH假设

CBDH假设（Computational Bilinear Diffie-Hellman Assumption）和DBDH假设（Decisional Bilinear Diffie-Hellman Assumption）是CDH的变体。前面提CDH假设和DDH假设时说的是将DH中的线性离散问题转移到群论离散问题，那么CBDH假设和DBDH假设就是将CDH和DDH中的群论离散问题转移到双线性映射中的椭圆曲线离散问题。

双线性映射操作的也是循环群，但是是满足特定属性的循环群，通常会使用椭圆曲线理论来得到这样的循环群。有趣的是，椭圆曲线理论最早用于椭圆曲线加密法（ECC）中，而双线性映射是在破解ECC的过程中发现的，之后人们发现这个性质太适合用于加密了。数学上计算出满足这种性质的循环群是比较难的，目前主流的库包括python的pypbc（这玩意儿依赖于PBC库，这个库只支持Linux系统）和Java里面的jpbc（听过没用过）。

都是群论离散问题，为什么有CDH和DDH不用又要提出还要提出新的假设呢？因为循环群的属性增加了，之前的假设无法保证新增的属性不会带来安全问题。实际上，现存的假设远不止这些，比如，我还在其他论文中看到过一种名为

     l 
    
   
  
    l 
   
  
l-DCBDH（Decisional  
 
  
   
   
     l 
    
   
  
    l 
   
  
l-Combined Bilinear Diffie-Hellman）的变体。只能说具体场景具体分析。

同样，我们给出两个假设对应的问题

Computational Bilinear Diffie-Hellman Problem（CBDHP）：
对于循环群

       G 
      
     
       1 
      
     
    
      , 
     
     
     
       G 
      
     
       2 
      
     
    
   
     G_1,G_2 
    
   
 G1​,G2​，生成元 
  
   
    
    
      g 
     
    
   
     g 
    
   
 g和映射函数 
  
   
    
    
      e 
     
    
   
     e 
    
   
 e，给定 
  
   
    
    
      < 
     
     
     
       G 
      
     
       1 
      
     
    
      , 
     
     
     
       G 
      
     
       2 
      
     
    
      , 
     
    
      e 
     
    
      , 
     
    
      g 
     
    
      , 
     
     
     
       g 
      
     
       a 
      
     
    
      , 
     
     
     
       g 
      
     
       b 
      
     
    
      , 
     
     
     
       g 
      
     
       c 
      
     
    
      > 
     
    
   
     <G_1,G_2,e,g,g^a,g^b,g^c> 
    
   
 <G1​,G2​,e,g,ga,gb,gc>，攻击者能否在多项式时间**计算**出 
  
   
    
    
      e 
     
    
      ( 
     
    
      g 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
      
      
        a 
       
      
        b 
       
      
        c 
       
      
     
    
   
     e(g,g)^{abc} 
    
   
 e(g,g)abc?

Decisional Bilinear Diffie-Hellman Problem（DBDHP）：
对于循环群

       G 
      
     
       1 
      
     
    
      , 
     
     
     
       G 
      
     
       2 
      
     
    
   
     G_1,G_2 
    
   
 G1​,G2​，生成元 
  
   
    
    
      g 
     
    
   
     g 
    
   
 g和映射函数 
  
   
    
    
      e 
     
    
   
     e 
    
   
 e，给定 
  
   
    
    
      < 
     
     
     
       G 
      
     
       1 
      
     
    
      , 
     
     
     
       G 
      
     
       2 
      
     
    
      , 
     
    
      e 
     
    
      , 
     
    
      g 
     
    
      , 
     
     
     
       g 
      
     
       a 
      
     
    
      , 
     
     
     
       g 
      
     
       b 
      
     
    
      , 
     
     
     
       g 
      
     
       c 
      
     
    
      , 
     
    
      e 
     
    
      ( 
     
    
      g 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
     
       d 
      
     
    
      > 
     
    
   
     <G_1,G_2,e,g,g^a,g^b,g^c,e(g,g)^d> 
    
   
 <G1​,G2​,e,g,ga,gb,gc,e(g,g)d>，攻击者能否在多项式时间**判断**出 
  
   
    
    
      e 
     
    
      ( 
     
    
      g 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
     
       d 
      
     
     
      
       
       
         = 
        
       
      
        ? 
       
      
     
    
      e 
     
    
      ( 
     
    
      g 
     
    
      , 
     
    
      g 
     
     
     
       ) 
      
      
      
        a 
       
      
        b 
       
      
        c 
       
      
     
    
   
     e(g,g)^d\overset{\text{?}}{=}e(g,g)^{abc} 
    
   
 e(g,g)d=?e(g,g)abc?

同样，CBDH假设认为CBDHP无多项式解，DBDH假设认为DBDHP无多项式解。Computational版本和Decisional版本的差异和上面是一样的，此处就不再重复。也是同样的道理，在安全性分析中我们常用的是DBDH假设。