One-way Functions

Prerequisites

Introduction to Sets Show

Ordered Pairs Show

Functions Show

Injections, Surjections, and Bijections Show

Inverse Functions Show

One-way Functions

Introduction

  • One-way functions are a special subset of functions in which it is easy to compute y given x but very hard to compute x given y
  • For example:
Example of a one-way function.
LaTeX formula:f(x) = 7^x \mod 23
  • We can calculate values for f(x) very easily:
Inputs and corresponding outputs of a one-way function.
  • However given a specific value for y it is difficult to find a corresponding x without computing each possible value of x and seeing if it results in a matching y.

code (Python)

Notice in the code below, the function f() has a much smaller complexity than function g()
def f(_x):
    return 7**_x % 23


def g(_y):
    for i in range(10*1000):
        if f(i) == _y:
            return i

    raise Exception("x is not in testable domain")


x = 8
y = f(x)
print("The image of " + str(x) + " is " + str(y))  # prints The image of 8 is 12

y = 12
x = g(y)

print("The preimage of " + str(y) + " is " + str(x))  # prints The preimage of 12 is 8