# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 3 Proposed Method
### FFM and Inv FFM
The outcome of the multiplication between 'input' and '\(zeta\)' is saved in the \(ancilla\) qubit. The \(Inv\)\(FFM_{1,2}\) functions pertain to individual operations within InvNTT. \(Inv\)\(FFM_{1}\) denotes the initial multiplication within a finite field, and \(Inv\)\(FFM_{2}\) represents the subsequent multiplication within that field in InvNTT. Algorithm 2 presents the quantum circuits for \(Inv\)\(FFM_{1}\) and \(Inv\)\(FFM_{2}\), both functioning within InvNTT. The \(Inv\)\(FFM_{1,2}\) functions use CNOT gates to store input values in \(ancilla\) and perform multiplication. Specifically, the \(Inv\)\(FFM_{1}\) function assesses the signs of both the input and zeta. When their signs align, the result is positive, but if they differ, the outcome is negative. The result of (input \(\times\)\(zeta\)) is stored in an ancilla qubit. On the other hand, the \(Inv\)\(FFM_{2}\) function carries out multiplication using the input and a constant \(f\), which is pre-determined as a positive number. Hence, in this case, only the sign of the input is verified. ```
Data:\(zeta\),r(32 bit),check(1-qubit) [\(\#FFM_{1}\) function in NTT(\(C=1\))] fori=0 to\(length(r)\):\(ancilla[i]\leftarrow\)\(\mathrm{CNOT}(r[i]\),\(\mathrm{ancilla}[i])\) ifzeta\(\
eq 1\)then ifzeta\(<0\)and\(input<0\)then fori=0 to\(-zeta+1\):Dagger:\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if ifzeta\(<0\)and\(input>0\)then fori=0 to\(-zeta-1\):\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if ifzeta\(\geq 0\)and\(input>0\)then fori=0 to\(zeta-1\):\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if ifzeta\(\geq 0\)and\(input<0\)then fori=0 to\(zeta+1\):Dagger:\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if end for returnancilla [\(\#FFM_{2}\) function in NTT(\(C\geq 2\))] check\(\leftarrow\)\(\mathrm{CNOT}(r[length(r)\)-1]\),check) ifzeta\(\
eq 1\)then ifzeta\(\geq 0\)then  X(check) ifcheck=1 then fori=0 to\(-zeta+1\):Dagger:\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if X(check) ifcheck=1 then fori=0 to\(-zeta-1\):\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if end if else X(check) ifcheck=1 then fori=0 to\(-zeta-1\):\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if X(check) ifcheck=1 then fori=0 to\(zeta+1\):Dagger:\(ancilla\leftarrow\)ADD(\(r\),\(ancilla\))  end if end for returnancilla
```  
**Algorithm 1**\(FFM_{1,2}\) multiplication for NTT  
```
Data:\(zeta\),r(32 bit)


```
Data:\(\mathit{zeta}\), \(\mathit{r(16 bit)}\), \(\mathit{check}(1\)-qubit) [#\(\mathit{Inv}\)\(\mathit{FFM}_{1}\)functioninInvNTT] check \(\leftarrow\)\(\mathrm{CNOT}(\mathit{r[length(r)-1]}\), check) if\(\mathit{zeta}\
eq 1\)then if\(\mathit{zeta}<0\)then X \(\mid\) check if\(\mathit{check}=1\)then fori=0 to\(-\mathit{zeta}-1\): \(\mathit{ancilla}\leftarrow\mathbf{ADD}(\mathit{r},\mathit{ancilla})\)  end if \(\mathit{check}=1\)then fori=0 to\(-\mathit{zeta}+1\): \(\mathit{\mathbf{Dagger}}\): \(\mathit{ancilla}\leftarrow\mathbf{ADD}(\mathit{r},\mathit{ancilla})\)  end if  end if else X \(\mid\) check if\(\mathit{check}=1\)then fori=0 to\(\mathit{zeta}+1\): \(\mathit{\mathbf{Dagger}}\): \(\mathit{ancilla}\leftarrow\mathbf{ADD}(\mathit{r},\mathit{ancilla})\)  end if \(\mathit{check}=1\)then fori=0 to\(\mathit{zeta}-1\): \(\mathit{ancilla}\leftarrow\mathbf{ADD}(\mathit{r},\mathit{ancilla})\)  end if return\(\mathit{ancilla}\) [#\(\mathit{Inv}\)\(\mathit{FFM}_{2}\)functioninInvNTT] check \(\leftarrow\)\(\mathrm{CNOT}(\mathit{r[length(r)-1]}\), check) if\(\mathit{check}=1\)then fori=0 to\(f-1\): \(\mathit{\mathbf{Dagger}}\): \(\mathit{ancilla}\leftarrow\mathbf{ADD}(\mathit{r},\mathit{ancilla})\)  end if X \(\mid\)check if\(\mathit{check}=1\)then fori=0 to\(f-1\): \(\mathit{ancilla}\leftarrow\mathbf{ADD}(\mathit{r},\mathit{ancilla})\)  end if X \(\mid\)check return\(\mathit{ancilla}\)
```
**Algorithm 2**Inv \(\mathit{FFM}_{1,2}\) multiplication for InvNTT

### Montgomery Reduction

This function performs the Montgomery reduction multiplication on the input \(\times\mathit{zeta}\). For each term, it is calculated on the \(Z_{q}[X]/(X^{n}+1)\) field.