# Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

Please consider we have finite field $\mathbb{F}_p$ for large prime number $p$. We have a fixed field element $\alpha$. By $r_i\leftarrow \mathbb{F}_p$ we mean we pick $r_i$ uniformly random from the field. We assume the values $r_i$ are distinct so $r_i\neq r_j$

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$?

Intuitively one may say the adversary can compute $gcd(v_1,...v_n)$ to extract value $\alpha$.

Am I right that the adversary cannot learn anything; otherwise, ElGamal encryption would not be secure?

• In a field, any two nonzero elements are associated, hence the set of $\gcd$s is either $\{0\}$ (if $\alpha$ or any $r_i$ is zero) or $\mathbb F_p^\ast=\{1,\dots,p-1\}$. – yyyyyyy Sep 3 '15 at 16:00
• @yyyyyyy I need exactly to know this bit. could you "please" tell me more about it. What if some of $r_i$ values are smaller than $p$. So we would have $\alpha\cdot r_i<p$. – user13676 Sep 3 '15 at 16:04
• In other words, my comment states that the notion of a "greatest common divisor" does not make much sense in a field (such as $\mathbb F_p$). In particular, greatest common divisors are not unique except in trivial cases; in fact any nonzero element is a greatest common divisor of a set of elements that does not contain zero. This is why your intuition does not work: Unless one of the $v_i$ is zero, you gain absolutely no information by the $\gcd$ "computation". – yyyyyyy Sep 3 '15 at 16:12
• @user13676: I assume you meant "what if some of the $r_i$ values are smaller than $p/\alpha$. So what if that happens? How can the attacker get any information about whether that happens? As my answer stated, the values that the attacker sees is consistent with any nonzero $\alpha$. The attacker can guess that $r_i \cdot \alpha < p$, however without any way of validating that guess, that doesn't tell him anything. – poncho Sep 3 '15 at 16:12

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$?
Answer: assuming that the $r_i$ values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about $\alpha$ (other than whether or not it's 0).
We can see this because, for any sets of values $v_i$, there are a unique set of $r_i$ values that is consistent with $\alpha$ being a specific nonzero value, namely, $r_i = \alpha^{-1} v_i$. So, if someone cannot distinguish the $r_i$ values from random, they cannot determine which nonzero $\alpha$ value is any more likely than any other.
You state that the $r_i$ values are distinct, and so technically that is a correlation. However, we can show that distinct $v_i$ values translate to distinct $r_i$ values (for any fixed nonzero $\alpha$), and hence any $\alpha$ value will preserve uniqueness. So, the attacker cannot use this correlation to gain any information.