Questions tagged [hash-function]
The hash-function tag has no usage guidance.
1
vote
0answers
121 views
Can a hash preimage be used to amplify BPP probabilities?
Suppose we have an algorithm in $\mathrm{BPP}$ to decide membership in a language $L$. Normally we amplify the probability of accepting and rejecting members correctly by running our algorithm ...
4
votes
0answers
62 views
What degree of hash function independence is needed for Bloom filters?
In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
1
vote
0answers
71 views
LSH Probabilistic guarantees
A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:
$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and
$\lVert x-y\rVert > cr \quad \...
1
vote
0answers
50 views
Why do k min-hashes, instead of one hash where we find the k minimum elements?
Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of $k$ permutation for comparison purposes, and then takes number_of_collisions / $k$ ...
3
votes
1answer
57 views
What is the maximal load of a “latency-bounded” Cuckoo Hash?
Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time.
They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
-1
votes
1answer
38 views
Hash-containing Binary Tree?
I saw the question somewhere "Binary tree vs hash table, which one is better?"
And then I thought - "Why not both? Why not combine the two and create a binary tree where each node contains a 'number' ...
4
votes
1answer
2k views
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.
Popular Bloom filter instead of marking just 1 hash ...
0
votes
1answer
74 views
Does this pairwise independent random process have expected max load $\sqrt{n}$?
This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in ...
0
votes
1answer
94 views
is Zero knowledge Proof same as commitment schemes? [closed]
I am studying about the zero knowledge proofs and I am looking for a practical (example based) approach to undrestand its process. I have studied the theory a little bit and I find it interesting yet ...
1
vote
1answer
277 views
“Linear” hashing function
Say we have two chunks of data $X$ and $Y$, which may be of different sizes, is there a non-trivial function $hash$, and operation $*$, such that:
$$hash(X+Y) = hash(X) * hash(Y)$$
...where $+$ is ...
3
votes
1answer
110 views
Notion similar to k-wise independence
I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ ...
6
votes
1answer
195 views
Two papers give contradictory bounds on linear probing. How do I resolve the disparity?
I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, ...
7
votes
1answer
60 views
Shoup-style hashing without one-wayness
Let $H$ be an almost universal hash family of functions from $D^2$ to $D$. For any functions $f,g \in H$ define the function $\langle f,g \rangle : D^4 \to D$ by $\langle f,g \rangle(a,b,c,d) \...
3
votes
2answers
166 views
Extended version of the paper “Consistent Hashing and Random Trees” with proofs
I've been reading the following paper:
David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for ...
-1
votes
1answer
322 views
Load factor of a hashtable: Why not resize based on number of actual buckets used? [closed]
From what I read, the load factor of a hashtable is defined as n/N where n=number of items N=Number of buckets in the hash table
Its recommended you increase the size of your hashtable when load ...
1
vote
1answer
65 views
Far point queries in high dimensions
Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".
This is ...
5
votes
1answer
501 views
Example of pairwise independent random process with expected max load $\sqrt{n}$
This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ...
2
votes
2answers
219 views
Sketches, using ideal hash functions
I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.). They use hash functions that are required to be 2-...
1
vote
0answers
541 views
What is the intuition behind simhash? [closed]
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
342 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
78 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
216 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
63 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
197 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
161 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? ...
9
votes
2answers
293 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 \...
13
votes
1answer
278 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 ...
6
votes
1answer
347 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
77 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
120 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
196 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
524 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
579 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 ...
9
votes
1answer
5k 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 ...
9
votes
1answer
2k 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 - A ...
7
votes
2answers
1k 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 has-...
14
votes
1answer
394 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
330 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
411 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 ...
-2
votes
1answer
2k 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 ...
11
votes
1answer
339 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:
...
2
votes
2answers
6k 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
659 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
339 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), ...
11
votes
1answer
676 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
489 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
1k 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. I've ...
36
votes
4answers
8k 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 O(...
9
votes
2answers
868 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 ...
