Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [compression-function]

The tag has no usage guidance.

1
vote
1answer
98 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 ...
7
votes
1answer
128 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 ...
0
votes
2answers
124 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 ...
2
votes
0answers
66 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 $...
3
votes
1answer
35 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 ...
12
votes
2answers
258 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 ...
1
vote
0answers
103 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 (source): The cryptographic sponge is a construction scheme for hash functions (and other symmetric ...
2
votes
1answer
69 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 $...
3
votes
3answers
298 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 ...
1
vote
0answers
102 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?
2
votes
2answers
166 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. ...
4
votes
0answers
84 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 ...
11
votes
1answer
282 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 ...