C.3. One-way Functions and the Complexity Class UP

Any public-key encryption behaves like a one-way function, easy to compute but difficult to invert.

Definition C.1.

Let Σ be an alphabet (a finite set of symbols). One may assume, without loss of generality, that Σ = {0, 1}. Let Σ* denote the set of all strings over Σ. A function f : Σ* → Σ* is called a one-way function, if it satisfies the following properties.

  1. f must be injective, that is, for every β the inverse f–1(β), if existent, is unique.

  2. For some real constant k > 0, we have |α|1/k ≤ |f(α)| ≤ |α|k for all . (Here, |α| denotes the length of a string .)

  3. f can be computed in deterministic polynomial time, that is, .

  4. f–1 must not be computable in polynomial time[1], that is, f–1 ∉ P. In view of Property (2), we have . So we require .

    [1] A stronger (but essential) requirement is that f–1 must not be computable by polynomial-time probabilistic algorithms.

Property (1) ensures unique decryption. Property (2) implies that the length of f(α) is polynomially bounded both above and below by the length of α. Property (3) suggests ease of encryption, whereas Property (4) suggests difficulty of decryption.

We do not know whether there exists a one-way function. The following functions are strongly suspected to be one-way. However, we do not seem to have any clues about how we can prove these functions to be one-way.

Example C.1.

  1. The function that multiplies two primes p, q with p < q is believed to be one-way. Computing its inverse is the RSA integer factoring problem.

  2. The discrete exponentiation function in a finite field , that maps , 0 ≤ x ≤ q – 2, to for some fixed is suspected to be one-way. Its inverse is the discrete logarithm function.

  3. The RSA encryption function m ↦ me (mod n) for some fixed parameters n, e is alleged to be one-way. Its inverse is RSA decryption.

It is evident that if P = NP, there cannot exist one-way functions. The converse of this is not true, that is, even if P ≠ NP, there may exist no one-way functions.

Definition C.2.

A non-deterministic Turing machine which has at most one accepting branch of computation for every input string is called an unambiguous Turing machine. The class of languages accepted by poly-time unambiguous Turing machines is denoted by UP.

Clearly, P ⊆ UP ⊆ NP. Both the containments are assumed to be proper. The importance of the class UP stems from the following result:

Theorem C.1.

There exists a one-way function if and only if P ≠ UP.

Therefore, the question is relevant for cryptography and not the question. The class UP is not known (nor expected) to have complete problems. So locating a one-way function may be a difficult task. But at the minimum we are now in the right track.[2] Complexity theory helped us shift our attention from NP (or bigger classes) to UP.

[2] Well, hopefully!

In order to use a one-way function f for cryptographic purposes, we require additional properties of f. Computing f–1 must be difficult for an intruder, whereas the same computation ought to be easy to the legitimate recipient. Thus, f must support poly-time inversion, provided that some secret piece of information (the trapdoor) is available during the computation of the inverse. A one-way function with a trapdoor is called a trapdoor one-way function.

The first two functions of Example C.1 do not have obvious trapdoors and so cannot be straightaway used for designing cryptosystems. The third function (RSA encryption) has the requisite trapdoor, namely, the decryption exponent d satisfying ed ≡ 1 (mod φ(n)).

The hunt for a theoretical foundation does not end here. It begins. Most part of complexity theory deals with worst-case complexities of problems, rather than their average or expected complexities. A one-way function, even if existent, may be difficult to invert for only few instances, whereas cryptography demands the inversion problem to be difficult for most instances. A function meeting even this cryptographic demand need not be suitable, since there may be reductions to map hard instances to easy instances. Moreover, the trapdoors themselves may inject vulnerabilities and prepare room for quick attacks.

There still remains a long way to go!

Exercise Set C.3

C.4Let f : Σ* → Σ* be a function with the property that f(f(α)) = f(α) for every . Argue that f is not a one-way function.
C.5Design unambiguous polynomial time Turing machines for computing the inverses of the functions described in Example C.1.
C.6Show that if there exists a bijective one-way function, then NP ∩ coNP ≠ P. [H]
..................Content has been hidden....................

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