Trapdoor function

A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". Trapdoor functions are widely used in cryptography.

In mathematical terms, if f is a trapdoor function, then there exists some secret information y, such that given f(x) and y, it is easy to compute x. Consider a padlock and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key is the trapdoor.

An example of a simple mathematical trapdoor is "6895601 is the product of two prime numbers. What are those numbers?" A typical solution would be to try dividing 6895601 by several prime numbers until finding the answer. However, if one is told that 1931 is one of the numbers, one can find the answer by entering "6895601 ÷ 1931" into any calculator. This example is not a sturdy trapdoor function – modern computers can guess all of the possible answers within a second – but this sample problem could be improved by using the product of two much larger primes.

Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric (or public-key) encryption techniques by Diffie, Hellman, and Merkle. Indeed, Diffie & Hellman (1976) coined the term. Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. This turned out – rather quickly – to be unsuitable.

As of 2004, the best known trapdoor function (family) candidates are the RSA and Rabin families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorization.

Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logarithms.

A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably, which is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.

Definition

A trapdoor function is a collection of one-way functions { fk : DkRk } (kK), 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 kK ∩ {0, 1}n and tk ∈ {0, 1}* satisfies | tk | < p (n), in which p is some polynomial. Each tk is called the trapdoor corresponding to k. Each trapdoor can be efficiently sampled.
• Given input k, there also exists a PPT algorithm that outputs xDk. That is, each Dk can be efficiently sampled.
• For any kK, there exists a PPT algorithm that correctly computes fk.
• For any kK, there exists a PPT algorithm A s.t. for any xDk, 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 kK, without trapdoor tk, for any PPT algorithm, the probability to correctly invert fk (i.e., find x given fk(x)) is negligible.

Example

In the following two examples, we always assume it is difficult to factorize a large composite number (see Integer factorization).

RSA Assumption

In this example, having the inverse of e modulo φ(n), the Euler's totient function of n, is the trapdoor:

$f(x) = x^e \mod n$

If the factorization is known, φ(n) can be computed, so then the inverse d of e can be computed d = e-1 mod φ(n), and then given y = f(x) we can find x = yd mod n = xed mod n = x mod n. Its hardness follows from RSA assumption.

Let n be a large composite number s.t. n = pq, where p and q are large primes and kept confidential to adversarial. Let y be a quadratic non-residue in the multiplicative group of integers modulo n Zn*. Let z be a randomly chosen number in Zn*, and z is confidential to adversarial. The trapdoor function f takes one bit x as input.

$f_{n,y}(x) = \begin{cases} z^2 \mod n & \mathrm{if} \, x=0,\\ yz^2 \mod n & \mathrm{if} \, x=1.\\ \end{cases}$

The trapdoor is the factorization n = pq. That is, given w = fn, y(x), check the Jacobi symbols

$\left( \frac{w}{p} \right), \quad \left( \frac{w}{q} \right).$

If both are 1, return x = 0. Otherwise, return x = 1. Its one-wayness follows from the hardness to correctly judge whether a given integer is quadratic residue modulo n, if the factorization of n is unknown.