# Quantum Implementation of AIM: Aiming for Low-Depth
## 1 Introduction  
Quantum computing is generating interest and speculation among experts, even within the field of cryptography [1, 2]. Recent advances in quantum computing emphasize the continued progress of physical solid-state qubits [3, 4], including spin, charge, and superconductor bits, shaping the quantum information processing landscape.  
Quantum computing poses a serious threat to cryptography, particularly to public key algorithms, which can be weakened by [PERSON]'s algorithm [5], reducing the attack complexity to a polynomial time. As a result, researchers have been studying the applicability of public key ciphers against a quantum adversary [6, 7, 8]. Generally speaking, symmetric key ciphers are more robust against quantum attacks than public key ciphers, with [PERSON]'s algorithm capable of recovering a \(k\)-bit key with \(\sqrt{2^{k}}\) searches (i.e., reduced by the square root). That means symmetric key ciphers should double their key size to achieve a reasonable level of security claim even on quantum computers. It is worth noting that quantum security is not properly analyzed during the design phase of symmetric key ciphers.  
Although [PERSON]'s algorithm [9] theoretically reduces the security of key search by the square root, practical quantum key recovery is still very difficult due to the extreme iterations required. Moreover, the current level of quantum computer development cannot handle the depth of extreme iterations. Thus, it is meaningful to implement and analyze newly proposed symmetric key ciphers with respect to adversaries that have quantum computing capabilities.  
If the quantum resources required to attack a symmetric key cipher are extensive, the cipher can be considered safe from quantum attacks without increasing the key size. In this context, it is important to note the post-quantum security requirements of the National Institute of Standards and Technology (NIST) [10, 11]. NIST has defined post-quantum security levels (Level-1\(\sim\)-5) to assess the resistance of ciphers against quantum attacks (this will be described in Section 2.2).  
In this work, we perform quantum cryptanalysis on the symmetric key primitive AIM used in the new signature, AIMer [12]. AIMer is one of the digital signatures (AIMer is the only symmetric key primitive (AIM) based digital signature in the KPQC competition) of Korea Post-Quantum Cryptography (KPQC) competition ([[https://www.kpqc.or.kr/competition.html](https://www.kpqc.or.kr/competition.html)]([https://www.kpqc.or.kr/competition.html](https://www.kpqc.or.kr/competition.html)), accessed on 24 March 2024). Additionally, AIMer is a candidate for additional post-quantum digital signature standardization by NIST ([[https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures](https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures)]([https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures](https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures)), accessed on 24 March 2024). We present quantum circuits for AIM, and our design philosophy prioritizes minimizing depth rather than qubit count. This choice is driven by the necessity of parallelizing [PERSON]'s search instances, which is often an inevitable option due to the substantial depth of [PERSON]'s search (discussed in Section 2.3). Based on the depth-optimized quantum circuits of AIM, we estimate the cost of [PERSON]'s key search and assess the post-quantum security level of AIM according to NIST's evaluation criteria.  
To the best of our knowledge, this work is the first attempt to analyze the post-quantum security of AIM on quantum computers. While the compromise of the inner key primitive (i.e., AIM) may not directly invalidate the security claims of the algorithm (i.e., AIMer), it can introduce vulnerabilities that should not be overlooked. From this perspective, our work holds significant importance within the context of security analysis.