4
$\begingroup$

It's easy to see that additive blinding (e.g., $x+r$ for secret x and random r) is perfectly secure in a finite field (this is a one-time-pad) and statistically secure for $r$ uniformly distributed in a domain sufficiently larger than $x$.

What I'm confused about is multiplicative blinding (i.e., $x \cdot r$) - in some places, I read that it's being used and is as secure as additive blinding, while in others it's stated that it is much less secure (e.g., multiplicative blinding less secure). Assuming, of course, both $x \neq 0$ and $r \neq 0$, is multiplicative blinding as good as additive (ignoring side channel attacks), and if not - what's the explanation?

$\endgroup$
  • $\begingroup$ Define "secure". The link you give is in reference to one specific cryptosystem. $\endgroup$ – fkraiem Feb 8 '16 at 6:05
  • 2
    $\begingroup$ Define multiplicative blinding; in particular how the blinding factor $b$ is chosen (its probability distribution); and how it is applied ($x\to x\cdot b$ is not the same as $x\to x\cdot b\bmod p$, the later form is just as secure as additive blinding when $x\ne0$ and $b$ is uniform over $[1\dots n-1]$). $\endgroup$ – fgrieu Feb 8 '16 at 6:24
  • $\begingroup$ @fgrieu shouldn't it be: $b$ is uniform over $\{1, \ldots, p-1\}$? $\endgroup$ – Guut Boy Feb 8 '16 at 9:44
  • $\begingroup$ @fgrieu - Very good point. I'm trying to understand both in $\mathbb{Z}_p$ and in the integers (i.e., ring $\mathbb{Z}_p$). In both cases $r$ is uniformly random in that domain. As to secure - the statistical distance between $f(x,r)$ and $r$, where $f \in \{+,\cdot \}$ (0 for perfect and some $\epsilon (n)$ for statistical). $\endgroup$ – RevFlash Feb 8 '16 at 13:25
  • $\begingroup$ @Guut Boy: Yes. I'm willing to trade rep against ability to fix my past comments, but that's not an option, apparently. $\endgroup$ – fgrieu Feb 8 '16 at 14:19
6
$\begingroup$

In a finite field $\mathbb{F}_q$, both maskings are perfectly secure, provided that $x \neq 0$ for the multiplicative masking.

This is easy to see. The finite field $\mathbb{F}_q$ defines two groups: the additive group $\mathbb{F}_p^+$ (i.e., $\mathbb{F}_q$ equipped with addition) and the multiplicative group $\mathbb{F}_q^*$ (i.e., $\mathbb{F}_q \setminus \{0\}$ equipped with multiplication).

Proposition Let $\mathbb{G}$ be a group and let $\star$ denote the group law in $\mathbb{G}$. Given $x \in \mathbb{G}$, if $r$ is a uniformly random element in $\mathbb{G}$ then so is $y:=x \star r$.

Let $x \in \mathbb{F}_q$. We have:

  • If $r$ is drawn uniformly at random in $\mathbb{F}_q^+$ then $x+r$ (where $+$ denotes the addition in $\mathbb{F}_q$) is uniformly random in $\mathbb{F}_q^+$;
  • If $r$ is drawn uniformly at random in $\mathbb{F}_q^*$ then $x*r$ (where $*$ denotes the multiplication in $\mathbb{F}_q$) is uniformly random in $\mathbb{F}_q^*$, provided that $x \neq 0$ (that is, $x \in \mathbb{F}_q^*$).
| improve this answer | |
$\endgroup$
  • $\begingroup$ how do you prove your claims? $\endgroup$ – ddddavidee Jun 3 '16 at 15:38
  • $\begingroup$ @ddddavidee: $\mathbb{G}$ is a group and therefore any element $x \in \mathbb{G}$ has an inverse (I note it $x^{-1}$). As a consequence, from associativity, $x \star r_1 = x \star r_2 \iff x^{-1}\star x \star r_1 = x^{-1} \star x \star r_2 \iff r_1 = r_2$. $\endgroup$ – user94293 Jun 3 '16 at 20:14
4
$\begingroup$

Whether multiplicative blinding is drastically worse than additive blinding depends fairly strongly on:

  • The ring are you doing the blinding in

  • Whether you need to blind the value 0

The second is a fairly obvious, as multiplicative blinding doesn't disguise 0 at all.

However, it would appear that the slides that you quote the statement from actually falls into the first category. That is, the ring that the operation is being done is not the field $GF(p)$ for some prime $p$ (which, if you select the randomizer properly, does a wonderful job at blinding any nonzero value); instead, it appears to be the ring of the integers (or equivalently, if they're in a ring $GF(p)$ and they select the parameter $r$ so that $r|d| < p/2$). In that case, disguising $d$ as $rd$ (for some random positive integer $r$) is, in fact, insecure, because from the value $rd$, someone can eliminate any possible value $d$ that's not a factor of $rd$.

So, yes, when some person talks about multiplicative blinding being secure, and some other person talks about it being insecure, they're both right -- they're talking about different scenarios.

| improve this answer | |
$\endgroup$
3
$\begingroup$

As fgrieu said in comments, $x\to x\cdot b\bmod p$ is just as secure as additive blinding. So we suppose that question is about $x\to x\cdot b$.

Here we suppose that factorizations time for $x\cdot b$ is negligible and examine brute force search for finding $b$:

  • In additive blinding let $c=x\cdot b$, we should check all $b$ for meaning $c-b$.

So we need to $c$ computation in worst case.

  • In multiplicative blinding let $c=c_1\times ... \times c_k$ , in best case when all $c_i$ are same then we should check all $k$ possible case for finding $b$.

With increasing $k$ and distinct $c_i$'s, time complexity became larger, but $k<log_2(c)$ so $2^k<c$ and this mean that multiplicative blinding is less secure.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Correct - interested in some ring $\mathbb{Z}_n$. Still, not sure I understand the explanation of all $c_i$ being 2. If $c$ is an exponent of 2, how does that help in finding $b$? $\endgroup$ – RevFlash Feb 8 '16 at 13:33
  • $\begingroup$ @RevFlash, I edited my answer. we search all possible cases for $b$ until founded $x$ is not meaningless. $\endgroup$ – Meysam Ghahramani Feb 8 '16 at 13:58
  • $\begingroup$ Any chance for a link to a proof or an example? I appreciate the effort but I still don't understand your derivation. Our goal is to unblind x given c. You're saying that if all bits in c are the same then we can do it in log time, but it's not clear how. Thanks! $\endgroup$ – RevFlash Feb 8 '16 at 14:23
  • $\begingroup$ @RevFlash, $c_i$'s are factors of $c$. I edited my answer. Thanks for your good comment. $\endgroup$ – Meysam Ghahramani Feb 9 '16 at 5:33
  • 1
    $\begingroup$ @Meysam Ghahramani, I wonder if there is a standard proof for the sentence: "$x\to x\cdot b\bmod p$ is just as secure as additive blinding". I found many people say the same but could not find a mathematical proof for it. $\endgroup$ – yGuest Mar 3 '16 at 23:18

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.