In this paper, Elena Trichina introduces a way to compute a masked AND operation. The principle is the following:

Having two operands $a$ and $b$ masked with random boolean shares $x$ and $y$ ($\tilde{a} = a \oplus x$ and $\tilde{b}=b \oplus y$), how to securely compute $\tilde{a} \cdot \tilde{b}$ where $\cdot$ refers to bitwise AND.

In the paper, the solution is first introduced for single bit operands but here I consider the case where operands can be of any size.

In section 4.2, the author underlines the fact that \begin{equation} \tilde{a} \cdot \tilde{b} = (a \cdot b) \oplus (x \cdot \tilde{b}) \oplus (y \cdot \tilde{a}) \oplus (x \cdot y) \end{equation} Hence, the mask of $\tilde{a} \cdot \tilde{b}$ is equal to $(x \cdot \tilde{b}) \oplus (y \cdot \tilde{a}) \oplus (x \cdot y)$, which does not manipulate unmasked data.

So far everything, is clear.

However, it is further said that if we only use two masks $x$ and $y$ to mask $a \cdot b$ then

in order to obtain a robust mask, we would have to XOR the result of computations on masked data with the new mask ($x \oplus y$), which can be achieved while computing the terms of the ''mask correction''. Far better solution is to use a third random, $z$, as a new mask computing a ''masked'' AND operation, for example, as follows \begin{equation} ((\tilde{a}\cdot \tilde{b}) \oplus ((x \cdot \tilde{b}) \oplus ((x \cdot y) \oplus z))) \oplus (y \cdot \tilde{a}) \end{equation}

I don't understand why is it necessary to introduce randomness to compute masked AND operation.

In other terms: What is wrong when computing $c = \tilde{a}\cdot\tilde{b}$ and considering the corresponding mask $(x \cdot \tilde{b}) \oplus (y \cdot \tilde{a}) \oplus (x \cdot y)$?

  • 1
    $\begingroup$ Your $c$ is $0$ with probability 75% and $1$ with probability 25%, but both shares should be uniformly distributed for being able to use them as inputs for further operations (I'd guess that the term "robust" refers to latter property, but I can't find its definition in her paper). $\endgroup$ – j.p. Nov 19 '17 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.