# Security of one-time-pad without $\bmod$ operation?

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$ ?

• Hint: what happens if $r + b = 0$? Could the attacker deduce anything about $b$ in that case? – poncho Aug 4 '16 at 17:20
• @poncho we can assume $r\neq 0$. – user153465 Aug 4 '16 at 17:22
• 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... – poncho Aug 4 '16 at 17:50
• @poncho I modified the question a lot. Can I have your idea? – user153465 Aug 4 '16 at 19:34

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.

• you have any idea how to force him to use $\bmod p$? – user153465 Aug 4 '16 at 20:01