Cryptography
rsa diffie-hellman one-way-function trapdoor
Updated Wed, 07 Sep 2022 00:27:05 GMT

Where is the definition of one-way trap-door function used in public key cryptography

This is a rather simple question but I've been unable to find a proper answer for this online.

When defining an asymmetric (public key) algorithm is the one-way trap-door function usage referring to the encryption/decryption function or the key generation process or perhaps both?

I believe that the one-way function is indeed used in the key generation process, but I'm not sure entirely.

For instance when we look upon Diffie-Hellman and RSA, it is known that RSA uses integer factorization as its one-way trap-door, meanwhile Diffie-Hellman uses discrete logarithms.

Solution

Elliptic curve cryptography (ECC) does not use a one-way trapdoor function. It uses a homomorphically-additive one-way function which transforms a private key into a public key. "Trapdoor" is not a synonym for "one-way" or "invertible". Trapdoor means a function that can be used without knowledge of the "trapdoor" secret, and inverted only with knowledge of the secret.

You can't directly encrypt or decrypt with ECC. You can only agree a key (using Elliptic Curve Diffie-Hellman), and then use that key for symmetric encryption/decryption. Signatures are achieved using a chameleon-hash function, which has a trapdoor (the private key) that can be used to find collisions in order to produce a valid signature that no one else would be able to produce. This is entirely different from the RSA trapdoor function, which allows the trapdoor function to be used in one direction without any secret knowledge, but can be inverted with knowledge of the trapdoor secret.

RSA uses a one-way trapdoor function. The private key (the trapdoor knowledge) and public key are created together from two secret primes when a key pair is generated. The trapdoor function is not used to create the key pair - it's the other way around. Generating the key pair provides the parameters for the trapdoor function. You can directly encrypt with RSA, because there is trapdoor information available that can directly reverse the encryption process. You can also directly sign, by "encrypting" with the private key something that anyone can "decrypt" with the public key.

Summary:

For DH, you choose a private key, and you calculate the public key using $$f(x)=g^x\ mod\ p$$, where the input is the private key and $$g$$ is a well-known generator. This is not a trapdoor function, because although the inverse function is $$f^{-1}(y)=y^{x^{-1}}\ mod\ p$$ (where $$x^{-1}$$ is the modular inverse of $$x$$), the secret needs to be known both for $$f$$ and for $$f^{-1}$$. The definition of a trapdoor function is that the secret trapdoor information is only required when going in one direction.

For ECDH, you choose a private key, and you calculate the public key using $$f(x)=xG$$, where the $$xG$$ operation is scalar multiplication of the scalar $$x$$ with the well-known generator point $$G$$. For the same reason as before, this is not a trapdoor function.

For RSA, the keygen is to pick a public key $$e$$, pick two secret primes $$p$$ and $$q$$, and then calculate the private exponent $$d$$ which can only be calculated with knowledge of $$p$$ and $$q$$ ($$p$$ and $$q$$ are then discarded, and we only retain the modulus $$n=pq$$). The one-way trapdoor function is $$f(x)=x^e\ mod\ n$$, and the secret knowledge to invert the trapdoor function is $$d$$. This allows us to use the inverse function $$f^{-1}(y)=y^d\ mod\ n$$. Unlike DH and EC, we can't re-determine the public key from the private key if we lose the public key exponent $$e$$.

• +0 – Dlog is a trapdoor function in EC. The additive notation is just that: notation. If you want, you could call it "discrete multiplicative", which works just like dlog. — Aug 07, 2022 at 20:12
• +1 – @tylo The definition of a trapdoor function is that it is reversible with knowledge of the trapdoor. This definition does not apply to EC scalar multiplication - it is one-way but not a trapdoor function. — Aug 07, 2022 at 20:19
• +1 – Trapdoor means that you can apply a function to an input, and then do the reverse and get from the output back to the input with knowledge of the trapdoor. Scalar multiplication does not meet this test. If you disagree with me, you're also disagreeing with Thomas Pornin — Aug 07, 2022 at 20:29
• +1 – @CryptoNewbie DH public key generation from the private key does not use a trapdoor one-way function, it uses a one-way function. The RSA trapdoor function is one whose parameters are decided during the key generation, it's not the other way around. A member of the public (or the private key holder that has lost their public RSA exponent) cannot try and apply a trapdoor function to a private RSA exponent in order to get the public RSA exponent. But anyone can transform a DH private key to the corresponding DH public key, or transform an EC private key to the corresponding EC public key. — Aug 07, 2022 at 21:07
• +1 – @knaccc Oh I understood your point 100% now with the added explanation. Everything is clear now, I missed that the secret is actually also needed in the public key generation algorithm and that this goes against the one-way trap-door definition. Thanks again for your help. — Aug 07, 2022 at 22:55