您能给我一个加密硬度假设的摘要吗？

#1 楼

评论中的链接之一指向本文，该文件包含了密码学中使用的各种硬度假设的详尽列表。这篇文章的结尾是一个附录，其中包含上述论文中未发现的问题。以下基本上是本文的目录：问题
SDH：静态Diffie-Hellman问题
差距CDH：差距Diffie-Hellman问题
DDH：决策Diffie-Hellman问题
强DDH：强决策Diffie-Hellman问题
sDDH：决策Diffie-Hellman问题偏斜
PDDH：并行决策Diffie-Hellman问题
Square-DH：方差Diffie-Hellman问题
l-DHI：l-Diffie-Hellman问题反演问题
l-DDHI：l决策Diffie-Hellman反演问题
表示形式：表示问题
LRSW：LRSW问题
线性：线性问题
D-Linear1：决策线性问题（版本1）
l-SDH：l-强Diffie-Hellman问题
c-DLSE：具有短指数的离散对数
CONF ：（会议密钥共享方案）
3PASS：3遍消息传输方案
LUCAS：Lucas Prob lem
XLP：x对数问题
MDHP：匹配Diffie-Hellman问题
DDLP：双离散对数问题
rootDLP：离散对数问题的根
nM-DDH ：多重决策Diffie-Hellman问题
l-HENSEL-DLP：l-Hensel离散对数问题
DLP（Inn（G））：内自同构群上的离散对数问题
IE：逆指数
TDH：双重Diffie-Hellman假设
XTR-DL：XTR离散对数问题
XTR-DH：XTR Diffie-Hellman问题
XTR-DHD：XTR决策Diffie-Hellman问题问题
CL-DLP：虚二次阶的类组中的离散对数
TV-DDH：曾变式决策Diffie-Hellman问题
n-DHE：n-Diffie-Hellman指数问题

因子


FACTORING：整数因式分解问题
SQRT：模求复合的平方根
/> CHARACTERd：字符问题
MOVAd：字符问题
CLCLOFACTd：Z [θ]中的因式分解
FERMATd：Z [θ]中的因式分解
RSAP：RSA问题
Strong-RSAP：强RSA问题
Difference-RSAP：差异RSA问题
Partial-DL-ZN2P：Z ∗ n中的部分离散对数问题
DDH-ZN2P：决策Diffie-Hellman问题Z ∗ n
Lift-DH-ZN2P：通过Z ∗ n提升Diffie-Hellman问题
EPHP：选举隐私同态问题
AERP：近似第e个根问题
l- HENSEL-RSAP：l-Hensel RSA
DSeRP：Z ∗ n2中的决策性小电子残差
DS2eRP：Z ∗ n2中的决策性小2e残差
DSmallRSAKP：决策性相互RSA-Paillier Z ∗ n2
HRP：较高的残留性问题
ECSQRT：Z / nZ上的椭圆曲线组的平方根
RFP：根发现ng问题
phiA：PHI假设
C-DRSA：计算相关的RSA问题
D-DRSA：决策相关的RSA问题
E-DRSA：提取相关的RSA问题
DCR：决定性复合残差类问题
CRC：决定性复合残渣类问题
DCRC：决定性综合残差类问题
GenBBS：广义Blum-Blum-Shub假设

产品组


co-CDH：协计算Diffie-Hellman问题
PG-CDH：产品组的计算Diffie-Hellman问题
XDDH：外部决策Diffie-Hellman问题
D-Linear2：决策线性问题（版本2）
PG-DLIN：产品组的决策线性问题
FSDH：柔性平方Diffie-Hellman问题
KSW1：Katz-Sahai-Waters的假设1

配对


BDHP：双线性Diffie-Hellman问题
DBDH：决策双线性Diffie-Hellman问题
B-DLIN：双线性决策线性问题
l-BDHI：l-双线性Diffie-Hellman反演问题
l-DBDHI：l-双线性决策Diffie-Hellman反演问题
l-wBDHI：l-弱双线性Diffie-Hellman反演问题
l-wDBDHI：l-弱决策双线性Diffie-Hellman反演问题
KSW2：Katz-Sahai-Waters的假设2
MSEDH：指数Diffie-Hellman假设的多序列

>格

主要格点问题


SVPγp：（近似）最短向量问题
CVPpγ：（近似）最接近向量问题
GapSVPpγ ：决策最短向量问题
GapCVPpγ：决策最接近向量问题

模格问题


SISp（n，m，q，β）：短整数解问题
ISISp（n，m，q，β）：不均匀的短整数解问题
LWE（n，q，φ）：有错误学习问题

其他格问题


USVPp（n，γ）：近似唯一最短向量问题
SBPp（n，γ）：近似最短基础问题
SLPp（n，γ）：近似最短长度问题
SIVPp（n，γ）：近似最短独立向量问题
hermiteSVP：埃尔米特最短向量问题
CRP ：覆盖半径问题

理想格点问题


理想值SVPf，pγ：（近似）理想最短向量问题/最短多项式问题
理想值- SISf，pq，m，β：理想小整数解问题

其他问题


KEA1：指数假设的知识
MQ：多变量二次方程
CF：给定权重的码字查找
ConjSP：辫子组共轭搜索问题
GenConjSP：广义辫子组共轭搜索问题
ConjDecomP：辫子组共轭搜索问题
ConjDP ：辫子组共轭决策问题
DHCP：辫子组共决策Diffie-Hellman型共轭问题
ConjSearch ：（多个同时）辫子群共轭搜索问题
SubConjSearch：子群受限辫子群共轭搜索问题
LINPOLY：多项式上的线性代数问题
HFE-DP：隐藏场方程分解问题
HFE-SP：解决问题的隐藏场方程
MKS：可乘背包
BP：平衡问题
AHA：自适应硬度假设
SPI：稀疏多项式插值
SPP：自功率问题
VDP：向量分解问题
2-DL：2广义离散对数问题

问题详细信息

全文提供有关每个假设的详细信息。这是一个示例条目：

CDH：计算Diffie-Hellman问题

定义：给定$ g ^ a，g ^ b∈G$以计算$ g ^ {ab } $。

减少项：


CDH $≤_{p} $ DLP
DLP $≤_{subexp} $ CDH平方自由阶。

算法：CDH的最著名算法实际上是解决DLP。

用于密码学：Diffie-Hellman密钥交换和变体，Elgamal加密和变体，BLS签名和变体。

历史：
由W. Diffie和M. Hellman发现。

备注：
CDH的变体是：给定$ g_0，g_0 ^ a，g_0 ^ b∈G$以计算$ g_0 ^ {ab} $。这是$ \ equiv_ {p} $ CDH。

参考文献：


W。 Diffie和M. E. Hellman，“密码学的新方向”，IEEE Transactions on
信息理论，第1卷。 IT-22，第6号，1976年11月，第1页。 644-654。
U.M. Maurer和S. Wolf，Diffie-Hellman Oracles，《 CRYPTO '96的议事录》，第
268-282页。 Boneh和R.J.用于黑匣子场的Lipton算法及其在Cryp-
上的应用，CRYPTO ’96的论文集，第2页。 283-297。

文本太长，无法在此处复制粘贴，但这提供了一个很好的示例，显示了它的广泛性和完整性。

附录：未列出问题

上面的参考文献中未列出以下问题：


MIHNP：模块化求反隐数问题

AGCD：近似最大公约数

SIP：小逆问题


子集和/背包问题



子集和问题


$（0，1）$背包问题（问题的标准版本）


有界背包问题
无界背包问题
RMSS：随机模块化子总和


有关参数的说明

硬度假设仅在正确设置参数后成立。不适当的参数会导致容易解决难题。