2
$\begingroup$

Consider the function

$$f(x_1, x_2, \ldots, x_k) = S_1^{x_1} S_2^{x_2} \cdots S_k^{x_k}.$$

Each $x_1, x_2, \ldots, x_k \in \{0, 1\}$ and each $S_i \in \mathbb{F}_q^{n \times n}$ is a randomly chosen $n \times n$ matrix over the field $\mathbb{F}_q$. $q$ is assumed to be a prime.

For a particular choice of these matrices, I am trying to find the expected number of collisions (number of inputs that map to the same output) for $f$ (and also the variance of the number of collisions for $f$.)

The number of collisions of $f$ is defined as

$$ \big|\{A : |f^{-1}(\{A\})| > 1\}\big|. $$

Since a random matrix is almost a full rank matrix, I expect the number of collisions to be very low, but I could not prove it.

Improve this question
$\endgroup$
9
  • $\begingroup$ While not directly relevant to your question, you may find it interesting that a quite similar function is the basis of a practical "pseudorandom function" (a cryptographic construction) known as SPRING, see section 5 of this paper (although there is follow-up work). The distributions that the $S_i$ are drawn from is different though (they are "short", roughly when one identifies $\mathbb{F}_q \cong \{-q/2, \dots, q/2\}\subseteq \mathbb{R}$, they are small norm), and peope only really care about whether $f$ "looks random" $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 25, 2022 at 21:17
  • $\begingroup$ to computationally bounded adversaries. Still, it seemed worth leaving a comment over. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 25, 2022 at 21:18
  • $\begingroup$ Should the expression in the product depend on $i$? $\endgroup$
    – Geoffrey Irving
    Commented Apr 25, 2022 at 22:51
  • $\begingroup$ @GeoffreyIrving Sorry for the typo. Fixed now. $\endgroup$
    – RandomMatrices
    Commented Apr 26, 2022 at 1:26
  • 1
    $\begingroup$ I don't understand "since a random matrix is almost a full rank matrix, I expect the number of collisions to be very high." Seems like the lower the rank of the $S_i$, the more collisions. $\endgroup$
    – Daniel McLaury
    Commented Apr 26, 2022 at 2:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .