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?

  • $\begingroup$ Is the error random? That would seem to have a significant impact on the answer. If it is random, I don't see any security issues (or enhancements). If it isn't random, that could be a significant issue. Especially if triggering the error condition is not computationally hard to do. $\endgroup$
    – mikeazo
    Commented Mar 28, 2018 at 13:03
  • $\begingroup$ Note that things probably would be more interesting if there's a (negliglible) probability (over all producable / possible ciphertexts) that the ciphertext has some "bad" property which results in a wrong decryption but with the decryption still being deterministic. $\endgroup$
    – SEJPM
    Commented Mar 28, 2018 at 13:07
  • $\begingroup$ @mikeazo For any specific input, the probability of correct decryption should be at least $1-\epsilon$. So theoretically by running the algorithm many times we could get arbitrarily high confidence in the decryption. $\endgroup$
    – Alon Navon
    Commented Mar 28, 2018 at 13:16
  • $\begingroup$ deniable encryption is not possible with perfect correctness, but things can be done with negligible probability of failures (there's a cool paper building that from LWE for example) $\endgroup$ Commented Mar 28, 2018 at 13:38
  • $\begingroup$ @AlonNavon, should the probabilities hold in an information-theoretic sense, a computational sense, or only under benign conditions? $\endgroup$
    – mikeazo
    Commented Mar 28, 2018 at 14:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.