Paper 2023/226

Impossibility of Indifferentiable Iterated Blockciphers from 3 or Less Primitive Calls

Chun Guo, Shandong University
Lei Wang, Shanghai Jiao Tong University
Dongdai Lin, Institute of Information Engineering, Chinese Academy of Sciences

Virtually all modern blockciphers are iterated. In this paper, we ask: to construct a secure iterated blockcipher "non-trivially", how many calls to random functions and permutations are necessary? When security means indistinguishability from a random permutation, optimality is achieved by the Even-Mansour scheme using 1 call to a public permutation. We seek for the arguably strongest security indifferentiability from an ideal cipher, a notion introduced by Maurer et al. (TCC 2004) and popularized by Coron et al. (JoC, 2014). We provide the first generic negative result/lower bounds: when the key is not too short, no iterated blockcipher making 3 calls is (statistically) indifferentiable. This proves optimality for a 4-call positive result of Guo et al. (Eprint 2016). Furthermore, using 1 or 2 calls, even indifferentiable iterated blockciphers with polynomial keyspace are impossible. To prove this, we develop an abstraction of idealized iterated blockciphers and establish various basic properties, and apply Extremal Graph Theory results to prove the existence of certain (generalized) non-random properties such as the boomerang and yoyo.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Blockcipherideal cipherindifferentiabilitylower bounds
Contact author(s)
chun guo sc @ gmail com
wanglei_hb @ sjtu edu cn
ddlin @ iie ac cn
2023-02-21: approved
2023-02-19: received
See all versions
Short URL
No rights reserved


      author = {Chun Guo and Lei Wang and Dongdai Lin},
      title = {Impossibility of Indifferentiable Iterated Blockciphers from 3 or Less Primitive Calls},
      howpublished = {Cryptology ePrint Archive, Paper 2023/226},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.