3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you are only given one encryption, not many (each with a different $r$, obviously)? $\endgroup$ – mikeazo Aug 10 '16 at 11:40
  • $\begingroup$ @mikeazo We can have many $m'_i$ values with different $r_i$ where each $r_i$ are chosen independently. $\endgroup$ – user153465 Aug 10 '16 at 11:44
  • $\begingroup$ @mikeazo this paper at page 4 (protocol 2, step 1) seems to use the same idea. siplab.tudelft.nl/sites/default/files/IJACT030205%20VEUGEN.pdf $\endgroup$ – user153465 Aug 10 '16 at 11:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It seems that $E(m + r_i)$ is not well-defined, since $E(\cdot )$ should only have a domain of $\mathbb{F}_p$ (if I'm reading correctly). You can, of course, add large unrelated values to the ciphertext, but you have to respect the homomorphic structure of the plaintext in order to ensure that the ciphertext's underlying information (the plaintext) is not destroyed by the addition of $r_i.$ $\endgroup$ – Daniel Apon Aug 10 '16 at 14:03
  • $\begingroup$ (Have to run, but.. you might also check whether a uniformly random value $r$ mod $p$ is actually sufficient here.. That would be in line with a few other schemes I've seen of this form. Note that adding a uniformly random value $r\bmod{p}$ to an arbitrary value $m\bmod p$ results in a value that's statistically indistinguishable from a random value $r'\bmod{p}$) $\endgroup$ – Daniel Apon Aug 10 '16 at 14:05
  • $\begingroup$ Could work :) Who knows! Good luck! $\endgroup$ – Daniel Apon Aug 10 '16 at 14:06
  • $\begingroup$ I have a relevant question. I'll be pleased to have your view point. Let $r_i$ be a uniformly random element of the ring. Let $r'_i=r_i \bmod p$. And let $(-r'_i)$ be additive inverse of $r'_i$ in $\mathbb{F}_p$. We compute $m'_i=(-r'_{i})+m_i + r_i$ where $m'_i\in \mathbb{Z}_N$, so we do not do any modular reduction. Can we still say that $m'_i$ is statically indistinguishable? The only difference is that I included $(-r'_i)$, but the size of ring can still be larger than the field size. Thank you in advance. $\endgroup$ – user153465 Aug 16 '16 at 14:35
  • $\begingroup$ If elements have different factorizations, then taking GCDs could distinguish things (independent of the elements' relative sizes) $\endgroup$ – Daniel Apon Aug 16 '16 at 20:32

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.