Questions tagged [hash-function]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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(...
jonderry's user avatar
  • 747
31 votes
3 answers
19k 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 ...
Thomas Owens's user avatar
16 votes
1 answer
573 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?
Hendrik Brummermann's user avatar
15 votes
1 answer
654 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 ...
Jay Hacker's user avatar
15 votes
3 answers
717 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 ...
Per Vognsen's user avatar
  • 2,161
15 votes
2 answers
575 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. (...
jbapple's user avatar
  • 11.2k
14 votes
1 answer
339 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 ...
jbapple's user avatar
  • 11.2k
11 votes
2 answers
926 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 ...
Alexandru's user avatar
  • 696
11 votes
1 answer
367 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 ...
Johannes Rudolph's user avatar
10 votes
2 answers
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 ...
Jason's user avatar
  • 397
10 votes
1 answer
800 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 ...
user avatar
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 ...
netvope's user avatar
  • 201
9 votes
2 answers
1k 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 ...
phreeza's user avatar
  • 93
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 ...
ChaosPandion's user avatar
9 votes
2 answers
352 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 \...
jbapple's user avatar
  • 11.2k
7 votes
1 answer
414 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 ...
Kaveh's user avatar
  • 21.6k
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-...
Clion's user avatar
  • 71
7 votes
2 answers
128 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) \...
jbapple's user avatar
  • 11.2k
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 ...
Jarek Duda's user avatar
6 votes
1 answer
221 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, ...
templatetypedef's user avatar
6 votes
1 answer
470 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 ...
RDN's user avatar
  • 325
6 votes
1 answer
679 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 ...
luis.espinal's user avatar
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 ...
Thomas Ahle's user avatar
5 votes
2 answers
899 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 ...
zengr's user avatar
  • 457
5 votes
0 answers
88 views

Does there exist a cryptographic associative hash function?

Does there exist a function $f(x,y)$ with these properties: Computing $f(x,y)$ is in P. $f$ is associative: $f(x, f(y, z)) = f(f(x, y), z)$. $f$ is one-way (assuming P $\neq$ NP): Given the value ...
Dale's user avatar
  • 251
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) ...
Kagura Hitoha's user avatar
5 votes
0 answers
488 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$ ...
Ram's user avatar
  • 639
5 votes
0 answers
258 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$, ...
Charles Fu's user avatar
4 votes
1 answer
807 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 ...
Simd's user avatar
  • 3,902
4 votes
0 answers
132 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 ...
user65356's user avatar
4 votes
0 answers
161 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 ...
templatetypedef's user avatar
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: ...
microsage's user avatar
3 votes
1 answer
267 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 ...
zengr's user avatar
  • 457
3 votes
1 answer
92 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 ...
R B's user avatar
  • 9,448
3 votes
1 answer
101 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$-...
AmeerJ's user avatar
  • 679
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')
Vinay's user avatar
  • 33
3 votes
1 answer
237 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 ...
Dave's user avatar
  • 183
3 votes
1 answer
146 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$ ...
NotSo Smart's user avatar
3 votes
2 answers
240 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 ...
ngub05's user avatar
  • 141
3 votes
1 answer
628 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 ...
Dominar's user avatar
  • 41
3 votes
0 answers
131 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 \...
delete000's user avatar
  • 818
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 ...
user avatar
2 votes
2 answers
565 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 ...
dss539's user avatar
  • 123
2 votes
1 answer
88 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) \, (...
catalyst's user avatar
2 votes
2 answers
319 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-...
D.W.'s user avatar
  • 12.1k
2 votes
2 answers
13k 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 ...
Shani's user avatar
  • 121
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 ...
treisenegger's user avatar
2 votes
1 answer
345 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), ...
crazyaboutliv's user avatar
2 votes
0 answers
48 views

Do prefix hash functions work well for approximate counting?

Given some set $S \subseteq \{0,1\}^n$, suppose we want to approximate $|S|$. One approach is hashing-based approximate counting, which exploits the structure of hash functions to approximately halve $...
Germ's user avatar
  • 191
2 votes
0 answers
113 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 ...
botsina's user avatar
  • 101