# Reason for difference in assumptions for practical private-key and public-key crypto

Theoretical cryptography tells us that everything in the world of private-key cryptography (CCA-secure symmetric encryption, message authentication codes, etc.) can be built from one-way functions and that public-key cryptography (e.g., CCA-secure public-key encryption) can be build from the stronger notion of one-way trapdoor permutations. In addition, it is known that both one-way functions and one-way trapdoor permutations can be built based on certain number-theoretic assumptions such as the hardness of integer factorization and the discrete log assumption.

In the case of practical private-key cryptography, however, constructions are almost never based on number-theoretic assumptions, but rather on much more "high-level" assumptions, for instance the assumption that AES is a pseudo-random permutation (here I'm ignoring some technical details, e.g. that a pseudo-random permutation must be defined for infinitely many key sizes, at least to be secure in an asymptotical sense).

In contrast, all known public-key constructions (including those used in practice) seem to be based on either number-theoretical assumptions (e.g., RSA, DDH) or, in a few cases, assumptions regarding linear codes or ideal lattices - all of which seem rather "low-level" compared to e.g. the AES or DES assumptions used for private-key schemes.

This seems to explain why the public-key crypto schemes used in practice today are orders of magnitude slower than the private-key schemes used in practice.

Is there any explanation for this difference in the level of assumptions underlying the private- and public-key crypto schemes used in practice today? Is this due to historical reasons, or is there some other, perhaps mathematical, reason why no efficient public-key schemes today are based on assumptions on a similar high level as e.g. the AES? Have I missed some fast public key encryption schemes based on assumptions on such high level?

• – user991 Feb 1 '14 at 21:37
• The above result explains why no known public-key schemes are based on one-way functions in a black-box manner. But it does not explain why we don't have any efficient constructions of, say, one-way trapdoor permutations that are not based on number-theory - in the same way that e.g. AES is an efficient construction of a one-way permutation (with no trapdoor) that is not based on number theory. – tpj Feb 1 '14 at 22:20
• I'm not aware of any other candidates for one-way trapdoor permutations, but there are these two candidates for CCA-secure PKE that are based on linear codes and ideal lattices, respectively. $\hspace{.72 in}$ – user991 Feb 2 '14 at 0:30

• Making "big jumbles of bits" is sufficient for signatures; namely, hash-based signatures. $\hspace{1.04 in}$ – user991 Feb 3 '14 at 21:06