0
$\begingroup$

We face many places to find the collision probability of two sets (or more) in my case the cryptographic hash functions. We can formalize as;

Given two sets of random variables $\mathbf{A}$ and $\mathbf{B}$ compromised $m$ and $n$ elements, respectively. Consider $t$ discrete values where each variable $\{A_1, A_2,\ldots,A_m\}$ and $\{B_1, B_2,\ldots,B_n\}$ can assume any of the $t$ values with equally likely probability. Clearly, a collision is at least one element of $\mathbf{A}$ is also in $\mathbf{B}$.

The problem investigated in

The probability of no collision $P_0(m,n,t)$ is given in the below theorem;

  • Theorem 1 (Probability of success). The probability of no collisions between two sets of random variables $\{A_1, A_2,\ldots,A_m\}$ and $\{B_1, B_2,\ldots,B_n\}$, the elements of which can assume any of $t$ discrete values with equally likely probability is $$ P_0(m,n,t) = \frac{1}{t^{m+n}}\sum_{i=1}^{m}\sum_{j=1}^{n} S_2(m,i)S_2(n,j) \prod_{k=0}^{i+j-1} t-k$$

    where $S_2$ represents Stirling numbers of the second kind.

When $t$ becomes very large like $2^{64}$ we cannot use this theorem to calculate the probability. Therefore we need a good approximation as in the birthday problem.

Is there any good approximation for this theorem/problem that can be used easily to calculate large values assuming that $A_1,\dots,A_m,B_1,\dots,B_n$ are independent and identically distributed random variables each uniformly distributed over the set $[t]:=\{1,\dots,t\}$.

$\endgroup$
11
  • $\begingroup$ What is the definition of a collision between two sets of random variables $\{A_1, A_2,\ldots,A_m\}$ and $\{B_1, B_2,\ldots,B_m\}$? Also, did you mean $B_n$ in place of $B_m$? $\endgroup$ Jan 17, 2022 at 20:50
  • $\begingroup$ @IosifPinelis thanks for the typo. The usual, if at least one element of $\mathsf{A}$ is in $\mathsf{B}$ it is a collision ($A_i = B_j)$ from some $i$ and $j$... I.e., the intersection of $\mathsf{A}$ and $\mathsf{B}$ is not empty. Consider two groups of people, if there is one person on the first group who has the same birthday in the other then we have a collision between these two groups ( however, random people cannot form a set, at least consider that groups of people are forming sets according to their birthdays). $\endgroup$
    – kelalaka
    Jan 17, 2022 at 20:56
  • $\begingroup$ What are then the $A_i$'s and $B_j$'s? Are they all iid random variables? $\endgroup$ Jan 17, 2022 at 21:00
  • $\begingroup$ Taken from $t$ discrete values like the days of the year or from $[0,2^{64}-1]$, they are equally likely... $\endgroup$
    – kelalaka
    Jan 17, 2022 at 21:02
  • $\begingroup$ Can you just answer my questions? I only need formal definitions. $\endgroup$ Jan 17, 2022 at 21:04

1 Answer 1

3
$\begingroup$

We are assuming that $A_1,\dots,A_m,B_1,\dots,B_n$ are iid random variables each uniformly distributed over the set $[t]:=\{1,\dots,t\}$.

By the Bonferroni inequalities, for the probability of at least one collision
\begin{equation} p:=P\Big(\bigcup_{(i,j)\in[m]\times[n]} \{A_i=B_j\}\Big), \end{equation} we have \begin{equation} p_1-p_2\le p\le p_1, \end{equation} where \begin{equation} p_1:=\sum_{(i,j)\in[m]\times[n]} P(A_i=B_j)=\frac{mn}t \end{equation} and \begin{equation} p_2:=\sum_{ \substack{(i_1,j_1)\in[m]\times[n], \\ (i_2,j_2)\in[m]\times[n]\setminus\{(i_1,j_1)\}} } P(A_{i_1}=B_{j_1},A_{i_2}=B_{j_2})=\frac{mn(mn-1)}{t^2} =o\Big(\frac{mn}t\Big) \end{equation} if $mn=o(t)$.

So, \begin{equation} p\sim\frac{mn}t \end{equation} if $mn=o(t)$.

Thus, the probability of no collisions is \begin{equation} 1-p=1-\frac{mn}t\,(1+o(1)) \end{equation} for very large $t$, that is, for $t$ much greater than $mn$.

$\endgroup$
0

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.