New Design Criteria for Hash Functions and Block Ciphers

Candidate: Prashant Puniya

Advisor: Yevgeniy Dodis

Cryptographic primitives, such as hash functions and block ciphers, are
integral components in several practical cryptographic schemes. In order to prove
security of these schemes, a variety of security assumptions are made on the
underlying hash function or block cipher, such as collision-resistance,
pseudorandomness etc. In fact, such assumptions are often made without much
regard for the actual constructions of these primitives. In this thesis, we
address this problem and suggest new, and possibly better, design criteria
for hash functions and block ciphers.

We start by analyzing the design criteria underlying hash functions. The
usual design principle here involves a two-step procedure: First, come up with a
heuristically-designed and ``hopefully strong'' fixed-length input
construction (i.e. the compression function), then use a standard domain extension
technique, usually the cascade construction, to
get a construction that works for variable-length inputs. We investigate
this design principle from two perspectives:

- To instantiate the Random Oracle. We suggest modifications to existing
constructions that make the resulting construction secure as a random
oracle, with appropriate assumptions on the underlying compression
function.

- In general, we look for ``black-box'' fixes to existing hash functions
to get secure constructions for each of the common security notions
required of hash functions. We also give suggestions for appropriate
modes for using existing hash functions along these lines.

We next move on to discuss the Feistel network, which is used in the
design of several popular block ciphers such as DES, Triple-DES,
Blowfish etc.
Currently, the celebrated result of Luby-Rackoff (and further
extensions) is regarded as the theoretical basis for using this construction
in block cipher design, where it was shown that a four-round Feistel network
is a (strong) pseudorandom permutation (PRP) if the round functions are
independent pseudorandom functions (PRFs). We study the Feistel network
from two different perspectives:

- Is there a weaker security notion for round functions, than
pseudorandomness, that suffices to prove security of the Feistel
network?

- Can the Feistel network satisfy a much stronger security notion,
i.e. security as an ideal cipher, under appropriate assumptions
on the round functions?

We give a positive answer to the first question and a partial positive
answer to the second question. In the process, we undertake a combinatorial study
of the Feistel network, that might be useful in other scenarios as well. We provide
several practical applications of our results for the Feistel network.