# Statistical distance for multiplicative blinding

A common way to mask an integer $$x$$ in a range is to add a uniformly random integer $$r$$ from a much larger range. More formally, if $$x$$ lies in $$[0,...,2^k)$$ and $$r$$ in $$[0,...,2^{k + l})$$, then $$\Delta(X+R,R) < 2^{-l}.$$

Edit: I mean multiplication in $$\mathbb{Z}$$. If more specifically we're modelling a range $$[-2^k,...,2^k)$$ by mapping it into $$\mathbb{Z}/n \mathbb{Z}$$ for $$n$$ large enough to fit both ranges (and slightly more), then the sign of $$x+r$$ will agree with the sign of $$x$$, which can be useful.

In a similar setting, what is known about the statistical distance of $$\Delta(X\cdot R,R)$$? Again the requirement is that the sign of $$x \cdot r$$ agrees with that of $$x$$. Clearly $$n$$ would have to be much larger...

Assuming you mean multiplication in $$\mathbb{Z}$$, the statistical distance is always at least $$\Omega(1/(k+l))$$. A simple way to distinguish is to test whether the number is prime.

• The distribution $$X\cdot R$$ outputs a prime only when $$1 \in \{X,R\}$$, and this happens with probability at most $$1/2^k + 1/2^{k+l}$$.

• The distribution $$R$$ outputs a prime with probability $$\Theta(1/(k+l))$$ by the prime number theorem.

I don't know if this is a tight answer, but it's enough to show that multiplicative blinding is not very useful for cryptographic purposes.

Multiplicative blinding works much better in finite fields and rings.

Consider $$GF(p),$$ where $$p$$ is an odd prime. Then the map $$x\mapsto R\cdot x \pmod p$$ is a permutation with no fixed points provided $$R \notin \{0,1\}.$$ This directly gives $$\Delta(X,X\cdot R)=1/p$$ which corresponds to a statistical distance not $$2^{-k}$$ but $$2^{-(k+\ell)}$$ (i.e., much lower) in your terminology.

If you avoid the divisors of the RSA modulus, this property survives. So if you let $$N=pq,$$ and choose $$k$$ from the set $$[2,\ldots,p-1]$$ (assume that $$p) you obtain the same statistical distance, i.e., $$1/N$$ otherwise you can obtain either $$1/p$$ or $$1/q$$ for $$k$$ divisible by $$q$$ or $$p$$ respectively, which is of the order $$1/\sqrt{N}.$$

• Thank you for this answer! I actually meant to avoid overflows, and with that requirement this setup does not work. I was wondering if you have any more comments there... Commented Dec 15, 2023 at 17:37
• can you clarify your comment about "overflow"? Commented Dec 15, 2023 at 18:08
• Sorry! That was badly phrased. Thank you for pointing this out. I hope it is clearer now. Commented Dec 15, 2023 at 21:28