# Can a block cipher with fixed point permutations be a good PRP?

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?

• How would an efficient adversary detect the fixed point? Jan 4, 2021 at 10:31
• Jan 7, 2021 at 18:43

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.

• What fo you mean by $\Pr_K[A^{E(K,\cdot)}()|{\rm Bad}]$? Jan 6, 2021 at 15:48
• @kelalaka I intended the probability that the bad event occur while running $A$, regardless of its output.
– Hhan
Jan 6, 2021 at 16:10
• 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? Jan 10, 2021 at 10:19
• @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.
– Hhan
Jan 11, 2021 at 10:45
• 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.
– Hhan
Jan 11, 2021 at 10:49