# Tag Info

Accepted

### Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution ...
• 51.1k
Accepted

### State of research on SHA-1 Collision Attacks

SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1. It is an identical-prefix collision attack that ...
• 206
Accepted

### Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key." 1.44 bits per ...
• 11.2k

### Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times ...
• 11.2k
Accepted

### Can a result of (any) hash algorithm contain the hash result itself?

For the first question, about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the ...
• 10.8k
Accepted

### Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing

I think a pragmatic approach would be to use a PRF (see also here) instead of a polynomial hash, because then you can say that the collision probability is $1/M$ (unless someone figures out how to ...
• 12.2k
Accepted

### Fibers of hash functions

Cryptographic hashes I don't think anything is known unconditionally. We can analyze this question using a random oracle assumption. MD5, SHA1, SHA256, etc., have a Merkle-Damgaard structure: they ...
• 12.2k
Accepted

### What is the maximal load of a "latency-bounded" Cuckoo Hash?

Section 4 of the journal version of the original Cuckoo Hashing paper shows that to have insertion succeed with probability $p$, your numbers $T$, $n$, and $\epsilon$ must satisfy  \frac{13}{n^2 \...
• 11.2k

As much as you're being downvoted and attacked, your idea is absolutely right, correct, and valid. You've nearly reinvented bcrypt. Let's say we have encryption algorithm (doesn't matter which one): ...
• 131
Accepted

### "Linear" hashing function

Sure. These are known as homomorphic hash functions. There are many schemes: see e.g., https://crypto.stackexchange.com/q/6497/351 for one possible entry point into the literature. One example ...
• 12.2k

• 1,743
Accepted

• 12.2k
1 vote
Accepted

### Extended version of the paper "Consistent Hashing and Random Trees" with proofs

Answering my own question. I found that the authors never published an extended version with proofs. The closest thing to an extended paper is, Rina Panigrahy. Relieving hot spots on the ...
• 141
1 vote

### Reusing 5-independent hash functions for linear probing

Today you should probably use Tabulation hashing for Linear Probing. In The Power of Simple Tabulation Hashing by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees ...
• 958
1 vote

### Reusing 5-independent hash functions for linear probing

One potential issue is when reading from a hash table, the elements should not be read in the order of the slots if all hash tables use the same hash function. This is because those elements, in that ...
• 11.2k

Only top scored, non community-wiki answers of a minimum length are eligible