Quantum Indistinguishability of random sponges

Jan Czajkowski, Andreas Hülsing, Christian Schaffner

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
EditorsAlexandra Boldyreva, Daniele Micciancio
Place of PublicationCham
PublisherSpringer
Pages296-325
Number of pages30
ISBN (Electronic)978-3-030-26951-7
ISBN (Print)978-3-030-26950-0
DOIs
Publication statusPublished - 1 Jan 2019
Event39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States
Duration: 18 Aug 201922 Aug 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11693 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th Annual International Cryptology Conference, CRYPTO 2019
CountryUnited States
CitySanta Barbara
Period18/08/1922/08/19

Fingerprint

Internal
Random Permutation
Random Function
Pseudorandom Function
Output
Joint Distribution
Superposition
Lemma
Attack
Model

Keywords

  • Indistinguishability
  • Keyed sponges
  • Message-authentication codes
  • Quantum security
  • Symmetric cryptography

Cite this

Czajkowski, J., Hülsing, A., & Schaffner, C. (2019). Quantum Indistinguishability of random sponges. In A. Boldyreva, & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings (pp. 296-325). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11693 LNCS). Cham: Springer. https://doi.org/10.1007/978-3-030-26951-7_11
Czajkowski, Jan ; Hülsing, Andreas ; Schaffner, Christian. / Quantum Indistinguishability of random sponges. Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. editor / Alexandra Boldyreva ; Daniele Micciancio. Cham : Springer, 2019. pp. 296-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{94d145dd20f74520aeb71cae40efbfc6,
title = "Quantum Indistinguishability of random sponges",
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.",
keywords = "Indistinguishability, Keyed sponges, Message-authentication codes, Quantum security, Symmetric cryptography",
author = "Jan Czajkowski and Andreas H{\"u}lsing and Christian Schaffner",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-26951-7_11",
language = "English",
isbn = "978-3-030-26950-0",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "296--325",
editor = "Alexandra Boldyreva and Daniele Micciancio",
booktitle = "Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings",
address = "Germany",

}

Czajkowski, J, Hülsing, A & Schaffner, C 2019, Quantum Indistinguishability of random sponges. in A Boldyreva & D Micciancio (eds), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11693 LNCS, Springer, Cham, pp. 296-325, 39th Annual International Cryptology Conference, CRYPTO 2019, Santa Barbara, United States, 18/08/19. https://doi.org/10.1007/978-3-030-26951-7_11

Quantum Indistinguishability of random sponges. / Czajkowski, Jan; Hülsing, Andreas; Schaffner, Christian.

Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. ed. / Alexandra Boldyreva; Daniele Micciancio. Cham : Springer, 2019. p. 296-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11693 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Quantum Indistinguishability of random sponges

AU - Czajkowski, Jan

AU - Hülsing, Andreas

AU - Schaffner, Christian

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Indistinguishability

KW - Keyed sponges

KW - Message-authentication codes

KW - Quantum security

KW - Symmetric cryptography

UR - http://www.scopus.com/inward/record.url?scp=85071455664&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-26951-7_11

DO - 10.1007/978-3-030-26951-7_11

M3 - Conference contribution

AN - SCOPUS:85071455664

SN - 978-3-030-26950-0

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 296

EP - 325

BT - Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings

A2 - Boldyreva, Alexandra

A2 - Micciancio, Daniele

PB - Springer

CY - Cham

ER -

Czajkowski J, Hülsing A, Schaffner C. Quantum Indistinguishability of random sponges. In Boldyreva A, Micciancio D, editors, Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. Cham: Springer. 2019. p. 296-325. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-26951-7_11