By Shanon theorem, a perfect secrecy encryption scheme must use a key space of equal size as the message space.

But when the correctness requirement is weakened such that $Pr[Dec_k(Enc_k(m))=m]=1/2$ we know that the key space may be smaller than the message space.

Generally, what is the lower bound of the key space when the scheme correctness requirement is $Pr[Dec_k(Enc_k(m))=m] >= 2^{-t}$? (and why?)

  • 1
    $\begingroup$ You can omit part of the information from the output and guess them. Those guesses will be incorrect sometimes. This boils down to using lossy compression before encrypting. $\endgroup$ – CodesInChaos Jan 31 '14 at 15:45

I'll further explain the comment of @CodesInChaos and then give a simple example:


When the correctness requirement is weakened the encryption scheme can omit part of the message $m$ (of length $|m|$) to be encrypted and just "loose" it in a way that the cipher (the output of the Encrypt method) is totally independent of that part. Thus the message that effectively is encrypted is not $m$ but rather just part of it of length $|\ell|<|m|$ and thus the key doesn't have to be of length at least $|m|$ but rather be of length at least $|\ell|$.


The most basic example is an encryption using the One-Time-Pad Scheme, in a model where the correctness requirement from the scheme is weakened to: $Pr[Dec_k(Enc_k(m))=m]=\frac{1}{2}$. Take a message $m$ of length $|m|$ and a random key $k\in\{0,1\}^{|m|-1}$; the encryption method take the first $|m|-1$ bits of $m$, call it $m'$ and output the cipher $c=m'\oplus k$. Then, given $c$ and $k$, we can decipher (or decrypt) the cipher correctly with probability of exactly $\frac{1}{2}$ by computing $m'=c\oplus k$ and then randomly guessing the $|m|^{th}$ bit of $m$; since we get the correct bit with probability $\frac{1}{2}$ we satisfy the correctness requirement.

About the bound

We can say the when the correctness requirement is $Pr[Dec_k(Enc_k(m))=m]\geq\frac{1}{2^t}$ the key space must be of length no less then $|m|-t$. If the key in the example above is of length $|m|-t$ then the decryption algorithm can guess the omitted $t$ bits of the message with probability $\frac{1}{2^t}$ as required.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.