# Trapdoor Functions

## Prerequisites

### Trapdoor Functions

#### 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 X2 to Y:
• 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:

#### 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)``````