Top

Published in:

2019 | OriginalPaper | Chapter

Quantum Indistinguishability of Random Sponges

Authors : Jan Czajkowski, Andreas Hülsing, Christian Schaffner

Published in: Advances in Cryptology – CRYPTO 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this work we show that the sponge construction can be used to construct quantum-secure pseudorandom functions. As our main result we prove that random sponges are quantum indistinguishable from random functions. In this setting the adversary is given superposition access to the input-output behavior of the construction but not to the internal function. Our proofs hold under the assumption that the internal function is a random function or permutation. We then use this result to obtain a quantum-security version of a result by Andreeva, Daemen, Mennink, and Van Assche (FSE’15) which shows that a sponge that uses a secure PRP or PRF as internal function is a secure PRF. This result also proves that the recent attacks against CBC-MAC in the quantum-access model by Kaplan, Leurent, Leverrier, and Naya-Plasencia (Crypto’16) and Santoli, and Schaffner (QIC’16) can be prevented by introducing a state with a non-trivial inner part.

The proof of our main result is derived by analyzing the joint distribution of any q input-output pairs. Our method analyzes the statistical behavior of the considered construction in great detail. The used techniques might prove useful in future analysis of different cryptographic primitives considering quantum adversaries. Using Zhandry’s PRF/PRP switching lemma we then obtain that quantum indistinguishability also holds if the internal block function is a random permutation.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Quantum Security Proofs Using Semi-classical Oracles

next chapter Revisiting Post-quantum Fiat-Shamir

See slide 16 (page 26) of their Crypto 2016 presentation available at https://who.rocq.inria.fr/Gaetan.Leurent/files/Simon_CR16_slides.pdf.

Andreeva, E., Daemen, J., Mennink, B., Van Assche, G.: Security of keyed sponge constructions using a modular proof approach. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 364–384. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_18CrossRef

Bertoni, G., Daemen, J., Peeters, M., van Assche, G.: Sponge functions. In: Ecrypt Hash Workshop, May 2007. http://sponge.noekeon.org/SpongeFunctions.pdf

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_11CrossRef

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the security of the keyed sponge construction. In: Symmetric Key Encryption Workshop, vol. 2011 (2011)

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge-based pseudo-random number generators. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 33–47. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15031-9_3CrossRef

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: single-pass authenticated encryption and other applications. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 320–337. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_19CrossRef

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Permutation-based encryption, authentication and authenticated encryption. In: Directions in Authenticated Ciphers (2012)

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

Carstens, T.V., Ebrahimi, E., Tabia, G.N., Unruh, D.: On quantum indifferentiability. Technical report Cryptology ePrint Archive, Report 2018/257 (2018). https://eprint.iacr.org/2018/257

10.

Chang, D.H., Dworkin, M.J., Hong, S., Kelsey, J.M., Nandi, M.: A keyed sponge construction with pseudorandomness in the standard model. In: The Third SHA-3 Candidate Conference, NIST (2012)

11.

Czajkowski, J., Groot Bruinderink, L., Hülsing, A., Schaffner, C., Unruh, D.: Post-quantum security of the sponge construction. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 185–204. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_9CrossRefMATH

12.

Czajkowski, J., Hülsing, A., Schaffner, C.: Quantum in-distinguishability of random sponges. Cryptology ePrint Archive, Report 2019/069 (2019). https://eprint.iacr.org/2019/069

13.

Gaži, P., Pietrzak, K., Tessaro, S.: The exact PRF security of truncation: tight bounds for keyed sponges and truncated CBC. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 368–387. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_18CrossRef

14.

Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 207–237. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_8CrossRef

15.

Kölbl, S., Lauridsen, M.M., Mendel, F., Rechberger, C.: Haraka v2 – efficient short-input hashing for post-quantum applications. IACR Trans. Symmetric Cryptol. 2016(2), 1–29 (2017). https://doi.org/10.13154/tosc.v2016.i2.1-29CrossRef

16.

Kuwakado, H., Morii, M.: Security on the quantumtype even-mansour cipher. In: 2012 International Symposium on Information Theory and its Applications (ISITA), pp. 312–316. IEEE (2012)

17.

Mennink, B., Reyhanitabar, R., Vizár, D.: Security of full-state keyed sponge and duplex: applications to authenticated encryption. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 465–489. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_19CrossRef

18.

Mennink, B., Szepieniec, A.: XOR of PRPs in a quantum world. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 367–383. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_21CrossRefMATH

19.

Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge University Press, Cambridge (2010). 10th anniversary

20.

Rivest, R.L., Schuldt, J.C.N.: Spritz-a spongy RC4-like stream cipher and hash function (2014). Charles River Crypto Day, 24 October 2014

21.

Santoli, T., Schaffner, C.: Using Simon’s algorithm to attack symmetric-key cryptographic primitives. In: arXiv preprint arXiv:1603.07856 (2016)

22.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 1994 Proceedings of 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE (1994)

23.

Sphincs+ Team: SPHINCS+ (2017). https://sphincs.org/

24.

Zhandry, M.: How to construct quantum random functions. In: FOCS 2013, pp. 679–687. IEEE Computer Society (2012). https://doi.org/10.1109/FOCS.2012.37

25.

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

26.

Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. Int. J. Quantum Inf. 13(04), 1550014 (2015)MathSciNetCrossRef

27.

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

Title: Quantum Indistinguishability of Random Sponges
Authors: Jan Czajkowski
Andreas Hülsing
Christian Schaffner
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2019
Print ISBN: 978-3-030-26950-0

Electronic ISBN: 978-3-030-26951-7

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-26951-7_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner