nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

On Finding Quantum Multi-collisions

verfasst von : Qipeng Liu, Mark Zhandry

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, \(\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) \) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel An Algebraic Approach to Maliciously Secure Private Set Intersection

Nächstes Kapitel On Quantum Advantage in Information Theoretic Single-Server PIR

Here, the Big Theta notation hides a constant that depends on k.

At least, the authors found it surprising!.

[Amb04]

Ambainis, A.: Quantum walk algorithm for element distinctness. In: 45th FOCS, pp. 22–31. IEEE Computer Society Press, October 2004

[AS04]

Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595–605 (2004)MathSciNetCrossRef

[BBBV97]

Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)MathSciNetCrossRef

[BBHT98]

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik: Progress Phys. 46(4–5), 493–505 (1998)CrossRef

[BDF+11]

Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3CrossRefMATH

[BDRV18]

Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: Multi-collision resistant hash functions and their applications. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 133–161. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_5CrossRef

[Bel12]

Belovs, A.: Learning-graph-based quantum algorithm for k-distinctness. In: 53rd FOCS, pp. 207–216. IEEE Computer Society Press, October 2012

[BES17]

Balogh, M., Eaton, E., Song, F.: Quantum collision-finding in non-uniform random functions. Cryptology ePrint Archive, Report 2017/688 (2017). http://eprint.iacr.org/2017/688

[BHT98]

Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 163–169. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054319CrossRef

[BKP18]

Bitansky, N., Kalai, Y.T., Paneth, O.: Multi-collision resistance: a paradigm for keyless hash functions. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th ACM STOC, pp. 671–684. ACM Press, June 2018

[BKT18]

Bun, M., Kothari, R., Thaler, J.: The polynomial method strikes back: tight quantum query bounds via dual polynomials. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th ACM STOC, pp. 297–310. ACM Press, June 2018

[BS13]

Belovs, A., Spalek, R.: Adversary lower bound for the k-sum problem. In: Kleinberg, R.D. (ed.) ITCS 2013, pp. 323–328. ACM, January 2013

[BZ13]

Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 592–608. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_35CrossRef

[CN08]

Chang, D., Nandi, M.: Improved indifferentiability security analysis of chopMD hash function. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 429–443. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_27CrossRef

[DDKS14]

Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Cryptanalysis of iterated Even-Mansour schemes with two keys. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 439–457. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_23CrossRef

[EU17]

Ebrahimi, E., Unruh, D.: Quantum collision-resistance of non-uniformly distributed functions: upper and lower bounds. Cryptology ePrint Archive, Report 2017/575 (2017). http://eprint.iacr.org/2017/575

[Gro96]

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC, pp. 212–219. ACM Press, May 1996

[HIK+11]

Hirose, S., Ideguchi, K., Kuwakado, H., Owada, T., Preneel, B., Yoshida, H.: A lightweight 256-bit hash function for hardware and low-end devices: Lesamnta-LW. In: Rhee, K.-H., Nyang, D.H. (eds.) ICISC 2010. LNCS, vol. 6829, pp. 151–168. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24209-0_10CrossRefMATH

[HSTX18]

Hosoyamada, A., Sasaki, Y., Tani, S., Xagawa, K.: Improved quantum multicollision-finding algorithm. Cryptology ePrint Archive, Report 2018/1122 (2018). https://eprint.iacr.org/2018/1122

[HSX17]

Hosoyamada, A., Sasaki, Y., Xagawa, K.: Quantum multicollision-finding algorithm. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 179–210. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_7CrossRef

[JJV02]

Jaulmes, É., Joux, A., Valette, F.: On the security of randomized CBC-MAC beyond the birthday paradox limit a new construction. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 237–251. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45661-9_19CrossRef

[JLM14]

Jovanovic, P., Luykx, A., Mennink, B.: Beyond \(2^{c/2}\) security in sponge-based authenticated encryption modes. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 85–104. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_5CrossRefMATH

[KMRT09]

Knudsen, L.R., Mendel, F., Rechberger, C., Thomsen, S.S.: Cryptanalysis of MDC-2. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 106–120. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_6CrossRef

[KNY18]

Komargodski, I., Naor, M., Yogev, E.: Collision resistant hashing for paranoids: dealing with multiple collisions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 162–194. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_6CrossRef

[NO14]

Naito, Y., Ohta, K.: Improved indifferentiable security analysis of PHOTON. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 340–357. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10879-7_20CrossRefMATH

[NSWY13]

Naito, Y., Sasaki, Y., Wang, L., Yasuda, K.: Generic state-recovery and forgery attacks on ChopMD-MAC and on NMAC/HMAC. In: Sakiyama, K., Terada, M. (eds.) IWSEC 2013. LNCS, vol. 8231, pp. 83–98. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41383-4_6CrossRefMATH

[NWW14]

Nikolić, I., Wang, L., Wu, S.: Cryptanalysis of round-reduced LED. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 112–129. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43933-3_7CrossRef

[RS97]

Rivest, R.L., Shamir, A.: PayWord and MicroMint: two simple micropayment schemes. In: Lomas, M. (ed.) Security Protocols 1996. LNCS, vol. 1189, pp. 69–87. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62494-5_6CrossRef

[TU16]

Targhi, E.E., Unruh, D.: Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 192–216. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_8CrossRefMATH

[van98]

van Dam, W.: Quantum oracle interrogation: getting all information for almost half the price. In: 39th FOCS, pp. 362–367. IEEE Computer Society Press, November 1998

[Zha12]

Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 758–775. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_44CrossRefMATH

[Zha15a]

Zhandry, M.: A note on the quantum collision and set equality problems. Quantum Inf. Comput. 15(7&8) (2015)

[Zha15b]

Zhandry, M.: Quantum oracle classification-the case of group structure. arXiv preprint arXiv:1510.08352 (2015)

[Zha18]

Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. Cryptology ePrint Archive, Report 2018/276 (2018). https://eprint.iacr.org/2018/276

Titel: On Finding Quantum Multi-collisions
verfasst von: Qipeng Liu
Mark Zhandry
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17658-7

Electronic ISBN: 978-3-030-17659-4

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17659-4_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner