Are there hash functions that make use of pseudorandom functions. Precisely, I'm looking for a specification of a hash function based on PRF (and based on the security of such a primitive).
$\begingroup$
$\endgroup$
5
-
$\begingroup$ @Thomas: but the question is whether there are hash functions built using PRF's. And not every PRF is a "hash" in the common sense - for example a PRF $\{0, 1\}^{128} \rightarrow \{0, 1\}^{128}$ does not compress the input (nor takes an arbitrary length input). $\endgroup$– orlpJul 25, 2013 at 9:33
-
$\begingroup$ Yes, I know that a hach function can be seen as a PRF. My question is related to construction, for instance by taking the example of PRF of nightcracker. $\endgroup$– Dingo13Jul 25, 2013 at 10:08
-
$\begingroup$ @Thomas No, standard notions for hash functions definitely do not imply that a hash function is a PRF. $\endgroup$– MaeherJul 25, 2013 at 10:22
-
2$\begingroup$ In fact, a hash function can never be a PRF, because it is publicly computable. $\endgroup$– MaeherJul 25, 2013 at 10:37
-
$\begingroup$ What is the context for this question? Where did this arise? Why are you asking? $\endgroup$– D.W.Jul 27, 2013 at 6:51
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Note that a PRP is a PRF for a large enough block size. Hash functions based on block ciphers will probably be of interest to you.
There are some general schemes for using block ciphers to build hash functions. You may want to investigate them and what requirements they have for the underlying block cipher. Unfortunately, the PRP model is a weak requirement for a block cipher, schemes that use block ciphers often use stronger assumptions (like the MDC-2 hash is built on block ciphers by using the Ideal Cipher model).
For a modern example, the popular SHA-3 hash contestant Skein is based on the block cipher Threefish. You could investigate if/what PRF or PRP models are used in the analysis of Skein and Threefish.
$\begingroup$
$\endgroup$
3
PRFs are closely related to cryptographic hash functions. However, usually PRFs are built from PRGs (GGM construction), which in return can be created from cryptographic hash functions. However, the reverse construction is not trivial.
The security notion of both primitives is similar: If the PRF is drawn randomly from the PRF family, then the output of the function is indistinguishable from a true random function. However, for hash functions the security requirements are more concrete: collision resistance and preimage resistance. A true random function already has these properties, IF the domain and range of this function family is large.
However, PRFs are missing one property of hash functions: Being able to reduce an infite domain to a finite range (and still have the collision and preimage resistance).
How to do this? First you need a PRF family, which is compressnig a larger domain into a smaller range. If you have a PRF familiy which is not compressing, you can apply universal hashing to get a compression function. And with this compressing function you can build a hash function with the Merkle-Damgard construction, or a similar construction (e.g. Keccac sponge).
-
$\begingroup$ Thank you, but I don't understand one thing, "A true random function already has these properties, IF the domain and range of this function family is large." Why we can say that a random function is preimage resistant ? In particular, If I take a random square matrix, Its behaviour is random, but I can reverse it if this one has a full rank... $\endgroup$– Dingo13Jul 25, 2013 at 18:12
-
1$\begingroup$ @Dingo13 Only a very small fraction of functions are multi-linear (i.e., can be described using matrices). Therefore there's a big difference between a random function and a random multi-linear function. By definition, each output of a random function is independent of not only the input, but also other (input, output) pairs. Therefore knowing the output doesn't help you guess the input (i.e., random functions are pre-image resistant). In contrast, the behavior of a random square matrix is not "random" in this same sense, since multilinear functions have strict algebraic properties. $\endgroup$– SethJul 25, 2013 at 20:21
-
$\begingroup$ A true random function is not an actual function, it is a description for a specific kind of random oracle (namely, finite domain and range). I.e. the function is not fixed but develops while being used: When you request f(x), which was not seen before, you get a random value in the domain. If f(x) was queried before, then you get the same value as before. $\endgroup$– tyloJul 26, 2013 at 10:55
$\begingroup$
$\endgroup$
0
A good place to look for such a construction is Building a Collision-Resistant Compression Function from Non-Compressing Primitives by Shrimpton and Stam (http://eprint.iacr.org/2007/409.pdf). This paper explains how to design a compression function from a random function. From a compression function, building a hash function is a standard problem and one frequent solution is to use the Merkle-Damgard construction.
The basic solution proposed in the above paper is to define: $$ H^{f_1,f_2,f_3}(V,M)=f_3(f_1(M)\oplus f_2(V))\oplus f_1(M), $$ where each $f_i$ is a random function from $n$ bits to $n$ bits and $M$, $V$ are the two $n$-bit halves of the $2n$-bit input to the compression function $H$.
