Welcome to the resource topic for 2023/226
Title:
Impossibility of Indifferentiable Iterated Blockciphers from 3 or Less Primitive Calls
Authors: Chun Guo, Lei Wang, Dongdai Lin
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.
ePrint: https://eprint.iacr.org/2023/226
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 .