| HN Mirror

Your question (if I interpret correctly) is about how trapdoor functions work in asymmetric cryptography, which is broader than elliptic curves in particular. I can give a basic overview; in essence, you use a trapdoor function because you want something to be very difficult to compute but comparatively easy to verify. Mathematically speaking, a good trapdoor function should be such that anyone without the solution will spend a great deal of time trying to calculate it, while anyone with the solution will spend almost no time verifying that the solution is correct.

If we use RSA as an example, we can see how this works in practice:

1. Let n be the product of two large primes, p and q. Large means 512 bits or greater in this context. Then n is the RSA modulus.

2. Select a special number e such that 1 < e < (p - 1)(q - 1), and such that e is coprime with (p - 1)(q - 1) (meaning no numbers divide evenly into both).

3. Your RSA public key is now (n, e) - you can share this publicly with anyone you want to securely communicate with. Conversely, p and q must not be public. This is where your one-way function comes in to separate what can be public from what must be private: n is part of the public key, but was generated by p and q, and multiplication of two primes is a one-way function.

4. Your RSA private key d is computed from q and e, such that for any pair (n, e) there can only be a unique d. d is the inverse of e modulo (p - 1)(q - 1) - in other words, d is a unique number such that, when multiplied by e, is equal to 1 modulo (p - 1)(q - 1). This can be expressed simply as ed = 1 mod (p - 1)(q - 1).

5. Assuming you chose e correctly, d is unique and very difficult to find without having p, q and e. However, while it's very difficult to find without those inputs, it's very easy to find if you have them, because you can use what's called the Extended Euclidean Algorithm to compute d in polynomial time given p and q.

6. So now you want to encrypt something with RSA. Your peer has your public key, (n, e). The encryption process to compute the ciphertext C from the plaintext P is simple: C = P^e mod n (C is equal to the plaintext P multiplied by itself e times and reduced modulo n). Exponentiation has polynomial complexity.

7. To decrypt the ciphertext C in order to compute the plaintext P, all the holder of the private key needs to do is this: P = C^d mod n. In other words, they raise the ciphertext C to the power of their private key.

So, returning to trapdoor functions in general: why does this work? It works because the solution is easy to compute with all inputs, easy to verify with a reduced (public) set of inputs, and extremely difficult to compute with only the reduced set of inputs (and the secret inputs are themselves difficult to find from the public ones).

Hope that helps a bit and I understood your question's context correctly! Trapdoor functions do not necessarily mean that there's "no way out", what they mean is that a set of values have a relation such that one of the values requires only a few of the values to compute a ciphertext and all or most of the values to compute a plaintext for that ciphertext. When we talk about functions being irreversible, we're specifically talking about one-way functions, and those are used in the context of hash functions. Trapdoor functions are "merely" difficult to reverse.

One of the things I'm actively researching at the moment is whether or not (and how) it would be possible to construct a post-quantum secure public-key cryptosystem based on a hardness assumption derived from problems in Ramsey Theoretic graph problems (coincidentally, this problem had a recent treatment after being quietly raised over a decade ago: https://pdfs.semanticscholar.org/1599/62064634fe10897aea300c...).