The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
65 views

What is the intuition behind simhash?

Why does simhash work? I understand how to implement the hash algorithm, mechanically, from the many articles such as http://matpalm.com/resemblance/simhash/. But is there a simple intuitive ...
5
votes
0answers
183 views

Tuning Parameters of Locality Sensitive Hashing

We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
1
vote
0answers
47 views

Entropy criterion of efficiency for (comparison using hashing)

I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects. E.g., "domain" is the set of valid english phrases with length ...
-3
votes
1answer
142 views

Isn't weakly universal hashing even a stronger than truly random? [closed]

So as far as I know the weakly universal hashing is defined as: for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen ...
3
votes
0answers
50 views

one-way functions vs. secret-coin CRHFs

Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not ...
5
votes
0answers
112 views

Ergodic Theory and Hash Functions

I was thinking about the old question regarding the existence of fixed points in hash functions (for instance, if we restrict the domain of MD5 to $S = \{0, 1\}^{128}$, making it a mapping $S \to S$, ...
2
votes
0answers
125 views

Locality Sensitive Hashing - meaning of a block

I'm reading one of the early LSH papers and I'm a little confused by the meaning of a "block". In particular, in the proof of theorem 1 in section 3.2 (p 522), what are the blocks being pointed to? ...
8
votes
2answers
212 views

Almost universal string hashing in $Z_{2^n}$ and sublinear space

Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$: For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in ...
12
votes
0answers
212 views

How much independence is required for separate chaining?

If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and ...
3
votes
1answer
239 views

What are alternatives to the random oracle model for modelling hash functions?

I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as ...
1
vote
0answers
74 views

Length Extension Attack with a fixed length message [closed]

It's well known that using a hash function as message authentication is vulnerable to length extension attacks. ie. H(key+message) is a bad idea. H(message+key), H(key+message+key) have their issues ...
0
votes
0answers
113 views

count number of i such that ( (a*i+b) mod p) mod k == l

How to determine the number of $i$'s as fast as possible such that $$1\le i \le L$ and $((ai+b)\mod p) \mod k = l$$ where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$. This ...
1
vote
1answer
147 views

fast range summable hash functions

I'm finding is there any range summable hash function. ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of ...
6
votes
1answer
331 views

Continuity vs Uniformity when designing Hash functions

Reading available literature (yep, including wikipedia), I see that hash functions should have (continuity) and map values that differ very little to similar/same hash codes, in particular for (hash ...
15
votes
1answer
468 views

Bloom filter hashes: more or bigger?

In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as ...
7
votes
1answer
2k views

How did Knuth derive A?

When interpreting keys as natural numbers we can use the following formula. \begin{equation} h(k) = \lfloor m (kA\bmod{1}) \rfloor \end{equation} What I am having trouble understanding is how we ...
5
votes
0answers
723 views

Why SHA-224 and SHA-256 use different initial values?

Wikipedia - SHA-2 says SHA-224 is identical to SHA-256, except that: the initial variable values h0 through h7 are different, and the output is constructed by omitting h7. RFC3874 - ...
6
votes
1answer
434 views

Zero knowledge proof for value of a hash function

Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w? In my understanding of the general theorems on zero-k there EXISTS such a function if the ...
13
votes
0answers
296 views

Reusing 5-independent hash functions for linear probing

In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. ...
7
votes
1answer
240 views

Separation between existence of crypto primitives

I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
2
votes
2answers
313 views

Can one reverse a hash with partial plaintext knowledge?

First off, please forgive my ignorance because I am not as well versed in cryptography and mathematics as I would like to be. I may say something obviously wrong/dumb; please point it out! Is there ...
0
votes
1answer
1k views

Minimal perfect hash function from sets of integers to integers

I would like to be able to map any subset of $S = \{0,..,m-1\}$ to an integer $k$. $m$ will probably be 32 because $|\mathcal{P}(S)| = 2^m$ and i want to use a variable with 32 bits to store this ...
7
votes
0answers
257 views

State of research on SHA-1 Collision Attacks

SHA-1 security has been discussed since an algorithm for finding collisions was first published at CRYPTO 2004 and has been subsequently improved. Wikipedia lists a couple of references, however it ...
3
votes
3answers
1k views

Is it possible to generate a collision free hash function from an equality function?

I'm wondering if it's possible to go from an arbitrary equality function: Eq :: (obj, obj) -> bool to an identity/collision-free hash function: ...
1
vote
2answers
1k views

How to compute Integer Hash of a string [closed]

Is it possible to convert a string to a unique number. Similar to any hashing algorithm (MD5, SHA-1 and SHA-2), I want to compute a unique integer value for an arbitrary length string, which should ...
-1
votes
1answer
471 views

Password checking algorithm

Usually to check password validity we used to create over given password it hash value and compare it with stored one. So password protection relies on strength of hashing function. Could it be used ...
2
votes
1answer
308 views

Getting started with Hashing for Information retrieval

I recently finished my bachelors and now work on Cross-lingual language search. I want to get started in hashing and see how they are useful in information retrieval. (Yes, I know what hashing is), ...
10
votes
1answer
525 views

Do 'reflexive' hash algorithms exist?

Is there a class of hash algorithms, whether theoretical or practical, such that an algorithm in the class might be considered 'reflexive' according a definition given below: hash1 = algo1 ( "input ...
3
votes
1answer
355 views

Collision Attacks, Message Digests and a Possible solution

I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 ...
10
votes
2answers
748 views

How do I choose a functional dictionary data structure?

I've read a bit about the following data structures: Bagwell's Ideal Hash Tries Larson's Dynamic hash tables Red-Black trees Patricia trees ...and I'm sure there are a lot of others out there. ...
23
votes
3answers
2k views

Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally: It uses O(1) space It can be updated to reflect an insertion or deletion in ...
9
votes
2answers
463 views

What is the optimal data structure for a tree of maps.

I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a ...
3
votes
1answer
196 views

How is DHT different than regular hash tables in context to data/node lookup?

How is DHT different than regular hash tables in context to data/node lookup? This (introduction, 3rd paragraph) paper says: First, in addition to the insertion and deletion of items, DHTs must ...
9
votes
2answers
644 views

Hashing sets of integers for inclusion testing

I'm looking for a hash function over sets H(.) and a relation R(.,.) such that if A is included in B then R(H(A), H(B)). Of course, R(.,.) must be easy to verify (constant time), and H(A) should be ...
5
votes
2answers
259 views

How is rebalancing of DHTs handled in case of failure or addition of new node?

I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say: A new node is added to the cluster (since all the nodes are full) then the ...
14
votes
3answers
403 views

Associative hash mixing

Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
12
votes
3answers
3k views

What is the difference between a second preimage attack and a collision attack?

Wikipedia defines a second preimage attack as: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1). Wikipedia defines a collision attack as: find two ...
13
votes
1answer
504 views

Why is it important that the secret is at the end when signing with MD5?

it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?