# Why does a perfect secrecy can be achieved when decryption correctness is not totally required?

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

• 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. – CodesInChaos Jan 31 '14 at 15:45

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

Explanation

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

Example

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.

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.