# Trapdoor function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Trapdoor_function
> Markdown URL: https://mediated.wiki/source/Trapdoor_function.md
> Source: https://en.wikipedia.org/wiki/Trapdoor_function
> Source revision: 1317857107
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

One-way cryptographic tool

This article is about the mathematical cryptography function. For the method of bypassing security, see [Backdoor (computing)](/source/Backdoor_(computing)).

This article needs additional citations for verification. Please help improve this article by adding 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)

The idea of trapdoor function. A trapdoor function *f* with its trapdoor *t* can be generated by an algorithm **Gen**. *f* can be efficiently computed, i.e., in probabilistic [polynomial time](/source/Polynomial_time). However, the computation of the inverse of *f* is generally hard, unless the trapdoor *t* is given.[1]

In [theoretical computer science](/source/Theoretical_computer_science) and [cryptography](/source/Cryptography), a **trapdoor function** is a [function](/source/Function_(mathematics)) that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its [inverse](/source/Inverse_function)) without special information, called the "trapdoor". Trapdoor functions are a special case of [one-way functions](/source/One-way_function) and are widely used in [public-key cryptography](/source/Public-key_cryptography).[2]

In mathematical terms, if *f* is a trapdoor function, then there exists some secret information *t*, such that given *f*(*x*) and *t*, it is easy to compute *x*. Consider a [padlock](/source/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 *t* 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](/source/Brute-force_attack)" 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 by [using the product of two much larger primes](/source/Integer_factorization).

Trapdoor functions came to prominence in [cryptography](/source/Cryptography) in the mid-1970s with the publication of [asymmetric (or public-key) encryption](/source/Asymmetric_key_algorithm) techniques by [Diffie](/source/Whitfield_Diffie), [Hellman](/source/Martin_Hellman), and [Merkle](/source/Ralph_Merkle). Indeed, [Diffie & Hellman (1976)](#CITEREFDiffieHellman1976) 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 the [subset sum problem](/source/Subset_sum_problem). This turned out rather quickly to be unsuitable.

As of 2004[\[update\]](https://en.wikipedia.org/w/index.php?title=Trapdoor_function&action=edit), the best known trapdoor function (family) candidates are the [RSA](/source/RSA_(algorithm)) and [Rabin](/source/Rabin_cryptosystem) families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of [prime factorization](/source/Prime_factorization).

Functions related to the hardness of the [discrete logarithm problem](/source/Discrete_logarithm_problem) (either modulo a prime or in a group defined over an [elliptic curve](/source/Elliptic_curve_cryptography)) 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](/source/Backdoor_(computing)) (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](/source/One-way_function) { *f**k* : *D**k* → *R**k* } (*k* ∈ *K*), in which all of *K*, *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*n*) = (*k*, *t**k*) with *k* ∈ *K* ∩ {0, 1}*n* and *t**k* ∈ {0, 1}* satisfies | *t**k* | < *p* (*n*), in which *p* is some polynomial. Each *t**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* ∈ *D**k*. That is, each *D**k* can be efficiently sampled.

- For any *k* ∈ *K*, there exists a PPT algorithm that correctly computes *f**k*.

- For any *k* ∈ *K*, there exists a PPT algorithm *A* s.t. for any *x* ∈ *D**k*, let *y* = *A* ( *k*, *f**k*(*x*), *t**k* ), and then we have *f**k*(*y*) = *f**k*(*x*). That is, given trapdoor, it is easy to invert.

- For any *k* ∈ *K*, without trapdoor *t**k*, for any PPT algorithm, the probability to correctly invert *f**k* (i.e., given *f**k*(*x*), find a pre-image *x'* such that *f**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 a **trapdoor permutation**.[6]

## Examples

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

### RSA assumption

In this example, the inverse d {\displaystyle d} of e {\displaystyle e} modulo ϕ ( n ) {\displaystyle \phi (n)} ([Euler's totient function](/source/Euler's_totient_function) of n {\displaystyle n} ) is the trapdoor:

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

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

### Rabin's quadratic residue assumption

Let n {\displaystyle n} be a large composite number such that n = p q {\displaystyle n=pq} , where p {\displaystyle p} and q {\displaystyle q} are large primes such that p ≡ 3 ( mod 4 ) , q ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}} , and kept confidential to the adversary. The problem is to compute z {\displaystyle z} given a {\displaystyle a} such that a ≡ z 2 ( mod n ) {\displaystyle a\equiv z^{2}{\pmod {n}}} . The trapdoor is the factorization of n {\displaystyle n} . With the trapdoor, the solutions of *z* can be given as c x + d y , c x − d y , − c x + d y , − c x − d y {\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy} , where a ≡ x 2 ( mod p ) , a ≡ y 2 ( mod q ) , c ≡ 1 ( mod p ) , c ≡ 0 ( mod q ) , d ≡ 0 ( mod p ) , d ≡ 1 ( mod q ) {\displaystyle 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](/source/Chinese_remainder_theorem) for more details. Note that given primes p {\displaystyle p} and q {\displaystyle q} , we can find x ≡ a p + 1 4 ( mod p ) {\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}} and y ≡ a q + 1 4 ( mod q ) {\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}} . Here the conditions p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3{\pmod {4}}} and q ≡ 3 ( mod 4 ) {\displaystyle q\equiv 3{\pmod {4}}} guarantee that the solutions x {\displaystyle x} and y {\displaystyle y} can be well defined.[8]

## See also

- [One-way function](/source/One-way_function)

## Notes

1. **[^](#cite_ref-1)** Ostrovsky, pp. 6–9

1. **[^](#cite_ref-2)** Bellare, M (June 1998). "Many-to-one trapdoor functions and their relation to public-key cryptosystems". *Advances in Cryptology — CRYPTO '98*. Lecture Notes in Computer Science. Vol. 1462. pp. 283–298. [doi](/source/Doi_(identifier)):[10.1007/bfb0055735](https://doi.org/10.1007%2Fbfb0055735). [ISBN](/source/ISBN_(identifier)) [978-3-540-64892-5](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-64892-5). [S2CID](/source/S2CID_(identifier)) [215825522](https://api.semanticscholar.org/CorpusID:215825522).

1. **[^](#cite_ref-3)** Pass's Notes, def. 56.1

1. **[^](#cite_ref-4)** Goldwasser's lecture notes, def. 2.16

1. **[^](#cite_ref-5)** Ostrovsky, pp. 6–10, def. 11

1. **[^](#cite_ref-6)** Pass's notes, def 56.1; Dodis's def 7, lecture 1.

1. **[^](#cite_ref-7)** Goldwasser's lecture notes, 2.3.2; Lindell's notes, p. 17, Ex. 1.

1. **[^](#cite_ref-8)** Goldwasser's lecture notes, 2.3.4.

## References

- [Diffie, W.](/source/Whitfield_Diffie); [Hellman, M.](/source/Martin_Hellman) (1976), ["New directions in cryptography"](https://www-ee.stanford.edu/~hellman/publications/24.pdf) (PDF), *[IEEE Transactions on Information Theory](/source/IEEE_Transactions_on_Information_Theory)*, **22** (6): 644–654, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.37.9720](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.9720), [doi](/source/Doi_(identifier)):[10.1109/TIT.1976.1055638](https://doi.org/10.1109%2FTIT.1976.1055638)

- Pass, Rafael, [*A Course in Cryptography*](https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf) (PDF), retrieved 27 November 2015

- Goldwasser, Shafi, [*Lecture Notes on Cryptography*](https://cseweb.ucsd.edu/~mihir/papers/gb.pdf) (PDF), retrieved 25 November 2015

- Ostrovsky, Rafail, [*Foundations of Cryptography*](https://web.cs.ucla.edu/~rafail/PUBLIC/OstrovskyDraftLecNotes2010.pdf) (PDF), retrieved 27 November 2015

- Dodis, Yevgeniy, [*Introduction to Cryptography Lecture Notes (Fall 2008)*](http://www.cs.nyu.edu/courses/fall08/G22.3210-001/index.html), retrieved 17 December 2015

- Lindell, Yehuda, [*Foundations of Cryptography*](http://u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf) (PDF), retrieved 17 December 2015

v t e Public-key cryptography Algorithms Integer factorization Benaloh Blum–Goldwasser Cayley–Purser Damgård–Jurik GMR Goldwasser–Micali Naccache–Stern Paillier Rabin RSA Okamoto–Uchiyama Schmidt–Samoa Discrete logarithm BLS Cramer–Shoup DH DSA ECDH X25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV EKE ElGamal signature scheme MQV Schnorr SPEKE SRP STS Lattice/SVP/CVP/LWE/SIS BLISS Kyber NewHope NTRUEncrypt NTRUSign RLWE-KEX RLWE-SIG Falcon Others AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern knapsack cryptosystem Three-pass protocol XTR SQIsign SPHINCS+ Theory Discrete logarithm cryptography Elliptic-curve cryptography Hash-based cryptography Non-commutative cryptography RSA problem Trapdoor function Tropical cryptography Standardization CRYPTREC IEEE P1363 NESSIE NSA Suite B CNSA Post-Quantum Cryptography Topics Digital signature OAEP Fingerprint PKI Web of trust Key size Identity-based cryptography Post-quantum cryptography OpenPGP card

---
Adapted from the Wikipedia article [Trapdoor function](https://en.wikipedia.org/wiki/Trapdoor_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Trapdoor_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.