Block ciphers are an essential ingredient in 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 encompasses the popular substitution-permutation networks). Both of these paradigms propose designs 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. Thus, this thesis helps further our understanding of the theory behind popular approaches to block cipher designs. Specifically, we make the following two contributions:

(1) We show that a 10-round Feistel network behaves as an ideal block cipher when assuming that the underlying functions are independent, random functions.

(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 assuming that the underlying permutations are independent, random permutations.

Examining Committee:

Chair: Dr. Jonathan Katz

Co-Chair: Dr. Dana Dachman-Soled

Dean's rep: Dr. Lawrence Washington

Members: Dr. Michelle Mazurek

Dr. Charalampos Papamanthou