# For a random permutation $P$, what's the probability of the following event?

For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$?

Note: I have tried to compute this probability, but it is quite hard for me to obtain the result, either for the exact probability or the lower bound of this probability. The following is my attempt to solve this problem when $q=2,3$.

Denote by $\mathsf{E}$ the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$.

• If $q=2$, it is easily seen that $\Pr[\mathsf{E}]=\Pr[P(x_1)\oplus x_1=P(x_2)\oplus x_2]=\frac{1}{2^n-1}$
• If $q=3$, we have 3 random elements $P(x_1)\oplus x_1,P(x_2)\oplus x_2,P(x_3)\oplus x_3$. We focus on computing $\overline{\mathsf{E}}$ the complementary event of $\mathsf{E}$: \begin{align}\Pr[\overline{\mathsf{E}}]=&\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2 \wedge P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3]\\ =&\Pr[P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3\mid P(x_1)\oplus x_1\neq P(x_2)\oplus x_2]\cdot\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2] \end{align} Without loss of generality, assume that the value of $P(x_1)$ is fixed. There are $2^n-1$ possibilites for $P(x_2)$. Conditioned on the event $P(x_1)\oplus x_1\neq P(x_2)\oplus x_2$ happening, the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ may change according to the choices of $P(x_2)$:
• If $P(x_2)=P(x_1)\oplus x_1\oplus x_3$ or $P(x_2)=P(x_1)\oplus x_2\oplus x_3$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-1}{2^n-2}$.
• If $P(x_2)\neq P(x_1)\oplus x_1\oplus x_3$, $P(x_2)\neq P(x_1)\oplus x_2 \oplus x_3$ and further $P(x_2)\neq P(x_1)\oplus x_1\oplus x_2$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-2}{2^n-2}$.
Hence, \begin{align} \Pr[\overline{\mathsf{E}}]=&\frac{2}{2^n-1}\cdot\frac{2^n-3}{2^n-2}+\frac{2^n-1-3}{2^n-1}\cdot\frac{2^n-4}{2^n-2}\\ =&\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)}, \end{align} and $\Pr[\mathsf{E}]=1-\Pr[\overline{\mathsf{E}}]=1-\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)}$.
• For $q\ge4$, the computation is complicated and I haven't found a good method to tackle it.
• A permutation P where there are no collisions of the kind you describe is called an orthomorphism. I would think that there would be some results about their numbers relative to all permutations, but I wasn't able to turn up anything with a quick search. Commented May 7, 2018 at 15:25
• @bmm6o: if I get homomorphism right, it is a permutation of the kind considered by the question when we add $q=2^n$.
– fgrieu
Commented May 9, 2018 at 8:35
• @fgrieu You're right, I didn't read the question closely enough. Commented May 9, 2018 at 15:40
• Consider asking on math.SE for someone more adept at cute combinatorics formulas than we are? Commented May 25, 2018 at 4:29
• @SqueamishOssifrage: You are right. I will try to ask this question on math.SE.
– bird
Commented May 26, 2018 at 7:11

Assuming the $x_i$ are chosen independently of $P$, and the witdth $k$ of $x$ is not too narrow, it makes sense to use the approximation that $x\mapsto P(x)\oplus x$ behaves like a random function, at least as far as collisions are concerned.

Note: I wish I had a proof or convincing argument of that. The best I have right now is that without knowledge of $P$, we need nearly $2^{k/2}$ queries to $x\mapsto P(x)\oplus x$ in order to get a significant advantage distinguishing that from a random function. But that argument does not explain why the approximation still holds for e.g. $k=10$, $q=100$, when it does.

If further assuming that the $x_i$ are distinct, the problem becomes a straightforward application of the birthday problem for cryptographic hashing.

• $x \mapsto P(x) \oplus x$ is close to a single-key Even–Mansour cipher. Probably the literature about that has some relevant bound. Maybe also the literature on Salsa20. Commented May 5, 2018 at 16:38
• $x\mapsto P(x)\oplus x$ is exaclty the Davis-Meyer contruction by replacing the underlying blockcipher with a random permutation. I have read several papers about Davis-Meyer conscrtion. But I only find some result about Davis-Meyer construction in ideal cipher model link, which means the the key can be chosen by the adversary. For the fixed-key Davis-Meyer construction,i.e., the problem I proposed, I don't find any result about the exact probability or the lower bound of the probability in the literature.
– bird
Commented May 7, 2018 at 14:46
• @bird: $x\mapsto P(x)\oplus x$ does not behave exactly as a random function, even collision-wise. That's easily visible for $x$ single-bit: that makes $x\mapsto P(x)\oplus x$ a constant function, which always collides for 2 distinct inputs, rather than with probability 50%. And (by enumeration) for $x$ two-bit. But I'm inclined to believe that this quickly vanishes collision-wise when the width of $x$ grows.
– fgrieu
Commented May 7, 2018 at 15:12
• @fgrieu: The statistical difference between $P(x)\oplus x$ and a random function $F(x)$ is about $O(q^2/2^n)$, where $q$ represents the number of queries. The probability of the event that there exists at least one collision among $\{F(x_1),\ldots,F(x_q)\}$ is $1-\prod_{i=1}^{q-1}(1-\frac{i}{2^n})\geq 1-e^{-\frac{q(q-1)}{2^{n+1}}}$, which is the birthday paradox. But I think the quesition I proposed is slightly different from this.
– bird
Commented May 8, 2018 at 7:00