2
$\begingroup$

It can be shown that if $E$ is a deterministic encryption with key of length $n$ and messages of length $l\geq n + 10$ then there exist two messages $m_0$, $m_1$ and a strategy for Eve so that given an encryption $c = E_{k}(m_b)$ for random $k$ and $b \in \{0, 1\}$, Eve can output $m_b$ with probability at least $0.99$. (Eve is computationally unbounded)

Proof is shown here (in the last page): http://www.boazbarak.org/cs127/chap01-introduction.pdf

Now, I would like to prove the exact same thing for random encryption algorithms that use, say n, random bits. The problem is that the set of all possible encryptions of a certain message can be much larger. Let's say $E$'s random bits are $r\gets\{0,1\}^n$ drawn uniformly, then the set $\{E(m;r)\}_{k,r}$ can have size $2^{2n}$ which might be (much) larger than $2^l$ where $l$ is the length of messages.

Comparing to the deterministic proof, it is not hard to show that if we still choose $m_0$ arbitrarily and use the same kind of decision rule for $A$ the adversary, there exists a randomized $E$ and some $m_0$ such that for every $m_1$ the probability for $A$ to be correct is bad. So in order to deal with the randomized case, we must not choose $m_0$ arbitrarily or come up with a new decision rule for $A$.

Our only assumption is that $D_k(E_{k}(m;r))=m$ for all $r,m,k$. (The decryption algorithm cannot "miss")

I was wondering if anyone could offer a useful observation or any hints.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Eventually, I was able to solve this question. For anyone wondering, my problem was (mainly) the generalization of the deterministic adversary decision rule to the randomized case.

Originally, the deterministic decision rule was $$A(ct)=\begin{cases}m_0 & ct\in\{E_{sk}(m_0)\mid sk\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$ And I generalized it to $$A(ct)=\begin{cases}m_0 & ct\in\{E_{sk}(m_0;r)\mid sk\in\{0,1\}^n,r\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$ But the good generalization would be $$A(ct)=\begin{cases}m_0 & m_0\in\{D_{sk}(ct)\mid sk\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$

Also, this time around you fix $m_1$ and check out random $m_0$'s. Well, the names do not really matter, but the point is that the decision rule depends on the random message, not the fixed one.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The rule is easy; how do you show that there always exist two messages $m_0, m_1$ where it decides correctly for $>0.99$ of the keys? I've been pondering that question; I believe that's true, but I haven't arrived at a proof... $\endgroup$
    – poncho
    Commented Nov 9, 2017 at 20:09
  • $\begingroup$ @poncho if we fix $m_1$ and check out $\Pr_{m_0,sk,r}[m_0\in\{D_s(E_{sk}(m_1;r))\mid s\in \{0,1\}^n\}]$ we see that for every choice of $sk$ and $r$ the probability is at most $\frac{2^n}{2^l}$ because $m_0$ is chosen uniformly at random and the set size is at most $2^n$. Therefore, the expectation over $m_0$ of $\Pr_{sk,r}[m_0∈\{D_s(E_{sk}(m_1;r))\mid s\in \{0,1\}^n\}]$ is also upper bounded by $\frac{2^n}{2^l}$ and we can fix a specific good $m_0$. Also, it is obvious that $\Pr_{sk,r}[m_0∈\{D_s(E_{sk}(m_0;r))\mid s\in \{0,1\}^n\}]=1$. $\endgroup$
    – Nathan
    Commented Nov 10, 2017 at 10:44
0
$\begingroup$

Let's say E's random bits are $r\gets\{0,1\}^n$ drawn uniformly, then the set $\{E(m;r)\}_{k,r}$ can have size $2^{2n}$ which might be (much) larger than $2^l$ where $l$ is the length of messages.

Hint: redefine the assumption on the message length $l \ge 2n + 10$...

Improve this answer
$\endgroup$
1
  • $\begingroup$ This would be trivial, this is NOT what I am trying to prove. $\endgroup$
    – Nathan
    Commented Nov 8, 2017 at 19:11

Your Answer

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

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