9 votes
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 ...
user avatar
9 votes
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 ...
user avatar
  • 206
8 votes
Accepted

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

Here's how to do it. First, choose a random $k$ between 1 and $n$ to be the "crowded bin". Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$. Now, for $1 \leq i \leq n-1$, $$ \mbox{put ...
user avatar
7 votes
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 ...
user avatar
  • 11k
5 votes

Why SHA-224 and SHA-256 use different initial values?

This We called Domain Separation, when we use same algorithm for different output size. Separation is necessary because if i found two messages which have hash value (SH256), differs only in last ...
user avatar
  • 51
4 votes
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 ...
user avatar
  • 8,223
4 votes

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 ...
user avatar
  • 11k
3 votes
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 ...
user avatar
  • 10.4k
3 votes
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 \...
user avatar
  • 11k
3 votes

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 ...
user avatar
3 votes
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 [...
user avatar
  • 11k
3 votes
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 ...
user avatar
  • 10.4k
3 votes

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): ...
user avatar
  • 131
2 votes

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 ...
user avatar
  • 2,789
2 votes

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 ...
user avatar
  • 171
2 votes
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"
user avatar
  • 1,427
2 votes

Notion similar to k-wise independence

You can do it with the isolation lemma. Here are the important details (admittedly hastily written): We'll imagine picking a hash function from $H$ as follows: first, pick $w_1^0,\ldots,w_n^0,w_1^1,\...
user avatar
2 votes
Accepted

Zero Knowledge proofs of knowledge

Yes. The simplest way to understand this is to understand the zero-knowledge proof that you know a 3-coloring of a graph. 3-coloring is NP-complete, so an arbitrary hash function $h$ and target value $...
user avatar
  • 256
2 votes

Family of functions with properties similar to k-wise independent hash functions

Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family $\mathcal{H} \subseteq \{...
user avatar
  • 1,733
2 votes
Accepted

Optimal random bits complexity for universal hashing

I believe the best known bound is in Woelfel's "Efficient strongly universal and optimally universal hashing", Theorem 5, which presents a set with $M = N + \lfloor (N - P)/2 \rfloor - 1$, ...
user avatar
  • 11k
1 vote

Are perceptual hashes connected to audio/video compression?

In practice there are significant differences: many perceptual hashes aren't (designed to be) reversible, and perceptual hashes usually map to a much lower-dimensional space than video compression. ...
user avatar
  • 10.4k
1 vote

Complexity of solving systems of linear equations with hash preimages

It depends what you mean by "arbitrary cryptographic hash function". If you care about practical cryptography, I think the most natural interpretation is to model $H$ as a random oracle (i.e., the ...
user avatar
  • 10.4k
1 vote

Shoup-style hashing without one-wayness

Here is a partial answer: Sometimes $H'$ is almost universal, but not always. For an example of an $H$ that makes $H'$ almost universal, let $D$ be a field and consider $H_R = \{ h_x(a,b) = a + bx : ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 11k

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