# Optimizing HAWK Signature Scheme Performance on ARMv8
## 3 HAWK Optimization Through Profiling
### Optimized Implementation of Critical Operations
#### 3.2.3 Parallel Implementation of NTT  
Our final optimization strategy is the parallel implementation of the Number Theoretic Transform (NTT). In this study, we also attempted an optimized implementation of NTT and proposed a parallel implementation that uses the vector registers of AArch64 for further optimization. Although NTT primarily involves simple operations like multiplication and addition, the high number of repetitions introduces significant overhead. The structure of NTT is depicted in Figure 7.  
Figure 7 illustrates the process of NTT (Number Theoretic Transform) computation when \(\log n=3\). As the value of \(\log n\) increases, an additional computation stage is added. By arranging the elements that perform identical operations into a single register, parallel implementation becomes possible. In this regard, Figure 7 prov  
Figure 5: The z computation process without using the ‘madd’ instruction: This diagram shows the step-by-step computation of the value \(z\) using standard arithmetic instructions. Subtraction operations are performed on inputs x0, x3 and x1, x2, followed by an addition to compute the final result. Figure 6: The z computation process using the ‘madd’ instruction: This version of the computation uses the ‘madd’ instruction, which combines multiplication and addition in a single step. The process reduces the number of instructions required compared to Figure 5, resulting in a more optimized computation of \(z\). When examining each stage separately, the parts connected by lines of the same color indicate that they all perform the same operations. Therefore, by aligning the values that perform the same operations into a single register, parallel implementation is achievable. However, since the indices that perform the same operations differ at each stage, different parallel implementation strategies must be applied at each stage. For this reason, it is necessary to check each stage during parallel implementation. Parallel implementation allows for the simultaneous processing of multiple data, offering better performance compared to serial execution of individual data computations. However, this is not always beneficial. The process of sorting data for parallel computation may introduce overhead, and if this overhead exceeds the performance gain from parallel processing, it can result in a decrease in overall performance. Such cases typically occur when the amount of data to be processed is small. In other words, when there is little computation, simple serial execution can be more efficient than parallel computation. In the case of NTT, when the value of \(\log n\) is small, the number of operations is not large, meaning that serial implementation can be more efficient than parallel implementation. This is because parallel execution may suffer from performance degradation due to the need for sorting data or fetching data from different memory locations. Therefore, in this study, we further analyzed the performance based on different values of \(\log n\), in order to identify at which point the performance shift towards parallel implementation occurs. While parallel implementation can enhance performance by processing multiple data simultaneously, performance degradation may occur due to the need for data alignment, stage verification and, in certain stages, the need to fetch values from different memory locations rather than from contiguous memory addresses. Therefore, the potential performance gains from parallel implementation should be compared against these issues to determine its feasibility. As shown in Figure 8, up to a \(\log n\) value of 7, there is minimal difference in performance between the Reference NTT and the Parallel NTT, with the parallel implementation occasionally exhibiting lower performance. However, beginning from a \(\log n\) value of 8, a noticeable performance difference emerges, and this gap continues to widen as \(\log n\) increases. This observation suggests that when \(\log n\) exceeds 8, parallel implementation can result in performance improvements.