 Composite moduli

The group of units of Zn, namely Z*, has been proposed for use in several cryptographic mechanisms, including the key agreement protocols of Yacobi and McCurley (see §12.6 notes on page 538) and the identification scheme of Girault (see §10.4 notes on page 423). There are connections of ciyptographic interest between the discrete logarithm and Diffie- Hellman problems in (cyclic subgroups of) Z*, and the problem of factoring n. This section summarizes the results known along these lines.

3.78 Fact Let n be a composite integer. If the discrete logarithm problem in Z* can be solved in polynomial time, then n can be factored in expected polynomial time.

In other words, the discrete logarithm problem in Z* is at least as difficult as the problem of factoring n. Fact 3.79 is a partial converse to Fact 3.78 and states that the discrete logarithm in Z* is no harder than the combination of the problems of factoring n and computing discrete logarithms in Z* for each prime factor p of n.

3.79 Fact Let ?г be a composite integer. The discrete logarithm problem in Z* poly time reduces to the combination of the integer factorization problem and the discrete logarithm problem in Z* for each prime factor p of n.

Fact 3.80 states that the Diffie-Heilman problem in Z* is at least as difficult as the problem of factoring n.

3.80 Fact Let n = pq where p and q are odd primes. If the Diffie-Hellman problem in Z* can be solved in polynomial time for a non-negligible proportion of all bases a € Z*, then n can be factored in expected polynomial time.

Computing individual bits

While the discrete logarithm problem in Z* (§3.6), the RSA problem (§3.3), and the problem of computing square roots modulo a composite integer n (§3.5.2) appear to be intractable, when the problem parameters are carefully selected, it remains possible that it is much easier to compute some partial information about the solution, for example, its least significant bit. It turns out that while some bits of the solution to these problems are indeed easy to compute, other bits are equally difficult to compute as the entire solution. This section summarizes the results known along these fines. The results have applications to the construction of probabilistic public-key encryption schemes (§8.7) and pseudorandom bit generation (§5.5).

Recall (Definition 1.12) that a function / is called a one-way function if f(x) is easy to compute for all x in its domain, but for essentially all у in the range of f, it is computationally infeasible to find any x such that f(x) = y.

Three (candidate) one-way functions

Although no proof is known for the existence of a one-way function, it is widely believed that one-way functions do exist (cf. Remark 9.12). The following are candidate one-way functions (in fact, one-way permutations) since they are easy to compute, but their inversion requires the solution of the discrete logarithm problem in Z*, the RSA problem, or the problem of computing square roots modulo n, respectively:

• 1. exponentiation modulo p. Let p be a prime and let q be a generator of Z*. The function is / : Z* —> Z* defined as f(x) = ax mod p.
• 2. RSA function. Let p and q be distinct odd primes, ?г = pq, and let e be an integer such that gcd(e, (p - 1 )(q - 1)) = 1. The function is / : Z„ —» Zn defined as f(x) = xe mod n.
• 3. Rabin f motion. Let n = pq, where p and q are distinct primes each congruent to 3 modulo 4. The function is / : Qn —> Qn defined as f(x) = x2 mod n. (Recall from Fact 2.160 that / is a permutation, and from Fact 3.46 that inverting /,

i.e., computing principal square roots, is difficult assuming integer factorization is intractable.)

The following definitions are used in §3.9.1,3.9.2, and 3.9.3.

• 3.81 Definition Let / : 5 —> 5 be a one-way function, where 5 is a finite set. A Boolean predicate В : S —» {0,1} is said to be a hard predicate for / if:
• (i) B{x) is easy to compute given x e .S'; and
• (ii) an oracle which computes B[x) correctly with non-negligible advantage0 given only fix) (where a- € S) can be used to invert / easily.

Informally, В is a hard predicate for the one-way function / if determining the single bit B(x) of information about x, given only fix), is as difficult as inverting / itself.

• 3.82 Definition Let / : S —» 5 be a one-way function, where 5 is a finite set. A k-bit predicate В^ : S —i {0,1}^' is said to be a hard к-bit predicate for / if:
• (i) B{kx) is easy to compute given x € 5; and
• (ii) for every Boolean predicate В : {(). 1}A' —» {0,1}, an oracle which computes B(B{k'> (cc)) correctly with non-negligible advantage given only f{x) (where xS) can be used to invert / easily.

If such a В^ exists, then / is said to hide к bits, or the к bits are said to be simultaneously secure.

Informally, Bl k ) is a hard /с-bit predicate for the one-way function f if determining any partial information whatsoever about B^1 (x), given only fix), is as difficult as inverting / itself.

6In Definitions 3.81 and 3.82, die probability is taken over all choices of x 6 S and random com tosses of die oracle.