4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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\}$. $\endgroup$
    – yyyyyyy
    Commented Sep 3, 2015 at 16:00
  • $\begingroup$ @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$. $\endgroup$
    – user13676
    Commented Sep 3, 2015 at 16:04
  • 1
    $\begingroup$ 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". $\endgroup$
    – yyyyyyy
    Commented Sep 3, 2015 at 16:12
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Sep 3, 2015 at 16:12

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Agreed; I read too hastily. $\endgroup$
    – Chris Peikert
    Commented Sep 3, 2015 at 17:08

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.