4.2. The Problems at a Glance

Let us first introduce the intractable problems of cryptology. In the rest of this chapter, we describe some known methods to solve these problems.

The integer factorization problem (IFP) is perhaps the most studied one in the lot. We know that is a unique factorization domain (UFD) (Definition 2.25, p 40), that is, given a natural number n there are (pairwise distinct) primes (unique up to rearrangement) such that for some . Broadly speaking, the IFP is the determination of these pi and αi from the knowledge of n. Note that once the prime divisors pi of n are known, it is rather easy to compute the multiplicities αi = vpi(n) by trial divisions. It is, therefore, sufficient to find out the primes pi only. It is easy (Algorithm 3.13) to check if n is composite. If n is already prime, then its prime factorization is known. On the other hand, if n is known to be composite, an algorithm that splits n into two non-trivial factors, that is, that outputs n1, with n = n1n2, n1 < n and n2 < n, can be repeatedly used to compute the complete factorization of n. It is enough that a non-trivial factor n1 of n is made available, the cofactor n2 = n/n1 is obtained by a single division. Finally, it is sometimes known a priori that n is the product of two (distinct odd) primes (as in the RSA protocols). In this case, the non-trivial split of n immediately gives the desired factorization of n. To sum up, the IFP can be stated in various versions, the presumed difficulty of all these versions being essentially the same.

Problem 4.1

General integer factorization problem Given an integer , determine all the prime divisors of n.

Problem 4.2

Integer factorization problem (IFP) Given a composite integer , find a non-trivial divisor n1 of n (that is, a divisor n1 of n in the range 1 < n1 < n).

Problem 4.3

RSA integer factorization problem Given a product n = pq of two (distinct odd) primes p and q, find the prime divisors p and q of n.

Recall that if is the prime factorization of n, then the Euler totient function φ(n) of n is . Thus, if the prime factorization of n is known, it is easy to compute φ(n). The converse is not known to be true in general. However, if n = pq is the product of two primes, factoring n is polynomial-time equivalent to computing φ(n) (Exercise 3.6).
Problem 4.4

Totient problem Given a natural number , compute φ(n).

Problem 4.5

RSA totient problem Given a product n = pq of two (distinct odd) primes p and q, compute φ(n).

Note that is also a UFD. Quite interestingly, it is computationally easy to find a non-trivial factor g of a polynomial (that is, 0 < deg g < deg f). One might, for example, use the polynomial-time deterministic L3 algorithm named after Lenstra, Lenstra and Lovasz (Section 4.8.2).

Square roots modulo an integer can be computed in probabilistic polynomial time, if n is a prime (Algorithm 3.16). If n is composite, the situation is different. If the factorization of n is known, then the square roots can be computed modulo each prime divisor of n, lifted modulo the appropriate powers of the prime divisors and subsequently combined using the Chinese remainder theorem. On the other hand, if the factorization of n is not known, then computing square roots modulo n turns out to be a very difficult task. Recall that the Blum–Blum–Shub algorithm (Algorithm 3.37) exploits this fact to design a cryptographically secure random number generator.

Problem 4.6

Modular square root problem (SQRTP) Given a composite integer and an integer a, compute an integer x, if one exists, such that x2 ≡ a (mod n).

Let us now look at another class of problems of an apparently distinct flavour. Let G be a finite cyclic group of order n := #G and let g be a generator of G. For a moment, let us assume that G is multiplicatively written. Any element can be written as a = gx for some integer x unique modulo n. In this case, x is called the discrete logarithm or the index of a with respect to the base g and is denoted by indg a.
Problem 4.7

Discrete logarithm problem (DLP) Given a finite cyclic group G, a generator g of G and an element , compute indg a.

If we now remove the restrictions that G is cyclic and/or that g is a generator of G (if G is cyclic), then we arrive at a generalized version of the DLP. Let us continue to assume that G is Abelian and finite. The subgroup H of G generated by is anyway cyclic. If , then the discrete logarithm or index of a with respect to the base g is an integer x unique modulo m := ord H such that a = gx. In this case, we denote such an integer x by indg a. On the other hand, if a ∉ H, then we say that the discrete logarithm indg a is not defined. Recall from Proposition 2.5 that if G is cyclic and if m is known, then checking if a belongs to H amounts to computing an exponentiation in G (that is, if and only if am is the identity of G). If G is not cyclic (or if m is not known), then it is not easy, in general, to develop such a nice criterion.
Problem 4.8

Generalized discrete logarithm problem (GDLP) Given a finite Abelian group G and elements g, , determine if a belongs to the subgroup of G generated by g, and if so, compute indg a.

Note that the DLP (or the GDLP) need not be an inherently difficult problem. Its difficulty depends on the choice of the group G and also on the representation of elements of G. For example, if G is the additive (cyclic) group and g is an integer with gcd(g, n) = 1, then for every integer a we have indg a ≡ g–1a (mod n), where the modular inverse g–1 (mod n) can be computed efficiently using the extended gcd algorithm (Algorithm 3.8) on g and n. Also note that if G is cyclic and if each element of G is represented as indg a for a given generator g of G (see, for example, Section 2.9.3), then computing discrete logarithms in G to the base g is a trivial problem. In that case, it is also trivial to compute discrete logarithms (if existent) to any other base h (Exercise 4.3).

On the other hand, there are certain groups G in which discrete logarithms cannot be computed so easily; that is, computing indices in G may demand time not bounded by any polynomial in log n, where n = ord G. However, if the group operation on any two elements of G can be performed in time bounded by a polynomial in log n, then cryptographic protocols can be based on G. Typical candidates for such groups are listed below together with the conventional names for the DLP over such groups.

Table 4.1. The discrete logarithm problem in various groups
GroupName for the DLP
The (cyclic) multiplicative group of a finite field The finite field discrete logarithm problem or simply the DLP by an abuse of notation.
The (not necessarily cyclic) additive group of points of an elliptic curve defined over a finite field The Elliptic curve discrete logarithm problem or the ECDLP
The Jacobian of a hyperelliptic curve C defined over a finite field The Hyperelliptic curve discrete logarithm problem or the HECDLP

Note that if we are interested in computing indices to a base , we may indeed replace, at least theoretically, G by the subgroup H of G generated by g and may assume, without loss of generality, that G is cyclic. Now, if we know an isomorphism , computing discrete logarithms in G is rather easy (Exercise 4.4). However, computing such an isomorphism is, in general, not an easy task and may demand exponential time and/or storage requirements.

Another problem that is widely believed to be computationally equivalent to the DLP (at least for the groups mentioned in the above table) is called the Diffie–Hellman problem (DHP). Similar to the DLP, the DHP is presumably difficult to solve for the groups , and and one may introduce the specific names DHP, ECDHP and HECDHP to designate this problem applied to these specific groups.

Problem 4.9

Diffie–Hellman problem (DHP) Let G be a multiplicative group and let . Given gx and gy for some (unknown) integers x and y, compute gxy.

Clearly, if a solution of the DLP is given, one may compute y = indg(gy) and, subsequently, gxy = (gx)y. That is, the DHP is no harder than the DLP. A proof for the validity or otherwise of the converse relation between these two problems is not known. It is also widely believed that the DLP is computationally equivalent to the IFP. A complete proof of this equivalence is not known, though certain partial results are available in the literature.

There are some other difficult problems on which cryptographic systems can be built. Problem 4.10 deserves specific mention in this regard.

Problem 4.10

Subset sum problem (SSP) Given a set A := {a1, . . . , an} of natural numbers and , find out if there exist , such that , that is, if there is a subset B of A with the property that . The integers a1, . . . , an are called the weights for the SSP.

The Knapsack problem is a related combinatorial optimization problem. In view of this, the set {a1, . . . , an} is often called a knapsack set, and the SSP is, by an abuse of notation, also referred to as the knapsack problem.

Some of the early cryptographic systems based on the SSP have succumbed to efficient (even polynomial-time) cryptanalytic attacks. However, some schemes have been proposed in the recent years, which seem to be resistant to such attacks, or, in other words, for which good attacks are not yet known. As a result, it is important to study the SSP in some detail.

The SSP is often mapped to problems on lattices. Let v1, . . . , vn be linearly independent vectors in . Consider the set of integer linear combinations of these vectors:

L is called the lattice generated by v1, . . . , vn.

Problem 4.11

Shortest vector problem (SVP) Find a non-zero vector whose length ‖v‖ is smallest in L.

Problem 4.12

Closest vector problem (CVP) Given a vector , find a vector such that the length ‖v – w‖ is smallest over all choices of .

For some other difficult computational problems and their applications to cryptography, we refer the reader to the references suggested at the end of this chapter and of Chapter 5.

Exercise Set 4.2

4.1

  1. Let n ≥ 2 be a square-free integer (that is, a product of pairwise distinct primes) and let . Show that the exponentiation map , x ↦ xa, is bijective if and only if gcd(a, φ(n)) = 1. [H]

  2. Show that if is not square-free, then for no integer a ≥ 2 the exponentiation map , is bijective. [H]

4.2Show that the following problems are polynomial-time reducible to the IFP.

  1. RSA key inversion problem (RSAKIP) Let n = pq be a product of two (distinct odd) primes p and q. Given with gcd(e, φ(n)) = 1, compute an integer such that ed ≡ 1 (mod φ(n)).

  2. RSA problem (RSAP) Let n and e be as in Part (a). Given , compute such that c ≡ xe (mod n). (By Exercise 4.1, such an x exists and is unique.)

  3. Quadratic residuosity problem (QRP) Given an odd integer n > 1 and an integer a with gcd(a, n) = 1, check if a is a quadratic residue modulo n. (Note that if n is a prime, then this problem reduces to the computation of the Legendre symbol . If, on the other hand, n is composite and , one cannot conclude that a is a quadratic residue modulo n.)

4.3Let G be a finite cyclic group of order n and let g, g′ be two arbitrary generators of G.

  1. Show that indg g′ is invertible modulo n and that for every we have indg′ a ≡ (indg a)(indg g′)–1 (mod n).

  2. Let , m := ord(h) and y := indg h. Show that m = n/gcd(y, n), that y/ gcd(y, n) is invertible modulo m and that for an arbitrary element the index indh a exists if and only if gcd(y, n)| indg a and in that case we have

    indh a ≡ (indg a/ gcd(y, n))(y/ gcd(y, n))–1 (mod m).

4.4Let G be a finite cyclic multiplicatively written group of order n. An algorithm on G is said to be polynomial-time if it runs in time bounded above by a polynomial function of log n. Assume that the product of any two elements in G can be computed in polynomial time. Recall from Exercise 2.47 that . Show that the computation of an isomorphism is polynomial-time equivalent to computing discrete logarithms in G. (That is, assuming that we are given a (two-way) black box that returns in polynomial time or for every and , discrete logarithms in G can be computed in polynomial time. Conversely, if discrete logarithms with respect to a primitive element can be computed in polynomial time, then such a black box can be realized.)
4.5Let p be an (odd) prime and let g be a primitive root modulo p. Show that is a quadratic residue modulo p if and only if the index indg a is even. Hence, conclude that there is a polynomial-time (in log p) algorithm that computes the least significant bit of indg a, given any . More generally, let p – 1 = 2r s, where r, and s is odd. Show that there exists a polynomial-time algorithm that computes the r least significant bits of indg a given any . (This exercise shows that the DLP has a polynomial-time solution for Fermat primes Fn := 22n + 1. Note that Fn is prime for n = 0, 1, 2, 3, 4. No other Fermat primes are known.)
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.139.80.209