Description-About-Common-Difficult-Problems-in-Cryptography

Posted on Edited on In Symbols count in article: 6.2k Reading time ≈ 6 mins.

Descriptions about the common difficult problems in cryptography.

I will learn about them in the nearly future.

web.archive.org

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.

-------------THE END-------------