Sebery J.Cryptography.An introduction to computer security.1989

Complexity of Computing

41

PROBLEM

INSTANCES

Input

ALGORITHM

Output

Fig. 2.1. Relation among a problem, its instances, and an algorithm

2.3.3 Problems and Algorithms

A problem is a general question with the associated parameters and variables whose values are not speci ed. The de nition of a problem consists of two parts. The rst one gives a general setting of the problem with precise description of the problem parameters. The second part determines the requested answer or solution.

Consider the problem of nding the greatest common divisor. The problem can be de ned as follows.

Name: GCD problem

Instance: Two natural numbers a; b 2 N.

Question: What is the greatest common divisor of a and b?

Clearly, any problem consists of the collection of instances whose all values are xed. An instance of GCD problem is: what is gcd(24; 16)?

An algorithm is a step-by-step procedure which for an instance produces the correct answer. An algorithm is said to solve a problem if it produces correct answers for all instances of the problem (Figure 2.1).

Obviously, there are some instances of a problem for which the answer is generated quicker than for the rest. For example, it is much easier to compute

42 2 BACKGROUND THEORY

gcd(2; 4) than gcd(1245; 35820). The commonly accepted characterization of the instance complexity is the size of an instance which is the length of input data needed to completely specify the instance.

The time complexity function (TCF) of an algorithm expresses how many steps (time intervals) are necessary to produce the solution for a given instance of the size n. The TCF of an algorithm depends upon

{the scheme used to encode instances, and

{the model of computer.

Assume that the TCF of an algorithm belongs to either polynomial, subexponential, or exponential class of functions from Section 2.3.2 hierarchy. Observe that the TCF will stay in its class even for a wide range of possible encoding schemes. Any encoding scheme which di ers polynomially from the best encoding scheme is acceptable as it leaves the TCF in the same class.

There are many computer models. But all realistic models are polynomially equivalent to the deterministic Turing machine (DTM) [192]. Moreover, Church's hypotesis says that any realistic notion of algorithm is equivalent to DTM.

The class of all problems can be divided into two broad subclasses:

{undecidable or provably intractable problems

{decidable problems.

A problem belongs to the class of undecidable problems if there is no algorithm that solves it. The existence of such problems was proved by Alan Turing in 1936. Being more speci c, Turing showed that the Halting problem is undecidable. Brie y, the Halting problem can be described as follows: Given an arbitrary DTM and an input, determine whether the machine will eventually halt. Another example of an undecidable problem is Hilbert's tenth problem.

Name: Hilbert's tenth problem

Instance: A polynomial equation with integer coeÆcients in an arbitrary number of unknowns.

Question: Are there integers that are solutions of the equation?

2.3.4 Classes P and NP

A problem is considered to be solved if we can provide an answer to the question. The amount of information required can range from a simple question about

s(ui) = B?

Complexity of Computing

43

PROBLEM

INSTANCES

Input

ALGORITHM

Output

(Yes/No)

Fig. 2.2. Decision problem

the existence of a solution to the question in which we require the enumeration of all possible solutions. In general, the more information that is required, the more computation e ort is expected. A class of decision problems includes all problems for which a sought answer is either \yes" or \no" (Figure 2.2).

Name: Knapsack problem

Instance: A nite set U = fui j i = 1; : : : ; ng, a size s(ui) of any element of ui 2 U, and an integer B.

Question: Is there a subset U0 U such that Pui2U0

The Knapsack problem given above requires a binary yes/no answer.

A class of decision problems which are solvable in polynomial time by a DTM is called the class P. Note that we are not particularly concerned about eÆciency of algorithms as long as they run in polynomial time. For instance, the matrix multiplication can be rephrased as a decision problem.

Name: Matrix multiplication problem

Instance: Given three n n matrices A; A1; A2.

Question: Does A = A1 A2?

44 2 BACKGROUND THEORY

As noted in Section 2.3.1, there are at least two polynomial-time algorithms fornding the product matrix of two matrices. This problem, however, requires a binary answer (yes/no) only. The \no" answer may be generated quicker if for instance, matrices A1 and A2 are not of the correct dimensions. The \yes" answer typically will require generating the product A1 A2 and and next comparing the product with A.

As we have indicated the classi cation of problems mainly depends on the computer model used. A nondeterministic Turing machine (NDTM) is much more powerful than the deterministic Turing machine. The NDTM works in two stages: guessing and checking. Informally, the guessing stage is where the computing power of the NDTM is \concentrated." In this stage, a correct solution (witness) is guessed. The solution (witness) is veri ed against the parameters of the instance and the nal yes/no answer is produced. A decision problem is solvable by the NDTM if the NDTM produces the \yes" answer whenever there is a solution. There is a ne point which needs to be clari ed. The solvability of a problem by the NDTM requires the correct \yes" answer for all \yes" instances of the problem. On the other hand, the NDTM can either produce the correct \no" answer or run forever for \no" instances of the problem.

A class of decision problems which are solvable in polynomial time by the nondeterministic Turing machine is called the class NP. NP can be thought of as a class of decision problems whose solutions (if exist) can be veri ed in polynomial time.

The class P contains all problems that are easy to solve. Clearly, any problem from P belongs to NP. An embarrassing fact in the theory of computational complexity is that we do not know whether P is really di erent from NP. In 1971 Cook made a major contribution to the theory of computational complexity. He showed that there is a decision problem which is the hardest in the class NP. The problem used by Cook was the Satis ability problem.

Name: Satis ability problem (SAT)

Instance: A set U of variables and a collection C of clauses over U. Question: Is there a satisfying truth assignment for C?

2.3.5 NP Completeness

The main tool used in proving the existence of equivalence subclasses in NP is the so-called polynomial reduction. Assume we have two decision problems

poly Q.

Complexity of Computing

45

Q1; Q2 2 NP with their corresponding sets of instances I1 and I2. Let I1+ and I2+ be subsets of all \yes" instances of I1 and I2, respectively. We say that Q1 is polynomially reducible to Q2 if there is a function f : I1 ! I2 which

1.is computable in polynomial time by a DTM,

2.for all instances x 2 I1+ if and only if f(x) 2 I2+.

This fact can be written shortly as

Q1 poly Q2:

If we know an algorithm A2 that solves Q2 and we are able to polynomially reduce Q1 to Q2, then we can create an algorithm A1 to solve Q1. A1 is a concatenation of the function f and A2, i.e. A1(x) = A2(f (x)) where f is the function that establishes the polynomial reducibility between Q1 and Q2. If Q2 2 P, then Q1 2 P. Although being polynomial, the complexity of A1(x) can be signi cantly larger. If Q1 has a higher than polynomial-time complexity, i.e. Q1 2= P, then of course Q2 2= P either.

Cook's theorem can be rephrased as follows: Any NP problem Q is polynomially reducible to the satis ability problem or

Q poly SAT:

The proof of the theorem starts from the observation that for each problem in NP, there is a NDTM program which solves it (in polynomial time). Next, it is shown that any NDTM program can be polynomially reduced to an instance of the SAT problem. The construction of the function which forces the polynomial reducibility is quite complex. The reader who wishes to learn more about the proof is referred to [192].

The SAT problem is NP-complete or NPC as any other problem from NP is polynomially reducible to it, i.e.

8Q2NP Q poly SAT:

The class NPC is nonempty as SAT belongs to it. Are there any other problems in it? The answer is positive and we know many other NPC problems. Core problems which share the same computational complexity with SAT are: 3-satis ability (3-SAT), 3-dimensional matching (3DM), vertex cover (VC), partition, Hamiltonian circuit (HC), etc. To prove that a given problem Q 2 NP is in NPC is enough to show that the satis ability problem or any other NPC problem is polynomially reducible to Q, i.e SAT

46 2 BACKGROUND THEORY

NP

NPC

NPI

P

Fig. 2.3. NP world

If we assume that P 6= NP then we can identify three subclasses: P, NPC, and NPI = NP n (NPC [ P) (Figure 2.3).

2.3.6 Complementary Problems in NP

Let us de ne the class of complementary problems as:

f ^ 2 g

co-NP = Q ; Q NP

^

where Q means the complementary problem to Q. A complementary problem

^

Q can be easily generated from Q as follows:

^

Name: Complementary problem Q Instance: The same as for Q.

Question: The complementary answer required. Consider the following two problems.

Name: Factorization problem (FACT) Instance: Positive integer N.

Question: Are there integers p and q such that N = p q (p; q 2)? and

Name: Primality problem (PRIM) Instance: Positive integer N.

Question: Is N prime?

Complexity of Computing

47

co-NPI

NP

NPC

P

UNPI

co-NP

co-NPC

NPI	co-NPI

Fig. 2.4. Classes NP and co-NP

It is easy to notice that the FACT problem is complementary problem to the PRIM problem. In our case, P RIM = FACT. So having the PRIM problem, we can create the FACT problem by putting not (Is N prime?) in the Question part. Of course, \not (Is N prime?)" is equivalent to \Is N Composite?" and it is the same as \Are there integers p, q such that: N = p q?". Consider an instance x of both PRIM and FACT. The answer is \yes" for x 2 PRIM if and only if the answer is \no" for the same instance x considered as the member of FACT.

In general, however, such an observation cannot be made for all problems in NP and numerous examples lead us to the assumption that:

co-NP 6= NP

In other words, the answer \yes" for an instance x 2 Q does not guarantee

^

that the answer is \no" for the same instance x in Q. If we consider the class P NP then it is easy to prove that: co-P = P that is, the class P is closed under complementation.

The next question concerns the interrelation between the class NPC and the class co-NPC. The answer is given in the following theorem.

^ 2

Theorem 11. If there exists an NP-complete problem Q such that Q NP, then NP = co-NP.

The proof can be found in Garey and Johnson [192, p.156]. Our discussion is summarized in Figure 2.4 (assuming that P 6= NP and NP 6= co-NP). Going back to the pair FACT and PRIM problems, Theorem 11 suggests that they

s(ui) = B?

48 2 BACKGROUND THEORY

must not belong to NPC. On the other hand there is the common consensus that the FACT problem does not belong to P as all existing factorization algorithms run in time longer than or equal to

epln(n) ln ln(n)

Thus we can assume that both PRIM and FACT problems belong to the intersection NPI \ co NPI.

2.3.7 NP-hard and #P-complete Problems

The theory of NP-completeness relates to decision problems only. Most problems used in cryptography are search problems so statements which are true for the NP class are not necessarily correct if we deal with search problems. A search problem Q consists of a set of instances denoted by I. For each instance x 2 I, we have a set SQ(x) of all solutions for x. An algorithm is said to solve the problem Q if it gives a solution from the set SQ(x) for an instance x whenever SQ(x) is not empty. Otherwise, the algorithm returns a \no" answer. The knapsack problem can be rewritten as a search problem.

Name: Knapsack search problem

Instance: A nite set U = fui j i = 1; : : : ; ng, a size s(ui) of any element of ui 2 U, and an integer B.

Question: What is a subset U0 U such that Pui2U0

Informally, a search problem Qs is NP-hard if there is a decision problem Qd 2 NPC which is polynomially reducible to it, i.e. Qd poly Qs. NP-hard problems are believed to be at least as hard as NPC problems. If there existed a polynomial-time algorithm for an NP-hard problem, then all NPC problems would collapse into the class P.

Another class of problems which is closely related to search problems is the class of enumeration problems. The enumeration problem based on the search problem Q (with the set SQ(x) of all solutions for an instance x) asks about the cardinality of SQ(x). The knapsack enumeration problem can be de ned as follows.

Name: Knapsack enumeration problem

Instance: A nite set U = fui j i = 1; : : : ; ng, a size s(ui) of any element of ui 2 U, and an integer B.

Complexity of Computing

49

Question: How many subsets U0 U satisfy the equation Pui2U0 s(ui) = B?

The class #P-complete problems comprises hardest problems of enumeration equivalents of NPC. If a #P-complete problem was solvable in polynomial time, then P=NP.

2.3.8 Problems Used in Cryptography

There are many problems that have been used in cryptography. We have already discussed the PRIM and FACT problems. There is another problem that shares the same computational complexity as PRIM and FACT problems. This is the discrete logarithm problem or DL problem.

Name: DL problem

Instance: Integers (g; s) that belong to GF (p) determined by a prime p. Question: Is there a positive integer h (h = 1; : : : ; p) such that h = logg s

(mod p)?

The DL problem or, more precisely, its search-problem variant is extensively used in conditionally secure cryptographic designs. There is a general purpose algorithm that solves instances of DL in subexponential time. Let us brie y describe a version of the algorithm that is applicable for GF (2n).

Assume that g 2 GF (2n) is a primitive element of GF (2n). We would like to compute h such that s = gh. The index-calculus algorithm starts from the preprocessing stage, which can be done once for the given primitive element g of GF (2n). In the preprocessing stage, a \big enough" set D of discrete logarithms of g is being computed. The elements of D are usually irreducible polynomials of degree m where m is appropriately selected.

Once the set D is created, we can proceed with the main stage of computations in which we select repeatedly at random an integer a = 1; : : : ; 2n 1 and compute

s^ = s ga:

Then the polynomial s^ is factorized into irreducible polynomials. If all factors are in D then

s^ = Y pbp(^s):

p2D

50 2 BACKGROUND THEORY

As polynomials p 2		D are discrete logarithms of g, we know the exponents of
g for any given p 2 D. Therefore
h = logg s =		bp(^s)		a	(mod 2n		1)
	p2D
	X

The algorithm needs to be run for many random a. It will terminate once all factors of s^ are in D. Probabilistic arguments can be used to prove that on average the algorithm takes the following number of steps

e((1+o(1)) mn log mn ):

The DiÆe-Hellman problem relates to the DL problem and is one of the most frequently used in cryptography. It was rst applied by DiÆe and Hellman for their key agreement protocol. Below we de ne the decision DH problem for which answer to the question is binary yes/no. Note that DiÆe and Hellman used search version of the DH problem.

Name: DH decision problem
Instance: Integers gk (mod p),	gs (mod p), and gr (mod p) where p is
prime, g generates Zp and k; s; r are integers.
Question: Is the integer r = ks	(mod p 1) or equivalently does the following
congruence hold

(gk)s = (gs)k gr (mod p)?

Search version of the DH problem can be easily derived by putting two integers gk (mod p) and gs (mod p) into the instance part and asking for gsk in the question part. It is easy to notice that the DH problem is not harder than the related DL problem.

The knapsack problem is also used in cryptography. The problem was applied in cryptography to build one of the rst public-key cryptosystems. Unfortunately, this application did not lead to a secure design despite the fact that the knapsack problem belongs to the NPC class! The statement that the knapsack problem belongs to NPC does not mean that all its instances are of the same complexity. It is possible to de ne an easy knapsack problem whose instances can be solved using a linear-time algorithm.

Name: Easy knapsack problem

Instance: The n-dimension vector space V over GF (2) with the basis v1 = (1; 0; : : : ; 0), : : :, vn = (0; : : : ; 0; 1) 2 V , the vector of sizes S = (s(v1); : : : ;

s(vn)) such that si+1 > Pi sj and an integer B.

j=0