Skip to main content

Questions tagged [compression-function]

A compression function takes two fixed-size inputs: a chaining value and a message and returns a fixed-size value.

Filter by
Sorted by
Tagged with
2 votes
2 answers
193 views

CRYSTALS-Kyber Compress and Decompress function role

I was reading CRYSTALS-Kyber design. They have used compress_q(x,d) to scale an element of $\mathbb{Z}_q$ to $[ 0,1,...,2^d-1 ]$. The definitions of ...
ABCD's user avatar
  • 23
1 vote
0 answers
83 views

Input/Output size of compression functions

I know that DES has 56 independent key bits, and that 3DES has 168 independent key bits by using 3 separate 56-bit DES keys. 3DES also has a block size of 64 bits. If I use 3DES as the underlying ...
mjg4's user avatar
  • 11
0 votes
0 answers
51 views

Cryptanalyzing a hash compression function

I'm designing a hash function which uses a double-tree construction and a compression function $c(s,A,B,C,a)$ ($s$ and $a$ may be omitted when there's only one of them) where $s$ is a set of three ...
Pierre Abbat's user avatar
2 votes
1 answer
134 views

Recommended output filter for Rumba20 [closed]

Rumba20 is a compression function that maps a 192-byte (1536-bit) string to a 64-byte (512-bit) string. It's designed to provide collision resistance by using Salsa20 (or ChaCha20) with the ...
samuel-lucas6's user avatar
0 votes
1 answer
104 views

Iterated hash functions

In this image, It describes the basic idea of an iterative hash function. I am confused as to why the i value is set to be m+t+1 ...
Simon Balfe's user avatar
2 votes
0 answers
72 views

Is there any standard extension of the Merkle-Damgård transform that handles arbitrary-length inputs?

I have seen multiple sources claim that the Merkle-Damgård transform is able to build a collision-resistant Hash-function $H$ for arbitrary-length inputs from a compression function $h : \{0,1\}^n \to ...
Steven's user avatar
  • 131
2 votes
1 answer
83 views

Is a compression function call the same as invoking the hash function itself?

In BLAKE2X paper it is said: BLAKE2X adds a constant overhead of $\lceil\ell/64\rceil$ (resp. $\lceil\ell/32\rceil$ compression function calls compared to the underlying 64-bit (resp. 32-bit) BLAKE2 ...
phantomcraft's user avatar
6 votes
1 answer
400 views

Fast irreversible transformation/compression of short messages using a secret

I'm looking for a very fast function $f(m, k) $ that takes a 64-bit integer $m$ and a fixed secret key $k$ of virtually any size (generated by a CSPRNG) and turns them into a 64- or 32-bit integer $ r ...
Nee's user avatar
  • 63
4 votes
2 answers
568 views

How can a collision be generated in this hash function by inverting the encryption?

This is from Joan Daemen's Doctoral thesis Per page 64 (or PDF page 79) 4.7.1 Our approach Our goal is the design of simple and portable unkeyed and keyed cryptographic hash functions that are ...
user93353's user avatar
  • 2,245
5 votes
2 answers
2k views

What is the difference between data compression and compression in cryptographic algorithms?

What is the differences between data compression as used in e.g. the ZIP protocol and compression as performed in cryptographic hashes? Are there common properties as well, apart from creating a ...
Maarten Bodewes's user avatar
  • 93.2k
1 vote
0 answers
180 views

"Reversing" SHA256 [duplicate]

Let's say I give you the sha256 hash of my password, which I'll call X. Now, the sha256 algorithm is a one-way function, meaning you can give it some input and get an output, but you can't get the ...
Ömer Enes Özmen's user avatar
0 votes
1 answer
346 views

Xor'ing sha256 words instead of adding

In sha-256, when the words go through the compression function, they get added to the previous hash. In case of the first 64 rounds, they get added to the initial words ($\bmod 2^{32}$ of course). ...
Ömer Enes Özmen's user avatar
1 vote
0 answers
248 views

Idea behind internal SHA-2 functions

In the SHA-2 family, specifically SHA-256, there are functions called Sigma0 and Sigma1, which look like this: ...
Ömer Enes Özmen's user avatar
0 votes
1 answer
191 views

An unusual use-case for HMAC as compression function in web browsers

It's an unfortunate fact that, right now (2019), browsers don't expose standardized streaming hashing interfaces in SubtleCrypto. The only way to hash a file, is to ...
DannyNiu's user avatar
  • 9,421
3 votes
0 answers
103 views

A "concatenation-like" cryptographic operation that has a fixed output?

I am designing a cryptographic protocol, and I was wondering whether or not there exists a simple cryptographic operation $\diamond$ that is: Associative: $(x\diamond y)\diamond z = x \diamond(y\...
ithisa's user avatar
  • 1,101
1 vote
1 answer
127 views

Does there exist a compression function (from four 32-bit words to one 32-bit word) that always detects any modification of a single word?

I need a compression function $F$ that uses only bitwise operations (AND, NOT, OR, XOR, shifts, rotations) and outputs one 32-bit word $W$ from four 32-bit words $w_1 \mathbin\Vert w_2 \mathbin\Vert ...
lyrically wicked's user avatar
7 votes
1 answer
688 views

SNARK-friendly one-way compression functions

I'm looking for a one-way compression function that is secure and efficient within a zk-SNARK circuit. The motivation behind this comes from these considerations: SHA256-compression is highly ...
1077's user avatar
  • 171
0 votes
2 answers
761 views

What characteristics define a function to be a block cipher

I'm trying to understand what characteristics or properties make the result of a function a block cipher. I understand that for a function to be a block cipher it has to be invertible and can't be a ...
Jez Don-Tresgrafteron's user avatar
2 votes
0 answers
469 views

Is the concatenation of one-way compression functions one-way?

Given two independently keyed compression functions $h_1$ and $h_2$: $h_b(x): \{0,1\}^{3n} \to \{0,1\}^{n}$, where $b \in \{1,2\}$. Let $h(x) = h_1(x) \| h_2(x)$. Given at least one of $h_1$ and $...
ambiso's user avatar
  • 706
3 votes
1 answer
53 views

For a hash over a finite space without size reduction, is a public permutation sufficient?

Suppose the application is a Lamport signature scheme. Is the following a secure hash $\{0,1\}^n \rightarrow \{0,1\}^n$? $$ H(x) = x \oplus P(x) $$ where $P$ is a public permutation that permutes an ...
MikeDav77741's user avatar
14 votes
2 answers
1k views

Why was Davies–Meyer chosen over Miyaguchi–Preneel most of the time?

The only Miyaguchi–Preneel MD hash I know is Whirlpool. I suppose there are likely others. Why do most MD hashes choose Davies–Meyer? If anything, Davies–Meyer relies on related-key resistance while ...
MikeDav77741's user avatar
3 votes
1 answer
376 views

Is it possible to apply a pseudo-random permutation (a keyed permutation) to construct a sponge function?

The description of the sponge function on Crypto.Stackexchange contains the following text The cryptographic sponge is a construction scheme for hash functions (and other symmetric primitives) based ...
lyrically wicked's user avatar
2 votes
1 answer
297 views

Is it possible to make use of a pseudo-random permutation to construct a one-way compression function?

Let $f_k(B)$ denote the underlying function (a pseudo-random permutation) of a block cipher: it uses an $x$-bit key $k$ to encrypt an $y$-bit block $B$. The question: is it possible to make use of $...
lyrically wicked's user avatar
3 votes
2 answers
461 views

Does there exist an “almost-ideal” compression function to compress an arbitrarily long bitstring into a single pseudo-random (unbiased) byte?

I need a function $F$ that compresses an arbitrary (unbounded from above) number of bytes into a single byte. The goal is creating a single unpredictable byte from an arbitrary bitstring. Here are ...
lyrically wicked's user avatar
1 vote
0 answers
163 views

Davies-Meyer without XORing in the previous state

A Davies-Meyer ccompression function operates with $H_{i} = E(m_{i}, H_{i-1}) \oplus H_{i-1}$. Why not use $H_{i} = E(m_{i}, H_{i-1})$ instead?
Melab's user avatar
  • 3,655
2 votes
2 answers
279 views

Optimal compression ratio in compression function [closed]

So we'll have a transform that maps any of $A=2^a$ possible inputs to $B=2^b$ possible outputs. $a$ is generally fixed as the number of bits in the input, and $b$ is determined by the transform used. ...
EPICI's user avatar
  • 359
4 votes
0 answers
111 views

Which compression functions are MACs?

The original HMAC paper based the security proof on the fact that the compression function of the Hash is already a MAC (appropriately keyed). How does this relate to common assumptions for ...
Elias's user avatar
  • 4,923
11 votes
1 answer
620 views

Which compression functions are PRFs?

In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs. The Wikipedia article on cryptographic hash functions ...
Elias's user avatar
  • 4,923
2 votes
1 answer
1k views

What is the logic behind Compress function in iterated hash function

I am working on cryptographic hash functions theorems. In the iterated hash functions part a specific word started appearing constantly: "Compress" for instance within the "compress function". I am ...
Bala Subrahmanyam's user avatar