Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration 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?)

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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.