AES function with 128 bit key and 128 bit input size - does it have perfect secrecy? If I look at the version of AES that gets key of size 128 bit and encrypts messages of size 128 bits.

If I get some random key for the function, can I say it has a perfect secrecy and why?

After a lot of thinking it got me to the next question: if I apply AES 2 times, both times on the same input but with 2 different keys, can I get the same output or must the result be different?
I don't think a block cipher can offer perfect secrecy. Perfect secrecy means that knowledge of the ciphertext doesn't give you any information about the plaintext.

However a block cipher is a keyed permutation: the key is used to choose one permutation of the plaintext to ciphertext. The number of possible permutations is almost infinite. This means that the permutations selected by the key is a (randomly chosen) subset of all possible permutations.

Now the problem is that there may be mappings of one plaintext to a ciphertext that are more common in this set than others. This means that the tiniest amount of information may be leaked by a ciphertext: a specific key or group of keys is more likely to convert a specific plaintext to a specific ciphertext. This means that a certain plaintext is more likely than another plaintext for a given ciphertext.

And this, in turn, means that a block cipher is not perfectly secret - even if the key is the same size as the plaintext / ciphertext.



As for the second question: yes, you can get the same output. Although the keys select a specific permutation, it isn't said that the same mapping of one specific plaintext to one specific ciphertext isn't part of the permutation; a permutation is different if even just one mapping in the complete set of mappings is different. The chances are of course abysmally small to find it.



In the end we just don't need perfect secrecy. If we do want perfect secrecy it makes absolutely no sense to use a block cipher while a simple XOR suffices. The trick - as always - is to generate and share the perfectly random key stream. Once you have that you don't need AES anymore.