14
$\begingroup$

Until recently, I had a link to a website which summarizes up-to-date cryptographic hardness assumptions. But, unfortunately I cannot find it.

The webpage is categorized well problems such as, DL problem, Factorization, Finite field, DH problems. More importantly, such problems are very well organized. For example, DH problem and most of its variants are listed with problem definition, introduced source (authors, paper name, etc.), and its applications.

What I had was not pdf file nor book chapter, just a webpage. As I remember, its web structure is similar to http://hyperelliptic.org/ECRYPTII/vampire/

I think such a summary would be very helpful.

$\endgroup$
  • 2
    $\begingroup$ There is a pdf, a report by the Ecrypt II workgroup, that contains all (sort of) hardness assuptions used in cryptography... ecrypt.eu.org/ecrypt2/documents/D.MAYA.6.pdf or ecrypt.eu.org/ecrypt2/documents.html $\endgroup$ – ddddavidee Apr 6 '16 at 17:07
  • $\begingroup$ Thank you very much ddddavidee. A number years ago, I found (sort of) web version of this pdf (as you linked). Do you know whether this web page is closed? The hyperlink in the wabpage was easy to follow. Anyway, what I wanted to find is included in that pdf you gave. Thank you again. $\endgroup$ – Arious Oh Nine Apr 6 '16 at 17:24
  • $\begingroup$ I think you may refere to the wiki, that is linked on the webpage I pt as second link, but the wiki appears to be offline $\endgroup$ – ddddavidee Apr 6 '16 at 17:36
  • $\begingroup$ Yes, what I found may be the wiki page (ecrypt.eu.org/wiki/index.php/Main_Page) on the webpage. But, as you said that, it was offline. But, the pdf version is also very helpful to me. Thanks for giving me the specific link. I appreciate it. $\endgroup$ – Arious Oh Nine Apr 6 '16 at 17:53
  • $\begingroup$ web.archive.org/web/20120121090326/http://www.ecrypt.eu.org/… ? $\endgroup$ – pg1989 Apr 7 '16 at 1:44
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @forest No, not necessarily. A counter-example is "RSAP", which is not provably reducible to the integer factorization problem. $\endgroup$ – Ella Rose May 4 '18 at 16:03
  • $\begingroup$ From what I understand, RSAP is the difficulty in finding $m$ from $c \equiv m^e (\mod n)$ given semiprime $n$ and exponent $e$, whereas the integer factorization problem is finding $n$ from $n = p \cdot q$ in polynomial time. I was under the impression that the only way to accomplish the former was to factor $n$. $\endgroup$ – forest May 5 '18 at 6:43
  • 1
    $\begingroup$ @forest The RSA problem is not known to be reducible to the integer factorization problem. There is a standard efficient algorithm (the obvious one) for solving the RSA problem given an integer factorization oracle, so integer factorization is not (much) easier than the RSA problem. There's no known standard efficient algorithm for integer factorization given an RSA problem oracle. $\endgroup$ – Squeamish Ossifrage May 5 '18 at 15:48
  • $\begingroup$ @forest At best, if an RSA problem solver has a specific form, then it can be converted into an efficient integer factorization algorithm. But conversely, there is some evidence that there may be a separation between the RSA problem and integer factorization. So the story remains unclear. $\endgroup$ – Squeamish Ossifrage May 5 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.