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

Question

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?

Answer 1

AES is not a one-way permutation; it is a permutation, for sure, but whoever can apply it can also apply its inverse. Crudely said, the AES decryption key is identical to the AES encryption key. A one-way permutation would be like a hash function: everybody can compute it in one direction, with no secret value, but nobody knows how to do it in the other direction.

Right now, we do not know how to make one-way trapdoor permutations without resorting to number theory. It is not that it is impossible; only that we did not find any. On the other hand, we have some good candidates for one-way functions (practical hash functions) which are considerably more efficient; therefore, for practical cryptography with systems that only need one-way functions, we use hash functions, not number theory. A hash function based on number theory has been tried but its performance is so abysmal that nobody is really interested in it.

Historically, the whole world was secret-key-only with no number theory; algorithms had evolved as ways to make big jumbles of bits. At best, some of these scrambling systems were designed to be permutations: these are modern block ciphers. We seem to know how to mix bits together so that the result cannot be unravelled (i.e. AES seems to be secure as a block cipher, and that's not for lack of trying to break it); but we don't know how to do it and disassociating the powers to encrypt and to decrypt. In other words, when we design a block cipher, we can inject the key, which selects the actual permutation, but we don't know how to inject it in such a way that the inverse permutation is not revealed as well. The only tools we have found yet to do that involve algebra and number theory, and they are slow.

On the other hand, the same algebraic tools open extra possibilities, namely asymmetric encryption and signatures. These extra features are so useful that we tolerate the performance issues implied by the use of these algebraic tools. So that's the historic point of view: the question is not why we don't make symmetric cryptography with number theoretic tools; rather, it is why we use the slow, cumbersome number theoretic tools at all. And the answer is that we don't know anything better for asymmetric crypto.