Return to Question

The proof I'm struggling with is the following:

Let $E$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, E] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, E]$ of an adversary $A$ (in a standard attack game) over cipher $E$ is defined as:

$SSadv[A, E] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, E] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are trying to prove is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

The proof I'm struggling with is the following:

Let $\mathcal{E}$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, \mathcal{E}] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, \mathcal{E}]$ of an adversary $A$ (in a standard attack game) over cipher $\mathcal{E}$ is defined as:

$SSadv[A, \mathcal{E}] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, \mathcal{E}] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are trying to prove is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

The proof I'm struggling with is the following:

Let $E$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, E] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, E]$ of an adversary $A$ (in a standard attack game) over cipher $E$ is defined as:

$SSadv[A, E] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, E] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are essentially trying to show is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

The proof I'm struggling with is the following:

Let $E$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, E] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, E]$ of an adversary $A$ (in a standard attack game) over cipher $E$ is defined as:

$SSadv[A, E] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, E] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are trying to prove is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

The proof I'm struggling with is the following:

Let $E$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, E] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, E]$ of an adversary $A$ (in a standard attack game) over cipher $E$ is defined as:

$SSadv[A, E] = |Pr[φ(E(k, m_0))] − Pr[φ(E(k, m_1))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$, $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, E] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are essentially trying to show is:

$|Pr[φ(E(k, m_0))] − Pr[φ(E(k, m_1))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?

The proof I'm struggling with is the following:

Let $E$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, E] ≤ \epsilon$ for all adversaries $A$, even including computationally unbounded ones. Show that $|K| \geq (1 − \epsilon)|M|$.

The semantic security advantage, $SSadv[A, E]$ of an adversary $A$ (in a standard attack game) over cipher $E$ is defined as:

$SSadv[A, E] := |Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]|$

Where $φ$ is a binary predicate on the ciphertext space $C$ (and the associated probability is the probability of the binary predicate evaluating to $1$), $k$ is a random variable uniformly distributed over the key space $K$, and $m_0, m_1 \in M$ (message space) are chosen by the adversary $A$, although the inequality $SSadv[A, E] ≤ \epsilon$ should hold for all $m_0, m_1 \in M$.

Thus, what we are essentially trying to show is:

$|Pr[φ(E(k, m_1))] − Pr[φ(E(k, m_0))]| ≤ \epsilon \implies |K| \geq (1 − \epsilon)|M|$

How would I approach this?