# Tag Info

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

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 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: ... 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! 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, \...

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

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

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

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?

2

As much as you're being downvoted and attacked, you've nearly reinvented bcrypt. Let's say we have encryption algorithm (doesn't matter which one): blowfish Then generate random sequence of chars consisting predefined array (for instance just random sequence of digits) A sequence of 24 characters; an even multiple of the 8-byte blocksize of blowfish: ...

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

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 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 ... 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 ... 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 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 as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well. Tabulation hashing is also a lot faster than even ... 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

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

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