2
$\begingroup$

I have a question about division operation.

There are two entities, Alice and Bob.

Bob randomly selects a finite set of numbers (set K). (about 10K or 100K)

Alice randomly generates one big number $x_1$ and chooses one element $y_1$ (from Bob's set K).

Alice makes $X$ ($X=x_1*y_1 \bmod n$) and sends $X$ to Bob.

In this case, can Bob figure out what Alice chooses from the set K?

Small number example: 3 ($x_1$) * 5 ($y_1$) mod 7 = 1 ($X$).

Bob knows that there is '5' in the set K, but I think that 1 divided by 5 (mod 7) equals 1.

So I don't think that Bob can figure out what Alice chooses from the set K.

Am I right?

Sorry for my bad English.

Thanks.

$\endgroup$
  • $\begingroup$ 1 divided by 5 modulo 7 is not equal to 1, it is equal to 3. $\endgroup$ – Geoffroy Couteau Feb 14 '17 at 11:59
  • 1
    $\begingroup$ Where does $n$ come from? You didn't define that previously, just used it at some point. $\endgroup$ – tylo Feb 14 '17 at 12:34
3
$\begingroup$

The answer depends on how $n$ is chosen.

If $n$ is coprime with each of the $y_j$ (including if $n$ is prime and all the $y_j$ are in range $[1..n[$), and $x_1\bmod n$ is uniformly random on $[0..n[$ (including if $x_1$ is uniformly random on that interval, or on a much larger interval), then demonstrably, Bob can not determine what $y_i$ Alice has picked by examination of $X\;=\;x_1*y_i\bmod n$. Proof sketch: the application $F_i:x_1\to X$ is a permutation of $[0..n[$; therefore $X$ is uniformly random on $[0..n[$, regardless of $y_i$; thus $X$ can't leak information about $y_i$.

However, if $n$ is the product of all the $y_i$ and these are distinct moderate primes, then Bob can find with fair odds which $y_i$ was chosen: $X$ is divisible by that $y_i$, and only those few (perhaps no) other $y_j$ that divide $X$.

There are gradations between theses two extremes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.