BDH、CDH、DDH、DBDH、IDH、HDH(持续更新~~~~)
BDH
CDH
Decisional Diffie-Hellman assumption(DDH)
考虑阶数为 q q q的有限循环群 G G G和群中一固定的生成元 g g g，已知 g a 、 g b ( a , b ∈ Z q ) g^a、g^b (a,b \in Z_q) ga、gb(a,b∈Zq)，若DDH Assumption成立，那么 g a b g^{ab} gab应与 G G G中的随机元素不可区分。
如果DDH在群 G G G中是困难的，那么对于所有概率多项式时间算法 P P T A \mathcal {PPT} \quad \mathcal A PPTA都应存在可忽略的函数 n e g l i g i b l e negligible negligible，其满足:
A d v A D D H ( k ) = ∣ P r [ A ( G , q , g , g a , g b , g c ) = 1 ] − P r [ A ( G , q , g , g a , g b , g a b ) = 1 ] ≤ n e g l i g i b l e ( k ) Adv^{DDH}_A (\mathcal k)= |Pr[\mathcal A(G, q, g, g^a, g^b, g^c) = 1] - Pr[\mathcal A(G, q, g, g^a, g^b, g^{ab}) = 1] \leq negligible(\mathcal k) AdvADDH(k)=∣Pr[A(G,q,g,ga,gb,gc)=1]−Pr[A(G,q,g,ga,gb,gab)=1]≤negligible(k)
其中 a , b , c a,b,c a,b,c是在 Z q Z_q Zq中随机选取的, k k k为安全参数。