Trapdoor Functions


Introduction to Sets Show

Ordered Pairs Show

Functions Show

Injections, Surjections, and Bijections Show

Important Sets Show

Inverse Functions Show

Sets of Ordered Pairs Show

One-way Functions Show

Trapdoor Functions


  • 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.


  • 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 X2 to Y:
    An example of a trapdoor function using semi-prime factorization.
  • Given x1 and x2 it is easy to find y (you can just multiply them together).
  • However given only y, it becomes computationally infeasible to find x1 and x2, 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 x1 is always equal to 23:
Trapdoor function that has been completed.

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)