Computational cryptography
Foundational assumption

Trapdoor functions exist

In plain words

A trapdoor function is a lock with a hidden back door: anyone can compute it, nobody can run it backwards, except whoever holds a secret, who gets the whole input back.

The idea: RSA turns a number x into x^e mod N, which anyone can compute from the public key. Running it backwards is believed hard, unless you know d, which is easy to compute from the two primes behind N. With d you recover x itself, not just a message hidden inside it: that full recovery is what makes it a trapdoor function.

Public-key encryption asks for less: the message must come back, but the randomness used to encrypt it may stay hidden, as in ElGamal. That's why public-key encryption could exist even if trapdoor functions didn't.

Why it matters: It's the oldest route to public-key cryptography (RSA) and the engine of hash-and-sign and blind signatures. It's a slightly stronger bet than public-key encryption itself, yet implied by nearly every public-key assumption in use.

The details

On the map: a secret lets you recover the whole input (RSA, lattice trapdoors). Gives public-key encryption. The converse fails in a black-box way, and ElGamal is not one. If impossible, every TD-tagged assumption falls

A trapdoor function is easy to compute from a public key, hard to invert, and easy to invert for whoever holds the matching secret, who gets the whole input back. RSA is the classic example: anyone computes x^e mod N, and the holder of d recovers x exactly. Lattices have trapdoors too: a short secret basis lets its holder solve problems that look random to everyone else[1].

A trapdoor function gives public-key encryption: send f(r) for a random r, and use a hard-core bit of r, one as hard to predict as inverting f, as a one-time pad for the message[2, 3]. The converse fails, at least in any black-box way: Gertner, Malkin and Reingold showed trapdoor functions can't be built that way from public-key encryption[4], and Rudich gave an oracle world with key agreement in three messages but no trapdoor functions at all[5]. So the arrow runs one way: if public-key encryption is impossible, trapdoor functions are too, not the reverse.

ElGamal shows the gap. It encrypts m as (g^r, m·h^r) with a fresh random r. The key holder gets m back but not r, which would be a discrete log even for them[6]. It is public-key encryption without being a trapdoor function. For the assumptions in use the gap closes: RSA and Rabin are trapdoor permutations directly, lattices have trapdoors, and Peikert and Waters built trapdoor functions from DDH and from LWE, the assumptions behind ElGamal and Regev's encryption[7]. The difference is between the abstract notions.

So if trapdoor functions didn't exist, every assumption tagged TD would fall: factoring (the Rabin function is a trapdoor permutation exactly as hard as factoring[8]), the RSA problem[9], composite residuosity[10], computational Diffie-Hellman[11] and decisional Diffie-Hellman[7] (and with them the pairing assumptions), LWE and its ring and module versions[1, 12], NTRU[13] and the knapsack trapdoor[14]. Code-based and isogeny assumptions are untagged: no trapdoor function from them alone is established.

What trapdoors are used for: hash-and-sign signatures, where signing is inverting the function on the message's hash (RSA signatures, and Falcon through the lattice framework above[1]). They also give blind signatures, behind privacy-preserving tokens[15], the classic oblivious transfer protocol and through it secure computation[16], non-interactive zero-knowledge proofs for any NP statement[17], encryption secure against chosen ciphertexts, and identity-based encryption from lattices[7, 1].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (38 boxes)

References

  1. Craig Gentry, Chris Peikert and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008. doi:10.1145/1374376.1374407
  2. Andrew C. Yao. Theory and application of trapdoor functions. 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). doi:10.1109/sfcs.1982.45
  3. O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89, 1989. doi:10.1145/73007.73010
  4. Y. Gertner, T. Malkin and O. Reingold. On the impossibility of basing trapdoor functions on trapdoor predicates. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 2001. doi:10.1109/sfcs.2001.959887
  5. Steven Rudich. The Use of Interaction in Public Cryptosystems. Advances in Cryptology — CRYPTO ’91, 1991. doi:10.1007/3-540-46766-1_19
  6. Taher ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. Advances in Cryptology, 1985. doi:10.1007/3-540-39568-7_2
  7. Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008. doi:10.1145/1374376.1374406
  8. Michael O. Rabin. Digitalized Signatures and Public-Key Functions as Intractable as Factorization. MIT/LCS/TR-212, 1979. apps.dtic.mil/sti/citations/ADA078415
  9. R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Defense Technical Information Center, 1978. doi:10.21236/ada606588
  10. Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Advances in Cryptology — EUROCRYPT ’99, 1999. doi:10.1007/3-540-48910-x_16
  11. Sanjam Garg and Mohammad Hajiabadi. Trapdoor Functions from the Computational Diffie-Hellman Assumption. Advances in Cryptology – CRYPTO 2018. doi:10.1007/978-3-319-96881-0_13
  12. Daniele Micciancio and Chris Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. Advances in Cryptology – EUROCRYPT 2012. doi:10.1007/978-3-642-29011-4_41
  13. Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. Algorithmic Number Theory, 1998. doi:10.1007/bfb0054868
  14. R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 1978. doi:10.1109/tit.1978.1055927
  15. F. Denis, F. Jacobs and C. A. Wood. RSA Blind Signatures. RFC 9474, 2023. rfc-editor.org/rfc/rfc9474
  16. S. Even, O. Goldreich and A. Lempel. A Randomized Protocol for Signing Contracts. Advances in Cryptology, 1983. doi:10.1007/978-1-4757-0602-4_19
  17. U. Feige, D. Lapidot and A. Shamir. Multiple non-interactive zero knowledge proofs based on a single random string. Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. doi:10.1109/fscs.1990.89549