4
$\begingroup$

Consider the case that

$c = a \cdot b \mod p$

where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are known.

Q1: Can an attacker learn some bits of $a$ using this information?

The question is based on the following non-modular example:

$a = x_1 \cdot 2^z + x_0$

and

$b = x_2 \cdot 2^z + x_3$

gives the product:

$a \cdot b = x_1x_22^{2z} + (x_0x_2+x_1x_3)2^z + x_0x_3$

Then if anyone knows the $z$ least significant bits of $a \cdot b$ (the product $x_0x_3$), then some of the divisors of $x_0x_3$ is equal to $x_0$, allowing to bound the possible values of $x_0$ to the possible divisors of $x_0x_3$.

Q2: Can this non-modular analysis be applied to the modular one ?

$\endgroup$
10
$\begingroup$

Can an attacker learn some bits of a using this information?

No. In the case of multiplication modulo a prime, we have, for any possible value of $a$, there is a unique value of $b$ that makes $a \cdot b \bmod p$ give any particular value of $c$ in the range $(1, p-1)$.

That is, even if we knew all the bits of $c$, no particular value of $a$ are any more likely than any other (assuming we have no information about $b$). And, in particular, we have no information on any of the bits of $a$ (other than what's implied by $1 \le a < p$, which we already knew).

Any observation in the non-modular case (where this observation does not apply) doesn't apply to the modular case.

$\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.