# 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  
As [PERSON]'s A2B algorithm requires several operations that are linear in terms of the sizes of bits, it can serve as a bottleneck when implemented. [PERSON] et al. improved the A2B algorithm by using pre-computation look-up tables. They used the pre-computation table \(T[. ]\) of \((k\cdot n)\)-bit size to reduce the number of iterations from \(K\) to \(K/k\). The Algorithms 2 and 3 are improved versions from [22]. Although [PERSON]'s algorithm takes time in the pre-computation phase, the execution time of its conversion phase can be reduced in comparison to that of [PERSON]'s algorithm. In summary, [PERSON]'s algorithm has been improved in terms of execution time. However, this algorithm still has a disadvantage in terms of its memory usage (i.e., the table size is too large). Table 1 shows the intermediate value A of Algorithm 3 when loop \(i=0\). \(0_{k}\) indicates \(0\) filled with \(k\)-bits. \(c\) denotes the carry bit at the pre-computation table \(T[A]\) in Algorithm 2. As can be verified in Table 1, the initial and final forms of the **for** loop are the same, i.e., it is intuitively confirmed that the algorithm operates recursively and correctly. The main idea for handling the carry bit is to blind the carry bit with a large random number \(\gamma\). To omit the step of removing the masking value \(\gamma\) in the conversion phase, these algorithms calculate \(\Gamma\) in the pre-computation phase and subtract it at the beginning of the conversion phase. ```
1:\(None\)
2:\(T[. ],r,\Gamma\)
3: Generate a random \(k\)-bit \(r\) and a random \(((n-1)\cdot k)\)-bit \(\gamma\)
4:\(\Gamma\leftarrow\sum_{i=1}^{n-1}2^{i\cdot k}\cdot\gamma\) mod \(2^{n\cdot k}\)
5:\(\gamma^{\prime}\leftarrow\gamma||r\)
6:for\(A=0\) to \(2^{k}-1\)do
7:\(T[A]\leftarrow(A+\gamma^{\prime}\) mod \(2^{k\cdot n})\oplus r\)
8:endfor
9:return\(T[. ],r,\Gamma\)
```  
**Algorithm 2** Improved Coron's Table T Generation [22]```
1:\((A,R),T[. ],r,\Gamma\) /* \(x=A+R\) mod \(2^{k\cdot n}*/\) /* \(T[. ],r,\Gamma\) generated during pre-computation phase */
2:\((x^{\prime},R)\) /* \(x=x^{\prime}\oplus R*/\)
3:\(A\gets A-(r||\ldots||r)-\Gamma\) mod \(2^{k\cdot n}\)
4:for\(i=0\) to \(n-1\)do
5: Split \(A\) into \(A_{h}||A_{l}\) and \(R\) into \(R_{h}||R_{l}\) (such that \(A_{l}\) and \(R_{l}\) have size \(k\))
6:\(A\gets A+R_{l}\) mod \(2^{\{n-i\}\cdot k}\)
7:\(A\leftarrow\left(A_{h}||0_{k}\right)+T[A_{l}]\) mod \(2^{k\cdot n}\)
8:\(x^{\prime}_{i}\gets A_{l}\oplus R_{l}\)
9:\(A\gets A_{h}\) and \(R\gets R_{h}\)
10:endfor
11:return\((x^{\prime}_{n-1}||\ldots||x^{\prime}_{0})\oplus(r||\ldots||r)\)
```

**Algorithm 3** Improved [PERSON]'s A2B Algorithm [22]

#### 2.3.3 [PERSON]'s A2B Algorithm

[PERSON] et al. suggested a new method to handle carry bits using complemented values in the conversion phase. This method was able to reduce the size of the pre-computation table. An adapted version of the Neisse-Pulkus method was proposed in [22]; however, the author claimed that this A2B algorithm is vulnerable to combination attacks that distinguish \(00...00\) and \(11...11(-1)\) using the Simple Power Analysis (SPA) attack and recovers the secret values using the DPA attack. For example, let us suppose that the value \(z\) at the conversion phase in [22] is extracted as \(0\) by the SPA attack. In this case, the most significant bit (i.e., the carry bit) is biased, and this biased bit allows for side-channel attacks. However, this vulnerability can easily be made secure. In addition, [PERSON]'s A2B algorithm in [22] does not work. Algorithms 4 and 5 are versions of this algorithm that are correct and secure against combination attacks due to their use of the LSB (Least Significant Bit) trick. The LSB trick is a technique that reduces pre-computation tables by one bit based on the equivalence that the Boolean masked value \(B_{i}\) is the same as the arithmetic masked value \(A_{i}\) on \(\mathbb{F}_{2}\). The LSB trick was mentioned in [PERSON]'s paper, and we applied this trick specifically to the A2B algorithms.