1
$\begingroup$

Consider a relaxed definition of security. Let $\epsilon < 1$ be a constant and say we only require that for any distribution over $M$ ,any $m \in M $, and any $ c \in C$

$$ |Pr[M=m|C=c] - Pr[M=m]| < \epsilon $$

I want to find a lower bound on the size of key space $K$ relative to $M$ for any encryption scheme that meets this definition.

Improve this question
$\endgroup$
1
  • $\begingroup$ $|\mathcal{K}|\geq|\mathcal{M}|\cdot2^{-\epsilon}$, and using a Taylor approximation, you get $|\mathcal{K}|\geq|\mathcal{M}|\cdot(1-\epsilon)$ for $\epsilon$ 'small'. $\endgroup$
    – Sachin Valera
    Nov 13, 2019 at 18:05

1 Answer 1

Reset to default
2
$\begingroup$

I believe that this 'relaxed' definition gives the same minimal key length as the standard perfect security definition; that is, the number of keys $|K|$ must be at least as large as the number of possible plaintexts $|P|$. This is true for any $\epsilon < 1$.

Suppose we had a set of keys that was smaller than the number of plaintexts, or $|K| < |P|$. In that case, we pick a possible ciphertext $c$ and see that can be decrypted to at most $|K|$ distinct plaintexts (depending on the key); hence there must be a plaintext $p_0$ that it cannot decrypt to. Let us call plaintext $p_1$ a plaintext that it can decrypt to.

Then, consider the probability distribution:

$M = p_0$ with probability $\epsilon$

$M = p_1$ with probability $1 - \epsilon$

$M$ is any other plaintext with probability 0

If we consider the equation with $m = p_0$, we have:

$Pr[ M = m | C = c ] = 0$ (because that plaintext is impossible with that ciphertext)

$Pr[ M = m ] = \epsilon$

And hence $|Pr[M=m|C=c] - Pr[M=m]| = \epsilon \not< \epsilon$, and so we find that the required inequality does not hold.

Hence, that relation can hold in general only if $|K| \ge |P|$, which is the same bound as what perfect secrecy requires.

Improve this answer
$\endgroup$
7
  • $\begingroup$ This is wrong - it would imply that all modern ciphers require the key to be at least as long as the plaintext. $\epsilon$-secrecy yields $|\mathcal{K}|\geq|\mathcal{M}|\cdot2^{-\epsilon}$ $\endgroup$
    – Sachin Valera
    Nov 13, 2019 at 17:58
  • $\begingroup$ @SValera: actually, this implies that no modern cipher gives "perfect secrecy", which is an accurate statement. Modern ciphers don't rely on perfect secrecy (that is, even with unbounded computation, you cannot obtain any information on the plaintext), but instead on computational assumptions (that is, you cannot perform any computation with the computational resources you have to obtain nontrival amounts of information about the plaintext; this computation may involve a key search, or another method) $\endgroup$
    – poncho
    Nov 13, 2019 at 18:07
  • $\begingroup$ OP was asking about $\epsilon$-secrecy though, not perfect secrecy - modern ciphers are $\epsilon$-secret (with $\epsilon>0$) $\endgroup$
    – Sachin Valera
    Nov 13, 2019 at 18:07
  • $\begingroup$ @SValera: both modern ciphers and this question talk about $\epsilon$-security, but they mean different things by it. This question explicitly talks about probability distributions; those are assumed to be infeasible to compute with modern ciphers. $\endgroup$
    – poncho
    Nov 13, 2019 at 20:27
  • $\begingroup$ The form of $\epsilon$-secrecy via distributions in the above question is equivalent to the usual one - my comment on OP's post holds true for his question. $\endgroup$
    – Sachin Valera
    Nov 13, 2019 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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