Hard math problems, complexity and assumptions
Contents
Hard problems and complexity
Hidden supgroup problem
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science.
The framework captures problems like factoring, discrete logarithm, graph isomorphism, and the shortest vector problem.
This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is
essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond
to finite groups that are not Abelian.
Hidden Field Equations problem
HFE is based on polynomials over finite fields Fq of different size to disguise the relationship between the private key and public key. HFE is a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations (the so-called MQ problem) since it uses private affine transformations to hide the extension field and the private polynomials.
Hidden Field Equations have been used to construct:
- a public key cryptosystem, introduced at Eurocrypt 1996 and proposed by (in French) Jacques Patarin following the idea of the Matsumoto and Imai system, and
- digital signature schemes, e.g. Quartz and Sflash.
Factorisation
- NFS, role of Legendre and Jacobi
- New approaches from PQ such as Shor
RSA assumption
Strong RSA assumption
The Strong-RSA assumption was introduced by Baric and Pfitzman
- HFE - introducing the strong RSA assumption
Descriptions
The strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent e (for e ≥ 3). More specifically, given a modulus N of unknown factorization, and a ciphertext C, it is infeasible to find any pair (M, e) such that C ≡ Me mod N.
The strong RSA assumption was first used for constructing signature schemes provably secure against existential forgery without resorting to the random oracle model.
The strong RSA assumption is mentioned in 'Boneh, Boyen Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups, 2014'.
Here it is phrased as 'It states that, given an RSA modulus N and s ∈ ZN, it is difficult to construct a non-trivial pair (c, s1/c) where c ∈ Z.
Roughly speaking, what makes Strong RSA useful for constructing secure signature schemes is the following property: given a problem instance (N, s) it is possible to construct a new instance (N, s 0 ) with some number q of known solutions (ci, (s')1/ci), such that learning any additional solution (c, (s')1/c) makes it possible to solve the original problem instance. This property provides a way to prove security against an adaptive chosen message attack.'
Discrete Logarithm Problem (DLP)
In any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a.
DLP applied to signatures
Often the group GF(p) with p a prime is used. Arithmetic is performed mod(p) in such a group. This is sometimes referred to as the 'regular' or 'basic' DLP.
There are many ways to base an electronic signature scheme on the DLP. These include:
- ElGamal (1985)
- DSA (1991)
- Schnorr
- Nyberg-Rueppel (allowing message recovery)
DLP in Elliptic Curve groups
Koblitz and Miller presumed that computing logarithms in the elliptic curve group was intractable. Menezes and Vanstone ('Reducing EC logarithms to logarithms in a finite field') showed how to reduce the EC logarithm problem in a curve over Fq to the discrete logarithm problem in an extension field Fqk, using the Weil pairing. Since the index-calculus method allows computing logarithms in a finite field in sub-exponential time, this reduction is useful for computing EC logarithms provided k is small. Which was the case for some recommended curves in 1991.
Which begs the question how to compute logarithms in finite fields... and how doable is this?
DL equivalence proofs
Chaum and Pedersen showed in 1992 that it is possible to proof logX(Y) = logP(Q).
Diffie-Hellman
The Diffie–Hellman problem is related to the DLP. Recall that the DLP is given g, gx, compute x.
The DH problem is stated informally as follows: given an element g and the values of gx and gy, what is the value of gxy?
This is used a.o. in the DH key exchange protocol. Participants agree on a group G, a generator g and a prime p for modular calculations. Participant A selects a as secret exponent, and B selects b. They publicly exchange ga and gb. An eavesdropper can obtain these values, but cannot determine a or b. The eavesdropper can easily obtain ga+b by multiplication, but not gab. A and B can raise what they received from each other to the power of their secret exponent, which in both cases yields the same gab. This can be used as a shared secret.
Remember 32 = 9, 33 = 27, 32 * 33 = 243 = 32+3, not 32*3.
Decisional Diffie-Hellman (DDH)
- Decisional Diffie-Hellman Problem: given g, gx , gy , gz, determine if xy = z.
- Decisional DH - Wikipedia
- The DDH assumption states that, given ga and gb for uniformly and independently chosen a, b in Zq, the value gab "looks like" a random element in G.
Further
- The DDH assumption is related to the discrete log assumption. If it were possible to efficiently compute discrete logs in G, then the DDH assumption would not hold in G.
- When using a protocol whose security depends on the DDH assumption, it is important that the protocol is implemented using groups where DDH is believed to hold. DDH does not hold e.g. in the multiplicative group Zp∗ where p is prime, nor in elliptic curves over GF(p) with small embedding degree.
Computational Diffie-Hellman (DDH)
- Computational Diffie-Hellman Problem. Given g, gx, gy, compute gxy.
- Computational DH - Wikipedia
- The CDH assumption states that, given ga and gb for a randomly chosen generator g and random a, b in { 0 , … , q − 1 } it is computationally intractable to compute the value gxy.
Static Diffie-Hellman (DDH)
- Static Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. See https://eprint.iacr.org/2004/306 where it is established that the SDHP is almost as hard as the associated discrete logarithm problem.
Bilinear Diffie-Hellman
Hash Diffie-Hellman
External and Gap Diffie-Hellman
- External and gap DH - Wikipedia
- The external Diffie–Hellman (XDH) assumption is used in ECC.
- XDH implies the existence of two distinct groups ⟨G1, G2⟩ with the following properties:
- The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in G1 and G2.
- There exists an efficiently computable bilinear map (pairing) e ( ⋅ , ⋅ ) : G1 × G2 → GT
- The decisional Diffie–Hellman problem (DDH) is intractable in G1.
- In certain EC subgroups, the existence of an efficiently-computable bilinear map (pairing) can allow for practical solutions to the DDH problem. These groups, referred to as gap Diffie–Hellman (GDH) groups, facilitate a variety of cryptographic protocols, including tri-partite key exchange, identity based encryption, and secret handshakes.
- BLS - Boneh–Lynn–Shacham - Wikipedia 'Short signatures from the Weil pairing' - uses gap DH
- Works in a 'gap group', a group in which CDH problem is intractable but DDH problem can be efficiently solved. Non-degenerate, efficiently computable, bilinear pairings permit such groups.
- Let e : G × G → GT be a non-degenerate, efficiently computable, bilinear pairing where G, GT are groups of prime order, r.
Let g be a generator of G.
- Consider an instance of the CDH problem, g, gx, gy. Intuitively, the pairing function e does not help us compute gxy, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable.
- Given gz, we may check if gz = gxy without knowledge of x, y, and z, by testing whether e(gx, gy) = e(g, gz ) holds.
- By using the bilinear property x+y+z times, we see that if e(gx, gy) = e(g, g)xy = e (g, g)z = e(g , gz), then, since GT is a prime order group, xy = z.
- The signature scheme is provably secure (the scheme is existentially unforgeable under adaptive chosen-message attacks) assuming both the existence of random oracles and the intractability of the computational Diffie–Hellman problem in a gap Diffie–Hellman group.
- Boneh and Franklin describe a generic method for converting any Identity-Based Encryption scheme into a signature scheme in 'Identity-based encryption from the Weil pairing. SIAM J. Comput., 32(3):586–615, 2003.'
q-Strong Diffie-Hellman
Introduced in 'Boneh, Boyen Short Signatures Without Random Oracles, 2004'. Analogy to Strong RSA Assumption.
For some parameter q, the SDH assumption in a group G of prime order p states that the following problem is intractable:
Given g, gx, gx2, ..., gxq ∈ G as input, output a pair (c, g1/(x+c)) where c ∈ Zp .
General Diffie-Hellman
Verheul, in 'Practical and backwards friendly privacy revocation in German e-ID, Idemix and U-Prove' states that although not known, it seems very unlikely that the hardness of the DDH problem is dependent of the generator of the group. To this end we say that one can solve the general DDH with respect to the group G if if one can solve it for all generators of the group.
Lattices
It is e.g. the basis of the lattice-based public-key encryption scheme, NTRU.
Learning with errors (LWE)
Based on the idea of representing secret information as a set of equations with errors. LWE is a way to hide the value of a secret by introducing noise to it. It refers to the computational problem of inferring a linear n-ary function f over a finite ring from given samples yi = f(xi) some of which may be erroneous.