Imagine that I have a "secret" vector $\mathbf{x} = (x_1, \dots, x_n) \in \{0,1\}^n$ and I give another person the matrix $$\mathbf{A_x} := \sum_{i=1}^n x_i \cdot \mathbf{A}_i,$$ with the elements of $\mathbf{A}_i \in\mathbb{Z}_q^{n \times n}$ taken uniformly at random from $\mathbb{Z_q}$, for a prime $q$.

Is there any way I can obtain some information about $\mathbf{x}$ (i.e., knowing the number of $0$'s) by just knowing $\mathbf{A_x}$? Is this a known problem? What would happen if we also provide the other person with the matrices $\mathbf{A}_i$, for $i=1,\dots,n$?

Could it happen that given two distinct secret vectors $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, we have that $\mathbf{A_x} = \mathbf{A_y}$? Is this probability negligible?

  • 1
    $\begingroup$ Unless the $A_i$ matrices are known, you cannot do much except determine if the vector has all-zeros or not (with high probability). Assuming all entries of all $A_i$ matrices are independent, the sum of two such matrices has distribution the same as just one. So the sum of any positive number of such matrices has the same distribution as just one of them. $\endgroup$
    – Michael
    Aug 3, 2020 at 10:09
  • $\begingroup$ @Michael You are right. What would happen if all $\mathbf{A}_i$ are known? $\endgroup$
    – Bean Guy
    Aug 3, 2020 at 10:14
  • 1
    $\begingroup$ Let us assume $x \in \{0, …, q-1\}^n$ and all arithmetic takes place mod $q$. If all $A_i$ are known the result looks like a big equation $Cx=d$ where $C$ is a known $n^2 \times n$ matrix with iid entries in $\{0, …, q-1\}$, and $d$ is a known vector. The probability of being able to solve $Cx=d$ for any $x$ is the same as the probability that all columns of $C$ are linearly independent, which is $$ (1-\frac{1}{q^{n^2}})(1-\frac{q}{q^{n^2}})…(1-\frac{q^{n-1}}{q^{n^2}})$$ This is close to $1$ if $q$ is large. If we know $x \in \{0,1\}^n$ then perhaps the probability is even higher than this. $\endgroup$
    – Michael
    Aug 3, 2020 at 10:26
  • $\begingroup$ @Michael Yeah... My other (maybe harder) idea was to defined $\mathbf{A_x}$ as $$\mathbf{A_x} := \sum_{i=1}^n (-1)^{x_i} \cdot \mathbf{A}_i.$$ Knowing $\mathbf{A_x}$ and all the $\mathbf{A}_i$'s, what would happen? $\endgroup$
    – Bean Guy
    Aug 3, 2020 at 10:36
  • 1
    $\begingroup$ Here $(-1)^{x_i} = 1$ if $x_i=0$, $(-1)^{x_i}=q-1$ if $x_i=1$. So if $A_i$ are unknown then the distribution of $A_x$ is the same for all $x$, even if $x$ is all-zeros. However, if $A_i$ are known then we again have $Cx=d$. We have a different $x$ and $d$ but the matrix $C$ is the same and the probability it has linearly independent columns is the same as before. Incidentally I evaluated the expression for $q=3$ and $n=5$ and we get very close to 1: $$0.999999999857...$$ wolframalpha.com/input/… $\endgroup$
    – Michael
    Aug 3, 2020 at 18:21


You must log in to answer this question.