DH问题汇总
本节内容主要转载于：弄清楚DL，D-H，CDH problem，CDH assumption，DDH，BDDH，BCDH。
DLP（Discrete Logarithm Problem）
在乘法群\((G,*)\)中：
离散对数问题：就是给出两个群元素\(P,Q\),求整数\(n\in Z_q^*\)是困难的，满足\(Q=P^n\)
DH密钥交换协议
具体请参考：计算困难假设（Computational hardness assumption），DH密钥交换
基于DLP（ 离散对数问题）的困难性。
DDHP（Decision Diffie-Hellman Problem）
给出任意\((a,b,c)\), 有多项式时间算法能将\((g^a,g^b,g^{ab})\) 和\((g^a,g^b,g^c)\)两者明显的区分开来。说白了就是区分\(ab\)和\(c\)，仍然是基于DLP。
BDDHP（bilinear decisional Diffie-Hellman Problem）
给出任意\(（a,b,c,d）\), 有多项式时间算法能\((g^a,g^b,g^c,g^{abc}))\)和\((g^a,g^b,g^c,g^d)\)两者区分开来是困难的。
CDHP（Computational Diffie-Hellman Problem）
给出任意的\(g^a,g^b\)，当数值较大时，求\(g^{ab}\)是困难的。
CDHP又分为两种：
Inv-CDHP（Inverse Computational Diffie-Hellman Problem）
求逆：对于\(a ∈ Z_q^*\), 给出\(P, P^a\)，计算\(P^{a^{-1}}\)是困难的.
Squ-CDHP（Square Computational Diffie-Hellman Problem）
求平方：对于\(a ∈ Z_q^*\), 给出\(P, P^a\)，计算\(P^{a^{2}}\)是困难的.
BCDHP（Bilinear Computational Diffie-Hellman problem ）
任意选取\((a,b,c)\)，在多项式时间内计算出\(g^{abc}\)是困难的
GHP群（Gap Diffie-Hellman group）
在一个群中，DDHP是容易的但CDHP很难的就被称为GDH。通过双线性对（bilinear pairing），我们可以得到GDH群，这种群在有限域上的supersingular 椭圆曲线或者hyperelliptic 椭圆曲线上可以找到，双线性对来自Weil 或者 Tate pairing。
可以看出BDDHP和BCDHP比DDHP和CDHP多了一个变量，为什么要多加一个变量？
因为，如果存在一个\(GxG\to G'\)（\(G，G'\)都是群）的双线性对的话， DDH问题是可以被快速解决的。所以就有了BDDH，故即使存在双线性对，BDDH问题仍然是难以计算的。
参考
1、An Efficient Signature Scheme from Bilinear Pairings and Its Applications
最新文章
- JavaWeb_day02_登录校验_查询所有员工信息_DeBug
- SQL Server编程入门
- 【BZOJ-2818】Gcd 线性筛
- HDU-4511 小明系列故事——女友的考验 floyd变种-标号递增最短路
- javascript 字符串和json的互转
- 如何解决：ERROR: the user data image is used by another emulator. aborting 的问题
- Server SAN：弄潮儿云计算时代
- Android系统文件目录路径说明
- Create AI Guard Class
- 数据结构之二分查找——Java语言实现
- 安装一个Linux
- oracle获取连续时间
- VS2008中英文转换
- Neural style transfer
- Cocos Creator采坑：原来使用Cocos Creator做游戏，是有服务器！！！
- SDN 第四次作业
- usb设备运行不正常的解决方法（转）
- [转帖]什么高速线缆DAC？有了有源光缆AOC为何还选择DAC？
- C# 求百分比并保留2位小数
- CRS无法随操作系统自动启动