Paper 2019/069
Quantum Indistinguishability of Random Sponges
Jan Czajkowski, Andreas Hülsing, and Christian Schaffner
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
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Symmetric cryptographykeyed spongesindistinguishabilityquantum securitymessage-authentication codes
- Contact author(s)
-
j czajkowski @ uva nl
andreas @ huelsing net
c schaffner @ uva nl - History
- 2019-01-25: received
- Short URL
- https://ia.cr/2019/069
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/069, author = {Jan Czajkowski and Andreas Hülsing and Christian Schaffner}, title = {Quantum Indistinguishability of Random Sponges}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/069}, year = {2019}, url = {https://eprint.iacr.org/2019/069} }