IMPROVING THE ROUND COMPLEXITY OF IDEAL-CIPHER CONSTRUCTIONS

Abstract

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

problems.

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

substitution-permutation network).

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.