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)
“The information links are like nerves that pervade and help to animate the human organism. The sensors and monitors are analogous to the human senses that put us in touch with the world. Data bases correspond to memory; the information processors perform the function of human reasoning and comprehension. Once the postmodern infrastructure is reasonably integrated, it will greatly exceed human intelligence in reach, acuity, capacity, and precision.”
—Albert Borgman, U.S. educator, author. Crossing the Postmodern Divide, ch. 4, University of Chicago Press (1992)