0
$\begingroup$

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...

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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<q$) 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}.$

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – user34968
    Commented Dec 15, 2023 at 17:37
  • $\begingroup$ can you clarify your comment about "overflow"? $\endgroup$
    – kodlu
    Commented Dec 15, 2023 at 18:08
  • $\begingroup$ Sorry! That was badly phrased. Thank you for pointing this out. I hope it is clearer now. $\endgroup$
    – user34968
    Commented Dec 15, 2023 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.