# NTT and Inverse NTT Quantum Circuits in CRYSTALS-Kyber for Post-Quantum Security Evaluation
## 1 Introduction  
The emergence of high-capacity quantum computers is anticipated to present a substantial threat to the existing cryptosystem. Public key cryptography maintains security based on the difficulty of factoring large integers. However, [PERSON]'s algorithm, a quantum algorithm, is known to pose a threat to public key cryptography (e.g., Rivest-Shamir-Adleman (RSA) and elliptic curve cryptography (ECC)) because it is possible to factor large integers within polynomial time [1]. The security level of symmetric key cryptography is contingent upon the length of the employed encryption key. [PERSON]'s algorithm can accelerate the attack by performing a brute force attack with \(\sqrt{2^{n}}\) queries against symmetric key cryptography using \(n\)-bit keys. In essence, this results in a reduction of security potency from \(2^{n}\) to \(2^{\frac{n}{2}}\) when executed on quantum computers. A potential safeguard against quantum computer attacks involves doubling the length of the encryption key. Nonetheless, due to the disparity in operational methodologies, resource requisites, and feasible computations between classical and quantum computers, the level of security achieved on a classical computing system does not align seamlessly with the quantum security potency achievable on a quantum computer. Hence, to confirm the quantum security of cryptography on quantum computers, it is imperative to optimize and implement the cryptographic operations within quantum circuits. Also, based on the implemented quantum circuit, it is necessary to confirm the required quantum gate and the depth of the quantum circuit. In recent years, research has focused on ascertaining the quantum resistance of cryptography through implementing quantum circuits for symmetric cryptography and hash functions [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21]. Uponthe alignment of available quantum computer resources with the requisites for executing a cryptographic attack, it is anticipated that the targeted cipher will be broken. Consequently, prevailing cryptographic systems are expected to be supplanted by algorithms in the realm of post-quantum cryptography (PQC). It is judged that the PQC algorithm can have quantum resistance because it is difficult to operate on a quantum computer, but discussions on this are ongoing. The National Institute of Standards and Technology (NIST) held a competition to select the standard post-quantum cryptography (PQC) algorithm. The PQC algorithm is intended to replace the current cryptosystems in the post-quantum era [22]. In the one round conducted in 2017, 69 candidate algorithms were released. In 2019, 26 out of 69 algorithms advanced to round 2 (17: encryption/key-encapsulation (PKE/KEM), 9: signature schemes). In round 3, 15 candidate algorithms were released (7 finalists, 8 alternatives). In 2022, four finalists were announced. Candidate algorithms included CRYSTALS-Kyber (KEMs/Encryption), CRYSTALS-Dilithium, Falcon, and SPHINCS+ (Signature). In this paper, we propose a quantum circuit for the number theoretic transform (NTT) and inverse number theoretic transform (InvNTT) used in CRYSTALS-Kyber. The implementation of encryption through quantum circuits is undertaken to leverage the distinctive properties of quantum computers. This approach involves investigating methods of attacking conventional cryptographic systems using quantum computational capabilities, thereby assessing the strength of quantum security. To ascertain the potency of quantum security, it is imperative to implement quantum algorithms on quantum computers and estimate the quantum resources. These efforts anticipate the commercialization of quantum computers, facilitating the development of robust security technologies and algorithms to effectively respond to quantum threats. The Montgomery reduction is used in NTT, and the Montgomery reduction and Barrett reduction are used in InvNTT. The inner function used in the InvNTT operation is similar to NTT but also uses the Barrett reduction.