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

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$.

Solved by user43864 (3,482 )
Aug 07, 2022 at 19:17