Skip to main content
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 ...
David Eppstein's 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 ...
kelalaka's user avatar
  • 206
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 ...
jbapple's user avatar
  • 11.2k
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 ...
jbapple's user avatar
  • 11.2k
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 ...
Neal Young's user avatar
  • 10.8k
3 votes
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 ...
D.W.'s user avatar
  • 12.2k
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 ...
D.W.'s user avatar
  • 12.2k
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 \...
jbapple's user avatar
  • 11.2k
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): ...
Ian Boyd's user avatar
  • 131
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 ...
D.W.'s user avatar
  • 12.2k
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,\...
Andrew Morgan's user avatar
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"
SamM's user avatar
  • 1,685
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 \{...
William Hoza's user avatar
  • 1,743
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 $...
lacker's user avatar
  • 256
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$, ...
jbapple's user avatar
  • 11.2k
2 votes
Accepted

Query Phase of Multi-Level Hashing

In locality-sensitive hashing, we generally concatenate a certain number of independently-drawn hash functions to get a single hash. This is most important for an LSH with a constant collision ...
SamM's user avatar
  • 1,685
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. ...
D.W.'s user avatar
  • 12.2k
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 ...
D.W.'s user avatar
  • 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 ...
ngub05's user avatar
  • 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 ...
Thomas Ahle's 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 ...
jbapple's user avatar
  • 11.2k

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