We’re rewarding the question askers & reputations are being recalculated! Read more.
19

See exercise 9 of section 6.4 of The Art of Computer Programming. Any irrational $A$ would work, because $\{kA\}$ breaks up a largest gap of $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ (I use the notation $\{x\}$ for $x\mod 1$). But if $A = \phi^{-1}$ or $A = \phi^{-2}$, it has a special property: these are the only values for which neither of the two newly ...


16

You're right to think of hash functions in terms of "random bits produced". So if you have a hash function that produces a 64 bit hash, you can treat is as 4 16-bit hashes (by splitting), and so on. For the scheme described above (which should be attributed to Dillinger and Manolios; Kirsch/Mitzenmacher just analyzed it), that means you're correct; if ...


10

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

(I am interpreting this question in the following way due to the comments.) In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings. This situation is troublesome for formal analyses (reductions) of these systems because, when ...


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-...


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 ...


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: ...


7

In the rump session of Crypto 98, Hal Finney provided a talk which might be of your interest. The title is "A zero-knowledge proof of possession of a pre-image of a SHA-1 hash." I have not found any transcripts., but the video is available on both YouTube and Google Videos. (the videos are no longer available; see the comments below.) The video is now ...


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

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 ...


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

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

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 $...


2

While continuity in a strong sense is probably too much to ask for, locality sensitive hashing (LSH) achieves a very similar goal: given a set of items $x_1, \ldots, x_n$ which belong to some metric space with metric $d$, an LSH family of hash functions (parametrized by $D, c, p, q$) maps $x_i$ and $x_j$ into the same bucket with probability $\geq p$ if $d(...


2

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})$".


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. ...


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 ...


1

I have found the newest one that gives 7-wise independence using MR code, also two others based on BCH and EH code with 3-wise independence. They are tested to be good enough for AMS sketch in this paper


1

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 ...


1

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 order, can cause the insert procedure on a smaller hash table with the same hash function to go quadratic, assuming that the max fill factor is over $1/2$. See: ...


1

What functional dictionary data structures are important to know about? Height-balanced binary trees and tries of them are a good all-round compromise. Also: Patricia trees. Hash tries. What are the pros and cons of these approaches? Height-balanced binary trees and tries of them are a good all-round compromise for atomic keys. Tries are the same for ...


1

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 ...


1

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 ...


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