This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Trapdoor function" – news ·newspapers ·books ·scholar ·JSTOR(July 2013) (Learn how and when to remove this message)

Intheoretical computer science andcryptography, atrapdoor function is afunction that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding itsinverse) without special information, called the "trapdoor". Trapdoor functions are a special case ofone-way functions and are widely used inpublic-key cryptography.^[2]

In mathematical terms, iff is a trapdoor function, then there exists some secret informationt, such that givenf(x) andt, it is easy to computex. Consider apadlock 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 keyt is the trapdoor and the padlock is the trapdoor function.

An example of a simple mathematical trapdoor is "6895601 is the product of two prime numbers. What are those numbers?" A typical "brute-force" solution would be to try dividing 6895601 by many 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 byusing the product of two much larger primes.

Trapdoor functions came to prominence incryptography in the mid-1970s with the publication ofasymmetric (or public-key) encryption techniques byDiffie,Hellman, andMerkle. Indeed,Diffie & Hellman (1976) coined the term. Several function classes had 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 thesubset sum problem. This turned out rather quickly to be unsuitable.

As of 2004^[update], the best known trapdoor function (family) candidates are theRSA andRabin families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem ofprime factorization.

Functions related to the hardness of thediscrete logarithm problem (either modulo a prime or in a group defined over anelliptic curve) arenot 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 abackdoor (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.

Atrapdoor function is a collection ofone-way functions {f_k :D_k →R_k } (k ∈K), in which all ofK,D_k,R_k are subsets of binary strings {0, 1}^*, satisfying the following conditions:

• There exists a probabilistic polynomial time (PPT)sampling algorithm Gen s.t. Gen(1ⁿ) = (k,t_k) withk ∈K ∩ {0, 1}ⁿ andt_k ∈ {0, 1}^* satisfies |t_k | <p (n), in whichp is some polynomial. Eacht_k is called thetrapdoor corresponding tok. Each trapdoor can be efficiently sampled.
• Given inputk, there also exists a PPT algorithm that outputsx ∈D_k. That is, eachD_k can be efficiently sampled.
• For anyk ∈K, there exists a PPT algorithm that correctly computesf_k.
• For anyk ∈K, there exists a PPT algorithmA s.t. for anyx ∈D_k, lety =A (k,f_k(x),t_k ), and then we havef_k(y) =f_k(x). That is, given trapdoor, it is easy to invert.
• For anyk ∈K, without trapdoort_k, for any PPT algorithm, the probability to correctly invertf_k (i.e., givenf_k(x), find a pre-imagex' such thatf_k(x') =f_k(x)) is negligible.^[3][4][5]

If each function in the collection above is a one-way permutation, then the collection is also called atrapdoor permutation.^[6]

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

In this example, the inverse${\displaystyle d}$ of${\displaystyle e}$ modulo${\displaystyle \varphi (n)}$ (Euler's totient function of${\displaystyle n}$) is the trapdoor:

${\displaystyle f(x)=x^e\mathrm{mod}n.}$

If the factorization of${\displaystyle n=pq}$ is known, then${\displaystyle \varphi (n)=(p-1)(q-1)}$ can be computed. With this the inverse${\displaystyle d}$ of${\displaystyle e}$ can be computed${\displaystyle d=e^{-1}\mathrm{mod}\varphi (n)}$, and then given${\displaystyle y=f(x)}$, we can find${\displaystyle x=y^d\mathrm{mod}n=x^{ed}\mathrm{mod}n=x\mathrm{mod}n}$.Its hardness follows from the RSA assumption.^[7]

Let${\displaystyle n}$ be a large composite number such that${\displaystyle n=pq}$, where${\displaystyle p}$ and${\displaystyle q}$ are large primes such that${\displaystyle p\equiv 3(\mathrm{mod}4),q\equiv 3(\mathrm{mod}4)}$, and kept confidential to the adversary. The problem is to compute${\displaystyle z}$ given${\displaystyle a}$ such that${\displaystyle a\equiv z^2(\mathrm{mod}n)}$. The trapdoor is the factorization of${\displaystyle n}$. With the trapdoor, the solutions ofz can be given as${\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}$, where${\displaystyle a\equiv x^2(\mathrm{mod}p),a\equiv y^2(\mathrm{mod}q),c\equiv 1(\mathrm{mod}p),c\equiv 0(\mathrm{mod}q),d\equiv 0(\mathrm{mod}p),d\equiv 1(\mathrm{mod}q)}$. SeeChinese remainder theorem for more details. Note that given primes${\displaystyle p}$ and${\displaystyle q}$, we can find${\displaystyle x\equiv a^{\frac{p+1}{4}}(\mathrm{mod}p)}$ and${\displaystyle y\equiv a^{\frac{q+1}{4}}(\mathrm{mod}q)}$. Here the conditions${\displaystyle p\equiv 3(\mathrm{mod}4)}$ and${\displaystyle q\equiv 3(\mathrm{mod}4)}$ guarantee that the solutions${\displaystyle x}$ and${\displaystyle y}$ can be well defined.^[8]

• One-way function

• Diffie, W.;Hellman, M. (1976),"New directions in cryptography"(PDF),IEEE Transactions on Information Theory,22 (6):644–654,CiteSeerX 10.1.1.37.9720,doi:10.1109/TIT.1976.1055638
• Pass, Rafael,A Course in Cryptography(PDF), retrieved27 November 2015
• Goldwasser, Shafi,Lecture Notes on Cryptography(PDF), retrieved25 November 2015
• Ostrovsky, Rafail,Foundations of Cryptography(PDF), retrieved27 November 2015
• Dodis, Yevgeniy,Introduction to Cryptography Lecture Notes (Fall 2008), retrieved17 December 2015
• Lindell, Yehuda,Foundations of Cryptography(PDF), retrieved17 December 2015

• Theory of cryptography
• Cryptographic primitives

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from July 2013
• All articles needing additional references
• Articles containing potentially dated statements from 2004
• All articles containing potentially dated statements