Trapdoor function

A trapdoor function is a collection of one-way functions { fk : Dk → Rk } (k ∈ K), in which all of K, Dk, Rk are subsets of binary strings {0, 1}*, satisfying the following conditions: • There exists a probabilistic polynomial time (PPT) sampling algorithm Gen s.t. Gen(1n) = (k, tk) with k ∈ K ∩ {0, 1}n and tk ∈ {0, 1}* satisfies | tk | k is called the trapdoor corresponding to k. Each trapdoor can be efficiently sampled. • Given input k, there also exists a PPT algorithm that outputs x ∈ Dk. That is, each Dk can be efficiently sampled. • For any k ∈ K, there exists a PPT algorithm that correctly computes fk. • For any k ∈ K, there exists a PPT algorithm A s.t. for any x ∈ Dk, let y = A ( k, fk(x), tk ), and then we have fk(y) = fk(x). That is, given trapdoor, it is easy to invert. • For any k ∈ K, without trapdoor tk, for any PPT algorithm, the probability to correctly invert fk (i.e., given fk(x), find a pre-image ''x' such that f''k(''x' ) = f''k(x)) is negligible. If each function in the collection above is a one-way permutation, then the collection is also called a trapdoor permutation. ==Examples==

In the following two examples, we always assume that it is difficult to factorize a large composite number (see Integer factorization). RSA assumption In this example, the inverse d of e modulo \phi(n) (Euler's totient function of n) is the trapdoor: : f(x) = x^e \mod n. If the factorization of n=pq is known, then \phi(n)=(p-1)(q-1) can be computed. With this the inverse d of e can be computed d = e^{-1} \mod{\phi(n)}, and then given y = f(x), we can find x = y^d \mod n = x^{ed} \mod n = x \mod n. Its hardness follows from the RSA assumption. Rabin's quadratic residue assumption Let n be a large composite number such that n = pq, where p and q are large primes such that p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}, and kept confidential to the adversary. The problem is to compute z given a such that a \equiv z^2 \pmod{n}. The trapdoor is the factorization of n. With the trapdoor, the solutions of z can be given as cx + dy, cx - dy, -cx + dy, -cx - dy, where a \equiv x^2 \pmod{p}, a \equiv y^2 \pmod{q}, c \equiv 1 \pmod{p}, c \equiv 0 \pmod{q}, d \equiv 0 \pmod{p}, d \equiv 1 \pmod{q}. See Chinese remainder theorem for more details. Note that given primes p and q, we can find x \equiv a^{\frac{p+1}{4}} \pmod{p} and y \equiv a^{\frac{q+1}{4}} \pmod{q}. Here the conditions p \equiv 3 \pmod{4} and q \equiv 3 \pmod{4} guarantee that the solutions x and y can be well defined. ==See also==