Trapdoor functions

A one-way function forbids everyone from inverting the operation — including its legitimate owner. Yet, to encrypt a message, someone must be able to decrypt it. The solution is called the trapdoor function.

The idea of the trapdoor

A trapdoor function is a one-way function equipped with a secret: without this secret, inversion remains infeasible; with it, inversion becomes easy.

The secret is called the trapdoor. It is a mathematical back door, known only to the holder.

   x  --[ facile : clé publique ]-->  y = f(x)

   y  --[ infaisable sans trappe ]-->  x        (attaquant)
   y  --[ facile AVEC la trappe   ]-->  x        (propriétaire)

The heart of public-key cryptography

This is exactly the mechanism of public-key cryptography:

• Encrypting corresponds to the easy direction of the function. Anyone can do it with the public key.
• Decrypting corresponds to the inversion. It is infeasible for an attacker, but easy for whoever holds the trapdoor, that is, the private key.

The public key describes the function; the private key is the trapdoor. We broadcast the first to the whole world and guard the second jealously.

RSA: factorization as the trapdoor

RSA is the historical example. The public modulus n = p × q defines an easy-to-compute function: c = m^e mod n. Inverting this operation — recovering m from c — amounts to being able to factor n.

Element	Role
(n, e)	public key: describes the function, allows encrypting
p, q	the trapdoor: the factorization known only to the owner
d	private key: derived from the trapdoor, allows decrypting

Whoever built the key knows p and q: for them, inversion is easy. The attacker sees only n and must factor it — infeasible for a large enough n.

One-way is not trapdoor

Be careful not to confuse the two notions:

• a plain one-way function has no shortcut: no one can invert it. Useful for hashing, not for reversible encryption.
• a trapdoor function is a one-way function with a secret shortcut. That is what allows decryption.

Every trapdoor function is one-way; the converse is false. It is this nuance that makes public-key cryptography possible.

In summary

A trapdoor function is a one-way function endowed with a secret that makes inversion easy for whoever knows it. This secret — the trapdoor — is the private key; the public key describes the function and serves to encrypt. In RSA, the trapdoor is the factorization n = p × q, known only to the owner.