# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 3 Proposed Method
### FFM and Inv FFM
```
1:Input:\(a\), temporary:\(ancilla_{1}\), \(ancilla_{2}\)
2:\(ancilla_{1}\gets a\)
3:for\(i=0\) to \(v\)do
4:\(ancilla_{1}\leftarrow\mathbf{ADD}(a,ancilla_{1})\)
5:endfor
6:\(ancilla_{1}\leftarrow\mathbf{ADD}(2^{25},ancilla_{1})\)
7:for\(i=0\) to \(6\)do
8:\(ancilla_{2}[i]\leftarrow\text{CNOT}(ancilla_{1}[26+i],ancilla_{2}[i])\)
9:endfor
10:for\(i=0\) to \(Q-1\)do
11:\(ancilla_{2}[i]\leftarrow\text{CNOT}(ancilla_{1}[26+i],ancilla_{2}[i])\)
12:endfor
13:Dagger:
14:\(a\leftarrow\mathbf{ADD}(ancilla_{2},a)\)
15:return\(a\)
```

**Algorithm 4**Quantum circuit for the Barrett reduction. ## 4 Evaluation

We conducted an estimation of quantum resources employing the quantum programming tool provided by ProjectQ. The NTT quantum circuit has three primary functions, while the InvNTT quantum circuit has four main functions. Each function operates in cycles (\(C\)). The quantum resources used in each sub-function of NTT are shown in Table 2. Table 3 presents the quantum resources allocated to each sub-function within the InvNTT. Since the table indicates the quantum resource used for one operation of each function, it represents the minimum resources used for operating the function at a smaller \(n\) parameter. The functions \(FFM_{1}\) and \(FFM_{2}\) both perform multiplication using the input and the constant \(zeta\) in the NTT process. The main difference is that \(FFM_{2}\) requires more \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Function**} & \multirow{2}{*}{\(C\)} & \multicolumn{4}{c}{**Quantum Gates**} & \multirow{2}{*}{**Depth**} \\ \cline{3-3} \cline{5-6}  & & **CCNOT** & **Toffoli** & **CNOT** & **X** \\ \hline \(fmul_{1}\) & 128 & - & 48,576 & 97,943 & 1 & 146,488 \\ \hline \(fmul_{2}\) & 768 & 97,024 & 195,564 & 33 & 2 & 292,592 \\ \hline Montgomery reduction & 896 & - & 306,270 & 639,184 & - & 945,438 \\ \hline \(NTT_{sub}\) & 896 & - & 124 & 318 & - & 379 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Quantum resources for the NTT function. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Function**} & \multirow{2}{*}{\(C\)} & \multicolumn{4}{c}{**Quantum Gates**} & \multirow{2}{*}{**Depth**} \\ \cline{3-3} \cline{5-6}  & & **CCNOT** & **Toffoli** & **CNOT** & **X** \\ \hline \(fmul_{3}\) & 896 & 97,024 & 195,564 & 50 & 2 & 292,608 \\ \hline \(fmul_{4}\) & 256 & 184,320 & 371,520 & 33 & 2 & 555,844 \\ \hline Barrett reduction & 896 & - & 1,349,696 & 2,793,402 & - & 4,143,041 \\ \hline Montgomery reduction & 1152 & - & 306,270 & 639,184 & - & 945,438 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Quantum resources for the InvNTT function. quantum resources than \(FFM_{1}\). This is because \(FFM_{2}\) needs to ascertain whether the input is positive or negative to determine the results expressed in the two's complement. In \(FFM_{2}\), a multi-controlled gate is used to determine the operation based on the input's sign. In \(InvFFM_{1}\), multiplication is conducted with the input and \(zeta\), while in \(InvFFM_{2}\), it is conducted with the input and the positive value \(f\). \(InvFFM_{2}\) uses more quantum resources because \(f\) is larger than \(zeta\). The Montgomery reduction requires the most resources in NTT due to multiplying large numbers. \(NTT_{sub}\) uses the least amount of resources by performing simple addition and subtraction on 32-bit qubits. The Barrett reduction uses the most resources in InvNTT due to the multiplication of large numbers. The quantum resource of each function is repeated by as much as \(C\). Consequently, the operation of NTT/InvNTT demands substantial resources. Given the quantum resources for the NTT/InvNTT within the Kyber operation, it is expected that a very large-scale quantum computer will be required to operate the entire cipher on the quantum computer. In this regard, an attempt to implement a quantum circuit for an efficient NTT/InvNTT architecture [31] may reduce quantum resources. This must be verified by efficiently implementing quantum circuits and estimating quantum resources.