# Is it possible to make use of a pseudo-random permutation to construct a one-way compression function?

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?

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

• 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... – lyrically wicked Nov 10 '18 at 9:07
• 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). – Yehuda Lindell Nov 10 '18 at 16:21