Cryptanalysis of this one-time pad

Question

My question is related to this: Security of one-time-pad without $\bmod $ operation? but the way we mask values is different here.

---

We consider a finite field, $\mathbb{F}_p$, and a ring $\mathbb{Z}_N$, where $N$ is RSA modulus, and such that $p<<N$. Value $p$ is a (large) prime number and indepent of the prime numbers used to generate $N$.

Let $m_i\in \mathbb{F}_p$. We mask it as:

$m'_i=m_i+r_i$, where $r_i$ is picked uniformly at random from the ring but $m_i+r_i \in \mathbb{Z}_{N}$.

Please note that we do NOT perform $\bmod N$ when we compute $m'_i$.

---

Question 1: Is there any way to argue that given $m'_i$, a semi-honest adversary cannot learn anything about $m_i$ ? for instance, it is statically indistinguishable etc.

---

For the sake of simplicity let's assume all the values are non-zero. we can pick large enough $p$ and $N$ to meet any security definition if it's required.

Answer 1

Yes, I believe you can argue statistical indistinguishability here. But, note that this is a weaker property than the typical one-time-pad which is perfectly secure, because XOR is mathematical magic (incurring no $\mathsf{negl}(\lambda)$-sized statistical offsets as below..).

High-level idea: If $N$ is sufficiently large with respect to $p$ --- i.e. if $N \ge \Omega(p\cdot\lambda^{\omega(1)})$ --- then random samples of size $\approx N$ will statistically swallow any "$p$-bounded" distribution (random samples of size $\approx p$).

---

[[Let $\lambda$ be the security parameter. For now, I'll ignore the factorization of $p$ vs $N$ for this..]]

Here's some fun with statistical distance between distributions:

A distribution $\chi$ is $(B,\epsilon)$-bounded if the probability of sampling a value larger than $B$ is unlikely; i.e. $$\Pr_{x\leftarrow\chi}[|x| > B] < \epsilon.$$

(Aside: Actually, my discussion here also assumes that the bound $B$ in $B$-bounded distributions is "chosen as small as feasible" for a given distribution; i.e. $B$ should be "tight" for $\chi$ asymptotically.)

A distribution $\widetilde{\chi}$ is $(B,\epsilon)$-swallowing if for all $y\in [-B, B]$ (respectively, $y\in [0, B]$), it holds that $\widetilde{\chi}$ and $y + \widetilde{\chi}$ are within $\epsilon$ statistical distance.

It turns out that the ("truncated," resp. "rounded") Gaussian distribution satisfies the property described above; namely, any $\left(B\cdot\lambda^{\omega(1)}, \epsilon\right)$-bounded distribution $\chi$ is also a $\left(B, \epsilon+\mathsf{negl}(\lambda)\right)$-swallowing distribution as well. (Gaussians just happen to often have "nice" geometric properties like this.)

For example: If $\chi$ is $(B, \mathsf{negl}(\lambda))$-bounded, and if $\widetilde{\chi}$ is $(B\cdot\lambda^{\omega(1)}, \mathsf{negl}(\lambda))$-bounded, and we sample $x\leftarrow\chi$ and $\widetilde{x}\leftarrow\widetilde{\chi},$ then we have: $$ \widetilde{x} + x \stackrel{\rm stat}{\approx} \widetilde{x} $$

---

In general, many "natural" distributions will exhibit this "swallowing" property. The Uniform distribution over (ranges of) integers is well-defined by a bound $B$ (or $p,$ or $N$), and swallows all 'small, uniformly random integers' w.h.p. whenever there is a superpoly gap in magnitude.

Note that you need to "sample & add-in" a fresh, i.i.d. "swallowing term" to each new message, for each time you use this kind of argument.. As far as going beyond truncuated Gaussians or bounded ranges of integers: Use your judgment! =) The distributions (certainly) must hit the same (say..) subgroups to use this argument, etc.

---

..finally, note there's no need to bother with statistical swallowing if the desired security property is a (standalone) One-Time Pad! Just using the standard OTP will be more efficient (fewer bits sampled in order to blind messages; i.e. less randomness needs to be securely/safely generated/shared). Moreover, the standard OTP will achieve stronger than just statistical indistinguishability.