A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [hash-function]

The tag has no usage guidance.

56 questions
Filter by
Sorted by
Tagged with
172 views

53 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$ ...
68 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 ...
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' ...
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 ...
76 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 ...
98 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 ...
314 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 ...
112 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$ ...
200 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, ...
64 views

287 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 ...
352 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 ...
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 ...
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 ...
198 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 ...
538 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 ...
592 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 ...
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 ...
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 ...
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-...
402 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. (...
336 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 ...
422 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 ...
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 ...
342 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 ...
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: ...
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 ...
692 views

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 ...
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), ...
686 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 ...
496 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 ...
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 ...