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 ...
- 50.8k
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 ...
- 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 ...
- 11.1k
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 ...
- 11.1k
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 ...
- 9,595
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 ...
- 11.6k
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 ...
- 11.6k
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 \...
- 11.1k
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):
...
- 131
3
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 ...
- 181
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 ...
- 11.6k
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,\...
- 1,419
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"
- 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 \{...
- 1,733
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 $...
- 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$, ...
- 11.1k
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 ...
- 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.
...
- 11.6k
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 ...
- 11.6k
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 : ...
- 11.1k
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.1k
Only top scored, non community-wiki answers of a minimum length are eligible