A Parallel Quantum Circuit Implementations of LSH Hash Function for Use with Grover’s Algorithm
Source abstract
Abstract
Grover’s search algorithm accelerates the key search on the symmetric key cipher and the pre-image attack on the hash function. To conduct Grover’s search algorithm, the target cipher algorithm should be efficiently implemented in a quantum circuit. Currently, small quantum computers are difficult to operate with large quantum circuits due to limited performance. Therefore, if a large quantum computer that can operate Grover’s algorithm appears, it is expected that a cipher attack will be possible. In this paper, we propose a parallel structure quantum circuit for the Korean hash function standard (i.e., LSH). The proposed quantum circuit designed a parallel operation structure for the message expansion (i.e., MsgExp) function and the mix function, which are the internal structures of the LSH hash function. This approach shows an efficient result for quantum circuit implementation in terms of quantum resources by reducing the depth of the quantum circuit by about 96% through the trade-off of appropriate quantum resources compared to previous work. This result can be a reference for the implementation of a parallel quantum circuit in the future and is expected to advance the attack timing of the search algorithm for Grover’s LSH hash function.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Quantum Computing Algorithms and Architecture · Quantum Information and Cryptography · Quantum-Dot Cellular Automata
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Division of IT Convergence Engineering, Hansung University, Seoul 02876, Korea
Funding
Hansung University
References (27)
Show source-provided references
1. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer10.1137/S0097539795293172 ↗
2. Grover, L.K. (1996, January 22–24). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA.10.1145/237814.237866 ↗
3. Grassl, M., Langenberg, B., Roetteler, M., and Steinwandt, R. (2016). Applying Grover’s algorithm to AES: Quantum resource estimates. Proceedings of the Post-Quantum Cryptography, Springer.10.1007/978-3-319-29360-8_3 ↗
4. Langenberg, B., Pham, H., and Steinwandt, R. (2019). Reducing the Cost of Implementing AES as a Quantum Circuit, Available online: https://eprint.iacr.org/2019/854.
5. Jaques, S., Naehrig, M., Roetteler, M., and Virdia, F. (2020, January 10–14). Implementing Grover oracles for quantum key search on AES and LowMC. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia.10.1007/978-3-030-45724-2_10 ↗
6. Grover on SIMON10.1007/s11128-020-02844-w ↗
7. Jang, K., Choi, S., Kwon, H., and Seo, H. (2020). Grover on SPECK: Quantum Resource Estimates, Available online: https://eprint.iacr.org/2020/640.
8. Jang, K., Kim, H., Eum, S., and Seo, H. (2020). Grover on GIFT, Available online: https://eprint.iacr.org/2020/1405.
9. Schlieper, L. (2020). In-place implementation of Quantum-Gimli. arXiv.
10. Jang, K., Choi, S., Kwon, H., Kim, H., Park, J., and Seo, H. (2020). Grover on Korean Block Ciphers. Appl. Sci., 10.10.3390/app10186407 ↗
11. Jang, K., Song, G., Kim, H., Kwon, H., Kim, H., and Seo, H. (2021). Efficient Implementation of PRESENT and GIFT on Quantum Computers. Appl. Sci., 11.10.3390/app11114776 ↗
12. Grover on Caesar and Vigenère Ciphers
13. Jang, K., Song, G., Kwon, H., Uhm, S., Kim, H., Lee, W.K., and Seo, H. (2021). Grover on PIPO. Electronics, 10.10.3390/electronics10101194 ↗
14. Jang, K., Baksi, A., Song, G., Kim, H., Seo, H., and Chattopadhyay, A. (2022). Quantum Analysis of AES, Available online: https://eprint.iacr.org/2022/683.
15. Quantum implementation and resource estimates for rectangle and knot10.1007/s11128-021-03307-6 ↗
16. Song, G., Jang, K., Kim, H., Eum, S., Sim, M., Kim, H., Lee, W., and Seo, H. (2022). SPEEDY Quantum Circuit for Grover’s Algorithm. Appl. Sci., 12.10.3390/app12146870 ↗
17. Huang, Z., and Sun, S. (2022). Synthesizing Quantum Circuits of AES with Lower T-depth and Less Qubits, Available online: https://eprint.iacr.org/2022/620.10.1007/978-3-031-22969-5_21 ↗
18. Amy, M., Matteo, O.D., Gheorghiu, V., Mosca, M., Parent, A., and Schanck, J. (2022, September 18). Estimating the Cost of Generic Quantum Pre-Image Attacks on SHA-2 and SHA-3, Available online: http://xxx.lanl.gov/abs/1603.09383.
19. Resource Eestimation of Grover Algorithm through Hash Function LSH Quantum Circuit Optimization
20. Demonstration of a small programmable quantum computer with atomic qubits10.1038/nature18648 ↗
21. Extending the lifetime of a quantum bit with error correction in superconducting circuits10.1038/nature18949 ↗
22. Architecture for a large-scale ion-trap quantum computer10.1038/nature00784 ↗
23. Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv.
24. Farhi, E., Goldstone, J., Gutmann, S., and Neven, H. (2017). Quantum algorithms for fixed qubit architectures. arXiv.
25. Superconducting quantum circuits at the surface code threshold for fault tolerance10.1038/nature13171 ↗
26. Kim, D.C., Hong, D., Lee, J.K., Kim, W.H., and Kwon, D. (2014, January 17–19). LSH: A new fast secure hash function family. Proceedings of the International Conference on Information Security and Cryptology, Latin America Florianópolis, Brazil.10.1007/978-3-319-15943-0_18 ↗
27. Cuccaro, S.A., Draper, T.G., Kutin, S.A., and Moulton, D.P. (2004). A new quantum ripple-carry addition circuit. arXiv.