One of the links in the comments points to this paper, which has a very extensive list of various hardness assumptions used in cryptography. At the end of this post is an addendum that includes problems not found in the mentioned paper. The following is basically the table of contents from the paper:
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 $g^a, g^b ∈G$ to compute $g^{ab}$.
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 $g_0,g_0^a,g_0^b ∈G$ to compute $g_0^{ab}$. This is $\equiv_{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:
Subset Sum/Knapsack problem
Note about parameters
Hardness assumptions only hold when parameterized correctly. Inappropriate parameters can lead to easily solved instances of hard problems.
