One-way compression function: Difference between revisions

Revision as of 08:05, 30 January 2023

Revision as of 14:04, 4 July 2023

Line 1:

{{Short description|Cryptographic primitive}}

In [[cryptography]], a '''one-way compression function''' is a function that transforms two fixed-length inputs into a fixed-length output.<ref name=":0">Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 328.</ref> The transformation is [[one-way function|"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 conventional [[data compression]] algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

[[Image:One-way compression.svg|thumb|upright=0.8|right|A one-way compression function]]

Line 8:

One-way compression functions are often built from [[block cipher]]s.

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]].)

Another method is '''2BOW''' (or '''NBOW''' in general), which is a "high-rate multi-block-length hash function based on block ciphers"<ref name=":0" /> 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.

== Compression ==