0
$\begingroup$

Let $f(x)$ and $g(x)$ denote two independent, “ideal”, unkeyed, public $n$-bit permutations (two publicly known bijective functions that produce $n$-bit outputs from $n$-bit inputs), where $n$ is an arbitrary natural number greater than or equal to $3$ (the number $3$ is here because it is the minimal size of a “cryptographically significant” S-Box).

Does there exist an efficient iterative algorithm (based on $f(x)$ and $g(x)$ as the underlying functions) that allows to construct a cryptographically secure $n$-bit hash function for $k$-bit inputs, assuming that $k$ is an arbitrary natural number greater than or equal to zero (that is, there should be no limit on the maximum length of the input)?

Improve this question
$\endgroup$
11
  • $\begingroup$ Intermix $f$ and $g$ using Feistel network? $\endgroup$
    – DannyNiu
    Commented Feb 24, 2020 at 5:36
  • 1
    $\begingroup$ Why can't you "just" use a Sponge construction with $f$? $\endgroup$
    – SEJPM
    Commented Feb 24, 2020 at 9:21
  • 1
    $\begingroup$ @SEJPM: if I use a sponge construction with the single underlying $n$-bit permutation, the size of the cryptographically secure hash output will be significantly less than $n$. For example, SHA-3 uses the $1600$-bit underlying permutation, but the size of hash is $512$ bits. $\endgroup$
    – lyrically wicked
    Commented Feb 24, 2020 at 9:41
  • 1
    $\begingroup$ @lirycally-wicked that is wrong. With a sponge you can have unbounded output, as in SHAKE. You just need to restrict the input size to n-c where c is the double of the security you target. $\endgroup$
    – Ruggero
    Commented Feb 24, 2020 at 10:08
  • 1
    $\begingroup$ @lirycally-wicked No. The squeezing phase, where you produce the output, can require multiple permutation calls and for each one it outputs the size of the rate. If your rate is 1, you can have hashes of 256 bits just by doing 256 permutations in the squeezing phase. $\endgroup$
    – Ruggero
    Commented Feb 26, 2020 at 9:17

2 Answers 2

Reset to default
1
$\begingroup$

If I understand the question correctly, one such possible construction would be something that was used in the SHA-3 competition candidate Grøstl, where an iterated compression function is built from two fixed permutations $P$ and $Q$:

Compression function of Groestl

The security proof of that construction is based on the paper: P.-A. Fouque, J. Stern, and S. Zimmer. Cryptanalysis of Tweaked Versions of SMASH and Reparation. Selected Areas in Cryptography 2008, LNCS 5381, Springer, 2009

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The size of $P$ and $Q$ in this construction is equal to $2n$ (where $n$ is the size of hash). My question implies that the size of each of the two permutations is equal to $n$. $\endgroup$
    – lyrically wicked
    Commented Feb 28, 2020 at 4:17
0
$\begingroup$

It is impossible to construct a collision-resistant hash function from one-way permutations, via a black-box construction. Thus, the answer in principle is no; such a construction is impossible. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? by Simon (Eurocrypt'98). This answer does not relate to heuristic constructions, but you cannot do this with a proof of security (unless it's not black box).

The question here actually relates to "ideal" permutations, and under such an assumption it may be different. (Although, I'm not sure what is meant by "public" ideal.) My answer referred to (non-ideal) one-way permutations.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ How do sponge-based hashes fit into this picture? $\endgroup$
    – SEJPM
    Commented Feb 26, 2020 at 10:24
  • 1
    $\begingroup$ You need an ideal assumption. I just noticed that this was actually in the question, so my answer is wrong. I will update. $\endgroup$
    – Yehuda Lindell
    Commented Feb 26, 2020 at 11:27
  • $\begingroup$ And even the security of the XOR of two permutations cannot help to construct the desired hash function? $\endgroup$
    – lyrically wicked
    Commented Feb 27, 2020 at 5:22
  • $\begingroup$ The XOR of two pseudorandom permutations is a pseudorandom function (and that's what the link shows). It says nothing about collision resistance. $\endgroup$
    – Yehuda Lindell
    Commented Feb 27, 2020 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.