Questions tagged [hash-function]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
41 votes
4 answers
13k views

Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally: It uses O(1) space It can be updated to reflect an insertion or deletion in O(...
jonderry's user avatar
  • 747
31 votes
3 answers
19k views

What is the difference between a second preimage attack and a collision attack?

Wikipedia defines a second preimage attack as: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1). Wikipedia defines a collision attack as: find two arbitrary ...
Thomas Owens's user avatar
16 votes
1 answer
571 views

Why is it important that the secret is at the end when signing with MD5?

it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?
Hendrik Brummermann's user avatar
15 votes
3 answers
709 views

Associative hash mixing

Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
Per Vognsen's user avatar
  • 2,161
7 votes
1 answer
414 views

Separation between existence of crypto primitives

I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
Kaveh's user avatar
  • 21.6k
4 votes
1 answer
776 views

Example of pairwise independent random process with expected max load $\sqrt{n}$

This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ...
Simd's user avatar
  • 3,902
3 votes
1 answer
142 views

Notion similar to k-wise independence

I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ ...
NotSo Smart's user avatar