How long random value is required in random masking method?

Question

I heard that random masking method requires a random number whose length is as long as a message to be sent, but I’m not sure that. So, I'd like to ask about that.

1. Boolean masking : $ x_i \oplus r_i$

Assume that a message is $ (x_7, x_6, \cdots , x_0)$ where $x_i$=0 or 1. Then, a random value of 8 bits is required! That is $(r_7, r_6, \cdots , r_0)$ where $r_i$=0 or 1 and the Boolean masking is $(x_7 \oplus r_7, x_6 \oplus r_6, \cdots , x_0 \oplus r_0)$

2. Arithmetic masking : $x + r$

Assume a message $x$ of 8 bits where $x \in \Bbb Z_{2^8}$. Then, a random value $r$ of 8 bits where $r \in \Bbb Z_{2^8}$ is required!

2-1. Arithmetic masking

Assume that the length of all message $x$ to be sent is 4 bits (that is, $0 \le x < 2^4$) where $x \in \Bbb Z_{2^8}$.

(Question 1) Is it possible to hide the message $x$ with random number $r$ of 4 bits using arithmetic masking method $x+r$ in $\Bbb Z_{2^8}$?

3. Multiplicative masking : $x*r$

Assume that the length of all message $x$ to be sent is 4 bits (that is, $0 \le x < 2^4$) where $x \in \Bbb Z_{2^8}$.

(Question 2) Is it possible to hide the message $x$ with random number $r$ of 4 bits using multiplicative masking method $x*r$ in $\Bbb Z_{2^8}$?

(Question 3) Where can I find the related references?

Thank you in advance.

Answer 1

Forget $s=8,$ let $s=2t$ and let $t$ be large. An answer of "yes" only means the masked quantity is uniformly distributed in some set which is brute force able if the set is small enough.

Question 1. No, the distribution of the secret plus the mask is not uniform, when the mask is uniformly chosen from $\{0,1,..,2^t-1\}.$ It is triangular. This assumes addition is mod $2^s.$

Edit: If in this question you mean the addition is mod $2^t$ with the secret from the integers mod $2^s,$ the answer is yes.

Question 2. No, and this is even worse since if you get a product divisible by $2^m$ where $m$ is the largest exponent with that property you leak a lot of information. Again this is because there is no modular reduction of the product, it being too small. Say product is 2, then either secret is 1 and mask is 2 or vice versa.

Even if you have wraparound multiplication mod $2^s$ is weak due to it being a ring with zero divisors.

2nd Edit after new comment by OP:

You won't get a uniform distribution. And the divisibility comments above still apply since in general there is no wraparound. Except you get a wraparound to zero only if you multiply the largest $x$ and the largest $r$ obtaining $2^{512}$ which would wrap around to zero if you reduce mod $2^{512}$ (and this would leak those values).

On the other hand, you now have huge numbers, and brute forcing, even when knowing the divisibility, will take a very very long time, if not being out of reach.

Question 3. Integer arithmetic.

In general addition is better, use full length uniformly distributed masks.