[密码学][困难问题][常见规约]密码学问题常见困难问题

太过爱你忘了你带给我的痛 2023-01-04 10:27 329阅读 0赞

[参考网址(科学上网)][Link 1]  
密码学问题常见困难问题,需要点击参考网址进行查找  
其困难问题的介绍非常友好，请根据目录快速找到相关资料  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

以下是检索 目录

## Discrete logarithm problem ##

DLP: discrete logarithm problem  
CDH: computational Diffie-Hellman problem  
SDH: static Diffie-Hellman problem  
gap-CDH: Gap Diffie-Hellman problem  
DDH: decision Diffie-Hellman problem  
Strong-DDH: strong decision Diffie-Hellman problem  
sDDH: skewed decision Diffie-Hellman problem  
PDDH: parallel decision Diffie-Hellman problem  
Square-DH: Square Diffie-Hellman problem  
l-DHI: l-Diffie-Hellman inversion problem  
l-DDHI: l-Decisional Diffie-Hellman inversion problem  
REPRESENTATION: Representation problem  
LRSW: LRSW Problem  
Linear: Linear problem  
D-Linear1: Decision Linear problem (version 1)  
l-SDH: l-Strong Diffie-Hellman problem  
c-DLSE: Discrete Logarithm with Short Exponents  
CONF: (conference-key sharing scheme)  
3PASS: 3-Pass Message Transmission Scheme  
LUCAS: Lucas Problem  
XLP: x-Logarithm Problem  
MDHP: Matching Diffie-Hellman Problem  
DDLP: Double Discrete Logarithm Problem  
rootDLP: Root of Discrete Logarithm Problem  
n-M-DDH: Multiple Decision Diffie-Hellman Problem  
l-HENSEL-DLP: l-Hensel Discrete Logarithm Problem  
DLP(Inn(G)): Discrete Logarithm Problem over Inner Automorphism Group  
IE: Inverse Exponent  
TDH: The Twin Diffie-Hellman Assumption  
XTR-DL: XTR discrete logarithm problem  
XTR-DH: XTR Diffie-Hellman problem  
XTR-DHD: XTR decision Diffie-Hellman problem  
CL-DLP: discrete logarithms in class groups of imaginary quadratic orders  
TV-DDH: Tzeng Variant Decision Diffie-Hellman problem  
n-DHE: n-Diffie-Hellman Exponent problem

## Factoring ##

FACTORING: integer factorisation problem  
SQRT: square roots modulo a composite  
CHARACTERd: character problem  
MOVAd: character problem  
CYCLOFACTd: factorisation in Z\[θ\]  
FERMATd: factorisation in Z\[θ\]  
RSAP: RSA problem  
Strong-RSAP: strong RSA problem  
Difference-RSAP: Difference RSA problem  
Partial-DL-ZN2P: Partial Discrete Logarithm problem in Z∗n  
DDH-ZN2P: Decision Diffie-Hellman problem over Z∗n  
Lift-DH-ZN2P: Lift Diffie-Hellman problem over Z∗n  
EPHP: Election Privacy Homomorphism problem  
AERP: Approximate e-th root problem  
l-HENSEL-RSAP: l-Hensel RSA  
DSeRP: Decisional Small e-Residues in Z∗n2  
DS2eRP: Decisional Small 2e-Residues in Z∗n2  
DSmallRSAKP: Decisional Reciprocal RSA-Paillier in Z∗n2  
HRP: Higher Residuosity Problem  
ECSQRT: Square roots in elliptic curve groups over Z/nZ  
RFP: Root Finding Problem  
phiA: PHI-Assumption  
C-DRSA: Computational Dependent-RSA problem  
D-DRSA: Decisional Dependent-RSA problem  
E-DRSA: Extraction Dependent-RSA problem  
DCR: Decisional Composite Residuosity problem  
CRC: Composite Residuosity Class problem  
DCRC: Decisional Composite Residuosity Class problem  
GenBBS: generalised Blum-Blum-Shub assumption

## Product groups ##

co-CDH: co-Computational Diffie-Hellman Problem  
PG-CDH: Computational Diffie-Hellman Problem for Product Groups  
XDDH: External Decision Diffie-Hellman Problem  
D-Linear2: Decision Linear Problem (version 2)  
PG-DLIN: Decision Linear Problem for Product Groups  
FSDH: Flexible Square Diffie-Hellman Problem  
KSW1: Assumption 1 of Katz-Sahai-Waters

## Pairings ##

BDHP: Bilinear Diffie-Hellman Problem  
DBDH: Decision Bilinear Diffie-Hellman Problem  
B-DLIN: Bilinear Decision-Linear Problem  
l-BDHI: l-Bilinear Diffie-Hellman Inversion Problem  
l-DBDHI: l-Bilinear Decision Diffie-Hellman Inversion Problem  
l-wBDHI: l-weak Bilinear Diffie-Hellman Inversion Problem  
l-wDBDHI: l-weak Decisional Bilinear Diffie-Hellman Inversion Problem  
KSW2: Assumption 2 of Katz-Sahai-Waters  
MSEDH: Multi-sequence of Exponents Diffie-Hellman Assumption

## Lattices ##

## Main Lattice Problems ##

SVPγp: (Approximate) Shortest vector problem  
CVPpγ: (Approximate) Closest vector problem  
GapSVPpγ: Decisional shortest vector problem  
GapCVPpγ: Decisional closest vector problem

## Modular Lattice Problems ##

SISp(n,m,q,β): Short integer solution problem  
ISISp(n,m,q,β): Inhomogeneous short integer solution problem  
LWE(n,q,φ): Learning with errors problem

## Miscellaneous Lattice Problems ##

USVPp(n,γ): Approximate unique shortest vector problem  
SBPp(n,γ): Approximate shortest basis problem  
SLPp(n,γ): Approximate shortest length problem  
SIVPp(n,γ): Approximate shortest independent vector problem  
hermiteSVP: Hermite shortest vector problem  
CRP: Covering radius problem

## Ideal Lattice Problems ##

Ideal-SVPf,pγ: (Approximate) Ideal shortest vector problem / Shortest polynomial problem  
Ideal-SISf,p q,m,β: Ideal small integer solution problem

## Miscellaneous Problems ##

KEA1: Knowledge of Exponent assumption  
MQ: Multivariable Quadratic equations  
CF: Given-weight codeword finding  
ConjSP: Braid group conjugacy search problem  
GenConjSP: Generalised braid group conjugacy search problem  
ConjDecomP: Braid group conjugacy decomposition problem  
ConjDP: Braid group conjugacy decision problem  
DHCP: Braid group decisional Diffie-Hellman-type conjugacy problem  
ConjSearch: (multiple simlutaneous) Braid group conjugacy search problem  
SubConjSearch: subgroup restricted Braid group conjugacy search problem  
LINPOLY : A linear algebra problem on polynomials  
HFE-DP: Hidden Field Equations Decomposition Problem  
HFE-SP: Hidden Field Equations Solving Problem  
MKS: Multiplicative Knapsack  
BP: Balance Problem  
AHA: Adaptive Hardness Assumptions  
SPI: Sparse Polynomial Interpolation  
SPP: Self-Power Problem  
VDP: Vector Decomposition Problem  
2-DL: 2-generalized Discrete Logarithm Problem

## Problem Details ##

The full paper provides details about each assumption. Here is an example entry:

#### CDH: computational Diffie-Hellman problem ####

#### Definition : ####

Given ga,gb∈G to compute gab.

#### Reductions: ####

*  CDH ≤p DLP
 *  DLP ≤subexp CDH in groups of squarefree order.

#### Algorithms: ####

The best known algorithm for CDH is to actually solve the DLP.

Use in cryptography: Diffie-Hellman key exchange and variants, Elgamal encryption and variants, BLS signatures and variants.

#### History: ####

Discovered by W. Diffie and M. Hellman.

#### Remark: ####

A variant of CDH is: Given g0,ga0,gb0∈G to compute gab0. This is ≡p CDH.

#### References: ####

*  W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, vol. IT-22, No. 6, Nov. 1976, p. 644-654.
 *  U.M. Maurer and S. Wolf, Diffie-Hellman Oracles, Proceedings of CRYPTO ’96, p. 268-282.
 *  D. Boneh and R.J. Lipton Algorithms for Black-Box Fields and Applications to Cryp- tography, Proceedings of CRYPTO ’96, p. 283-297.

The complete text is far too long to copy paste here, but this provides a pretty good example of how extensive and thorough it is.

#### Addendum: Unlisted Problem(s) ####

The following problem(s) were not listed in the above reference:

*  MIHNP: Modular Inversion Hidden Number Problem
 *  AGCD: Approximate Greatest Common Divisor
 *  SIP: Small Inverse Problem

#### Subset Sum/Knapsack problem ####

*  Subset Sum problem
    
     *  (0,1) knapsack problem (The standard version of the problem)
 *  Bounded knapsack problem
 *  Unbounded knapsack problem
 *  RMSS: Random Modular Subset Sum

#### Note about parameters ####

Hardness assumptions only hold when parameterized correctly. Inappropriate parameters can lead to easily solved instances of hard problems.

[Link 1]: https://web.archive.org/web/20120121090326/http://www.ecrypt.eu.org/wiki/index.php/Main_Page
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221119/38f6035111b54c4eac2f15a9b852273a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221119/da297b29ef664e6d9c49ee9b8e8217b2.png