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