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 that 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...

-

The short answer is that if your encryption routine is a bijection, then the first is fine. However, if it is not surjective, then you need to define what on earth it means to decrypt an invalid element. This could be done by having elements with multiple preimages (as may occur in schemes using bad/misimplemented padding) or output an error symbol $\perp$.

Below the bar is a longer, rather more rambling answer, as initially posted.

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$. In this case it would be fine to define decryption as having simply the message space as it's codomain.

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).

In the case of authenticated encryption, we design our encryption routines such that it is hard to find an element $c$ of the ciphertext space that has a preimage $m$ unless that we have already calculated $E_k(m) = c$. In these cases, the symbol $\perp$ demonstrates that the attempted decryption of a ciphertext that does not pass the authenticity check.

A possible reference for further related questions would be Section 2.1 of Katz-Lindell, but note that this is given in the probabilistic model. Most modern AE work is performed in a nonce-based setting.

-
Where did the OP get this definition from? – Melab Apr 17 at 17:44
@Melab: looking back at it, I'm not particularly happy with my initial answer. I've have a very quick go at improving it, but its still not great. – figlesquidge Apr 19 at 12:16