# What primitives are needed to generically implement public-key cryptography?

Public-key cryptographic systems are often implemented on top of an existing problem. For example, RSA is built on top of integers and the difficulty of factoring. ECDSA/ECIES are built on top of elliptic curves and the difficulty of the discrete logarithm.

My question is, what are, mathematically speaking, the exact primitives needed to implement public-key based signature and encryption cryptography in a generic way?

• A large pile of NAND gates is generally sufficient... :-) Dec 29 '16 at 20:09
• Also, generically, we don't even know whether public-key cryptography can actually exist. Dec 30 '16 at 3:08

Unfortunately there is no real answer to this. We know that one-way trapdoor permutations suffice, but this is really just an abstraction of factoring. ECDSA/ECIES/ElGamal don't work via any trapdoor permutation, and neither do lattice-based public-key encryption schemes.

In the private-key world, we know that one-way functions are necessary and sufficient. However, we have no analogous primitive that is both necessary and sufficient for public-key encryption, beyond itself. (That is, of course, public key encryption is both sufficient and necessary for public-key encryption, but this is a very annoying answer that means nothing.)

Note, that one-way functions are sufficient for building digital signatures, and so the question of what is necessary is really only for public-key encryption.

• Hey, beyond itself; what you need for public key cryptography is ... public key cryptography. More information here (on the ingredients of pie). Dec 29 '16 at 19:30
• I might suggest using "symmetric encryption" where you wrote "private-key [encryption]". Private key generally refers to one side of a public-key (asymmetric) system, not to symmetric systems. Dec 30 '16 at 4:22
• Thanks for the great answer. I don't understand how one way functions are sufficient to build digital signatures, though. Dec 30 '16 at 14:09
• @MaiaVictor: to build signatures out of one way functions, see en.wikipedia.org/wiki/Merkle_signature_scheme for a start; also see datatracker.ietf.org/doc/… and datatracker.ietf.org/doc/draft-mcgrew-hash-sigs for two active proposals for how to do it. Dec 30 '16 at 15:27
• @poncho that is so neat! Thank you! I'm so glad you're a member of this site. Thanks for devoting your time to make the world a better place. :) ~ Thanks you all! Dec 30 '16 at 15:52

It depends of course what you require for your cryptosystem, but for just encryption and signature generation (which is also used for authentication, not just for non-repudiation) you just require RSA or ECC.

For RSA the key pair generation is identical for signature generation and encryption. Even the modular exponentiation is about the same. Signature generation is largely identical to decryption and signature verification is largely identical to encryption. The main difference is the padding scheme used for encryption and the signature.

For ECC the key pair generation is also identical for signature generation and encryption. There are some differences between ECDH and ECDSA, but the calculations can still be performed within a largely overlapping set of calculations. ECDH can be used as input for ECIES, which is the encryption method commonly used for ECC cryptography.

There is however not a generic requirement for primitives within a signature generation or encryption scheme, as there is no common construction for signature generation or encryption schemes. Both RSA signature generation and ECDSA are quite different, and the same goes for RSA OAEP and ECIES with, for instance, AES-CBC.

Note that signature generation usually also requires a secure hash algorithm and that encryption schemes usually also require a symmetric cipher, unless they are used for a very small amount of data.

[EDIT] And all schemes rely on a (well seeded, pseudo) random number generator, certainly when it comes to key pair generation.