# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 3 Proposed Method
### FFM and Inv FFM
The parameters of Kyber NTT are fixed as \(q=3329\), \(n=256\). Figure 4 and Algorithm 3 show the operations of the Montgomery reduction quantum circuit. In the for loop, \(Q\) is \(q=3329\) and \(QINV\) is the inverse of \(Q\): \(-3327\). Since \(Q\) and \(QINV\) are known values, the result of their multiplication with the corresponding sizes can be obtained without allocating qubits to store their values. Input \(\times\)\(Q\) and input \(\times\)\(QINV\) are quantum-to-classical operations, not quantum-to-quantum operations. Finally, index values [0] to [15] are discarded through the 16-bit left shift and the values of indexes [16] to [31] are returned. ```
Input:\(a\), \(ancilla_{1}\), \(ancilla_{2}\)
1:for\(i=0\) to \(-QINV\)do
2:Dagger:\(tmp_{1}[0:16]\leftarrow\mathbf{ADD}(a[0:16],tmp_{1}[0:16])\)
3:endfor
4:for\(i=0\) to \(Q\)do
5:\(tmp_{2}[0:32]\leftarrow\mathbf{ADD}(tmp_{1}[0:32],tmp_{2}[0:32])\)
6:endfor
7:Dagger:\(a[0:32]\leftarrow\mathbf{ADD}(ancilla_{2}[0:32],a[0:32])\) return\(a[16:32]\)
```
**Algorithm 3**Quantum circuit for the Montgomery reduction. ### \(Ntt_{sub}\)

The \(NTT_{sub}\) function carries out both addition and subtraction operations, contrasting the Montgomery reduction outcome with the input of a matching index. Specifically, it functions through the detailed operations of \(NTT_{sub1}\) and \(NTT_{sub2}\). The calculations for \(NTT_{sub1}\) and \(NTT_{sub2}\) are as follows:

\[NTT= \begin{cases}NTT_{sub1}=input-Montgomery\;\;result\\ NTT_{sub2}=input+Montgomery\;\;result\end{cases} \]

In order to perform the sequential computations of the formula, it is imperative to retain both the initial input values and the Montgomery results subsequent to the \(NTT_{sub1}\) operation. Keeping all calculation targets (the input and Montgomery reduction results) is not feasible; thus, one practical solution involves storing the input in temporary qubits. Figure 5 shows the operations of the quantum circuit for \(NTT_{sub1}\) and \(NTT_{sub2}\). Figure 4: Quantum circuit for the Montgomery reduction; \(\dagger\) indicates the reversible gate. In the \(NTT_{sub1}\), it saves the subtraction of the temporary value from the Montgomery result in the temporary qubit, while keeping the Montgomery result as is. In the \(NTT_{sub2}\), it stores the addition of the initial input value and the Montgomery result in the input qubit. The results of all operations are sorted in order according to the index in the NTT array. ### Barrett Reduction

This function performs the Barrett reduction on the 16-bit input. The constant \(v\) used inside the Barrett reduction is calculated as \(v=((1<<26)+q/2)\) and used for multiplication. In a quantum circuit, \(v\) denotes classic data and is used to determine the number of multiplications. Figure 6 shows the quantum circuit for the Barrett reduction. The quantum circuit operation for the Barrett reduction is the same as Algorithm 4. In the quantum circuit, the number \(2^{25}\) used in the Barrett reduction is stored in the qubit as a binary number. The Barrett reduction is processed for the sum of two 16-bit inputs. The function employs the ripple-carry adder [29] for multiplication and addition. The multiplication with the constant \(v=20\),159 consumes the most quantum resources. Figure 5: \(NTT_{sub1,sub2}\) operation for the input and Montgomery results (above: (1) \(NTT_{sub1}\), below: (2) \(NTT_{sub2}\)); \(\dagger\) indicates the reversible gate. Figure 6: Quantum circuit for the Barrett reduction; \(\dagger\) indicates the reversible gate.