3
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\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 Mar 28 '18 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♦ Mar 28 '18 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 Mar 28 '18 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$ – Florian Bourse Mar 28 '18 at 13:38
  • $\begingroup$ @AlonNavon, should the probabilities hold in an information-theoretic sense, a computational sense, or only under benign conditions? $\endgroup$ – mikeazo Mar 28 '18 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.