Let $(E,D)$ be a cipher with message space $M = \{0,1\}^n$ and key space $K = \{0,1\}^n$.

Assume that there is an algorithm $A\colon \{0,1\}^n \to \{0,1\}^n$ of size $T$ that given an encryption of a message can guess the entire message with probability $0.2$. Namely, for a message $m \in M$ it satisfies $$P[A(E(k,m)) = m] = 0.2$$

I want to prove that $(E,D)$ is not $(T + O(n), 0.1)$-secure.

A cipher $(E,D)$ is called $(T + O(n), 0.1)$-secure if for every two messages $m_1, m_2 \in M$ and every algorithm $B\colon \{0,1\}^n \to \{0,1\}$ of size at most $T + O(n)$, it follows that: $$| P[B(E(k,m_1)) = 1] - P[B(E(k,m_2)) = 1] | \le 0.1$$

My idea was to assume on the contrary that $(E,D)$ is $(T+O(n), 0.1)$-secure, and then find an algorithm $B\colon \{0,1\}^n \to \{0,1\}$ of size $T+O(n)$ that uses $A$ to break this encryption.

Namely I need to show that for any two messages $m_1, m_2 \in M$ it satisfies:

$$| P[B(E(k,m_1)) = 1] - P[B(E(k,m_2)) = 1] | > 0.1$$

Basically I need to describe such $B$ and two messages $m_1, m_2$ that satisfy this inequality.

My idea was to pick two random messages $m_1, m_2 \in M$. Then, somehow use $A$ to get the probability $P[B(E(k,m_1)) = 1] = 0.2$, and use randomness somehow to get the probability $P[B(E(k,m_2)) = 1] = 0.2 \times 0.5 = 0.1$

However, I don't really know how to do that.

Help or some hint would be very appreciated!

  • 1
    $\begingroup$ What is "$(T + O(n),0.1)$-secure"? $\endgroup$ – Yuval Filmus Nov 13 '20 at 20:31
  • $\begingroup$ Can you give us a citation to the source where you originally encountered this problem, and provide chapter and exercise number? For instance, this helps provide context, and helps others with a similar question to find this page via search. $\endgroup$ – D.W. Nov 13 '20 at 22:22
  • $\begingroup$ What is $k$ in the definition of $(\cdot,\cdot)$-secure? $\endgroup$ – xskxzr Nov 14 '20 at 4:11

Let $m_1$ be an arbitrary message. We are guaranteed that $P(A(E(k,m_1)) = m_1) = 0.2$. Averaging over all other messages, there is some message $m_2$ such that $P(A(E(k,m_1)) = m_2) \leq 0.8/(2^n-1) \leq 2^{-n}$.

Consider the following algorithm $B$: on input $x$, if $A(x) = m_2$ then output $1$, else output $0$. By assumption, $P(B(E(k,m_1))=1) \leq 2^{-n}$, whereas $P(B(E(k,m_2))=1) = 0.2$. When $n \geq 4$, the difference between the two probabilities is larger than $0.1$.

  • $\begingroup$ Thanks! this is a great solution. I Guess I need a little more exercise $\endgroup$ – Gabi G Nov 14 '20 at 12:35

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.