According to eavesdropping indistinguishability experiment $PrivK_{A,\Pi}^{eav}$ from page 34 of this book, I define $\varepsilon$-perfect secrecy as this($\varepsilon>0)$: For every adversary $A$ We have: $Pr[PrivK_{A,\Pi}^{eav}=1]≤\frac12+\varepsilon$. I want to prove that $\varepsilon$-perfect secrecy holds, when $|K|<|M|$. Can anybody guide me? ($|K|$ and $|M|$ are the number of keys and messages in our schema respectively).

  • $\begingroup$ Don't you mean "I want to prove that $\epsilon$-perfect secrecy does not hold, when $|K| < |M|$"? $\endgroup$ – poncho Jun 21 '17 at 13:48
  • $\begingroup$ I mean with $|K| < |M|$, ϵ-perfect secrecy can be achieved, when ϵ > 0. @poncho $\endgroup$ – Patris Jun 21 '17 at 15:26
  • $\begingroup$ this is a problem from the book. Try to understand the proof about why we need $|\mathcal K| \geq |\mathcal M|$ for perfect secrecy + Shannon's theorem. It may help $\endgroup$ – DiamondDuck Jun 21 '17 at 17:14
  • $\begingroup$ Yes, specifically, this is problem 2.12 of the second editon of Katz & Lindell's "Introduction to Modern Cryptography". $\endgroup$ – user47922 Jun 21 '17 at 18:14
  • 1
    $\begingroup$ Here's a sketch then: in that chapter there are 3 equivalent definitions of perfect secrecy. How do they change due to additive advantage $\epsilon$? $\text{Pr}(M = m | C = c) - \text{Pr}(M = m) = 0$ becomes...what? Once you decide that, fix a particular ciphertext $c$, and consider how many messages could encrypt to $c$, assuming you draw from uniform distribution over the messages. (remember that the encryption function can be probabilistic). $\endgroup$ – user47922 Jun 21 '17 at 19:58

I want to prove that $\epsilon$-perfect secrecy holds, when $|K|<|M|$.

I think you are misunderstanding something here. For perfect secrecy as defined, $|K| \geq |M|$ does not imply perfect secrecy. It is the other way around: If perfect secrecy is given, this implies $|K| \geq |M|$.

The implication the other way is impossible to show: Consider $E(m,k) = m$, with some keyspace $K$ larger than the message space $M$ (no need to be more specific). In this case we have $|K| \geq |M|$, but obviously it's not perfectly secret.

And the same goes for your idea: You can not show that something has any kind of secrecy definition, when just the size of the messagespace and keyspace fullfill some equation or inequality. The (almost trivial) counterexample $E(m,k) = m$ with matching key- and message spaces works there as well.

  • $\begingroup$ I mean with $|K| < |M|$, ϵ-perfect secrecy can be achieved, when ϵ > 0. $\endgroup$ – Patris Jun 21 '17 at 15:26
  • $\begingroup$ @Patris But that's not what you wrote in your question. Regarding the question if you can achieve your definition, my guess would be you have exactly the same solutions as perfect secrecy itself, and therefore none with $|K| < |M|$. I would also guess that you have some specific kind of encryption in mind (e.g. block ciphers). And that is definately not going to work. $\endgroup$ – tylo Jun 22 '17 at 7:26

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.