# A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with [PERSON]'s Algorithm
## 3 Proposed Method
### Parallel Quantum Circuit for LSH
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Algorithm** & **Qubits** & **Toffoli Gates** & **CNOT Gates** & **X Gates** & **Depth** \\ \hline LSH-256-224 & 1552 & 62,464 & 170,752 & 59,392 & 6879 \\ \hline LSH-256-256 & 1552 & 62,464 & 170,752 & 59,392 & 6879 \\ \hline LSH-512-224 & 3088 & 138,000 & 375,760 & 134,688 & 14,517 \\ \hline LSH-512-256 & 3088 & 138,000 & 375,760 & 134,688 & 14,517 \\ \hline LSH-512-384 & 3088 & 138,000 & 375,760 & 134,688 & 14,517 \\ \hline LSH-512-512 & 3088 & 138,000 & 375,760 & 134,688 & 14,517 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Quantum resource estimation results for our LSH parallel quantum circuit. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Algorithm** & **Qubits** & **Toffoli Gates** & **CNOT Gates** & **X Gates** & **Depth** \\ \hline LSH-256-224 & 1537 & 63,488 & 145,152 & 1536 & 210,051 \\ \hline LSH-256-256 & 1537 & 63,488 & 145,152 & 3492 & 210,049 \\ \hline LSH-512-224 & 3073 & 139,104 & 312,832 & 7663 & 421,851 \\ \hline LSH-512-256 & 3073 & 139,104 & 312,832 & 7668 & 421,851 \\ \hline LSH-512-384 & 3073 & 139,104 & 312,832 & 7668 & 421,850 \\ \hline LSH-512-512 & 3073 & 139,104 & 312,832 & 7680 & 421,852 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Quantum resource estimation results for the sequential LSH quantum circuit proposed in [19]. ## 5 Conclusions

In this paper, we proposed a parallel LSH quantum circuit that improved the previous sequential LSH quantum circuit [19]. We compare the results of the quantum resource estimation for the parallel quantum circuit of LSH with previous work and show the result of reducing the depth of the quantum circuit by about 96% through an efficient trade-off of quantum resources. Quantum resources required for a quantum preimage attack using [PERSON]'s search algorithm are determined according to the quantum circuit of the target hash function. Therefore, the results of this paper are expected to advance the timing of [PERSON]'s search algorithm attack on the LSH hash function in the future. Investigation, H.K. ; Software, G.S. and K.J. ; Supervision, H.S. ; Writing--original draft, G.S. All authors have read and agreed to the published version of the manuscript. This research was financially supported by Hansung University. The authors declare no conflict of interest. ## References

* [1] [PERSON] Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. _SIAM J. Comput._**1997**, _26_, 1484-1509. [CrossRef]
* [2] [PERSON] A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA, 22-24 May 1996; pp. 212-219. * [3] [PERSON]; [PERSON]; [PERSON]; [PERSON] Applying [PERSON]'s algorithm to AES: quantum resource estimates. In _Proceedings of the Post-Quantum Cryptography_; Springer: Berlin/Heidelberg, Germany, 2016; pp. 29-43. * [4] [PERSON]; [PERSON]; [PERSON] _Reducing the Cost of Implementing AES as a Quantum Circuit_; Technical Report; Cryptology ePrint Archive, Report 2019/854; 2019. Available online: [[https://eprint.iacr.org/2019/854](https://eprint.iacr.org/2019/854)]([https://eprint.iacr.org/2019/854](https://eprint.iacr.org/2019/854)) (accessed on 18 September 2022). * [5] [PERSON]; [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; pp. 280-310. * [6] [PERSON]; [PERSON]; [PERSON] on SIMON. _Quantum Inf. Process._**2020**, _19_, 1-17. [CrossRef]
* [7] [PERSON]; [PERSON]; [PERSON]; [PERSON] _[PERSON] on SPECK: Quantum Resource Estimates_; Cryptology ePrint Archive, Report 2020/640; 2020. Available online: [[https://eprint.iacr.org/2020/640](https://eprint.iacr.org/2020/640)]([https://eprint.iacr.org/2020/640](https://eprint.iacr.org/2020/640)) (accessed on 18 September 2022).