Would a symmetric cipher with a keylength a big as the data length be information theoretically secure?

Question

One-Time-Pad is information theoretically secure as long as the random number stream is evenly long or longer than the data stream it encrypts, for a "deciphered" message could have been any message with the same length as the given with the same probabillity. Does the same apply to symmetric ciphers, too?

For instance if I have 1024 bits to encrypt, break it into chunks 128 bits and encrypt it with AES-128, each with a different (assume: true) random key, will that be information theoretically secure just as OTP? Or would a hypothetical algorithm (let's assume it would be as quick as the encryption function) impact the (theoretical) security?

In other words: Does using a symmetric encryption algorithm (such as AES) lower the probabillity of a ciphertext being originated from a specific plaintext even if the used key has "OTP-length" and is completely unknown?

Answer 1

AFAIK, no one has proven that AES on a single 128-bit block with a true-random 128-bit key does not provide information theoretic security (such a proof would probably be the end of AES as it would demonstrate a weakness). OTOH, no one has proven that it does. I suppose it is possible that it does, but such a proof is likely to be extremely difficult. Just look at the simplicity of the ciphers which do provide information theoretic security. The simplicity of the cipher is part of what made it possible to prove. Therefore, due to the lack of a proof showing such a high level of security, and the perceived difficulty of formalizing such a proof, I'm going to have to say the answer is no.

Answer 2

No, using any keyed permutation with key length equal to the block size reduces the number of possible plain texts by ~1/3

Assume first that AES reasonably approximates a pseudorandom permutation, for each block of the message, the attacker (assuming unbounded computing power) can calculate the plain text for all keys. This is equivalent to throwing 2^128 balls into 2^128 baskets randomly. There will be collisions. The chance that any plain text is not a valid solution is approximately 1/e

filled fraction = 1-((n-1)/n)^n , n=2^128

this converges to 1-1/e

this reduces the effective number of plaintexts by about 1/3 (=0.63 ~= -0.66 bits). The reduction also tells the adversary about the probablity of any ciphertext being correct since about half the remaining plain texts got two hits instead of one with 2x the probability of being correct.

A problem with this scheme is that fooling the observer into accepting a plausible fake message requires solving for the key K which would connect the plaintexts and ciphertexts, fortunately, thanks to the recent SHA3 competition the cryptanalysis to do so has been mostly done.

Answer 3

If you have a keyed family of $2^b$ distinct permutations $E_k(p) : \{0,1\}^b \times \{0,1\}^b \to \{0,1\}^b$ over $b$-bit blocks, and select an independent, uniform random key for each plaintext block, then your proposed mode is perfectly secure for the same reason that one-time pads are: for any candidate plaintext/ciphertext pair $(p, c)$, there exists a key $k$ such that $E_k(p) = c$. You securely show $c$ to an adversary, because given that $k$ was selected uniformly at random, with the information they have every possible plaintext is equally likely.

We don't even have to assume that the family $E_k$ is pseudorandom for the above to work. For example, $E_k(p) = k \oplus p$ is not a pseudorandom family, but is perfectly secure when used in the mode that you propose. We just need $2^b$ distinct permutations—it doesn't matter what those permutations are!

However, if your blockcipher provides fewer than $2^b$ distinct permutations, then you no longer have perfect security. In this case for some ciphertext/plaintext pair $(c,p)$, there is no key $k$ such that $E_k(p) = c$. A computationally unlimited adversary that observes $c$ can therefore learn that $p$ is not the corresponding plaintext, and this violates perfect security.

So your question comes down to whether your blockcipher has equivalent keys. Some do! For example, the Tiny Encryption Algorithm (TEA):

TEA has a few weaknesses. Most notably, it suffers from equivalent keys—each key is equivalent to three others, which means that the effective key size is only 126 bits.

TEA does have a 64-bit block size, though, so having "only" $2^{126}$ distinct permutations would not render it insecure in the mode you propose. But AES has a block size of 128 bits; therefore if AES-128 has even just one pair of duplicate keys, then your AES-based proposal is not perfectly secure. (See also: "Do all ciphers have equivalent decryption keys?")

---

So the big lesson here is this: blockciphers are designed to be pseudorandom permutation families, but this property is neither necessary nor sufficient for perfect security in the mode you propose. Apples, meet oranges...