# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 3 Proposed Method  
This paper introduces quantum circuits designed for NTT/InvNTT operations within a lattice-based algorithm. The formulated NTT/InvNTT quantum circuits are tailored to accommodate CRYSTALS-Kyber parameters \(n=256\) and \(q=3329\), facilitating multiplication within the modulus \(Z_{q}[X]/(X^{n}+1)\). Within these quantum circuits, an optimization technique was implemented to reduce the consumption of quantum resources. To perform addition within the quantum circuit, the ripple-carry adder proposed by [PERSON] (1986) was appropriately used. Figure 2 illustrates the quantum circuit for the proposed NTT, with the sequence of operations detailed as follows (\(\circ\): Connect the algorithms from left to right):  
\[\text{NTT}=NTT_{sub}\circ\text{Montgomery reduction}\circ FFM_{1,2}\]  
Figure 3 illustrates the quantum circuit for the proposed InvNTT, with the sequence of operations detailed as follows:  
\[\text{InvNTT}=InvFFM_{2}\circ\text{Montgomery reduction}\circ InvFFM_{1}\circ\text{Barret reduction}\]  
* \(FFM\) and \(Inv\)\(FFM\): These perform multiplication in a finite field. It outputs 32-qubit results by multiplying the two 16-qubit values. In detail, it is divided into \(FFM_{1}\), \(FFM_{2}\), \(Inv\)\(FFM_{1}\), and \(Inv\)\(FFM_{2}\) functions. \(FFM_{1}\) and \(FFM_{2}\) are used in the NTT quantum circuit, and \(Inv\)\(FFM_{1}\) and \(Inv\)\(FFM_{2}\) are used in the InvNTT quantum circuit.
* _Montgomery reduction_: The process executes the Montgomery reduction multiplication on the product of a 32-qubit input and zeta; (input \(\times\)\(zeta\)). This operation is achieved in the quantum circuit via multiplication, subtraction, and shifting, employing values \(Q=3329\) and \(QINV=-3327\). The outcome of the Montgomery reduction is a 16-qubit value.
* \(NTT_{sub}\): This function in the NTT quantum circuit manages addition and subtraction between the Montgomery reduction multiplication outcome and the input. Specifically, it branches into \(NTT_{sub1}\) and \(NTT_{sub2}\). \(NTT_{sub1}\) yields the subtraction result while \(NTT_{sub2}\) produces the addition result.
* _Barrett reduction_: The function executes the Barrett reduction multiplication on a 16-bit input. Within the quantum circuit, this operation involves both multiplication and addition. Additionally, this function utilizes an extra 16 qubits.  
In qubit representation, negative numbers are denoted using the two's complement method. Since zeta is a pre-calculated value, there is no separate calculation. The NTT quantum circuit is performed using the Montgomery reduction. We allocate 32 qubits for each term to represent the multiplication result as a binary number. In the CRYSTALS-Kyber parameter \(n=256\), \(q=3329\), \(32\times n\)-qubits are used to store the coefficients in the \(Z_{q}[X]/(X^{n}+1)\). The original input must be used in the last \(NTT_{sub}\) function, so the function proceeds while maintaining the input. Therefore, each function uses the temp qubit to store the operation result and proceeds to the next function. Source codes for the NTT and inverse NTT quantum circuits in CRYSTALS-Kyber are available in [30]. A description of each function follows.