Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
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$ ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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.
1
vote
2answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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,...
2
votes
3answers
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 ...
3
votes
2answers
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 ...
0
votes
0answers
15 views

ElGamal Hash Function

The ElGamal signature scheme presented is weak to a type of attack known as existential forgery. Here is the basic existential forgery attack. Choose $u,v$ such that $\gcd(v, p — 1) = 1$. Compute $r = ...
0
votes
0answers
15 views

Probability of Hashing function to be perfect

Suppose we have a table of size M and we want to map N elements using a hashing function. This question had a lot of sub parts - The first one was that find the expected number of collisions which I ...
3
votes
0answers
528 views

Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
0
votes
1answer
889 views

is it possible to hash a range?

OK. I am not a math guy. I'm a programmer, so forgive me for the non-math lingo. let's say I have 3 ranges ...
2
votes
1answer
82 views

Why Proof of Work is Hard

I am finally beginning to understand how Proof of Work (PoW) works, and am wondering briefly why it is considered "hard" mathematically to solve. The whole goal of it (it sounds like) is for it to ...
0
votes
1answer
29 views

True or False: After inserting '(2/3)m' elements into a hash table of size 'm', the probability of a collision upon the next insertion is at least 1/2

I was asked this question today, and my initial thought was - let's check a numeric example. So $m$ is obviously a multiple of $3$, and the smallest possible value is $m=3$. I divided the sample ...
1
vote
0answers
21 views

Non-reversible primitive operations on integers [closed]

Along the lines of How to map 256 unique strings to 256 unique but effectively arbitrary integers, I am wondering how to generate basically a hashing function. For this question I am wondering if ...
0
votes
1answer
198 views

Expected maximum number of collisions for universal hash function

If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide? We break down this computation into a sequence ...
1
vote
1answer
464 views

How to prove pairwise independence of a family of hash functions?

I want to prove pairwise independence of a family of hash functions, but I don't know where to start. Given the family of hash functions: H with h(x) = a * x + b (mod M). ( Say h: U -> V, then: M ...
5
votes
2answers
11k views

How can I convert this unique string of characters into a unique number?

I have an unusual programming problem and the math side of it has me stumped. It's probably a simple answer but math isn't my strongest area. I've generated a unique string of 7 characters which are ...
0
votes
1answer
20 views

Hash function that describe solid tetromino in the table

I'm trying to find a hash function that describes solid tetromino in a matrix 4x4 consisting of '0' and '1'. Here is what I mean: 1) 1111 0000 0000 0000 - solid tetromino, all this ones have the same ...
1
vote
1answer
47 views

Given a boolen hash function (based on XOR), find the $n^{th}$ key for a specific hash.

A boolen hash function is given that takes a hexadecimal key as input and returns the hash for that key (hash can be only 0 or 1). The hash function is based on XORing bits of the key. For example, ...
0
votes
1answer
29 views

Distinguishing cryptographic properties: hiding and collision resistance

I saw from Another question the following definitions, which clarifies somewhat: Collision-resistance: Given: $x$ and $h(x)$ Hard to find: $y$ that is distinct from $x$ and such that $h(y)=h(x)$. ...
0
votes
0answers
47 views

What enables hash function to produce uniform distribution given any distribution of input

I always take the uniformity of hash output as a given and didn't think much of it. Now I am kind of curious, how does good hash function like sha guarantees output uniformity. Intuitively, given 1:1 ...
2
votes
4answers
132 views

Can different source files produce the same hash value?

It is often said in judicial opinions and legal briefs that the hash value derived from a file is like a fingerprint that uniquely corresponds to the source file. While this may be true in a practical ...
0
votes
1answer
68 views

What is the probability that the first collision occurs at the Kth insertions?

Question Consider a hash table with $n$ buckets, where external (overflow) Chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a ...
0
votes
1answer
40 views

How to calculate Pool reward for Race of Work?

I invented a new concept called Race of Work. It's based on Proof of Work, except there is no difficulty. Instead, there is a predefined time in each hour that consider being Block time. During the ...
0
votes
2answers
1k views

Are there any reversible hash function?

I read about hash function and I know that there can be some $x$ values which lead to the same $y$ ($x$ is the parameter of the hash function, $y$ is the result). Is there a way, given a $y$ and a ...
1
vote
2answers
88 views

Why are those hash functions considered a bad choice?

Given Hashtable $T[0,..,m-1]$ and $U = \{0, . . . , n − 1 \}$ set of possible keys $k$ with $m \ll n$ Let $$h: U \rightarrow \{0, . . . , m − 1 \} $$ I am trying to understand why the hash ...
1
vote
1answer
35 views

Given a square grid of side length N and m objects, design a bijection between each object and a unique set of coordinates

Given a square grid of side length N and m objects, can I design a 1-1 relationship between each object and a unique set of coordinates in that 2-D plane? Imagine the context being something like ...
-1
votes
1answer
93 views

Finding collision probability of hash function using modulo operation

I have a hash function which maps elements from a set A to another set B. The size of the two sets are n and m respectively (with n >> m). The hash function is of the form - $h: x' = x \; (mod \; m) \...
1
vote
0answers
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 ...
1
vote
1answer
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) ...
1
vote
0answers
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 ...
1
vote
0answers
125 views

2-universal family of hash functions and $\varepsilon$ good

Let $V=\{0,1\}^m$ and $H\subseteq V\to V$ a 2-universal family of hash functions. Fix two sets $A,B\subseteq V$. Call a hash function $h\in H$ $\varepsilon$-good for $A,B$ if: $$ |\Pr_{x\in V} [x\in A ...
1
vote
1answer
22 views

Existence of a Perfect Cryptographic Hash Function

Is there a hash function that satisfies all the following properties: 1. It is 1 to 1 (no collisions). 2. It can take any size input. 3. For any input, and some desired set of characters, there ...
2
votes
1answer
148 views

Representing a String of n characters, as a unique integer

So I have been following the lecture series on algorithms from MIT. I got to the part on Rolling Hashes and Karp-Rabin algorithm Karp Rabin Notes The way I understand it is in order to represent ...
1
vote
1answer
282 views

Calculating probability of no hash collision

Given a 64-bit hash function that takes arbitrary inputs, what is the probability that feeding 10 million inputs into the hash function will outputs 10 million unique outputs. I've came up with this: $...
1
vote
0answers
53 views

What is the graph of my chances to mine a bitcoin?

Consider the next hashing definishion of $f(x)$ $$f(1) = 100$$ $$f(x) = \operatorname{SHA-256}(f(x-1))$$ Where $x$ is a positive integer and SHA-256 is the hash algorithm. You can think of SHA-256 ...
5
votes
0answers
225 views

Bloom filter optimization on an interval of inputs

I'v been tackling a problem with bloom filters. I have a basic version working on paper, but I need to be able to put a large interval of numbers into the filter at a given time. Let ...
4
votes
3answers
1k views

Birthday Problem applied to collisions

I'm trying to extend the birthday problem to detect collision probability in a hashing scheme. Here is my problem. I use the letters and numbers [A-Z][a-z][0-9] to make a set of keys by randomly ...
5
votes
0answers
82 views

Bloom Filter with an interval input

I have been trying to design a variant of a bloom filter that can insert an interval of values at once, as well as query if a certain interval is in the bloom filter. I haven't been able to think of a ...
0
votes
1answer
105 views

Universal hash function with probabilty of multiple collisions

The problem is: Consider the universal hash function: $h(x, r) = x_1 r_1 + ... + x_d r_d \mod m$, with $m$ prime, where for an integer dimension d>0 you break up the key $x=(x_1,x_2, . . .,x_d), 0 \...
0
votes
1answer
55 views

Expected number of unique selections

If I'm selecting $N$ elements uniformly at random (with replacement) from $\{1, \dots, M\}$, what is the expected number of values that are selected exactly once? The basis for this question ...
0
votes
1answer
55 views

Finding all keys that hash to the same index

In my algo class, we discussed how uniform hashing algorithms aren't the best since it is possible to generate many keys that all hash to the same location. Take this hashing algorithm for example: ...
1
vote
1answer
36 views

Hash function to determine whether two vectors had an equal entry on some row

Do you know about a hash function, that approximates (in probability) the following function: Original function: Two vectors collide if there is a row where their entries are equal. $$ \text{E.g., }\...
1
vote
1answer
575 views

If k-universal hash family then (k-1)-universal hash family

A family of hash functions $H = \{h: U \rightarrow \{1, \ldots , m\}\}$ is called k-universal (or k-independent) if for every distinct $\{x_1, \ldots, x_k \} \in U$ keys and for every $\{i_1, \ldots, ...
0
votes
2answers
52 views

Sum of weighted integers.

I have to calculate hash value for an array of integers. The array has $8$ integers always, and the integers are a permutation of the integers from $1$ to $8$. For example, the array can be like this: ...
1
vote
0answers
84 views

Gradient noise hashing.

I'm working on a gradient noise function based on Simplex noise that uses simple squares instead of triangles (for performance and to avoid the patent for 3D noise). The original Simplex noise ...
1
vote
1answer
73 views

P vs NP, Has anyone proved there is no such thing as a collision-less one-way function. [closed]

I know that there has not been a proof against or for, the existence for a true one-way function. But i was wondering has such a thing been proven for collision-less (injective) one-way functions.