# Questions tagged [hash-function]

For questions about hash functions: functions from a big set to a smaller one such that the same output $f(x_1)=f(x_2)$ for different input $x_1\ne x_2$ is unlikely, especially if $x_2$ differs from $x_1$ by a random error or is crafted by an adversary.

175 questions
18 views

### A more general case of pairwise hash functions

I want to find a set $H = \{x\mid x=(x_1, x_2, \ldots, x_k), x_i \in \{0, 1, \ldots, k-1\}\}$, which is pairwise independent(every $x_i$ and $x_j$ of the vector $\mathbf x$ in the set, it's $k^2$ ...
1k views

### What's the difference between a fingerprint and a hash?

My understanding is that both a fingerprint and a hash are functions that take as input some arbitrarily long bitstring, and output a bitstring of a fixed size. The Wikipedia page for Hash Functions ...
26 views

### Universal hashing family

I'm not really sure this question is proper for MathExchange but I have found it more suitable than StackOverFlow. So, I'm taking the course of Data Structures and Algorithms and we got some example ...
13 views

### perfect hashing when not knowing the keys

knowing only the number of keys, n, how can you create a data structure of some sort that satisfies the following: initialization takes O(n) time after being initialized, you can insert and search ...
13 views

### Hash proof system programming implementation

Does anyone know if there is a hash proof system implementation using some programming language? Like C++, python.
1k views

### Proof of calculating MinHash

I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for ...
12 views

### Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
25 views

### Approximating a probability threshold for hash collisions

First off: I know this is on the verge of being subjective and i'll try my best to make it as specific as possible. I am in a situation where I need to generate a fixed number of hashes (k), say 10,...
46 views

### How can I increase the complexity of a number and maintain uniqueness

I have an 8-digit number and you have an 8-digit number - I want to see if our numbers are the same without either of us passing the other our actual number. Hashing the numbers is the obvious ...
485 views

### Toy cryptographic hash function for education purposes?

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for ...
15 views

55 views

### An m-dimensional space with each 'point' in the space having an n-dimensional value

Say I have an $m$-dimensional space (continuous or discrete) such that every point in that space has a value, and that value is an $n$-dimensional vector (continuous or discrete). My question is how ...
43 views

### Days required to collide at least one hash? [closed]

Sorry I am new here and learning mathematics and cryptographic problems. Assume an hash algorithm is collision resistant like SHA256, and the hash value is 64bit in length, (2^{64} possibilities) ...
101 views

### Hash without overflow

I am trying to hash an $n$-character string into one of $m$ slots by treating the string as radix-128 number without overflowing a 32-bit word, where $0 < m < 2^{31}$. I utilize the properties ...
125 views

575 views