# 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
In summary, our pre-computation table \(G\) is constructed with \(k\)-bit memories, and it can be hugely advantageous in real devices that use the char type. In addition, table \(C\) is used to handle carry bits and \(\Gamma\) is used to guarantee security against DPA attacks. For a carry bit \(c\), table \(C\) is based on the following equation, with \(\alpha\) and \(k\) denoting a random value and the size of converted bits, respectively. \[C[c\oplus\gamma]=(c+\alpha)\cdot 2^{k}\]

The bit sizes of table \(C\) and \(\Gamma\) should make up the total bit size of \((k\cdot n)\)-bit, and the reason for this is discussed in further detail in Section 4. Algorithm 8 is also remarkable not only in terms of memory usage but also in terms of execution time. [PERSON]'s Algorithm 6 has two steps (Lines 3, 4) inside the **for** loops. This means that the number of generated tables is \(2^{k+1}\). Quantitatively, the number of **for** loops of Algorithm 6 can be considered to be \(2^{k+1}\), whereas ours has only \(2^{k}\) loops, like [17]. Therefore, our algorithm will take approximately half of the execution time required by [PERSON]'s algorithm. In terms of the security against side-channel attacks of a carry bit, our A2B masking scheme masks the carry bit with a probability of \(1/2\), like [22], and the outputs of table \(C\) are uniformly distributed in \([0,2^{k\cdot(n-1)})||0_{k}\). We designed \(\Gamma\) to eliminate the extra step of removing \(\alpha\) in the conversion phase. ```
1:None
2:\(G[.],C[. ],\Gamma,r\)
3:Generate a random \(((k-1)\cdot n)\)-bit \(\alpha\), a random \(k\)-bit \(r\) and a random bit \(\gamma\)
4:for\(A=0\) to \(2^{k}-1\)do
5:\(G[A]\leftarrow\{(A+r)\oplus(\gamma||r)\}\gg 1\)
6:endfor
7:\(C[\gamma]\leftarrow\alpha\cdot 2^{k}\)
8:\(C[\gamma\oplus 1]\leftarrow(\alpha+1)\cdot 2^{k}\)
9:\(\Gamma\leftarrow\sum_{l=1}^{l-1}(\alpha\cdot 2^{l\cdot k})\)
10:return\(G[.],C[. ],\Gamma,r\)
```

**Algorithm 8** Table G and C generation

### Conversion Phase

Algorithm 9 is the proposed A2B algorithm using the pre-computation table. This algorithm divides the arithmetic masked value \(A\) into a \(k\)-bit, converts it to a Boolean masked value \(B_{i}\), and handles carry bit using the table \(C\). At Line 4, the masked LSB can be computed correctly because the Boolean masked value \(B_{i}\) is the same as the arithmetic masked value \(A_{i}\) on \(\mathbb{F}_{2}\). At Line 6, the carry bit \(t\), which is masked by \(\gamma\) in Algorithm 8 (Line 3), is handled by table \(C[t]\) by adding \(\alpha\) or \(\alpha+1\) when the carry bit is 0 or 1, respectively. As we designed the algorithm to subtract \(\Gamma\) at Line 1, \(\alpha\) of table \(C\) is removed without the need for any extra steps. It is also worth noting that our algorithm does not require modulus operations. In real devices, data that exceeds the memory size of the register is automatically deleted. Based on this, our algorithm proceeds with the A2B conversion from the least significant word to the most significant word without any modulus operations. ```
/* Notation: Split \(A\) into \(A_{n-1}||\ldots||A_{i}||\ldots||A_{0}\) and \(R\) into \(R_{n-1}||\ldots||R_{i}||\ldots||R_{0}\), such that \(A_{i}\) and \(R_{i}\) have size \(k\)*/ /* \(r\) and \(B_{i}\) is used of \(k\)-bit register*/ /* \(A\) is used of \((k*n)\)-bit register*/
11
12:\((A,R),G[.],C[. ],\Gamma,r\)/* \(x=A+R\) mod \(2^{k\cdot n}*\)/ /* \(G[.],C[.