2
$\begingroup$

Assume $r_1,r_2$ are used only once, and picked uniformly at random (each time we want to mask a value) from finite field $\mathbb{F}_p$, where $p$ is a large prime number. Assume $r_i\neq0$ and $b$ is a (non-zero) fixed element of the field. Let $(r_i)^{-1}$ be multiplicative inverse of $r_i$.

Imaging there is a client $B$ and a server. The server does some homomorphic operation on an encrypted value and then provides $c=E_{pk_{B}}(r_1\cdot b)$ to client $B$. Where the cipchertext space is much larger than $p$.

So the plaintext may overflows in field $\mathbb{F}_p$, in other words $r_1\cdot b$ may not be in the field $\mathbb{F}_p$. Therefore, there is a rick that client $B$ after decrypting learns something about $b$. So we want to force client $B$, after decrypting the message performs $\bmod p$.

To this end, we compute $c'=E_{pk_{B}}(r_1\cdot b \cdot r_2\cdot (r_2)^{-1})$.

Question 1: Given $c'$, can client $B$ learn anything about $b$ after decrypting the ciphertext before it performs $\bmod p$ operation?


Simpler version: Given $r_1\cdot b \cdot r_2\cdot (r_2)^{-1}$ without involving $\bmod p$ operation can a semi-honest party learn anything about $b$ ?

$\endgroup$
4
  • 1
    $\begingroup$ Hint: what happens if $r + b = 0$? Could the attacker deduce anything about $b$ in that case? $\endgroup$
    – poncho
    Commented Aug 4, 2016 at 17:20
  • $\begingroup$ @poncho we can assume $r\neq 0$. $\endgroup$
    – user153465
    Commented Aug 4, 2016 at 17:22
  • 1
    $\begingroup$ You say "we can assume $r \ne 0$"; however the question states "$r$ ... is picked uniformly at random"; if it is uniform, then $r=0$ is certainly a possibility; if you meant "$r$ is selected from nonzero entries", then what if $r + b = 1$? In any case, that's a hint, by exploring that possibility, I expect you to uncover more general possibilities... $\endgroup$
    – poncho
    Commented Aug 4, 2016 at 17:50
  • $\begingroup$ @poncho I modified the question a lot. Can I have your idea? $\endgroup$
    – user153465
    Commented Aug 4, 2016 at 19:34

1 Answer 1

3
$\begingroup$

Given $c'$, can client $B$ learn anything about $b$ after decrypting the ciphertext before it performs $\bmod p$ operation?

Given $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ without involving $\bmod p$ operation can a semi-honest party learn anything about $b$ ?

These would appear to be the same question; it's just that in the first question, $B$ is handed a ciphertext for which he has the decryption key for;.

The answer: obviously, yes. If $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ happens to be relatively prime to a prime $q$ (for example, $q=3$), then the attacker knows that $b$ also is relatively prime to $q$. This doesn't immediately tell him the value of $b$; however it allows the attacker to deduce what $b$ is not.

If the attacker can factor $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$, he can then put together a short list of plausible values for $b$; however it is likely that $b$ and either $r_1$ or both of $r_2, r_2^{-1}$ have large enough prime factors to make this intractable (this assumes that $b$ was ultimately chosen in a way that didn't favor smooth numbers).

However, if the attacker is given two such encodings of the same $b$, $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ and $r'_1\cdot b \cdot r'_2⋅(r'_2)^{−1}$, then he is in luck; he can compute $\gcd( r_1 \cdot b \cdot r_2⋅(r_2)^{−1}, r'_1\cdot b \cdot r'_2⋅(r'_2)^{−1})$, and that's $r$, multiplied by a (likely small) integer.

$\endgroup$
1
  • $\begingroup$ you have any idea how to force him to use $\bmod p$? $\endgroup$
    – user153465
    Commented Aug 4, 2016 at 20:01

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.