Are there any symmetric cryptosystems based on computational complexity assumptions?

Question

Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer factorisation?

If not, why not?

Answer 1

1. Finding uniform random $x$ given $x^3 \bmod{pq}$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.^*

2. Finding uniform random $k$ given $\operatorname{AES256}_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.

That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 \bmod{pq}$ is much costlier than the computation of $\operatorname{AES256}_k(92187681)$. In other words, RSA-2048 is much more expensive for less security than AES-256.

You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’. But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks. In reality, AES is a much harder problem than RSA!

There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM. Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.

The term ‘provable security’ means nothing more than there is a theorem. These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA. So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.

---

_{^* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier. There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard. Hence not even the RSA problem has ‘provable security’ relative to factoring.}

Answer 2

The existence of one-way functions (OWFs) implies symmetric-key encryption (SKE) through the following sequence of reductions:

1. Build a pseudo-random generator (PRG) from the OWF using the HILL construction [H+] (This is not very efficient --- one gets better constructions from one-way permutations: see [BM]).
2. Use the GGM construction [GGM] to construct a pseudo-random function (PRF) from this PRG
3. The construction of SKE from PRF is folklore (the key of the PRF serves as the key $k$ of the SKE, and to encrypt a message $m$ in the range of the PRF, pick a random element $r$ from the domain of the PRF and set $m\oplus PRF_k(r)$).
4. Alternatively, one can construct a block cipher a.k.a pseudo-random permutation (PRP) from the PRF using Luby-Rackoff [LR] --- once you have block ciphers, it is possible to encrypt arbitrary-sized messages using an appropriate mode of operation (e.g., CBC).

So, it boils down to the assumptions that yield OWFs as raised in this previous question. There are several candidate constructions of one-way functions from diverse problems arising from cryptography (e.g., stream ciphers, hash functions), complexity theory (e.g., the planted SAT and planted Clique problem), combinatorics (e.g., Goldreich's one-way function) and learning theory: I'd recommend reading Barak's recent survey titled "The Complexity of Public-Key Cryptography" for a thorough treatment of this topic. Number theoretic assumptions like integer factorisation or discrete-log problem also yield one-way functions, but they are in some sense an overkill as they have more "structure" than required for SKE.

In practice, however the constructions that you get by following the above chain of reductions are terribly inefficient and one relies on a (heuristic) block cipher like AES.

[BM] Blum and Micali. How to Generate Cryptographically Strong Sequence of Pseudorandom Bits. SIAM JoC’82.

[GGM] Goldreich, Goldwasser and Micali. How to Construct Random Functions. JACM’86.

[H+]: Håstad, Impagliazzo, Levin and Luby. A Pseudorandom Generator from Any One-Way Function. SIAM JoC’99.

[LR] Luby and Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM JoC’88.

Answer 3

The cipher from Fully Homomorphic Encryption over the Integers is a candidate example.

It is a symmetric cipher that is provably reducible to the approximate greatest common divisor problem.

Note that it is symmetric in the sense of "the same key is used to encrypt and decrypt", as opposed to "extremely fast and useful for bulk data". The latter definition is typically assumed when the words "symmetric cipher" are used, but that is not the case here.