# Lightweight Conversion from Arithmetic to Boolean Masking for Embedded IoT Processor
## 2 Background
### The A2B Algorithm Based on the Ripple-Carry Adder
#### 2.3.2 [PERSON]'s A2B Algorithm
],r,\rho\)
3:Generate a random \(k\)-bit \(r\) and a random bit \(\rho\)
4:for\(A=0\) to \(2^{k}-1\)do
5:\(T[\rho||A]\leftarrow\{(A+r)\oplus(\rho||r)\}\gg 1\)
6:\(T[\rho\oplus 1||A]\leftarrow\{(A+r+1)\oplus(\rho||r)\}\gg 1\)
7:endfor
8:return\(T[. ],r,\rho\)
```

**Algorithm 6** [PERSON]'s Table T Generation [22] \begin{table}
\begin{tabular}{c l} \hline \hline
**Line** & **Intermediate Value of \(A(i=0)\)** \\ \hline
1 & \(\widetilde{A}+z-(r||\ldots||r)\bmod 2^{k\cdot n}\) \\  & \(=(\widetilde{x}-\widetilde{R})+z-(r||\ldots||r)\bmod 2^{k\cdot n}\) \\  & \(=\widetilde{x}-\widetilde{R}-(r||\ldots||r)\bmod 2^{k\cdot n}\) \\  & \((\ddots\cdot\cdot(\widetilde{a-b})=\widetilde{a}-\widetilde{b}-z)\) \\ \hline
4 & \((\widetilde{x}_{h}||0_{k})-(\widetilde{R}_{h}||0_{k})-(r||\ldots||0_{k})\) \\  & \(+\widetilde{x}_{l}-\widetilde{R_{l}}-r\bmod 2^{k\cdot n}\) \\ \hline
5 & \((\widetilde{x}_{h}||0_{k})-(\widetilde{R}_{h}||0_{k})-(r||\ldots||0_{k})\) \\  & \(+\widetilde{x}_{l}-r\bmod 2^{k\cdot n}\) \\ \hline
6 & \((\widetilde{x}_{h}||0_{k})-(\widetilde{R}_{h}||0_{k})-(r||\ldots||0_{k})\) \\  & \(+T[\widetilde{x}_{l}-r]\bmod 2^{k\cdot n}\) \\  & \(=(\widetilde{x_{h}}||0_{k})-(\widetilde{R}_{h}||0_{k})-(r||\ldots||0_{k})+(c^{ \prime}||0_{k})\) \\  & \(+(\widetilde{x}_{l}\oplus r)\bmod 2^{k\cdot n}\) \\  & \(=((\widetilde{x_{h}}+c)||0_{k})-(\widetilde{R}_{h}||0_{k})-(r||\ldots||0_{k})\) \\  & \(+(\widetilde{x}_{l}\oplus r)\bmod 2^{k\cdot n}\) \\ \hline
8 & \(=\widetilde{x_{h}}-\widetilde{R_{h}}-(r||\ldots||r)\bmod 2^{(n-1)\cdot k}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Intermediate Values of Algorithm 5. ```
1:\((A,R),T[. ],r,\rho\ /*\ x=A+R\ \text{mod}\ 2^{k\cdot n}*/\) /
2:\(/*\ T[. ],r,\rho\) generated during pre-computation phase */
3:\((x^{\prime},R)\ /*\ x=x^{\prime}\oplus R\ */\)
4:\(A\gets A-(r||\ldots||r)\ \text{mod}\ 2^{n\cdot k}\)
5:\(\beta\leftarrow\rho\)
6:for\(i=0\) to \(n-1\)do
7: Split \(A\) into \(A_{h}||A_{l}\) and \(R\) into \(R_{h}||R_{l}\) (such that \(A_{l}\) and \(R_{l}\) have size \(k\))
8:\(A\gets A+R_{l}\ \text{mod}\ 2^{(n-i)\cdot k}\)
9:\(\beta||x_{i}^{\prime}\leftarrow((T[\beta||A_{l}]||\texttt{LSB}_{A_{l}})\oplus \beta)\oplus\rho\)
10:\(x_{i}^{\prime}\gets x_{i}^{\prime}\oplus R_{l}\)
11:\(A\gets A_{h}\) and \(R\gets R_{h}\)
12:endfor
13:return\((x_{n-1}^{\prime}||\ldots||x_{0}^{\prime})\oplus(r||\ldots||r)\)
```

**Algorithm 7** [PERSON]'s A2B Algorithm with LSB trick [22]

**Remark 2**. : \((x_{n}^{\prime},R)\) /* \(x=x^{\prime}\oplus R\) */

\begin{table}
\begin{tabular}{c c} \hline \hline
**Line** & **Intermediate Value of \(A\) and \(\beta\)** \\ \hline
1 & \(\begin{array}{l}\text{A}:A-(r||\ldots||r)\ \text{mod}



## 3 Our Proposal

In this section, we propose an A2B algorithm that is designed for extremely low memory usage while preserving execution time. Our A2B algorithm consists of the use of one table only (like [17]), combined with the stronger secure management of the carry bit such that the carry bit is masked with the same probability (like [22]). The key idea is to construct a pre-computation table of the same size as the input bits. To handle the carry bit with stronger security, we designed a memory of size two which was constructed to minimize the additional costs in the A2B conversion phase. ### Pre-Computation Phase

Algorithm 8 is a new algorithm that generates the pre-computation tables of our A2B algorithm. Table \(G\) is stored, except for the LSB of \(\{(A+r)\oplus(\gamma||r)\}\in\mathbb{F}_{2^{k+1}}\) at Line 3. The A2B algorithm works correctly even if the pre-computation table does not store the LSB; this is the so-called _LSB trick_. The reason for this is that the subtraction in the arithmetic masking and the XOR in the Boolean masking are equal on \(\mathbb{F}_{2}\). This means that the information regarding the LSB can be handled by a trick in the A2B algorithm without needing to be stored in the pre-computation table. The conversion process is described in further detail in Section 4.