In chapter 2 of Katz's Introduction to Modern Cryptography there is a formal definition of an encryption scheme. As part of this definition, the decryption algorithm is required to be perfectly correct, and thereafter the book assumes the decryption algorithm is deterministic and never outputs a wrong decryption.
Throughout the book, we assume that encryption schemes are perfectly correct, meaning that for all $k\in\mathcal K$, $m \in M$, and any ciphertext $c$ output by $Enc_k ( m)$, it holds that $Dec_k (c) = m$ with probability 1. This implies that we may assume $Dec$ is deterministic without loss of generality (since $Dec_k(c)$ must give the same output every time it is run). We will thus write $m := Dec_k(c)$ to denote the process of decrypting ciphertext $c$ using key $k$.
My question is: If we allow $\mathrm {Dec}$ to produce a wrong decryption with negligible probability $\epsilon$ (this could be any value < 1, and by repeated application of $Dec$ we could get any level of confidence we want short of 1), would this affect the theory at all?
Would everything be the same, only with this additional chance of error? Or, if we allow these negligible mistakes, could there conceivably be some algorithm, that is 'better' (security or efficiency-wise) than anything possible with deterministic decryption?
