Questions tagged [hash-function]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
0 answers
56 views

How to prove that all pairwise independent hashing circuits are superconcentrators?

It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) ...
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$...
3 votes
0 answers
126 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 \...
2 votes
1 answer
80 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) \, (...
6 votes
0 answers
135 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 ...
1 vote
1 answer
96 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 ...
0 votes
1 answer
114 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 ...
4 votes
0 answers
127 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 ...
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) \...
3 votes
1 answer
230 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 ...
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 ...
0 votes
2 answers
1k 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 ...
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$-...
0 votes
0 answers
199 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 $\...
15 votes
2 answers
574 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. (...
2 votes
0 answers
111 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 ...
1 vote
0 answers
109 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 ...
0 votes
1 answer
90 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: ...
3 votes
1 answer
189 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')
2 votes
1 answer
182 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 ...
3 votes
3 answers
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: ...
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 ...
1 vote
0 answers
185 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 $...
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 ...
4 votes
0 answers
156 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
0 answers
107 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
0 answers
124 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$ ...
11 votes
1 answer
366 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 ...
-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' ...
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 votes
2 answers
234 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 ...
0 votes
1 answer
146 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
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 ...
41 votes
4 answers
13k 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(...
6 votes
1 answer
463 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 ...
3 votes
1 answer
142 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
1 answer
219 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, ...
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 \...
-1 votes
1 answer
423 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
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 ...
4 votes
1 answer
776 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 ...
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 ...
10 votes
1 answer
3k 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 ...
9 votes
1 answer
7k 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 ...
7 votes
2 answers
2k 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-...
2 votes
2 answers
315 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 votes
1 answer
3k 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 ...
1 vote
0 answers
633 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
0 answers
484 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$ ...