# Tag Info

## Hot answers tagged hash-function

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 ...
• 50.2k
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

• 11k

### Far point queries in high dimensions

See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on ...
• 9,556
Accepted

### How much independence is required for separate chaining?

Apparently not. "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [...
• 11k
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 ...
• 10.4k

### Password checking algorithm

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

### Zero knowledge proof for value of a hash function

There is an elegant and rather efficient zero-knowledge protocol for these kinds of NP statements given in this paper: Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: Zero-Knowledge Using Garbled ...
• 2,789

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

Carter and Wegman cover this in New hash functions and their use in authentication and set equality; it's very similar to what you describe. Essentially a commutative hash function can be updated one ...
• 171
Accepted

### Does this pairwise independent random process have expected max load $\sqrt{n}$?

The hash family you give has expected max load $\tilde{O}(n^{1/3})$, as shown in this recent paper: Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"
• 1,427

• 256

• 11k
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

### Sketches, using ideal hash functions

Another reason for not using cryptographic algorithms in practice is speed. In the streaming setting, we typically do not want to spend too long processing each item in the stream. Computing k ...
• 111
1 vote

### Sketches, using ideal hash functions

The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be ...
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 ...
• 778
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 ...
• 11k

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