IMPROVING THE ROUND COMPLEXITY OF IDEAL-CIPHER CONSTRUCTIONS
Publication or External Link
Block ciphers are an essential ingredient of modern cryptography.
They are widely used as building blocks in many cryptographic constructions
such as encryption schemes, hash functions etc.
The security of block ciphers is not currently
known to reduce to well-studied, easily formulated, computational
Nevertheless, modern block-cipher constructions
are far from ad-hoc,
and a strong theory for their design has been developed.
Two classical paradigms for block cipher design are the Feistel network and the
key-alternating cipher (which is encompassed by the popular
Both of these paradigms that are iterated structures
that involve applications of random-looking functions/permutations
over many rounds.
An important area of research is to understand the provable
security guarantees offered by these classical design paradigms for block cipher constructions.
This can be done using a security notion called indifferentiability which formalizes
what it means for a block cipher to be ideal.
In particular, this notion allows us to assert the structural robustness
of a block cipher design.
In this thesis, we apply the indifferentiability notion to the two classical paradigms
mentioned above and improve upon the previously known round complexity
in both cases.
Specifically, we make the following two contributions:
(1) We show that a 10-round Feistel network behaves as an ideal block cipher
when the keyed round functions are built using a random oracle.
(2) We show that a 5-round key-alternating cipher (also known as the iterated Even-Mansour
construction) with identical round keys behaves as an ideal block cipher when the round permutations are independent, public random permutations.