# 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. – bmm6o May 7 '18 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 May 9 '18 at 8:35
• @fgrieu You're right, I didn't read the question closely enough. – bmm6o May 9 '18 at 15:40
• Consider asking on math.SE for someone more adept at cute combinatorics formulas than we are? – Squeamish Ossifrage May 25 '18 at 4:29
• @SqueamishOssifrage: You are right. I will try to ask this question on math.SE. – bird May 26 '18 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. – Squeamish Ossifrage May 5 '18 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 May 7 '18 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 May 7 '18 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 May 8 '18 at 7:00