# 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