Paper 2023/226
Impossibility of Indifferentiable Iterated Blockciphers from 3 or Less Primitive Calls
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2023
- Keywords
- Blockcipherideal cipherindifferentiabilitylower bounds
- Contact author(s)
-
chun guo sc @ gmail com
wanglei_hb @ sjtu edu cn
ddlin @ iie ac cn - History
- 2023-02-21: approved
- 2023-02-19: received
- See all versions
- Short URL
- https://ia.cr/2023/226
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/226,
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},
url = {https://eprint.iacr.org/2023/226}
}
