Cryptology ePrint Archive: Report 2021/288

Redeeming Reset Indifferentiability and Post-Quantum Groups

Mark Zhandry

Abstract: Indifferentiability is used to analyze the security of constructions of idealized objects, such as random oracles or ideal ciphers. Reset indifferentiability is a strengthening of plain indifferentiability which is applicable in far more scenarios, but is often considered too strong due to significant impossibility results. Our main results are:

- Under weak reset indifferentiability, ideal ciphers imply (fixed size) random oracles and random oracle domain shrinkage is possible. We thus show that reset indifferentiability is more useful than previously thought.

- We lift our analysis to the quantum setting showing that ideal ciphers imply random oracles under quantum indifferentiability.

- Despite Shor's algorithm, we observe that generic groups are still meaningful quantumly, showing that they are quantumly (reset) indifferentiable from ideal ciphers; combined with the above, cryptographic groups yield post-quantum symmetric key cryptography. In particular, we obtain a plausible post-quantum random oracle that is a subset-product followed by two modular reductions.

Category / Keywords: secret-key cryptography / indifferentiability, random oracles, ideal ciphers, quantum

Date: received 4 Mar 2021, last revised 4 Mar 2021

Contact author: mzhandry at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210307:022531 (All versions of this report)

Short URL: ia.cr/2021/288


[ Cryptology ePrint archive ]