Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Do there exist proofs of security for primitives like hash functions (based on a block cipher) in the PRP model.
I often see proofs in the random oracle model (for hash function based on compression function) and proofs in the ideal cipher model (for hash function based on block cipher).
Are there proofs of such primitive in a real world model?
A PRP is a keyed primitive, so proving properties of a keyed hash on top of it is often possible. Reducing the security of an unkeyed hash to a keyed primitive on the other hand is rarely possible.
For example keyed Skein (a hash) is provably a PRF if Threefish (a block-cipher) is a PRP:
PRF, MAC, and KDF. We prove that if Threefish is a tweakable PRP (pseudorandom permutation) then Skein is a PRF. It is important to understand that we are referring, in this context, to the keyed version of Skein. The PRF property is that the input-output behavior of keyed Skein should look like that of a random function to an attacker who is not given the key. This proof supports the usage of keyed Skein for key derivation (KDF). It also supports the use of keyed Skein as a MAC. This is true because any PRF is a secure MAC
Let $b$ be the number of elements in the block cipher's domain. $\:$ Let $n$ be the block cipher's key size.
If $\:\frac{2^n}{b!}\:$ is negligible, then one can construct an eTCR (page 4) hash from the block cipher as follows:
If $b$ is greater than, say, $\:2\hspace{-0.05 in}\cdot\hspace{-0.04 in}n\:$,$\:$ then one can fix a subset of $n$ elements
of the block cipher's domain, and define $\hspace{.04 in}f$ to take a key as input and
output the evaluation of the block cipher with that key on those inputs.
If one used a truly random permutation instead, then that function
would have $\:\displaystyle\prod_{0\leq q< n} (b\hspace{-0.04 in}-\hspace{-0.03 in}q)\:$ possible outputs. $\;\;\;$ If $\: 4\leq n \:$ then
$$\frac{2^n}{\displaystyle\prod_{0\leq q< n} (b\hspace{-0.04 in}-\hspace{-0.03 in}q)} \; \leq \; \frac{2^n}{\displaystyle\prod_{0\leq q< n} ((2\hspace{-0.05 in}\cdot\hspace{-0.04 in}n)\hspace{-0.04 in}-\hspace{-0.03 in}n)} \; = \; \frac{2^n}{\displaystyle\prod_{0\leq q< n} n} \; = \; \frac{2^n}{n^n} \; = \; \left(\hspace{-0.04 in}\frac2{n}\hspace{-0.04 in}\right)^{\hspace{-0.04 in}n} \; \leq \; \left(\hspace{-0.04 in}\frac24\hspace{-0.04 in}\right)^{\hspace{-0.04 in}n} \; = \; \left(\hspace{-0.04 in}\frac12\hspace{-0.04 in}\right)^{\hspace{-0.04 in}n} \; = \; \frac1{2^n}$$
If one uses the construction of $\hspace{.04 in}f$ on a truly random permutation rather than the block cipher with a given key, then the probability of there existing a preimage is negligible. $\:$ By the PRP property, if one attempts to invert $\hspace{.04 in}f$ on its actual output for a randomly chosen input, the probability of success will
still be negligible. $\:$ Thus $\hspace{.04 in}f$ is one-way. $\;\;\;$ If $b$ is at most $\:2\hspace{-0.05 in}\cdot\hspace{-0.04 in}n\:$,$\:$ then one can efficiently evaluate the
block cipher on its entire domain. $\;\;\;$ In that case, one defines $g$ to take a key as input and output the evaluation of the block cipher with that key on its entire domain. $\;\;\;$ If one uses the construction of
$g$ on a truly random permutation rather than the block cipher with a given key, then the probability
of there existing a preimage is $\;\frac{2^n}{b!}\:\:$. $\;\;\;$ By assumption, $\:\frac{2^n}{b!}\:$ is negligible. $\;\;\;$ By the PRP property,
if one attempts to invert $g$ on its actual output for a randomly chosen input, the probability of
success will still be negligible. $\:$ Thus $g$ is one-way. $\:$ In either case, one gets a one-way function.
Next, by this paper, one gets a "universal one-way hash function", now known as a TCR hash.
By chaining with independent keys a number of times equal to the length of the
TCR hash's outputs, one gets a TCR hash that compresses by at least a factor of 2.
By padding the message to an appropriate length, truncating the result if that would be too long,
using one of a linear number of independent keys for each layer in a hash tree, and ignoring the rest
of those keys, one gets a TCR hash with fixed-length output that can handle arbitrary length inputs.
Finally, by making the entire key (including the parts that were previously ignored)
of such a TCR hash part of the output, one gets an eTCR hash.
