# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 3 Proposed Method
### FFM and Inv FFM  
\(FFM\) and \(Inv\)\(FFM\) are divided into four sub-functions: \(FFM_{1}\), \(FFM_{2}\), \(Inv\)\(FFM_{1}\), \(Inv\)\(FFM_{2}\). \(FFM_{1}\) and \(FFM_{2}\) are used in NTT, \(Inv\)\(FFM_{1}\) and \(Inv\)\(FFM_{2}\) are used in InvNTT. \(FFM_{1}\), \(FFM_{2}\), and \(Inv\)\(FFM_{1}\) output 32-bit results by multiplying the input with a constant \(zeta\) (input \(\times\)\(zeta\)), while \(Inv\)\(FFM_{2}\) multiplies the input with a constant \(f\) (input \(\times\)\(f\)). In detail, it is divided into \(FFM_{1}\), \(FFM_{2}\), \(Inv\)\(FFM_{1}\), and \(Inv\)\(FFM_{2}\) functions. In NTT, \(FFM_{1}\) and \(FFM_{2}\) are used, and in InvNTT, \(Inv\)\(FFM_{1}\) and \(Inv\)\(FFM_{2}\) are used. In this quantum circuit, the ripple-carry adder [29] proposed by [PERSON] et al. was used. The difference between each function is as follows:  
The \(FFM_{1}\) function yields a 32-qubit output by multiplying a 32-qubit input with the constant \(zeta\); (input \(\times\)\(zeta\)). Importantly, within this \(FFM_{1}\) function, the signs of both the input and \(zeta\) are ascertained, determining the sign of the resultant multiplication output. Similarly, the \(FFM_{2}\) function generates a 32-qubit output by multiplying a 32-qubit input with the constant \(zeta\); (input \(\times\)\(zeta\)). Figure 3: Process for the inverse NTT quantum circuit; \(\dagger\) indicates reversible gates. Figure 2: Process for the NTT quantum circuit. Within the \(FFM_{2}\) function, while the sign of \(zeta\) is known, the sign of the input remains undetermined. Consequently, an additional step is necessary within the \(FFM_{2}\) quantum circuit to identify whether the sign of the input is the same as or different from that of \(zeta\). (If equal, the result is positive, if different, the result is negative). To meet this step, a 1-qubit \(check\) serves the purpose of determining the sign. The \(Inv\)\(FFM_{1}\) function yields a 32-qubit result by multiplying a 16-qubit input with the value \(zeta\); (input \(\times\)\(zeta\)). Within this \(Inv\)\(FFM_{1}\) function, the sign of \(zeta\) is known, while the sign of the input remains undetermined. To determine the output's sign, it is necessary to ascertain the sign of the input. For this, an additional step is introduced to check the input's sign (whether it matches or differs from that of \(zeta\)). To meet this step, a 1-qubit \(check\) is used to determine the sign (similar to \(FFM_{2}\)). Since \(zeta\) are fixed constants, we can reduce the number of qubits used by performing an addition to the input up to the value of \(zeta\) without assigning a value to the qubit. It is not a qubit-to-qubit multiplication, but an iteration of the qubit-to-qubit addition up to the value of \(zeta\). Finally, \(Inv\)\(FFM_{2}\) outputs a 32-bit result by multiplying a 32-qubit input with the constant \(f\) (input \(\times\)\(f\)). Exceptionally, in this function, the value of \(f\) is always fixed as a positive number. Consequently, there is no need to judge its sign. One task involves checking the sign of the input (whether the sign of the input is negative or positive). The \(FFM_{1,2}\) functions mean that each function operates in the first NTT cycle and other cycles. In the first NTT cycle (\(C=1\)), the sign of the input and \(zeta\) are known, so the process of determining the sign is not necessary. On the other hand, in \(C\geq 2\), since the sign of the input needs to be confirmed, the 1-qubit \(check\) is used to confirm the sign. Algorithm 1 illustrates the procedure of the \(FFM_{1,2}\) functions within NTT. To preserve the original value of the input, the result of the function is saved in a 32-qubit \(ancilla\). The \(FFM_{1,2}\) functions use CNOT gates to deposit input values into ancilla and then carry out multiplication. Within both \(FFM\) and \(Inv\)\(FFM\), the signs of the input and \(zeta\) are confirmed. If the signs are the same, the result is a positive integer, and if the sign is different, the result is a negative integer.