Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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
Can you please give a more concrete answer? (with a lower bound..) – Bush Jan 31 '14 at 16:52
up vote 1 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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