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 X² to Y:
  
• Given x₁ and x₂ it is easy to find y (you can just multiply them together).
• However given only y, it becomes computationally infeasible to find x₁ and x₂, 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₁ 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)