Questions tagged [hash-function]
The hash-function tag has no usage guidance.
62
questions
37
votes
4answers
9k 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(...
26
votes
3answers
14k 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 arbitrary ...
16
votes
1answer
559 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?
15
votes
1answer
611 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 ...
15
votes
2answers
458 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. (...
14
votes
3answers
587 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 ...
14
votes
1answer
314 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
votes
1answer
362 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 ...
11
votes
1answer
736 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 ...
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 ...
10
votes
2answers
804 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 ...
9
votes
2answers
938 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 ...
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
2answers
325 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 \...
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
1answer
351 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 ...
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-...
7
votes
1answer
65 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) \...
6
votes
2answers
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 ...
6
votes
1answer
206 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, ...
6
votes
1answer
364 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 ...
6
votes
1answer
564 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 ...
5
votes
2answers
732 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 whole ...
5
votes
0answers
393 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$ ...
5
votes
0answers
206 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$, ...
4
votes
1answer
603 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 ...
4
votes
0answers
87 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 ...
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:
...
3
votes
1answer
259 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 ...
3
votes
1answer
72 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 ...
3
votes
1answer
132 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')
3
votes
1answer
118 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$ ...
3
votes
2answers
174 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 ...
3
votes
1answer
529 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 ...
3
votes
0answers
64 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 ...
2
votes
2answers
436 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
2answers
256 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-...
2
votes
2answers
8k 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 ...
2
votes
1answer
116 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 ...
2
votes
1answer
340 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), ...
2
votes
0answers
86 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 ...
2
votes
0answers
43 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 ...
2
votes
0answers
162 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? ...
1
vote
1answer
323 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 ...
1
vote
1answer
66 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 ...
1
vote
1answer
205 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 ...
1
vote
0answers
62 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 ...
1
vote
0answers
178 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
vote
0answers
80 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
60 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$ ...
