What languages have been successfully cryptographically trapdoored?

Question

An observation associated with asymmetric cryptography is that some functions are (believed to be) easy to perform in one direction but difficult to invert. Furthermore, if there exists some 'trapdoor' information that allows the inverse operation to be computed quickly then the problem becomes a candidate for a public key cryptography scheme.

Classic trapdoor problems, made famous by RSA, include the factoring problem and the discrete log problem. Around the same time that RSA was published, Rabin invented a public key cryptosystem grounded on finding discrete square roots (this was later proved to be at least as difficult as factoring).

Other candidates have cropped up over the years. KNAPSACK (soon after RSA), Elliptic Curve "Logarithms" with specific parameters, and Lattice Shortest Basis Problems are examples of problems whose trapdoor problems used in other published schemes. It is also easy to see that such problems must reside somewhere in NP.

This exhausts my knowledge of trapdoor functions. It also seems to exhaust the list on Wikipedia as well.

I am hoping that we can get a community wiki list of languages that admit trapdoors and relevant literature. The list will be useful. Evolving demands of cryptography also change which trapdoor functions can be the basis of cryptosystems. The explosion of storage on computers makes schemes with large keysizes possible. The perpetual-looming spectre of Quantum Computing invalidates schemes that can be broken with an oracle for finding hidden abelian subgroups. Gentry's Fully Homomorphic Cryptosystem works only because we've discovered trapdoor functions that respect homomorphisms.

I am especially interested in problems that are not NP-Complete.

Answer 1

It is important to distinguish between trapdoor functions and public-key encryption. While trapdoor functions do yield public-key encryption schemes, some of the candidates you mentioned are only known to imply public-key encryption and do not necessarily give you trapdoor functions. In fact, Gertner, Malkin and Reingold show that there is no black-box construction of a trapdoor function from a "trapdoor predicate" (which can be thought of as a one-bit public-key encryption scheme).

Classical examples of trapdoor functions are the RSA and Rabin functions. A classical example of a trapdoor predicate is deciding Quadratic Residuosity modulo a composite, due to Goldwasser and Micali. The discrete-log and lattice based constructions that you mention yield public-key encryption directly, without going through trapdoor functions.

Below is a (non comprehensive) list of constructions of public-key encryption schemes, most of which are not known to go through trapdoor functions.

• El Gamal public-key cryptosystem (including elliptic curve variants). Security is based on the Decisional Diffie Hellman assumption. Doesn't go throuhg trapdoor functions (but see the Peikert-Waters item below for a trapdoor function whose security is based on the semantic security of El Gamal).

  [Taher El Gamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. CRYPTO 1984: 10-18]

• Ajtai-Dwork, Regev. Security is based on unique SVP in lattices. Not known to imply trapdoor functions.

  [Miklós Ajtai, Cynthia Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC 1997: 284-293]

  [Oded Regev: New lattice based cryptographic constructions. STOC 2003: 407-416]

• Regev, Peikert. Security is based on hardness of learning with errors (this includes a reduction from SVP). Not known to imply trapdoor functions.

  [Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005: 84-93]

  [Chris Peikert: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. STOC 2009: 333-342]

• Peikert, Waters. Security is based on decisional Diffie Hellman and on lattice problems. Known to imply trapdoor functions (through lossy trapdoor functions).

  [Chris Peikert, Brent Waters: Lossy trapdoor functions and their applications. STOC 2008: 187-196]

• Lyubashevsky, Palacio, Segev. Security is based on Subset-Sum. Not known to imply trapdoor functions.

  [Vadim Lyubashevsky, Adriana Palacio, Gil Segev: Public-Key Cryptographic Primitives Provably as Secure as Subset Sum. TCC 2010: 382-400]

• Stehlé, Steinfeld, Tanaka, Xagawa, and Lyubashevsky, Peikert, Regev. Security is based on hardness of ring LWE. The advantage of these over previous proposals is their smaller key size. Not known to imply trapdoor functions.

  [Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Efficient Public Key Encryption Based on Ideal Lattices. ASIACRYPT 2009: 617-635]

  [Vadim Lyubashevsky, Chris Peikert, Oded Regev: On Ideal Lattices and Learning with Errors over Rings. EUROCRYPT 2010: 1-23]