One-way compression function

In <a href="/facts/Cryptography/e94PEVau">cryptography</a>, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is <a href="/facts/One-way_function/rGtcumDW">"one-way"</a>, meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional <a href="/facts/Data_compression/gMFuY4FT">data compression</a> algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

One-way compression functions are for instance used in the <a href="/facts/Merkle%25E2%2580%2593Damg%25C3%25A5rd_construction/nEuAJBAs">Merkle–Damgård construction</a> inside <a href="/facts/Cryptographic_hash_function/cuxkgbST">cryptographic hash functions</a>.
One-way compression functions are often built from <a href="/facts/Block_cipher/MJywAyfQ">block ciphers</a>.
Some methods to turn any normal block cipher into a one-way compression function are Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (single-block-length compression functions) and MDC-2/Meyer–Schilling, MDC-4, Hirose (double-block-length compression functions). These methods are described in detail further down. (<a href="/facts/MDC-2/cXBRCsMf">MDC-2</a> is also the name of a hash function patented by <a href="/facts/IBM/QszA7nwd">IBM</a>.)
Another method is 2BOW (or NBOW in general), which is a "high-rate multi-block-length hash function based on block ciphers" and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead). This method has not yet seen any serious security analysis, so should be handled with care.

One-way compression function open-in-new

One-way compression function