Quantum indistinguishability of random sponges

Jan Czajkowski, Andreas Hülsing, Christian Schaffner

Onderzoeksoutput: Boek/rapportRapportAcademic

Uittreksel

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.
TaalEngels
UitgeverijIACR
Aantal pagina's36
StatusGepubliceerd - 2019

Publicatie series

NaamCryptology ePrint Archive
Nr.2019/069

Bibliografische nota

to appear in proceedings of CRYPTO '19

Citeer dit

Czajkowski, J., Hülsing, A., & Schaffner, C. (2019). Quantum indistinguishability of random sponges. (Cryptology ePrint Archive; Nr. 2019/069). IACR.
Czajkowski, Jan ; Hülsing, Andreas ; Schaffner, Christian. / Quantum indistinguishability of random sponges. IACR, 2019. 36 blz. (Cryptology ePrint Archive; 2019/069).
@book{96c02cfae5d7457a81df587433c468c6,
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.",
author = "Jan Czajkowski and Andreas H{\"u}lsing and Christian Schaffner",
note = "to appear in proceedings of CRYPTO '19",
year = "2019",
language = "English",
series = "Cryptology ePrint Archive",
publisher = "IACR",
number = "2019/069",

}

Czajkowski, J, Hülsing, A & Schaffner, C 2019, Quantum indistinguishability of random sponges. Cryptology ePrint Archive, nr. 2019/069, IACR.

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

IACR, 2019. 36 blz. (Cryptology ePrint Archive; Nr. 2019/069).

Onderzoeksoutput: Boek/rapportRapportAcademic

TY - BOOK

T1 - Quantum indistinguishability of random sponges

AU - Czajkowski,Jan

AU - Hülsing,Andreas

AU - Schaffner,Christian

N1 - to appear in proceedings of CRYPTO '19

PY - 2019

Y1 - 2019

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.

M3 - Report

T3 - Cryptology ePrint Archive

BT - Quantum indistinguishability of random sponges

PB - IACR

ER -

Czajkowski J, Hülsing A, Schaffner C. Quantum indistinguishability of random sponges. IACR, 2019. 36 blz. (Cryptology ePrint Archive; 2019/069).