## 3 Boolean Masking for Addition Circuits
### Sklansky Adder (SA)  
The Sklansky Adder was introduced in 1960 [15] as an efficient parallel adder with low area requirements. It has the same latency as a KSA at \(\log n+1\) cycles but requires a lower \begin{table}
\begin{tabular}{l l l l l} \hline \hline  & \(g(i)\) & \(p(i)\) & \(g(\{i,j\})\) & \(p(\{i,j\})\) & \(s(i)\) \\ \hline Kogge-Stone & \(n-1\) & \(n\) & \((n-1)\cdot\log n-n+1\) & \((n-1)\cdot\log n-2\cdot n+3\) & \(n\) \\ Sklansky & \(n-1\) & \(n\) & \((n/2-1)\cdot\log n\) & \((n/2-1)\cdot\log n-n+2\) & \(n\) \\ Brent–Kung & \(n-1\) & \(n\) & \(2\cdot n-2\cdot\log n-2\) & \(n-2\cdot\log n\) & \(n\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Number of required basic functions for different parallel-prefix adders. Figure 1: 8-bit Kogge-Stone Adder. \begin{table}
\begin{tabular}{l l l l} \hline \hline  & \(\mathbf{Kogge-Stone}\) & \(\mathbf{Sklansky}\) & \(\mathbf{Brent-Kung}\) \\ \hline AND & \(2\cdot(n-1)\cdot\log n-2\cdot n+3\) & \((n-2)\cdot\log n-n+1\) & \(3\cdot n-4\cdot\log n-1\) \\ XOR & \((n-1)\cdot\log n-3\cdot n\) & \((n/2-1)\cdot\log n+2\cdot n\) & \(4\cdot n-2\cdot\log n-2\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Number of elementary XOR and AND operations for different parallel-prefix adders including the preprocessing stage and final computation of the sum bits. total number of PG blocks. In contrast to the previously described circuit, the number of PG blocks per stage is constant at \(n/2\). Figure 2 depicts an 8-bit Sklansky adder, realized with 12 PG blocks in 3 stages, excluding preprocessing. In the first stage, every other PG term is combined with its neighbor, i.e.,  
\[PG(\{2\cdot i+1,2\cdot i+1\}\,\ \{2\cdot i,2\cdot i\})\ \forall 0\leq i<n/2\]  
is computed. The second stage combines these 2-bit PG terms as  
\[PG\bigg{(}\bigg{\{}4\cdot\bigg{\lfloor}\frac{i}{2}\bigg{\rfloor}+2+(i\bmod 2 ),4\cdot\bigg{\lfloor}\frac{i}{2}\bigg{\rfloor}+2\bigg{\}}\,\ \bigg{\{}4\cdot\bigg{\lfloor}\frac{i}{2}\bigg{\rfloor}+1,4\cdot \bigg{\lfloor}\frac{i}{2}\bigg{\rfloor}\bigg{\}}\bigg{)}\ \forall 0\leq i<n/2.\]  
In general, the \(k\)-th stage for \(k>0\) combines the previous PG terms using \(n/2\) PG blocks in the following way:  
\[PG\bigg{(}\bigg{\{}\bigg{\lfloor}\frac{i}{2^{k}}\bigg{\rfloor} \cdot 2^{k+1}+2^{k}+(i\bmod 2^{k}),\bigg{\lfloor}\frac{i}{2^{k}}\bigg{\rfloor} \cdot 2^{k+1}+2^{k}\bigg{\}}\,\] \[\bigg{\{}\bigg{\lfloor}\frac{i}{2^{k}}\bigg{\rfloor}\cdot 2^{k+1}+2^{k }-1,\bigg{\lfloor}\frac{i}{2^{k}}\bigg{\rfloor}\cdot 2^{k+1}+2^{k-1}-1\bigg{\}} \bigg{)}\ \forall 0\leq i<n/2\]  
Following the reasoning of Section 3.1, \((n/2-1)\cdot\log n\) PG blocks are needed to build a SA when excluding the preprocessing stage. As in in the Kogge-Stone case, \(n-2\) of these do not need to compute the propagate term. The resulting number of required the basic blocks is provided in Table 2.  
Masking SAs  
When compared to a KSA, the main advantage of an SA in the context of masked implementations lies in the reduced number of required PG blocks, which directly results in a lower area requirement. If HPC2 gadgets are used this also leads to reduces randomness use of \(d\cdot(d+1)\cdot((n-2)\cdot\log n-n+1)\) bit. Figure 2: 8-bit Sklansky Adder. If only first-order security is desired, a TI similar to [2] can be used to reduce the randomness requirements in comparison to HPC2 gadgets. In this publication, the authors re-use shares of the generate terms to reduce the required fresh randomness in the computation of the propagate term. Specifically, when computing \(p_{\{i,j\}}\) as a masked version of Equation (2), the first share of \(g_{\{k,j\}}\) is used to achieve the uniformity of the tuple \((p_{\{i,j\}},g_{\{i,j\}})\). In the KSA-case, each \(p\)-term is not used more than once per stage as the rightmost term in Equation (2). Therefore, each \(g\)-term is not used more than once to replace a bit of fresh randomness, preventing potential violations of the joint uniformity of the PG tuples in later stages.