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.

-1
votes
1answer
12 views

Hash proof system programming implementation

Does anyone know if there is a hash proof system implementation using some programming language? Like C++, python.
0
votes
0answers
11 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
21 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
45 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 ...
0
votes
0answers
13 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
14 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 ...
2
votes
1answer
81 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
26 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
19 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
183 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 ...
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 ...
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)$. ...
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
0answers
46 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 ...
0
votes
1answer
66 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 ...
1
vote
2answers
87 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
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, ...
-1
votes
1answer
90 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
1answer
42 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
99 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
108 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
21 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
140 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
265 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
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
104 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 \...
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 ...
3
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
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
54 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
527 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.
1
vote
0answers
180 views

Universal Hashing - probability of collision

I can't seem to get my head around a following conclusion: Def: H is a finite set of hashing functions from U to [m] (set of size m). We'll call H universal if: $\forall x,y; x\ne y $ there exists $\...
1
vote
1answer
45 views

3 Letter Initial Phone Keypad Hash Distribution

I have written a c++ function that generates a 3 digit number corresponding to each letter in a random 3 letter initial and their location on a phone keypad. For Example, my initials MSG, would return ...
0
votes
0answers
409 views

Why is this hash function for english words is perfect hash?

I have a question that seems really intuitive to me but I can't think of a way to prove it. Assume we a have a file with words that are different from each other and contain digits only for example ...
0
votes
1answer
67 views

Hash Table Dynamical Resizing

I read the concept about dynamical resizing hash table from this lecture. And for my understanding, it claims that the average run time of all insertions is $O(1)$ for each iteration. Now, suppose we ...
3
votes
1answer
48 views

What is the distribution of $x^2\pmod p$ where $p$ is a prime number, and $x \in \mathbb{Z_p}$?

Let $p$ be a prime number. How will numbers get distributed in $\mathbb{Z_{p}}$ upon doing $x^2 \pmod p$ where $x \in [0,p]$ is an integer? My approach: Let $p = 97$. Then, $x^2 \equiv (97-x)^2 \pmod{...
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
252 views

How many SHA-256 hashes of emails are duplicates of each other?

There are $5$ billion unique email addresses in the World. If I created a database containing their SHA-256 hashes, how any unique hashes would we expect that database to contain? By my crude methods,...
1
vote
1answer
49 views

Birthday paradox over power law distribution

In the classic birthday paradox problem we assume a uniform distribution of birthdays across the year, i.e. $p(x)=\frac{1}{365}, x=1,2,...,365$. What is the coincidence probability of two birthdays if ...
1
vote
0answers
117 views

MinHash single vs multiple hash functions

I'm trying to get familiar with MinHash function, and there are a few things a do not understand: Why to use multiple hash function version over single hash function alternative? MinHash wiki says - ...
0
votes
1answer
166 views

Beginner level understanding concept on how to derive probability of hash collision

A hash function indexes all items in hash tables and searches for near items via hash table lookup. The hash table is a data structure that is composed of buckets, each of which is indexed by a hash ...
0
votes
0answers
117 views

Generalization of Birthday Problem over Sets of Dates

At the classic version of the birthday problem we check for collisions of scalars $ b_i $ sampled from a uniform distribution. How can this be generalised over sets with more than one samples per ...
0
votes
1answer
12 views

Equivalance of statement

I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika Inside specifically had this ...