Trapdoor Function
Definition
A one-way function with a secret 'trapdoor' that makes the reverse direction tractable. RSA's trapdoor is the factorisation of n into p and q.
- Definition
- A one-way function with a secret shortcut for reversal
- RSA example
- Trapdoor is the factorisation of n into p and q
- Field
- Asymmetric cryptography
- Property
- Forward direction easy, reverse hard without the secret
Common questions
How does a trapdoor function differ from an ordinary one-way function?+
An ordinary one-way function is hard to reverse for everyone, with no shortcut at all, while a trapdoor function is deliberately built so that reversal becomes easy for anyone who holds the secret trapdoor, such as a private key.
Why does the security of RSA rely on a trapdoor function rather than a simple one-way function?+
Public-key encryption needs the private key holder to decrypt easily while everyone else finds it computationally infeasible, and only a trapdoor function provides that asymmetry between the public and private sides.
Related terms
- Asymmetric Cryptography
- Cryptosystem that uses a key pair: a public key (shareable) and a private key (secret). Built on mathematical trapdoor functions where the...
- Digital Signature
- Cryptographic proof of authenticity, integrity and non-repudiation. Sign by encrypting a hash of the message with the signer's private key; verify by...
- DSC
- Digital Signature Certificate. An Indian X.509 certificate issued by a CCA-licensed CA. Class 3 is the current mandatory tier for income tax,...
- ECC
- Elliptic Curve Cryptography. Smaller keys for equivalent security; 256-bit ECC is roughly equivalent to 3072-bit RSA. Used in ECDSA signatures, ECDH key...
- Hash Function
- Deterministic function that maps an input of arbitrary length to a fixed-length output. A cryptographic hash adds pre-image resistance, second pre-image resistance,...
- HMAC
- Hash-based Message Authentication Code, RFC 2104. Combines a secret key with a hash function to produce a MAC; immune to the length-extension...
- PKI
- Public Key Infrastructure. The set of roles (CA, RA, VA) and artefacts (X.509 certificates, CRL, OCSP) that bind a public key to...
- RSA
- Rivest-Shamir-Adleman, 1977. Public-key cryptosystem based on the hardness of factoring a product of two large primes. Common sizes today: 2048-bit (standard), 3072-bit...