# 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
However, it is not perfectly safe to change \((0,-1)\) to \((0,1)\) against SPA. It has been

\begin{table}
\begin{tabular}{c l} \hline \hline
**Line** & **Intermediate Value of \(\bm



published that binary classification of \"0\" and \"1\" is possible using side-channel information [28]. [PERSON]'s A2B algorithm could be potentially exploited via side-channel vulnerabilities. The working principle of [PERSON]'s algorithm is that the converted data from arithmetic to Boolean masking are either \((x,R)\) or \((\bar{x},\bar{R})\). Their complementary values are determined by \(z\). Although this masking scheme does not mask the carry bit with a probability of \(1/2\), the carry bit is 0 or 1 with probabilities of \(\frac{(2^{k}-1)}{2^{k+1}}\) and \(\frac{(2^{k}+1)}{2^{k+1}}\) respectively for arbitrary \(z\) and \(r\). In other words, the probability that the carry bit is generated for any sensitive value \(x\) is always equal to the same distribution, and so it is safe against DPA attacks. Table 2 shows the intermediate value A of Algorithm 5 when loop \(i=0\). For a value \(w\), let \(\widetilde{w}\) denote \(w\) if \(z=0\), and \(\overline{w}\) if \(z=1\). These computations are based on following equations. \[\left\{ \begin{array}{l}\widetilde{(p+q)}=\widetilde{p}+\widetilde{q}+z\\ \widetilde{(p-q)}=\widetilde{p}-\widetilde{q}-z\end{array} \right. \tag{3a}\] \[\left\{ \begin{array}{l}\widetilde{(p+q)}=\widetilde{p}+\widetilde{q}+z\\ \widetilde{(p-q)}=\widetilde{p}-\widetilde{q}-z\end{array} \right. \tag{3b}\]

As we can verify in Table 2, the initial and final forms of the **for** loop are the same. The algorithm operates recursively. ```
0:None
0:\(T[.],r,\gamma,z,Z[. ]\)
1: Generate a random bit \(z\), a random \(k\)-bit \(r\), and a random \((n\cdot k)\)-bit \(\gamma\)
2:for\(A=0\) to \(2^{k}-1\)do
3:\(T[A]\leftarrow\{(A+r)\oplus r\}\gg 1\)
4:endfor
5:\(Z[0]\leftarrow\gamma\)
6:\(Z[1]\leftarrow\gamma\oplus(-1\bmod 2^{k\cdot n})\)
7:return\(T[.],r,\gamma,z,Z[. ]\)
```

**Algorithm 4** [PERSON]'s Table T Generation [17]

```
0:\((A,R),T[.],r,\gamma,z,Z[. ]\) /* \(x=A+R\bmod 2^{k\cdot n}*/\) /* \(T[.],r,\gamma,z,Z[. ]\) generated during pre-computation phase */
0:\((x^{\prime},R)\) /* \(x=x^{\prime}\oplus R\) */
1:\(A\leftarrow\left((A\oplus\gamma)\oplus Z[z]\right)-(r||\ldots||r)+z\bmod 2^{k\cdot n}\)
2:\(R\leftarrow(R\oplus\gamma)\oplus Z[z]\)
3:for\(i=0\) to \(n-1\)do
4: Split \(A\) into \(A_{h}||A_{l}\) and \(R\) into \(R_{h}||R_{l}\) (such that \(A_{l}\) and \(R_{l}\) have size \(k\))
5:\(A\gets A+R_{l}\bmod 2^{(n-i)\cdot k}\)
6:\(A\leftarrow(A_{h}||0_{k})+(T[A_{l}]||\texttt{LSB}_{A_{l}})\bmod 2^{(n-i)\cdot k}\)
7:\(x^{\prime}_{i}\gets A_{l}\oplus R_{l}\)
8:\(A\gets A_{h}\) and \(R\gets R_{h}\)
9:endfor
10:return\((x^{\prime}_{n-1}||\ldots||x^{\prime}_{0})\oplus(r||\ldots||r)\)
```

**Algorithm 5** [PERSON]'s A2B Algorithm with LSB trick [17]

#### 2.3.4. [PERSON]'s A2B Algorithm

[PERSON] proposed an A2B algorithm which was quite optimized in terms of the memory usage of the pre-computation table as well as the execution time with security against DPA attacks. [PERSON]'s algorithms reduce the complexity of the conversion phase by using the masked carry bit as the input to the table. This means that the algorithm does not require for extra costs to handle the carry bit. However, the LSB trick briefly mentioned previously in this paper is not easy to directly apply to [PERSON]'s algorithms. Algorithms 6 and 7 are versions of [PERSON]'s algorithms adjusted to include the LSB trick. As shown at Line 6 in Algorithm 7, it is required for the process to update the carry bit of the previous **for** loop on the LSB. Table 3 provides an understanding of [PERSON]'s conversion process. Although the original algorithms are well designed in terms of execution time and memory usage, applying the LSB trick incurs additional costs. ```
1:\(None\)
2:\(T[.