Why don't most encryption algorithms use perfect secrecy?

Question

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?

Why aren't many popular algorithms like AES like this?

Answer 1

Why don't most encryption algorithms use perfect secrecy?

Perfect secrecy can only achievable if the $\text{key size} \geq \text{message size}$ and the key is never re-used.

It is not suitable for modern usage, where a lot of messages are sent/received and that is impractical since one has to send the key beforehand in a secure channel and this is not encryption. You must trust the carrier or you have to carry the keys yourself. Instead, we go the other way, use shorter keys with good analyzes algorithms. Exchange the key with DHKE protocol ( where mostly elliptic curve version is used), and use AES-GCM, AES-GCM-SIV, or ChaCha20-Poly1305.

Reuse of the key has catastrophic results that confidentiality is broken. What will you do when the keystream is depleted? Would you wait for the new key, or you would re-use some part of the keystream? Both have critical results. You will not communicate when needed or OTP will fail, see Crib-Dragging. Instead, one can use DHKE to create a new key, even for every encryption, and even can achieve forward secrecy.

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?

The encryption should be easily computed so that the legal party doesn't use so much power to encrypt. This doesn't mean that it is breakable since the adversary can compute with lots of resources. If the algorithm, block or stream cipher, use correctly given key then, then one can adjust the key size so that brute force out of reach of anybody, even for the quantum computers.

The encryption can be randomized and indeed in modern cryptography, we prefer this, forget the otherwise, it is insecure. See semantic security and indistinguishability. For example, we prefer at least Ind-CPA security. CBC and CTR mode can achieve this, however, ECB cannot. Actually we want more, the standard of IND-CCA2/NM-CCA2- ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack. The examples are AES-GCM, AES-CCM, and ChaCha20 which are an Authenticated Encryption with Associated Data (AEAD) and provides Confidentiality, Integrity and Authentication.

The decryption must be unique since there is no way for the receiver to determine the correct message among the possible answers.

The password is not the correct term. We use the encryption key or in a short key when it is clear in the context. The password is only applicable if the key is generated by using a Password Based Key Derivation Function like PBKDF2 or Argon2id.

Why aren't many popular algorithms like AES like this?

Mostly answered, AES is a fast and secure keyed permutation. Yes, for each key, AES chooses a permutation from all possible permutations. We expect that it chooses this in a way that its selection is indistinguishable.

---

There are also Q/A and answer here that talks about achieving perfect secrecy with AES with some very nice answers;

• Can one claim that AES is a perfect cipher?
• Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
• Key length and message length in AES and perfect secrecy if plaintext length <= key length