# 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 this case, the distribution of the lower part is not uniform. As a result, the distribution of the side-channel signals is determined by sensitive data. In other words, the algorithm cannot provide security against side-channel attacks, and therefore, a clearing process must be performed. We now use mathematical induction to prove the soundness of the proposed algorithm. In detail, we observe changes in the internal state at \(i=0\) (the first loop) through the _Base case_. At this time, we prove the operating principles of the pre-computation tables by Lemmas 1 and 2. In the _Inductive hypothesis_, we define the state when loop \(i=a\). This can be easily inferred in the form of a _Base case_. Finally, in the _Inductive step_, we claim that the proposed A2B algorithm for arbitrary \(k,n\) works correctly. \begin{table}
\begin{tabular}{l} \hline \hline \(V_{1}...V_{7}\) is intermediate values of Algorithm 9 \\ \hline \(V_{1}=(x-R)-(r||\ldots||r)-\sum_{l=1}^{n-1}(\alpha\cdot 2^{l\cdot k})\) \\ \hline \(V_{3}=[(x-R-(r||\ldots||r))-\sum_{l=i+1}^{n-1}(\alpha\cdot 2^{l\cdot k})]||(x-r)||0 _{i\cdot k}\) \\ \hline \(V_{4}=(c\oplus\gamma)||(x_{withoutLSB}\oplus r_{withoutLSB})||(x_{LSB}-r_{ LSB})\) \\ \hline \(V_{5}=x\oplus r\oplus R_{i}\) \\ \hline \(V_{6}=(x-R)-(r||\ldots||r)\) \\ \(-\sum_{l=i+2}^{n-1}(\alpha\cdot 2^{l\cdot k})||(x+c-R-r)||(x-r)||0_{i\cdot k}\) \\ \hline \(V_{7}=(x-R)-(r||\ldots||r)\) \\ \(-\sum_{l=i+2}^{n-1}(\alpha\cdot 2^{l\cdot k})||(x+c-R-r)||0_{(i+1)\cdot k}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Intermediate Values. \(X_{i}^{j}\) denotes the partial bits of \(X\) from the \(i\)-th to the \(j\)-th bits. For example, \((R_{k}^{n-1}||0_{0}^{k-1})\) means the concatenated bits of the \(R\) from \((n-1)\)-th to \(k\)-th bits, and other bits which are zeros. Theorem 2: _The proposed A2B algorithm for arbitrary \(k,n\) works correctly._

**Proof. **

_Base case:_ The algorithm works correctly in the initial state (\(i=0\)), as shown in the following steps. \[\text{(Line 1)}\;\;A =(x-R)-(r||\ldots||r)-\sum_{l=1}^{n-1}(\alpha\cdot 2^{l\cdot k}) \tag{4}\] \[\text{(Line 3)}\;\;A =x-(R_{k}^{n-1}||0_{0}^{k-1})-(r||...||r)-\sum_{l=1}^{n-1}(\alpha \cdot 2^{l\cdot k}) \tag{5}\]

We must verify that the A2B operation at Lines 4 and 5 is correct. Refer to the following Lemma 1:

Lemma 1: _At Lines 4 and 5, the arithmetic masked value \(A_{i}\) is correctly converted from arithmetic masking to Boolean masking with pre-computation table \(G\)._

**Proof. ** The value of table \(G\) is as follows. \[G[A_{i}] =\{(A_{i}+r)\oplus(\gamma||r)\}\gg 1\] \[=\{(c\oplus\gamma)||(x\oplus r)\}\gg 1\] \[=\{(c\oplus\gamma)||B_{i}\}\gg 1\]

This means that the output of \(G[A_{i}]\) is \(\{(c\oplus\gamma)||B_{i}\}\) without the LSB. In the LSB, the Boolean masked value (\(x^{\prime}=x\oplus r\)) is the same as the arithmetic masked value on \(\mathbb{F}_{2}\) (\(A=x-r\) mod 2), based on the following definition. Remark 1: _Exclusive or (XOR) is defined in the arithmetic as modulo-2 addition/subtraction._

In the above definition, LSB of \(A_{i}\) is \(A_{i}\) mod 2. \[A_{i}\text{ mod 2}=x-r\text{ mod 2}=(x\oplus r)\&1=B_{i}\&1\]

The important implication of this equation is that we can calculate without storing the LSB in the masking conversion process. This is the so-called _LSB trick_. Line 4 is summarized as follows. \[G[A_{i}]||(LSB\;of\;A_{i})=(c\oplus\gamma)||B_{i}=t||B_{i}\]

Therefore, Lines 4 and 5 are valid. \[\text{(Line 6)}\left\{ \begin{array}{l}\text{when}\;\;c=0,\\ A=x\quad-\quad(R_{k}^{n-1}||0_{0}^{k-1})\\ \quad-(r||...||r)-\sum_{l=2}^{n-1}(\alpha\cdot 2^{l\cdot k})\\ \text{when}\;\;c=1,\\ A=(x+1)-(R_{k}^{n-1}||0_{0}^{k-1})\\ \quad-(r||...||r)-\sum_{l=2}^{n-1}(\alpha\cdot 2^{l\cdot k})\\ \end{array} \right.\] (6a) Here, for Line 6, we must prove that the carry bit is handled correctly by table \[C\]. Lemma 2: The carry bit is handled correctly by table \(C\) at Line 6.