Welcome to the resource topic for 2022/464
Title:
Superposition Attacks on Pseudorandom Schemes based on Two or Less Permutations
Authors: Shaoxuan Zhang, Chun Guo, Qingju Wang
Abstract:We study quantum superposition attacks against permutation-based pseudorandom cryptographic schemes. We first extend Kuwakado and Morii’s attack against the Even-Mansour cipher (ISITA 2012), and exhibit key recovery attacks against a large class of pseudorandom schemes based on a single call to an n-bit permutation, with polynomial O(n) quantum steps. We also show how to overcome restrictions on available quantum data in certain relevant settings. We then consider TPPR schemes, namely, Two Permutation-based PseudoRandom cryptographic schemes. Using the improved Grover-meet-Simon method of Bonnetain et al. (ASIACRYPT 2019), we show that the keys of a wide class of TPPR schemes can be recovered with O(n) superposition queries and O(n2^{n/2}) quantum steps. We also exhibit sub-classes of “degenerated” TPPR schemes that lack certain internal operations, and exhibit more efficient key recovery attacks using either the Simon’s algorithm or Chailloux et al.'s algorithm for collision searching (ASIACRYPT 2017). Further using the all-subkeys-recovery idea of Isobe and Shibutani (SAC 2012), our results give rise to key recovery attacks against several recently proposed permutation-based PRFs, as well as the 2-round Even-Mansour ciphers with generic key schedule functions (Chen et al., JoC 2018) and their tweakable variants (Cogliati et al., CRYPTO 2015). From a constructive perspective, our results establish new quantum Q2 security upper bounds for two permutation-based pseudorandom schemes as well as sound design choices.
ePrint: https://eprint.iacr.org/2022/464
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .