Let $E:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a good PRP and consider blockcipher $\widetilde{E}$ defined as follows

$$\widetilde{E}(K,X) = \begin{cases}K & \text{if } X=K \\ E(K,K ) & \text{if } X = E^{-1}(K,K)\\ E(K,X) & \text{otherwise}\end{cases}$$

Black used this to show that Matyas-Meyer-Oseas construction which is proven in the ideal-cipher-model can fail in the standard model, i.e. it will fail if we instantiate it with $\widetilde{E}$;

So $\widetilde{E}$ is the same block cipher as $E$  with one change: we now have the invariant  that $E(K, K)= K$ for all $K \in \{0, 1\}^n$. Clearly   $\widetilde{E}$   is a good PRP since have $E$ was:  for a randomly chosen key $K, \widetilde{E}(K,\cdot)$  is computationally indistinguishable from a random permutation.  

Is the claim computationally indistinguishable from a random permutation true?

We can say that for a fixed key $K$, $\widetilde{E}$ we will always output $K$ if $ K = X$

The probability of getting a single point is fixed from all permutations of $k$ elements is $\frac{(k-1)!}{k!} = \dfrac{1}{k}$.

If we turn this into permutations generated by the $n$-bit block cipher. Then we have $\dfrac{1}{2^n}$. Therefore the permutations of $\widetilde{E}$ is distinguishable and $\widetilde{E}$ cannot be a good PRP.

Any missing point?

Could one provide a formal proof for this an example?


Short answer

As Maeher said, the adversary cannot recognize which points are reprogrammed or distinguish $\widetilde E$ from $E$, given oracle access to $\widetilde E$ (or $E$). This is because the adversary who detects such points can also be used to break the PRP security of $E$ by finding the key $K$.

Formal proof

It suffices to prove that no efficient algorithm can distinguish $E$ from $\widetilde E$ via oracle access. That is, we will prove that for any efficient $A$ with $q$ query to the oracle such that $$ |\Pr_{K}[A^{E(K,\cdot)}()=1] - \Pr_K[A^{\widetilde E(K,\cdot)}() =1]|=\epsilon, \label{1}\tag{1} $$ it holds that $\epsilon$ is negligibly small.

To measure the advantage in a different term, first note that a difference in the oracle access to $E$ and $\widetilde E$ only happens if the adversary query $(K,K)$ or $(K,X)$ for $X=E^{-1}(K,K)$ to the oracle. Otherwise, both oracles work exactly the same and there is no chance to figure out the difference. Let's say the above event by $\rm Bad$. Then it holds that $$ \epsilon \le \Pr_K[A^{E(K,\cdot)}()=1|{\rm Bad}] \le \Pr_K[A^{E(K,\cdot)}()|{\rm Bad}].\label{2}\tag{2} $$ Note that whether the oracle is $E$ or $\widetilde E$ doesn't make any difference. We choose $E$ here.

What is the probability of $\rm Bad$? We define a new adversary $B$ having oracle access to $E$ to find the key of PRP as follows.

  1. Choose a random $1 \le i \le q$.
  2. Run $A$ with the given oracle right before $i$-th query. Let the input of $i$-th query by $X$ and with probability, $1/2$ do either
    • output $X$, or
    • query $X$ to the oracle and output the answer $E(K,X)$.

Suppose that in the $i$-th query the $\rm Bad$ event occurs. If the first case of $\rm Bad$ occurs, i.e. $A$ queries $K$ to the oracle, then $B$ outputs $K$ with probability $\epsilon/2q$ by the first action (output $X$ directly). On the other hand, if $A$ queries $E^{-1}(K,K)$, the second action outputs $E(K,E^{-1}(K,K))=K$ that also has probability $\epsilon/2q$. Overall, the algorithm $B$ outputs $K$ with probability $\epsilon/2q$.

However, the PRP security of $E$ says that this probability is negligibly small. This implies $\epsilon$ is small as well since $q$ is polynomially bounded (given that $A$ is efficient). Thus no efficient algorithm can distinguish $E$ from $\widetilde E$ via oracle access, and since $E$ is PRP, $\widetilde E$ is a PRP as well, which is as we desired.

  • $\begingroup$ What fo you mean by $\Pr_K[A^{E(K,\cdot)}()|{\rm Bad}]$? $\endgroup$
    – kelalaka
    Jan 6 at 15:48
  • 1
    $\begingroup$ @kelalaka I intended the probability that the bad event occur while running $A$, regardless of its output. $\endgroup$
    – Hhan
    Jan 6 at 16:10
  • $\begingroup$ Thanks for your answer. Consider this as a learning question for me. I've read this $\Pr_K[A^{E(K,\cdot)}()|{\rm Bad}]$ like conditional probability. Is it? Are there any relation between the two $\epsilon$ in the equations 1 and 2? Why the probability is $\epsilon/2q$, doesn't the bad event occurs once? $\endgroup$ Jan 10 at 10:19
  • $\begingroup$ @YunusKarakaya Sorry for my bad presentation. The probability $Pr_K[A^{E(K,⋅)}()|Bad]$ says the chance that $A$ met Bad event in its running. I used the term for showing the inequality. Two $\epsilon$'s are the same, and the argument between equation 1 and 2 shows inequality 2, which essentially says the advantage of adversary $\epsilon$ is less than the probability of Bad event. $\endgroup$
    – Hhan
    Jan 11 at 10:45
  • $\begingroup$ For the last part, we constructed an adversary $B$ that finds the key of PRP whenever it halts the exact point that Bad event occurs. The bad event occurs probability at least $\epsilon$ by inequality 2, and the probability that the random guess of $B$ find the Bad point is (if any) $1/2q$. Combining them, $B$ finds the point that Bad event happens with probability $\epsilon/2q$, which is not negligible. $\endgroup$
    – Hhan
    Jan 11 at 10:49

Your Answer

