Recovering a secret that has been blinded several times

Question

I'm analyzing a protocol that, during one of the steps, sends a blinded secret. Let's denote the secret $x \in \mathbb Z_p^*$ (for $p$ prime) and the blinded secret $y$, so that $y = r\cdot x \bmod p$, where $r$ is a blinding factor randomly sampled from $\mathbb Z_p^*$. We can assume that the blinding factors won't repeat.

Several runs of the protocol would produce several $y_i$ values, with the same fixed secret $x$:

$$y_1 = r_1 \cdot x \bmod p$$ $$y_2 = r_2 \cdot x \bmod p$$ $$...$$ $$y_n = r_n \cdot x \bmod p$$

Knowing only the $y_i$ values, what would be the best algorithm to retrieve $x$?

Answer 1

If all we know are the blinded values $y_i$ (and the modulus $p$), and if the blinding factors $r_i$ are indeed sampled randomly from the multiplicative group modulo $p$, I don't see any way to recover the secret $x$.

This is because, for any list of blinded values $y_i$ and any candidate $x$ value, we can compute a unique list of blinding values $r_i \equiv y_i \cdot x^{-1} \pmod p$ that, when multiplied by $x$ modulo $p$, will yield exactly those blinded values. Given that the $r_i$ values are chosen randomly, this particular list of blinding values is exactly as likely as any other. Thus, this blinding scheme appears to be unconditionally secure.

(Also, the knowledge that the $r_i$ values cannot repeat won't help, since all it implies is that the $y_i$ values won't repeat either. If we did observe repeated $y_i$ values for the same secret $x$, we would know that the corresponding $r_i$ values must be the same, but would still gain no further knowledge about $x$.)

Answer 2

There is no algorithm to find an $x$ only having $y_i$.

Answer 3

As long $(r_i)_{i=1\dots n}$ is sampled uniformly from the set $Z := \{(z_i)\in(\mathbb Z_p^\times)^n|1\le i<j\le n\implies z_i\ne z_j\}$ and the attacker gets all the $y_i$'s, but no information about the $r_i$'s and $x$ (during the other steps), no algorithm can obtain any information about $x$, as multiplying by $x$ preserves the uniform distribution on $Z$.

Hence knowing $(r_i)_{i=1\dots n}$ is equivalent to knowing $(y_i)_{i=1\dots n}$ [as long one doesn't know both!], as both look (statistically) the same, so nobody is able to distinguish between the random or the blinded secrets. So anything one can conclude from the blinded secret, one can as well conclude from the random.

If the blinding factors are allowed to repeat, using $Z=(\mathbb Z_p^\times)^n$ in the argument above would lead to the same conclusion.