Introduction
- Trapdoor functions are very similiar to one-way functions in that their inverse is computationally infeasible.
- However they have an additional property such that they contain a trapdoor.
- A trapdoor is an extra piece of information which makes it easy to invert the function.
Example
- A common one-way function is semi-prime factorization:
- X is a set of prime numbers
- Y is a set of integers
- f is a function that maps X^{2} to Y:
- Given x_{1} and x_{2} it is easy to find y (you can just multiply them together).
- However given only y, it becomes computationally infeasible to find x_{1} and x_{2}, especially if they are very large.
- The trapdoor in this function is when you know one of the values of X. For example: if you know that x_{1} is always equal to 23:
code (Python)
def f(_x1, _x2):
return _x1 * _x2
def g(_y, _x1):
return _x1, _y // x1
x1, x2 = 7, 13
y = f(x1, x2)
print("The image of " + str((x1, x2)) + " is " + str(y)) # prints: The image of (7, 13) is 91
x1 = 7
y = 91
x1, x2 = g(y, x1)
print("The preimage of " + str(y) + " is " + str((x1, x2))) # prints: The preimage of 91 is (7, 13)