Let $f_k(B)$ denote the underlying function (a pseudo-random permutation) of a block cipher: it uses an $x$-bit key $k$ to encrypt an $y$-bit block $B$.
The question: is it possible to make use of $f_k(B)$ to construct a cryptographically secure One-way compression function that transforms any sequence of $y$ bits to a sequence of $y/2$ bits? If yes, then what is an example of how to do it? If no, then why?
For example, consider the following construction. Let $V$ denote a sequence of $x$ zero bits: $$V = 0^x.$$ Then $W$ denotes the inverse of $V$: $$W = 1^x.$$ Consider a function that outputs the first half of a bitstring $T$, where
$$T = f_V(b) \oplus f_W(B),$$ assuming that $B$ denotes the input, $b$ denotes the inverse of $B$ and $\oplus$ denotes a standard XOR.
Can we use such function as a compression function?

  • $\begingroup$ $b$ is the bitwise complement of $B$, $b = \overline{B}$, b = \overline{B} $\endgroup$
    – kelalaka
    Nov 9, 2018 at 12:57

1 Answer 1


This is possible in the ideal cipher model, and is the basis of the Davies-Meyer and other hashes; see https://en.wikipedia.org/wiki/One-way_compression_function. There has been a lot of work looking at this, but I think a good place to start is the paper Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. It is important, however, to be aware that the ideal cipher model is very strong. For example, AES suffers from related-key attacks and so is not a good basis for such constructions. In addition, due to DES weak keys, some of these constructions are completely broken with DES. However, it does explain the rationale behind the SHA256 and other SHA constructions that essentially construct a type of block cipher and apply a Davies-Meyer type transformation.

  • $\begingroup$ So it does not make any sense to talk about the fixed-length input compression from $y$ bits to $y/2$ bits? All described schemes are iterated and output $y$ bits from the variable-length input... $\endgroup$ Nov 10, 2018 at 9:07
  • $\begingroup$ Actually, you will notice that they all start with a basic construction that takes $2n$ bits to $n$ bits, which is the same as you are looking at. They then iterate to get something from a general input length (as in Merkle-Damgård). $\endgroup$ Nov 10, 2018 at 16:21

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.