## 3 A New Dual-Rail-Based Power-Balancing Countermeasure without Look-Up Tables
### Constant ADD Operation  
In this section, we present a description of the manner in which the PB methods can be used for addition operations involving constant Boolean operations. We were inspired by the Kogge-Stone adder (KS adder) in achieving our goal. A concept of the KS adder was developed by [PERSON] and [PERSON] [22]. The KS adder, which can be calculated using only Boolean operators, is known as a very fast addition algorithm. [PERSON] et al. expanded the KS adder that was designed using operators that are supported by general software such as XOR, AND, and SHIFT [20]. [PERSON] et al. developed the KS adder to handle multi-word data [21]. Each algorithm is summarized in Appendix A. Additionally, the papers of [PERSON] et al. and [PERSON] et al. are mainly about implementing the KS-adder in software, not related to PB methods. However, in order to compare the performance to the multi-word operation, the algorithms were set as a comparison group. To apply PB methods to the KS adder, several problems must be addressed. For instance, assume that we apply our encoding rule to 8-bit based block ciphers in a 32-bit microcontrollers. In this case, we simply apply the constant XOR and AND operations to [PERSON]'s algorithm. In other words, we replace 8-bit data with a 32-bit codeword and put it in a 32-bit register. However, most ARX block ciphers require 32-bit additions. These cryptosystems represent 32-bit data using four 32-bit codewords in our encoding rule. This means that a carry bit generated in a lower word should be updated in an upper word, as in the case of arbitrary-precision arithmetic. [PERSON]'s algorithm addressed this problem; however, the algorithm is not efficient because it computes the carry bit of a lower word as a decimal point. For instance, suppose that 32-bit data is calculated as four 8-bit words. [PERSON]'s algorithm requires five 8-bit KS adders. We designed an algorithm that directly applies a carry bit of a lower word to the least significant bit (LSB) of an upper word. Algorithm 3 shows our KS adder. Algorithm 4 is an addition algorithm with multi-words comprising our KS adder and [PERSON]'s KS adder. Here, we present a comparison of the differences between our Algorithm 3, [PERSON]'s Algorithm A1, and [PERSON]'s algorithms Algorithms A3 and A5. [PERSON]'s algorithm Algorithm A1 did not consider carry bits. According to the design principles of the KS adder, a carry bit of an upper word is the most significant bit of the last state of \(G\). That is, the carry bit of an upper word can be easily solved. A problem arises when handling a carry bit in a lower word. ```
1:\(x_{\in E_{1}},y_{\in E_{2}}\)
2:\(z_{\in E_{1}}(=E_{1}(x\wedge y))\)
3:\(T\gets 0\)
4:\(T\gets x



```
0:\(x,y\in\{0,1\}^{k}\), Carry \(c\in\{0,1\}\), and \(l=max(\lceil\log_{2}(k-1)\rceil,1)\)
0:\(\text{Carry }c\in\{0,1\},z(=x+y\mod 2^{k})\)
1:\(P\gets x\oplus y\oplus c\)
2:\(P^{\prime}\gets P\)
3:\(G\leftarrow((c\oplus x)\wedge(c\oplus y))\oplus c\) {\((x\wedge c)\oplus(x\wedge y)\oplus(y\wedge c)\)}
4:for\(i=0\) to \(l-2\)do
5:\(G\leftarrow(G\wedge(G\ll(1\ll i)))\oplus G\)
6:\(P\leftarrow(P\wedge(P\ll(1\ll i)))\)
7:endfor
8:\(G\leftarrow(G\wedge(G\ll(1\ll(l-1))))\oplus G\)
9:\(c||z\gets P^{\prime}\oplus(2G)\) {Carry bit is MSB of \(G\)}
10:return\((c,z)\)
```

**Algorithm 3**KSAdderOurs, Our Kogge-Stone Adder

```
0:\(X(=x_{n-1}||...||x_{0})\), \(Y(=y_{n-1}||...||y_{0})\) {\(x_{i},y_{i}\in\{0,1\}^{k}\)}
0:\(Z(=z_{n-1}||...||z_{0})\)
1:\(C\gets 0\)
2:\((C,z_{0})\leftarrow\texttt{KSAdder}_{\texttt{Coron}}(x_{0},y_{0})\)
3:for\(i=1\) to \(n-1\)do
4:\((C,z_{i})\leftarrow\texttt{KSAdder}_{\texttt{Ours}}(x_{i},y_{i},C)\)
5:endfor
6:return\((z_{n-1}||...||z_{0})\)
```

**Algorithm 4**Our Multi-bit Adder Combining Kogge-Stone Adders

Before describing our algorithm, consider the following example; \"A carry bit is generated in a lower word, and both LSBs of the words are 1.\" Even in this case, a carry bit, which is generated in both LSBs and the lower carry bit, does not exceed 1.