In cryptography, a one-way compression function is a function that transforms a fixed-length input into a fixed-length output. The transformation is "one-way", 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 data compression, which by definition is invertible.
One-way compression functions are for instance used in the Merkle–Damgård construction inside cryptographic hash functions.
One-way compression functions are often built from block ciphers. 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. (MDC-2 is also the name of a hash function patented by IBM.)
Read more about One-way Compression Function: Compression, One-way, The Merkle–Damgård Construction, Construction From Block Ciphers, Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel, Hirose
Famous quotes containing the words compression and/or function:
“Do they [the publishers of Murphy] not understand that if the book is slightly obscure it is because it is a compression and that to compress it further can only make it more obscure?”
—Samuel Beckett (1906–1989)
“Every boy was supposed to come into the world equipped with a father whose prime function was to be our father and show us how to be men. He can escape us, but we can never escape him. Present or absent, dead or alive, real or imagined, our father is the main man in our masculinity.”
—Frank Pittman (20th century)