In the paper "Efficient Boolean-to-Arithmetic Mask Conversion in Hardware" by Aein Rezaei Shahmirzadi and Michael Hutter of PQShield, the authors claim to have found a method for boolean-to-arithmetic mask conversion without the use of masked adders. Their method, if correct, appears to be an enormous improvement in terms of resource usage compared to alternative constructions.
However, I believe their result is slightly incorrect: given boolean shares $(x_0,x_1)$ of $x=x_0\oplus x_1$, it appears to me that their "gadget 4" results in arithmetic shares modulo $2^k$ of the value $x\hspace{-.3cm} \mod q$, rather than arithmetic shares modulo $q$ of $x$; the difference being that the output shares satisfy $(z_1-z_2 )\mod 2^k = x \mod q$, rather than $(z_1-z_2)\mod q = x \mod q$.
Of course, the latter is what we're really after since it allows us to perform $\mathbb{F}_q$-linear functions share-wise; it is not at all clear to me how this is to be done with the author's output shares.
I have two questions:
- Am I interpreting their results correctly?
- If so, is it possible to perform some simple (secure) operations on their output in order to get genuine arithmetic shares modulo $q$?
EDIT 1: Here are my thoughts after thinking on it a bit... Assuming $q<2^k$ (which is no problem), Gadget 4 results in two values $z_1,z_2<2^k$ such that $(z_1-z_2) \hspace{-.3cm} \mod 2^k = x \hspace{-.3cm} \mod q,$ so that either $$z_1-z_2 = (x \hspace{-.3cm} \mod q)$$ or $$z_1+(2^k-z_2) = (x \hspace{-.3cm} \mod q)$$ with equality over $\mathbb{Z}$. We are in the first case iff $z_1\geq z_2$, and then $(z_1 \hspace{-.3cm}\mod q, -z_2\hspace{-.3cm}\mod q)$ is an arithmetic sharing modulo $q$ of $x\hspace{-.3cm} \mod q$. We are in the second case iff $z_1 < z_2$, and then $(z_1 \hspace{-.3cm}\mod q, (2^k-z_2)\hspace{-.3cm}\mod q)$ is an arithmetic sharing of $x \hspace{-.3cm}\mod q$.
So at least we can easily derive genuine arithmetic shares modulo $q$ from Gadget 4, but the question is: how can we do it securely?
EDIT 2: Here is my proposed method for generating genuine arithmetic shares modulo $q$ in a secure way from their Gadget 4: following up from EDIT 1, we know that we need to securely decide whether $z_1\geq z_2$. Let's assume we have access to a function $\text{SecGeq}(x_0,x_1,y_0,y_1)$ that takes as input boolean shares $(x_0,x_1)$ of $x$ and $(y_0,y_1)$ of $y$ and returns shares $(b_0,b_1)$ with $b_0\oplus b_1 = [[x\geq y]]$ --- it is easy enough to make such a function with slight modifications to the author's masked carry-bit calculator (Gadget 3). Now generate random $k$-bit values $r_1$ and $r_2$ to calculate $(b_0,b_1) = \text{SecGeq}(z_1\oplus r_1, r_1, z_2\oplus r_2, r_2)$, which gives us a sharing of $[[z_1\geq z_2]]$. Finally, we can use the author's masked multiplexor (lines 4,5, and 7 of Gadget 4), to securely calculate $$z_3 = \begin{cases} -z_2 \hspace{-.3cm}& \mod q & \text{ if } z_1\geq z_2 \\ (2^k-z_2)\hspace{-.3cm}& \mod q & \text{ if } z_1 < z_2 \end{cases} $$ Then $(z_1 \hspace{-.3cm} \mod q, z_3)$ are the arithmetic shares of $x$ modulo $q$ we are looking for.
Hopefully there is room for improvement, as this is quite a bit more expensive than the author's proposed solution. The solution presented here requires 3 extra modular reductions, as well as a call to $\text{SecGeq}$, which can be thought of as a more expensive version of the author's Gadget 3 (more expensive because we can no longer assume the second argument is an unmasked, publicly known value).
EDIT 3: If we assume that x < q < 2^k at the outset, then we can indeed do better. In such a case, (stricken because it's actually an unnecessary assumption)
Let $(t_1,t_2)$ be the result of the author's B2A2k (Gadget 2, line 1 of Gadget 4). Then either $$t_1 - t_2 = x$$ or $$t_1+(2^k-t_2) = x.$$ Again, we are in the former case iff $t_1 \geq t_2$ and we can play the same game with the $\text{SecGeq}$ and the secure multiplexor from the previous edit. We still incur the cost of an unoptimized Gadget 3, but this is better than the solution in EDIT 2.
However, I'm still a bit uneasy about the leakiness of performing the comparison $z_1 \stackrel{?}{\geq} z_2$. Since $z_1$ and $z_2$ are not themselves sensitive values (only together do they leak sensitive information), I think it is fine to generate boolean shares on-the-fly $(z_1 \oplus r_1,r_1)$ and $(z_2\oplus r_2,r_2)$ for randomly generated $r_1$ and $r_2$ and to use a $\text{SecGeq}$ on these shared values, but I've yet to fully convince myself of this.
EDIT 4: Don't forget to refresh the output shares! Reducing values in the range $[0,2^k)$ modulo $q$ results in non-uniform shares since $q$ does not divide $2^k$. A simple refresh ought to do the trick.
