Because of their connections with public-key cryptography, trapdoor functions are surrounded by a lot of mystery. While one-way functions (functions that are easy to compute, yet hard to invert) like integer multiplication are familiar and intuitive, the idea of a function that is hard to invert except if one possesses some secret, the "trapdoor", seems a more remote possibility. The few such functions suitable for cryptographic purposes that have been found (like the modular exponentiation functions as used by the RSA and Rabin cryptosystems) unsurprisingly require heavy use of number theory to understand and analyze.
The main difficulty with public-key cryptosystems, however, is not the requirement for trapdoor functions, but for injective trapdoor functions (it should be possible to reconstruct the original plaintext after all). As soon as the requirement for injectivity is dropped, trapdoor functions are readily constructed from elementary primitives:
Let $N = pq$ for some prime numbers $p$ and $q$. Define
$$
\begin{align}
g(n) &= n-\lfloor \sqrt{n} \rfloor^2 \\
h(n) &= | \lfloor \sqrt{n} \rfloor - g(n) | \\
f_N(n) &= \frac{g(n)}{2} \left( 1 - \cos \left( 2^{|N \, - \, (g(h(n))+2) \, (h(h(n))+2)|} \, \pi \right) \right)
\end{align}
$$
Then, conditional on the hardness of integer factorization, $f_N$ is a surjective trapdoor function with trapdoor $(p,q)$. Indeed, we have
Theorem: $f_N$ satisfies the following properties:
- For every $m \in \mathbb N$ there exists a (not necessarily unique) $n \in \mathbb N$ such that $f_N(n) = m$.
- For every $m > 0$, finding any $n$ with $f_N(n) = m$ is equivalent to factoring $N$.
Proof
What at first glance might appear incomprehensible is actually a rather simple decision procedure, obfuscated through arithmetic.
Observe that $g$ and $h$ induce a surjective map $\mathbb N \rightarrow \mathbb N \times \mathbb N$ (a non-injective inverse pairing function). In other words, $(g(n),h(n))$ runs over all pairs of integers. It follows that $(g(n),g(h(n)),h(h(n)))$ runs over all triples of integers. $f_N$ can thus be rewritten as a function on $\mathbb N^3$:
$$
f_N'(n,m_1,m_2) = \frac{n}{2} \left( 1 - \cos \left( 2^{|N \, - \, (m_1+2) \, (m_2+2)|} \, \pi \right) \right)
$$
Now note that
$$
\frac{1}{2} \left( 1 - \cos \left( 2^{|k|} \, \pi \right) \right) =
\begin{cases}
1 & \text{if} \quad k = 0 \\
0 & \text{otherwise}
\end{cases}
$$
This unmasks the true nature of $f_N'$:
$$
f_N'(n,m_1,m_2) =
\begin{cases}
n & \text{if} \quad (m_1+2) \, (m_2+2) = N \\
0 & \text{otherwise}
\end{cases}
$$
Since the factorization is nontrivial and preimages for any values of $g$ and $h$ are readily found, it follows that knowing the prime factors $p$ and $q$ of $N$ is both necessary and sufficient for making the original function $f_N$ produce any value other than $0$.
References
Background on non-injective trapdoor functions: Bellare et al.: Many-to-One Trapdoor Functions and Their Relation to Public-Key Cryptosystems
Inspiration for pairing function (simplified): Szudzik: An Elegant Pairing Function
Cover image: English Lock (Wikimedia Commons, CC-BY-SA)
