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 language | English |
|---|---|
| Title of host publication | Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings |
| Editors | Alexandra Boldyreva, Daniele Micciancio |
| Place of Publication | Cham |
| Publisher | Springer |
| Pages | 296-325 |
| Number of pages | 30 |
| ISBN (Electronic) | 978-3-030-26951-7 |
| ISBN (Print) | 978-3-030-26950-0 |
| DOIs | |
| Publication status | Published - 1 Jan 2019 |
| Event | 39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States Duration: 18 Aug 2019 → 22 Aug 2019 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 11693 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 39th Annual International Cryptology Conference, CRYPTO 2019 |
|---|---|
| Country | United States |
| City | Santa Barbara |
| Period | 18/08/19 → 22/08/19 |
Fingerprint
Keywords
- Indistinguishability
- Keyed sponges
- Message-authentication codes
- Quantum security
- Symmetric cryptography
Cite this
}
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 proceeding › Conference contribution › Academic › peer-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 -