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 (19061989)
“Think of the tools in a tool-box: there is a hammer, pliers, a saw, a screwdriver, a rule, a glue-pot, nails and screws.The function of words are as diverse as the functions of these objects.”
—Ludwig Wittgenstein (18891951)