4
$\begingroup$

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.
Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – bmm6o
    Commented May 7, 2018 at 15:25
  • $\begingroup$ @bmm6o: if I get homomorphism right, it is a permutation of the kind considered by the question when we add $q=2^n$. $\endgroup$
    – fgrieu ♦
    Commented May 9, 2018 at 8:35
  • $\begingroup$ @fgrieu You're right, I didn't read the question closely enough. $\endgroup$
    – bmm6o
    Commented May 9, 2018 at 15:40
  • 1
    $\begingroup$ Consider asking on math.SE for someone more adept at cute combinatorics formulas than we are? $\endgroup$
    – Squeamish Ossifrage
    Commented May 25, 2018 at 4:29
  • $\begingroup$ @SqueamishOssifrage: You are right. I will try to ask this question on math.SE. $\endgroup$
    – bird
    Commented May 26, 2018 at 7:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ $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. $\endgroup$
    – Squeamish Ossifrage
    Commented May 5, 2018 at 16:38
  • $\begingroup$ $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. $\endgroup$
    – bird
    Commented May 7, 2018 at 14:46
  • $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Commented May 7, 2018 at 15:12
  • $\begingroup$ @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. $\endgroup$
    – bird
    Commented May 8, 2018 at 7:00

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.