{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T08:26:17Z","timestamp":1769415977671,"version":"3.49.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present the implementation of Grover\u2019s algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions, whose design only uses modular addition, word rotation and bitwise exclusive or. Our implementation provides the means to assess with precision the scaling of the number of gates and depth of a full-fledged quantum circuit designed to find the preimages of a given hash digest. The detailed construction of the quantum oracle shows that the presence of AND gates, OR gates, shifts of bits and the reuse of the initial state along the computation require extra quantum resources as compared with other hash functions based on modular additions, XOR gates and rotations. We also track the entanglement entropy present in the quantum register at every step along the computation, showing that it becomes maximal at the inner core of the first action of the quantum oracle, which implies that no classical simulation based on tensor networks would be of relevance. Finally, we show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover\u2019s algorithm can only provide some marginal practical advantage in terms of error mitigation.<\/jats:p>","DOI":"10.1007\/s11128-021-03118-9","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T06:02:36Z","timestamp":1620626556000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Quantum search for scaled hash function preimages"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9629-9814","authenticated-orcid":false,"given":"Sergi","family":"Ramos-Calderer","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Bellini","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 I.","family":"Latorre","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Manzano","sequence":"additional","affiliation":[]},{"given":"Victor","family":"Mateu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"issue":"5","key":"3118_CR1","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/s11128-018-1864-3","volume":"17","author":"M Almazrooie","year":"2018","unstructured":"Almazrooie, M., Samsudin, A., Abdullah, R., Mutter, K.N.: Quantum reversible circuit of AES-128. Quantum Inf. Process. 17(5), 112 (2018)","journal-title":"Quantum Inf. Process."},{"key":"3118_CR2","unstructured":"Anand, R., Maitra, A., Mukhopadhyay, S.: Grover on SIMON. arXiv preprint arXiv:2004.10686 (2020)"},{"issue":"7779","key":"3118_CR3","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F.G.S.L., Buell, D.A., Burkett, B., Chen, Y., Chen, Z., Chiaro, B., Collins, R., Courtney, W., Dunsworth, A., Farhi, E., Foxen, B., Fowler, A., Gidney, C., Giustina, M., Graff, R., Guerin, K., Habegger, S., Harrigan, M.P., Hartmann, M.J., Ho, A., Hoffmann, M., Huang, T., Humble, T.S., Isakov, S.V., Jeffrey, E., Jiang, Z., Kafri, D., Kechedzhi, K., Kelly, J., Klimov, P.V., Knysh, S., Korotkov, A., Kostritsa, F., Landhuis, D., Lindmark, M., Lucero, E., Lyakh, D., Mandr\u00e0, S., McClean, J.R., McEwen, M., Megrant, A., Mi, X., Michielsen, K., Mohseni, M., Mutus, J., Naaman, O., Neeley, M., Neill, C., Niu, M.Y., Ostby, E., Petukhov, A., Platt, J.C., Quintana, C., Rieffel, E.G., Roushan, P., Rubin, N.C., Sank, D., Satzinger, K.J., Smelyanskiy, V., Sung, K.J., Trevithick, M.D., Vainsencher, A., Villalonga, B., White, T., Yao, Z.J., Yeh, P., Zalcman, A., Neven, H., Martinis, J.M.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505\u2013510 (2019)","journal-title":"Nature"},{"key":"3118_CR4","doi-asserted-by":"crossref","unstructured":"Aumasson, J.P., Meier, W., Phan, R.C.W., Henzen, L.: BLAKE2. In: The Hash Function BLAKE, pp. 165\u2013183. Springer (2014)","DOI":"10.1007\/978-3-662-44757-4_9"},{"key":"3118_CR5","doi-asserted-by":"crossref","unstructured":"Banegas, G., Bernstein, D.J.: Low-communication parallel quantum multi-target preimage search. In: Selected Areas in Cryptography\u2014SAC 2017\u201424th International Conference, LNCS, vol. 10719, pp. 325\u2013335. Springer (2017)","DOI":"10.1007\/978-3-319-72565-9_16"},{"issue":"5","key":"3118_CR6","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A Barenco","year":"1995","unstructured":"Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457 (1995)","journal-title":"Phys. Rev. A"},{"key":"3118_CR7","first-page":"3","volume":"8","author":"DJ Bernstein","year":"2008","unstructured":"Bernstein, D.J.: Chacha, a variant of salsa20. Worksh. Rec. SASC 8, 3\u20135 (2008)","journal-title":"Worksh. Rec. SASC"},{"key":"3118_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Hopwood, D., H\u00fclsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., Wilcox-O\u2019Hearn, Z.: Sphincs: Practical stateless hash-based signatures. In: Advances in Cryptology\u2014EUROCRYPT, Vol. 2015, pp. 368\u2013397 (2015)","DOI":"10.1007\/978-3-662-46800-5_15"},{"key":"3118_CR9","doi-asserted-by":"crossref","unstructured":"Bonnetain, X.: Quantum key-recovery on full AEZ. In: International Conference on Selected Areas in Cryptography, pp. 394\u2013406. Springer (2017)","DOI":"10.1007\/978-3-319-72565-9_20"},{"key":"3118_CR10","doi-asserted-by":"crossref","unstructured":"Bonnetain, X., Hosoyamada, A., Naya-Plasencia, M., Sasaki, Y., Schrottenloher, A.: Quantum attacks without superposition queries: the offline Simon-algorithm. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 552\u2013583. Springer (2019)","DOI":"10.1007\/978-3-030-34578-5_20"},{"key":"3118_CR11","doi-asserted-by":"crossref","unstructured":"Bonnetain, X., Jaques, S.: Quantum period finding against symmetric primitives in practice. arXiv preprint arXiv:2011.07022 (2020)","DOI":"10.46586\/tches.v2022.i1.1-27"},{"key":"3118_CR12","doi-asserted-by":"crossref","unstructured":"Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: On quantum slide attacks. In: International Conference on Selected Areas in Cryptography, pp. 492\u2013519. Springer (2019)","DOI":"10.1007\/978-3-030-38471-5_20"},{"issue":"2","key":"3118_CR13","doi-asserted-by":"publisher","first-page":"55","DOI":"10.46586\/tosc.v2019.i2.55-93","volume":"2019","author":"X Bonnetain","year":"2019","unstructured":"Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: Quantum security analysis of AES. IACR Trans. Symmetr. Cryptol. 2019(2), 55\u201393 (2019)","journal-title":"IACR Trans. Symmetr. Cryptol."},{"issue":"4\u20135","key":"3118_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik Prog. Phys. 46(4\u20135), 493\u2013505 (1998)","journal-title":"Fortschritte der Physik Prog. Phys."},{"key":"3118_CR15","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Tapp, A.: Quantum algorithm for the collision problem. In: Encyclopedia of Algorithms, pp. 1662\u20131664. Springer (2016)","DOI":"10.1007\/978-1-4939-2864-4_304"},{"key":"3118_CR16","doi-asserted-by":"crossref","unstructured":"Chailloux, A., Naya-Plasencia, M., Schrottenloher, A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: Advances in Cryptology - ASIACRYPT 2017\u201423rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3\u20137, 2017, Proceedings, Part II, Lecture Notes in Computer Science, vol. 10625, pp. 211\u2013240. Springer (2017)","DOI":"10.1007\/978-3-319-70697-9_8"},{"key":"3118_CR17","unstructured":"Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv preprint arXiv:quant-ph\/0410184 (2004)"},{"key":"3118_CR18","doi-asserted-by":"crossref","unstructured":"Davenport, J.H., Pring, B.: Improvements to quantum search techniques for block-ciphers, with applications to AES. In: Selected Areas in Cryptography\u2014SAC 2020: 27th International Conference, Lecture Notes in Computer Science. Springer (2020)","DOI":"10.1007\/978-3-030-81652-0_14"},{"key":"3118_CR19","unstructured":"Draper, T.G., Kutin, S.A., Rains, E.M., Svore, K.M.: A logarithmic-depth quantum carry-lookahead adder. arXiv preprint arXiv:quant-ph\/0406142 (2004)"},{"key":"3118_CR20","doi-asserted-by":"publisher","unstructured":"Efthymiou, S., Ramos-Calderer, S., Bravo-Prieto, C., P\u00e9rez-Salinas, A., Garc\u00eda-Mart\u00edn, D., Garcia-Saez, A., Latorre, J.I., Carrazza, S.: Quantum-tii\/qibo: Qibo (2020). https:\/\/doi.org\/10.5281\/zenodo.3997195","DOI":"10.5281\/zenodo.3997195"},{"key":"3118_CR21","doi-asserted-by":"crossref","unstructured":"Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying grover\u2019s algorithm to AES: quantum resource estimates. In: Takagi, T. (Ed.) Post-Quantum Cryptography\u20147th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24\u201326, 2016, Proceedings, Lecture Notes in Computer Science, vol. 9606, pp. 29\u201343. Springer (2016)","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"3118_CR22","doi-asserted-by":"crossref","unstructured":"Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover-algorithm to AES: quantum resource estimates. In: Post-Quantum Cryptography, pp. 29\u201343. Springer (2016)","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"3118_CR23","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"3118_CR24","unstructured":"Guido, B., Joan, D., Micha\u00ebl, P., Gilles, V.: Cryptographic Sponge Functions (2011)"},{"key":"3118_CR25","doi-asserted-by":"crossref","unstructured":"Hosoyamada, A., Sasaki, Y.: Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound. IACR Cryptology ePrint Archive (2020). https:\/\/eprint.iacr.org\/2020\/213","DOI":"10.1007\/978-3-030-45724-2_9"},{"issue":"18","key":"3118_CR26","doi-asserted-by":"publisher","first-page":"6407","DOI":"10.3390\/app10186407","volume":"10","author":"K Jang","year":"2020","unstructured":"Jang, K., Choi, S., Kwon, H., Kim, H., Park, J., Seo, H.: Grover on Korean block ciphers. Appl. Sci. 10(18), 6407 (2020)","journal-title":"Appl. Sci."},{"key":"3118_CR27","unstructured":"Jang, K., Choi, S., Kwon, H., Seo, H.: Grover on SPECK: Quantum Resource Estimates. Cryptology ePrint Archive, Report 2020\/640 (2020). https:\/\/eprint.iacr.org\/2020\/640"},{"key":"3118_CR28","unstructured":"Jang, K., Kim, H., Eum, S., Seo, H.: Grover on GIFT. arXiv preprint arXiv:2020.1405 (2020). https:\/\/eprint.iacr.org\/2020\/1405.pdf"},{"key":"3118_CR29","unstructured":"Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing grover oracles for quantum key search on AES and LowMC. IACR Cryptology ePrint Archive 2019, 1146 (2019). https:\/\/eprint.iacr.org\/2019\/1146"},{"key":"3118_CR30","doi-asserted-by":"crossref","unstructured":"Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing grover oracles for quantum key search on AES and lowmc. In: Advances in Cryptology\u2014EUROCRYPT 2020\u201439th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 12106, pp. 280\u2013310. Springer (2020)","DOI":"10.1007\/978-3-030-45724-2_10"},{"key":"3118_CR31","unstructured":"Kaplan, M.: Quantum attacks against iterated block ciphers. arXiv preprint arXiv:1410.1434 (2014)"},{"key":"3118_CR32","doi-asserted-by":"crossref","unstructured":"Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Annual International Cryptology Conference, pp. 207\u2013237. Springer (2016)","DOI":"10.1007\/978-3-662-53008-5_8"},{"issue":"1","key":"3118_CR33","doi-asserted-by":"publisher","first-page":"71","DOI":"10.46586\/tosc.v2016.i1.71-94","volume":"2016","author":"M Kaplan","year":"2016","unstructured":"Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetr. Cryptol. 2016(1), 71\u201394 (2016)","journal-title":"IACR Trans. Symmetr. Cryptol."},{"issue":"12","key":"3118_CR34","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s11128-018-2107-3","volume":"17","author":"P Kim","year":"2018","unstructured":"Kim, P., Han, D., Jeong, K.C.: Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2. Quantum Inf. Process. 17(12), 339 (2018)","journal-title":"Quantum Inf. Process."},{"key":"3118_CR35","doi-asserted-by":"crossref","unstructured":"Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory, pp. 2682\u20132685. IEEE (2010)","DOI":"10.1109\/ISIT.2010.5513654"},{"key":"3118_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2020.2965697","volume":"1","author":"B Langenberg","year":"2020","unstructured":"Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Trans. Quantum Eng. 1, 1\u201312 (2020)","journal-title":"IEEE Trans. Quantum Eng."},{"key":"3118_CR37","doi-asserted-by":"crossref","unstructured":"Leander, G., May, A.: Grover meets Simon-quantumly attacking the FX-construction. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 161\u2013178. Springer (2017)","DOI":"10.1007\/978-3-319-70697-9_6"},{"issue":"2","key":"3118_CR38","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1080\/0161-110391891838","volume":"27","author":"MA Musa","year":"2003","unstructured":"Musa, M.A., Schaefer, E.F., Wedig, S.: A simplified AES algorithm and its linear and differential cryptanalyses. Cryptologia 27(2), 148\u2013177 (2003)","journal-title":"Cryptologia"},{"key":"3118_CR39","unstructured":"NIST: Post-quantum cryptography standardization process (2016). https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/call-for-proposals-final-dec-2016.pdf"},{"issue":"5","key":"3118_CR40","doi-asserted-by":"publisher","first-page":"052308","DOI":"10.1103\/PhysRevA.69.052308","volume":"69","author":"R Or\u00fas","year":"2004","unstructured":"Or\u00fas, R., Latorre, J.I.: Universality of entanglement and quantum-computation complexity. Phys. Rev. A 69(5), 052308 (2004)","journal-title":"Phys. Rev. A"},{"key":"3118_CR41","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018)","journal-title":"Quantum"},{"key":"3118_CR42","doi-asserted-by":"publisher","unstructured":"Ramos, S., Carrazza, S.: Quantum-TII\/quantum-search-scaled-hash-preimages: Quantum Search for Scaled Hash Function Preimages\u2014Qibo (2020). https:\/\/doi.org\/10.5281\/zenodo.4007914","DOI":"10.5281\/zenodo.4007914"},{"key":"3118_CR43","unstructured":"Saarinen, M.J.O., Aumasson, J.P.: RFC 7693: The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC) (2015). https:\/\/tools.ietf.org\/html\/rfc7693#appendix-C"},{"key":"3118_CR44","unstructured":"Schlieper, L.: In-place implementation of Quantum-Gimli. arXiv preprint arXiv:2007.06319 (2020)"},{"issue":"5","key":"3118_CR45","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"3118_CR46","doi-asserted-by":"crossref","unstructured":"van Oorschot, P.C., Wiener, M.J.: Parallel collision search with application to hash functions and discrete logarithms. In: Proceedings of the 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 2\u20134, 1994, pp. 210\u2013218. ACM (1994)","DOI":"10.1145\/191177.191231"},{"issue":"1","key":"3118_CR47","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1103\/PhysRevA.54.147","volume":"54","author":"V Vedral","year":"1996","unstructured":"Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54(1), 147 (1996)","journal-title":"Phys. Rev. A"},{"key":"3118_CR48","doi-asserted-by":"publisher","first-page":"147902","DOI":"10.1103\/PhysRevLett.91.147902","volume":"91","author":"G Vidal","year":"2003","unstructured":"Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91, 147902 (2003)","journal-title":"Phys. Rev. Lett."}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03118-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03118-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03118-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T20:55:06Z","timestamp":1672088106000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03118-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["3118"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03118-9","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5]]},"assertion":[{"value":"26 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Data are generated using the code in [].","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Data availability"}},{"value":"The code for this project is available in the GitHub repository found in [].","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}],"article-number":"180"}}