Questions tagged [hash-function]
The hash-function tag has no usage guidance.
73
questions
0
votes
2
answers
33
views
Combining different length epsilon-ADU hash function families
For context, an $\epsilon$-almost delta universal ($\epsilon$-ADU) hash function family $\mathcal{H} = \{h : M \to D\}$ hashes inputs from $M$ to digests in $D$ such that
for any distinct $m, m' \in M$...
- 720
2
votes
1
answer
78
views
Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing
$\newcommand{\bigparen}[1]{\Bigl ( #1 \Bigr )}$
I'm working with polynomial hashes $H$ defined by the pair $(B, M)$ (base, modulo):
$$H_{B, M}(s) \equiv \sum_{i=0}^{n-1} B^{n-1-i} \cdot conv(s_i) \, (...
- 23
3
votes
0
answers
122
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 778
6
votes
0
answers
133
views
Consistent Sampling a Random Walk
Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid.
I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
- 958
1
vote
1
answer
94
views
Query Phase of Multi-Level Hashing
I am trying to understand the fundamentals of multilevel Locality Sensitive Hashing. It is defined in the paper paper (page no-6).
A Multi-level LSH data structure for $S$ is set up in the following
...
- 113
4
votes
0
answers
117
views
How many bits are required to sample an almost pairwise independent hash function?
A family of functions $\mathcal{H} = \{ h\colon \{0,1\}^n \to \{0,1\}^m \}$ is said to be $\varepsilon$-almost pairwise independent if, for every distinct $x_1,x_2 \in \{0,1\}^n$ and (not necessarily ...
- 41
0
votes
1
answer
106
views
Are perceptual hashes connected to audio/video compression?
Without loss of generality, I'll only talk about video, but this should apply to any sort of signal.
A perceptual hash function (WP) maps videos to fingerprints such that each fingerprint's preimage ...
- 271
0
votes
0
answers
61
views
Reference Request : Accessible reference for Randomised algorithms and Hashing for non-Computer Scientists?
My goal is to understand well a paper like ApproxMC. It discusses the use of Hash functions for Propositional Model Counting. In my understanding what they call hash functions are just random XOR's ...
- 706
3
votes
1
answer
98
views
Optimal random bits complexity for universal hashing
Let $Q_N:=\{0,1\}^N$ denote the $N$-dimensional Hamming cube. Let $a\in Q^N$ and $X\sim\mathrm{Unif}(Q^M)$ be input and random bits respectively, and function $f$ maps the the joint space to the $P$-...
- 679
0
votes
0
answers
190
views
"Fair" hash functions
Motivation. When I use a hash function, I would like my pre-images (original values) to a given output (hash) to be evenly distributed as it could be that an uneven distribution could make guessing / ...
1
vote
1
answer
119
views
Fibers of hash functions
Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\...
2
votes
0
answers
109
views
Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea) [closed]
To conform with the CS Theory SE crossposting rules, I've created a separate post for dequantizing Shor's algorithm (discussion on the Quantum Computing Stack Exchange was mostly about Shor's ...
- 101
0
votes
1
answer
89
views
Can a result of (any) hash algorithm contain the hash result itself? [closed]
Suppose you have a file of 240 lines. Any lines, any content.
You then calculate the hash of that file, let's say MD5, and the result is something in the following structure:
...
- 103
1
vote
0
answers
107
views
Sampling from a family of hash functions, not uniformly at random?
Many algorithms and data structures assume access to a family of hash functions satisfying some nice property (say, $k$-independence or $k$-universality). In these cases, we usually assume that we ...
- 2,121
3
votes
1
answer
188
views
Zero Knowledge proofs of knowledge
Is there Zero Knowledge Proof of Knowledge protocol for Hash function? (If h(v)=w) without revealing v to the anyone can we prove that we know 'v')
- 33
2
votes
1
answer
178
views
Complexity of solving systems of linear equations with hash preimages
Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are ...
- 31
3
votes
1
answer
220
views
Family of functions with properties similar to k-wise independent hash functions
I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
- 183
1
vote
0
answers
184
views
Can a hash preimage be used to amplify BPP probabilities?
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample a number $...
- 1,063
4
votes
0
answers
150
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 ...
- 2,121
1
vote
0
answers
106
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 \...
- 21
1
vote
0
answers
121
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$ ...
- 729
3
votes
1
answer
89
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 ...
- 9,438
-1
votes
1
answer
51
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' ...
6
votes
2
answers
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 ...
- 325
0
votes
1
answer
91
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 ...
- 3,950
0
votes
1
answer
145
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 ...
- 101
1
vote
1
answer
342
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 ...
- 131
3
votes
1
answer
141
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$ ...
- 31
6
votes
1
answer
218
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, ...
- 2,121
7
votes
2
answers
127
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) \...
- 11.2k
3
votes
2
answers
229
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 ...
- 141
-1
votes
1
answer
422
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 ...
- 109
1
vote
1
answer
68
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 ...
- 958
4
votes
1
answer
771
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 ...
- 3,950
2
votes
2
answers
312
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-...
- 11.7k
1
vote
0
answers
630
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 ...
- 111
5
votes
0
answers
483
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$ ...
- 639
1
vote
0
answers
89
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 ...
- 11
-3
votes
1
answer
324
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 ...
- 95
3
votes
0
answers
68
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 ...
user6973
5
votes
0
answers
252
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$, ...
- 193
2
votes
0
answers
166
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? ...
- 21
9
votes
2
answers
350
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 \...
- 11.2k
14
votes
1
answer
338
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 ...
- 11.2k
6
votes
1
answer
457
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 ...
- 315
1
vote
0
answers
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 ...
- 19
0
votes
0
answers
124
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 ...
- 121
1
vote
1
answer
234
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 ...
- 121
6
votes
1
answer
668
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 ...
- 183
15
votes
1
answer
647
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 ...
- 303