# A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with [PERSON]'s Algorithm
## 1 Introduction  
Quantum computers can solve specific problems much faster than classic computers. [PERSON]'s algorithm [1] and [PERSON]'s algorithm [2], known as quantum algorithms, can threaten the current cryptosystem. [PERSON]'s algorithm poses a threat to the security of Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC), which are public-key cryptography. The integer factorization and discrete logarithm problems used in the safety of RSA and ECC are difficult problems on classical computers. However, using [PERSON]'s algorithm, this problem can be solved in polynomial time. [PERSON]'s algorithm accelerates the speed of finding specific data in unsorted data. Thus, [PERSON]'s algorithm poses a threat by accelerating brute-force attacks to find the key to symmetric cryptography. If \(O(n)\) queries have to be performed for a brute-force attack in a classic computer, a quantum computer can be performed in \(O(\sqrt{n})\) queries. To prevent such quantum algorithm attacks, the Institute of Standards and Technology (NIST) is working on standardization of post-quantum cryptography. Recently, research has been conducted actively to optimize symmetric key cryptography [3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17] and hash functions [18; 19] as quantum circuits.  
Current quantum computers are difficult to operate due to performance limitations such as the number of available qubits and errors. The depth of a quantum circuit is connected to the time step (i.e., time complexity) required for quantum operations executed in quantum hardware [20; 21; 22; 23; 24; 25]. Therefore, much research has proposed the implementation of a quantum circuit that reduces the number and error (i.e., depth) of qubits in the implementation of the quantum circuit.  
With this research motivation, we propose a parallel-structured quantum circuit for the LSH [26] hash function, a Korean national standard hash function designed in Korea. We implemented a parallel structure using the parallel adexpansion function(MsgExp) and the mix function, which are internal functions of the LSH hash function. The proposed parallel quantum circuit is designed to reduce circuit depth through efficient trade-offs between quantum resources. We improved the sequential LSH quantum circuit in previous work [19], greatly reducing the depth of the quantum circuit. The sequential LSH quantum circuit of the previous work showed about 210,000 depth based on LSH-256-\(n\) (i.e., \(n=224\) or 256) and about 420,000 depth based on LSH-512-\(m\) (i.e., \(m=224\), 256, 384, or 512). On the other hand, the depth of the proposed parallel quantum circuit is 6879 based on LSH-256-\(n\). The proposed work reduced the depth by about 96.73% compared to the previous work. As a result of resource estimation, the CNOT and X gates increased, but the Toffoli gates, which are more expensive than the CNOT and X gates, decreased. Therefore, we argue that this is an efficient trade-off. The structure of this paper is as follows: Section 2, background knowledge about LSH hash function, quantum computing, and [PERSON]'s algorithm is explained. Section 3 describes the proposed LSH quantum circuit, and Section 4 evaluates the quantum resources estimation result.