Publication

Beyond uniformity: Better security/efficiency tradeoffs for compression functions

Martijn Stam
2008
Conference Papers

Abstract

Suppose we are given a perfect n + c-to-n bit compression function f and we want to construct a larger m + s-to-s bit compression function H instead. What level of security, in particular collision resistance, can we expect from H if it makes r calls to f? We conjecture that typically collisions can be found in 2((nr+cr-m)/(r+1)) queries. This bound is also relevant for building a m + s-to-s bit compression function based on a blockcipher with k-bit keys and n-bit blocks: simply set c = k, or c = 0 in case of fixed keys.

Official source

https://infoscience.epfl.ch/entities/publication/1d6057b3-b5f1-418c-aa9e-3f2ab2f10779

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Martijn Stam
2008
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/1d6057b3-b5f1-418c-aa9e-3f2ab2f10779

About this result

Related concepts (19)

One-way compression function

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs 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 conventional data compression algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

Lossless compression

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates (and therefore reduced media sizes).

Compression artifact

A compression artifact (or artefact) is a noticeable distortion of media (including , audio, and video) caused by the application of lossy compression. Lossy data compression involves discarding some of the media's data so that it becomes small enough to be stored within the desired or transmitted (streamed) within the available bandwidth (known as the data rate or bit rate). If the compressor cannot store enough data in the compressed version, the result is a loss of quality, or introduction of artifacts.

Related publications (15)

Beyond uniformity: Better security/efficiency tradeoffs for compression functions

Chat with Graph Search

Near Collision Attack Against Grain V1

Making Classical (Threshold) Signatures Post-quantum for Single Use on a Public Ledger

PAE: Towards More Efficient and BBB-Secure AE from a Single Public Permutation