# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 3 Proposed Method
### FFM and Inv FFM
These efforts are anticipated to contribute to the establishment of benchmarks for efficient NTT/InvNTT quantum circuits. Therefore, this needs to be pursued in future research. According to IBM's quantum computer development roadmap, they plan to have over 1000 qubits by 2023. After 2024, the goal is to reach between 1000 and 1 million qubits. As a result, it is expected that large-scale quantum computers will appear in the future. Given this, it is expected that in the future we can evaluate the post-quantum security of CRYSTAL-Kyber using the large-scale quantum circuit. ## 5 Conclusions

In this paper, we propose a quantum circuit for NTT/InvNTT that is used to speed up polynomial multiplication in CRYSTALS-Kyber. The proposed quantum circuits are implemented as part of an optimization method to reduce quantum resources. The NTT/InvNTT quantum circuits elucidate the operation by showcasing pseudo-codes for the sub-functions. Finally, we estimate quantum resources based on the proposed quantum circuits and analyze them. As a result of the estimation of quantum resources, NTT has the largest depth in the Montgomery reduction function and uses the most quantum resources. In InvNTT, the Barrett reduction function has the largest depth, the most quantum resources are used, and the Montgomery reduction function uses the most qubits. In the event of the eventual development of large-scale quantum computers, it is foreseeable that the NTT operations could be executed through the utilization of the proposed quantum circuit. To the best of our knowledge, these are the first NTT/InvNTT quantum circuits to operate on the CRYSTALS-Kyber cryptographic algorithm. We anticipate that this will serve as a pivotal tool in assessing the post-quantum security robustness of CRYSTALS-Kyber. Software, G.S. ; Investigation, S.E. ; Writing--original draft, G.S. ; Writing--review & editing, K.J. and M.S. ; Supervision, H.S. All authors have read and agreed to the published version of the manuscript. This work was partly supported by Institute for Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (<Q| Crypton>, Number 2019-0-00033, Study on Quantum Security Evaluation of Cryptography based on Computational Quantum Complexity, 40%) and this work was partly supported by Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIT) (Number 2018-0-00264, Research on Blockchain Security Technology for IoT Services, 50%) and This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (Number NRF-2020R1F1A1084878, 10%). The authors declare no conflict of interest. ## References

* (1) [PERSON] Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. _SIAM Rev._**1999**, _41_, 303-332. [CrossRef]
* (2) [PERSON]; [PERSON]; [PERSON] A quantum circuit design of AES requiring fewer quantum qubits and gate operations. _Front. Phys._**2022**, _17_, 41501. [CrossRef]
* (3) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Quantum circuit implementations of AES with fewer qubits. In Proceedings of the Advances in Cryptology-ASIACRYPT 2020: 26 th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, Republic of Korea, 7-11 December 2020; Proceedings, Part II 26; Springer: Berlin/Heidelberg, Germany, 2020; pp. 697-726. * (4) [PERSON]; [PERSON]; [PERSON]; [PERSON] Implementing Grover oracles for quantum key search on AES and LowMC. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 10-14 May 2020; Springer: Berlin/Heidelberg, Germany, 2020; pp. 280-310. * (5) [PERSON]; [PERSON]; [PERSON] Improved Low-Depth SHA3 Quantum Circuit for Fault-Tolerant Quantum Computers. _Appl. Sci._**2023**, _13_, 3558. [CrossRef]
* (6) [PERSON]; [PERSON]; [PERSON] Evaluation of [PERSON]'s algorithm toward quantum cryptanalysis on ChaCha.