C.2. Provably Difficult Computational Problems Are not Suitable

The problem, arguably the deepest unsolved problem in theoretical computer science, may be suspected to have some bearing on public-key cryptography. Under the assumption that P ≠ NP, one may feel tempted to go for using NP-complete problems for building secure cryptosystems. Unfortunately, this tempting invitation does not prove to be fruitful. Several cryptosystems based on NP-complete problems were broken and that is not really a surprise.

It may be the case that P = NP, and, if so, all NP-complete problems are solvable in polynomial time. It may, therefore, be advised to select problems that lie outside NP, that is, in strictly bigger complexity classes. By the time and space hierarchy theorems, we have and . Both EXPTIME and EXPSPACE have complete problems. An EXPTIME-complete problem cannot be solved in polynomial time, whereas an EXPSPACE-complete problem cannot be solved in polynomial space nor in polynomial time too. How about using these complete problems for designing cryptosystems? The idea may sound interesting, but these provably exponential problems turn out to be even poorer, perhaps irrelevant, for use in cryptography.

Let fe and fd be the encryption and decryption transforms for a public-key cryptosystem. We assume that the set of plaintext messages and the set of ciphertext messages are both finite. (Public-key cryptosystems are like block ciphers in this respect.) Moreover, since a ciphertext c = fe(m, e) is computable in polynomial time, the length of c is bounded by a polynomial in the length of m. An intruder can non-deterministically guess messages m (from the finite space) and check if c = fe(m, e) to validate the correctness of the guess. It, therefore, follows that deciphering a ciphertext message (with no additional information) is a problem in NP. That is the reason why we should not look beyond NP.

However, the full class NP, in particular, the most difficult (that is, complete) problems of NP, may be irrelevant for cryptography, as we argue in the next section. In other words, for building cryptosystems we expect to effectively exploit problems that are believed to be easier than NP-complete. Both the integer factoring and the discrete log problems are in the class NP ∩ coNP. We have P ⊆ NP ∩ coNP. It is widely believed that this containment is proper. Also NP ∩ coNP is not known (nor expected) to have complete problems. Even if , both the factoring and the discrete log problems need not be outside P, since we are unlikely to produce completeness proofs for them. Only historical evidences exist, in favor of the fact that these two problems are difficult. The situation may change tomorrow. Complexity theory does not offer any formal protection.

Exercise Set C.2

C.1Prove that the primality testing problem

is in NP ∩ coNP.

(Remark: The AKS algorithm is a deterministic poly-time primality testing algorithm and therefore PRIME is in P and so trivially in NP ∩ coNP too. It can, however, be independently proved that primes have succinct certificates.)

C.2Consider the decision version of the integer factorization problem:

  1. Prove that .

  2. Given a poly-time algorithm for DIFP, design a poly-time algorithm that factors an integer (that is, that solves the functional problem IFP).

C.3Let G be a finite cyclic multiplicative group with a generator g. Assume that one can compute products in G in polynomial time. Consider the decision version of the discrete log problem in G:

Here, indices (indg a) are assumed to lie between 0 and (#G) – 1.

  1. Prove that .

  2. Given a poly-time algorithm for DDLP, design a poly-time algorithm that computes indices in G (that is, that solves the functional problem DLP in G).

..................Content has been hidden....................

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