Trapdoor function

What is it and is it safe against quantum computers?

Imagine a house with a door that’s easy to latch but very hard to unlock unless you have the key. That’s the basic idea behind a “trapdoor function” in cryptography.

A trapdoor function is a function that is easy to compute in one direction but hard in the opposite direction unless you have a special piece of information called the “secret”.

Let’s look at some popular cryptographic systems to understand this concept:

RSA:
How it works: #RSA is like multiplying two large prime numbers. It’s easy to compute the product, but if I just gave you the result, it would be very hard to figure out the original numbers.
The Trapdoor: Here, the trapdoor is knowledge of those two prime numbers. If you know them, you can easily “unlock” the function and find out the original message. Without them, it’s a nightmare but not for quantum computers which could break it with Shor’s algorithm.

Elliptic Curve Cryptography (ECC):
How it works: ECC uses curves and points on those curves. Imagine walking a certain distance along a curve; it’s easy. But if I just show you where you ended up, it’s hard to determine your starting point and the distance you walked, especially with the complex mathematics of elliptic curves.
The Trapdoor: In ECC, the trapdoor is knowing the distance you walked. With that knowledge, you can easily go backward on the curve to the original point. However, this one is also not safe against quantum computers!

Lattice-based cryptography:
How it works: Lattices are like multi-dimensional grids of points. The challenge is finding the closest point on the grid to a random point in space. This is easy if the grid is in two dimensions, but extremely difficult in higher dimensions.
The Trapdoor: The trapdoor here is having a special basis (perpendicular vectors creating the grid) that makes finding the closest point much easier. With more parallel vectors, even quantum computer finds it extremely hard to solve.