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?


1 Answer 1


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
    Commented Jan 6, 2021 at 15:48
  • 1
    $\begingroup$ @kelalaka I intended the probability that the bad event occur while running $A$, regardless of its output. $\endgroup$
    – Hhan
    Commented Jan 6, 2021 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$ Commented Jan 10, 2021 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
    Commented Jan 11, 2021 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
    Commented Jan 11, 2021 at 10:49

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.