In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
and
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, a trapdoor function is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
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 a special case of
one-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
s and are widely used in
public-key cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
.
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
Padlocks are portable locks with a shackle that may be passed through an opening (such as a chain link, or hasp staple) to prevent use, theft, vandalism or harm.
Naming and etymology
The term ''padlock'' is from the late fifteenth century. T ...
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" 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
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
in the mid-1970s with the publication of
asymmetric (or public-key) encryption techniques by
Diffie,
Hellman Hellman is a surname. Notable people with the surname include:
* Åke Hellman (1915–2017), Finnish centenarian, painter, and art professor
*Bonnie Hellman (born 1950), American actress
*C. Doris Hellman (1910–1973), American historian of scienc ...
, and
Merkle. Indeed, 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 The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' T ...
. This turned out – rather quickly – to be unsuitable.
, the best known trapdoor function (family) candidates are the
RSA and
Rabin
Rabin is a List of Jewish surnames, Hebrew surname. It originates from the Hebrew word ''rav'' meaning Rabbi, or from the name of the specific Rabbi Abin I, Abin. The most well known bearer of the name was Yitzhak Rabin, prime minister of Israel ...
families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of
prime factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
.
Functions related to the hardness of the
discrete logarithm problem
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b'' ...
(either modulo a prime or in a group defined over an
elliptic curve
In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. If ...
) 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
A back door is a door in the rear of a building. Back door may also refer to:
Arts and media
* Back Door (jazz trio), a British group
* Porta dos Fundos (literally “Back Door” in Portuguese) Brazilian comedy YouTube channel.
* Works so title ...
(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 function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
s (''k'' ∈ ''K''), in which all of ''K'', ''D''
''k'', ''R''
''k'' are subsets of binary strings
*, 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'' ∩
''n'' and ''t''
''k'' ∈
* 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.
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 it is difficult to factorize a large composite number (see
Integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
).
RSA Assumption
In this example, the inverse
of
modulo
(
Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
of
) is the trapdoor:
:
If the factorization of
is known, then
can be computed. With this the inverse
of
can be computed
, and then given
we can find
.
Its hardness follows from the RSA assumption.
Rabin's Quadratic Residue Assumption
Let
be a large composite number such that
, where
and
are large primes such that
, and kept confidential to the adversary. The problem is to compute
given
such that
. The trapdoor is the factorization of
. With the trapdoor, the solutions of ''z'' can be given as
, where
. See
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
for more details. Note that given primes
and
, we can find
and
. Here the conditions
and
guarantee that the solutions
and
can be well defined.
[Goldwasser's lecture notes, 2.3.4]
See also
*
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...
Notes
References
*
*
*
*
*
*
{{Cryptography public-key
Theory of cryptography
Cryptographic primitives