# The exact definition of a symmetric encryption

I have doubts for the definition of the decryption algorithm $D(.)$. I think I've already seen that the decryption returns a plaintext $M$ on input the key $K$ and $C=E_K(M)$.

I have also seen thet the decryption algorithm returns either $M$ or the special symbol $\bot$.

Is the first definition valid in the case of symmetric encryption ? Especially when we deal with non authenticated encryption...

Thank you.

-

## 1 Answer

This depends on the encryption algorithms in use. If the encryption algorithm is a bijection, then every possible $C$ must have a preimage. Examples of this include block ciphers like AES. In these cases, the decryption algorithm will output a message $m$ such that $E_k(m)=c$. Note that if $c$ has been tampered with by an adversary but is still the same length, then it will be possible to find a preimage under $E_k$ even though it was not produced as such. That is, in these cases: $D_k(c)$ returns the unique value such that $E_k([D_k(c)])=c$.

However, theoretically at least, there is no reason my encryption scheme would need to be surjective (it doesn't need to 'fill' the ciphertext space). For example, I can define a scheme where the message space $M = \{0,1\}^{128}$ and ciphertext space $C=\{0,1\}^{130}$ such that $$c = E_k(m) = 00||\mathrm{AES}_k(m)$$ This would meet the security promises of AES (after all, it is just an embedding). However, consider the decryption function. Writing the ciphertext as $c=x||y||c'$, where $x,y$ are bits and $c'$ is a 128-bit bitstring, then $$D_k(c)=D_k(x||y|c')=\begin{cases} \mathrm{AES}_k^{-1}(c') & x=y=0 \\\perp & else \end{cases}$$ In this case, whilst for all valid ciphertexts we can provide a decryption, there is no way any ciphertext valid can be generated that begins with anything other than $00$. So, when asked to decrypt such a message we must provide some form of error message, the standard for which is to use $\perp$ (as in contradiction).

This irritating observation is covered by the standard assumption that all encryption schemes are perfectly correct. That is, we normally assume that for every element of the ciphertext space, there is a single valid decryption. With this assumption, we have that for any $c\in C$ there exists exactly one $m\in M$ such that $D_k(c)=m$. Notice that we do not require that $E_k(m)=c$, since $E_k$ may be probabilistic and thus $E_k(m)$ might have multiple correct outputs.

In the case of authenticated encryption, the decryption algorithm must be slightly more complicated. Not only must it calculate the decryption of the ciphertext, it must also confirm that the ciphertext is valid (using one of many possible methods depending on the scheme). In these cases, the symbol $\perp$ is used to denote the attempted decryption of a ciphertext that does not pass the authenticity check.

A good reference for further related questions would be section 2.1 of Katz-Lindell.

-