9

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 that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make ...


9

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 ball } i \mbox{ into bin } \begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\ k + \pi(i) \mbox{ with probability }1 - \frac{...


9

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 enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-...


7

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 element is optimal. See "Hash, displace, and compress" "Improved Bounds For Covering Complete Uniform Hypergraphs" Data Structures and Algorithms , Vol. 1: ...


5

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 octet and then i can publish the hash value as first 7 octet showing i used SHA224. since i already have two messages colliding on SHA224 which i can use later for ...


5

Yes. Wegman and Carter's "New hash functions and their use in authentication and set equality" (mirror) shows a scheme meeting the requirements stated (almost universal, over $\mathbb{Z}_{2^b}$, sublinear space and randomness, linear evaluation time) based on a small number of hash functions drawn from a strongly universal family. This is sometimes called "...


4

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 answer is yes -- take 240 lines with total parity 0. But the answer is no if the hash function is defined by $$f(x_1, x_2, \ldots, c_n) = \neg (x_n \oplus f(x_1, \...


4

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 more expensive than 1.79 bits per key!


3

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 \epsilon} + 2(1+\epsilon)^ {1-(2T-1)/3} <p $$ where the two sub-tables are of size $n(1+\epsilon)$. So for $p = 9/10$, $T=8$, and $n=1,000,000$, we get $\...


3

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 construction is to let $\mathbb{G}$ be a group with group operation $*$ and let $h:\{0,1\} \to \mathbb{G}$ be an arbitrary function, then extend $h$ to a function $...


3

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 split the input $x$ up into blocks $x_1,\dots,x_n$, then compute $$h_i = F(x_i,h_{i-1})$$ where $h_0$ is a constant and $h_n$ is used as the output of the hash ...


3

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 [heaviest loaded bin] size $\Omega(n^{1/k})$".


3

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 the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web... http://dblp.org/...


3

No, "weakly universal" is not a stronger requirement than "truly random". There are hash functions that satisfy the former but not the latter, e.g., $h(x) = ax+b$ over a finite field. As far as whether "weakly universal" is a "quite strong" requirement, I guess that depends on your definition of "quite strong", now, doesn't it?


3

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): I'll choose blowfish. Then generate random sequence of chars consisting predefined array (for instance just random sequence of digits) I'll pick a sequence ...


2

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 element at a time for insertions and deletions, and high probability matches, in O(1).


2

One solution is to use Merkle hashing. Use an immutable/persistent binary tree data structure. Annotate each leaf node with the hash of the data contained within that leaf. Annotate each internal node with the hash of the hashes on its two children. In other words, if $n$ is an internal node with children $n',n''$, and they have been annotated with the ...


2

The almost-universal family of hash functions $$\{h_a(\vec{x}) = \sum a^i x_i \bmod p: a \in \mathbb{Z}_p\}$$ has a nice property here: $h_a(\vec{x}) + a^{|\vec{x}|}h_a(\vec{y}) = h_a(\vec{x} \circ \:\vec{y})$, where "$\circ$" denotes concatenation. If you cache at the root of each tree both its hash value and $a^{|\vec{x}|}$, you can calculate the hash of ...


2

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 Circuits: How To Prove Non-Algebraic Statements Efficiently (CCS 2013) In fact, SHA-256 preimage is the example they list in the abstract. Maybe this old ...


2

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 \{0, 1\}^n$ consists of an $\varepsilon$-biased set for a suitable $\varepsilon = \ell^{-\Theta(k)}$. Explicit constructions of such a hash family are known with ...


2

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"


2

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,\ldots,w_n^1$ uniformly and independently from integer weights in $[1,4n]$. Then pick a threshold $T$ in $[1,4n^2]$ also uniformly and independently at random. ...


2

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 $w$ can be represented as a graph where knowing a 3-coloring for that graph is equivalent to knowing a $v$ such that $h(v) = w$. That isn't the most efficient ...


2

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$, where $P$ is the number of bits in the codomain.


1

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 random oracle model for hash functions). In this setting, the problem is hard. As a lower bound, it requires exponential running time. To prove this, let $u=(1,...


1

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 : x \in D\}$. $H_R$ is universal: Consider $(a,b) \neq (c,d)$. If $b \neq d$, then $(\Pr_x h_x(a,b) = h_x(c,d)) = (\Pr_x a + bx = c + dx) = (\Pr_x (b-d)x = c-a) =...


1

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 worldwide web. 1997. 1 which was the Master's thesis of Rina Panigrahy (under Prof. Karger & Prof. Smith), who's also a co-author of the paper under discussion. ...


1

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 cryptographic hash functions will be much more expensive than computing k fast non-cryptographic hash functions, e.g. MurmurHash. In practice, I think most people use ...


1

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 avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of ...


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