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.

Filter by
Sorted by
Tagged with
2
votes
1answer
55 views

I need a hash function that will give all values from $0$ to $2^n - 1$. Will $f(x) = \frac{x^2 + x}{2} \; \text{mod} \; 2^n$ do the job?

I need a hash function that will give all values from $0$ to $2^n - 1$. I want to know if this function does what is needed? $$f(x) = \frac{x^2 + x}{2} \; \text{mod} \; 2^n$$ the values of $x$ are ...
0
votes
0answers
25 views

Probability distribution for collisions / birthday problem

Let's say I have a source of randomly produced values from a range $M$. I want to test if the source is a uniform distribution by examining a sample sequence of $n$ values $m_1, m_2,\dots,m_n$. ...
0
votes
0answers
21 views

Probability a near universal hash function $ax \mod p \mod m$ produces an output from inputs equal modulo $m$

For a given near universal hash function $f(x) = ax \mod p \mod m$ where $p$ is prime and $m < p$, what is the probability that given $x_r \in \{ x | x \mod p \mod m =r\}$, $f(x_r) = s$? That is, ...
1
vote
1answer
27 views

show that $h(k)=\left \lfloor{\frac{k}{m}}\right \rfloor \mod m$ is a bad hash function where $m$ is prime

A "good" hash function should make use of all slots with equal frequency. In this case the ammount of slots is given with $m$. Also keys which are similar should be distributed as broadly as possible....
0
votes
0answers
9 views

Check if element was used to construct Hash

For a given set of data $D = \{d_1, d_2, \dots, d_n \}$ is there a hash-function $f$ that for any subet $D_s \subset D$ $$ f(D_s) = H_{D_s} $$ so that a second function $g$ exisist with $$ g(f(D_s)...
1
vote
0answers
11 views

Is there a hash-like function from pointed digraphs where if A and B differ only in the placement of the point, this is clear in the hash?

I want a cryptographically secure hash-like function (it need not output integers, it could be any data type) which takes directed graphs with a single marked point as input, so that if graphs A and B ...
2
votes
2answers
67 views

Constructive proof of secure hash collision

The SHA3-512 hash algorithm can be considered as a map h from the set F of "files" (finite sequences of octets, each octet being an integer in the range 0 to 255) to the set H of "hashes" (sequences ...
1
vote
1answer
31 views

Prove inequality with $\theta$

I was given a task about hash tables, to prove that for a hash table with n buckets and separate chaining collision resolution the probability of collision occurrence within $\theta(\sqrt{n})$ inserts ...
0
votes
1answer
107 views

Expected number of colliding pairs in hashing (example)

Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing --- that is, with each key mapped independently and uniformly to a random ...
0
votes
1answer
25 views

Why is $h(x) = (x^2 + 1) \mod 11$ a bad choice for a hash function considering an array of 11 slots?

Why is $h(x) = (x^2 + 1) \mod 11$ a bad choice for a hash function considering an array of 11 slots? We consider uniform hashing so we have two conditions to respect: Uniformity: meaning that we ...
1
vote
1answer
26 views

Understanding hash functions.

What I understand by a Hash function, is a function $H$, such that taking an input $x$ of some bit-length $L$, produces an output $y$ of some bit-length $l$ such that $L >> l$ (where ">>" means ...
0
votes
0answers
87 views

Custom hash-function that preserves behavior from previous hash-function

Let's define a Hash-function in the following way: $$ H_n(x) = a_n $$ where $L$ could be any Language with $x \in L$ and $a \in \{1, 2, \dots, n\}$. So this means the Hash-function $H_n$ should ...
2
votes
0answers
24 views

Is this a good method for deterministically randomising the order of two names?

In English speaking culture, when a man and a woman get married, the woman traditionally takes the man's surname. My brother took his wife's surname, but he is the exception, not the rule. Some ...
1
vote
1answer
34 views

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

Regarding this question: If k-universal hash family then (k-1)-universal hash family It's been answered and I dont understand the answer: \begin{align} Pr[h(x_1) = i_1 &\land \cdots \land h(x_{k-...
0
votes
0answers
38 views

A random oracle as a CRHF

Reading through the book Introduction to Modern Cryptography by Katz/Lindell, I'm having some trouble understanding this part. (It's on p.178 in 2e, chapter 5.5) What I'm struggling with are: How ...
1
vote
0answers
31 views

Goldwasser Sipser Protocol, perfect completeness

The Goldwasser-Sipser set lower bound protocol is as follows: Let $\mathcal{H}_{m,k}$ be a pairwise independent family of hash functions from $\{0,1\}^{m} \rightarrow \{0,1\}^{k}$. Given $S \subset \{...
14
votes
3answers
308 views

How to classify polyominoes by shape

I am trying to find a robust way to classify and distinguish polyominoes. I would like to write a simple algorithm that could identify similar free polyominoes (under translation, rotation, reflection ...
0
votes
0answers
19 views

Expected Number of Iterations in Perfect Hashing

We know that we can do Perfect Hashing in expected linear time using a well-known two-level hash table approach. But what is the expected number of iterations that we do to construct the first level, ...
1
vote
0answers
67 views

Is a neural network convolution a hash function?

ConvNet is a class of neural networks which use kernels to extract position-dependent data from data and perform further classification or regression operations on it. Simply put, kernels work like ...
0
votes
0answers
87 views

Expected value of collisions

There are two definitions that are needed in the following problem: A probability distribution $H$ over a hash function $h : U \rightarrow \{1, 2, \ldots, m\}$ is said to be universal if for all $x\...
1
vote
1answer
33 views

How difficult would it be to find valid answers for this hash arrangement?

If $A$ is a 160-bit number, and $X \& Y$ are two SHA-1 hashes, to be generated such that the 320-bit number $X\mathbin\|A$ hashed to $Y$, and the 320-bit number $A \mathbin\| Y$ hashed to $X$? ...
-4
votes
1answer
68 views

Probability of A is a subset of B if Hash(A) is a subset of Hash(B).

There is an infinite countable set $S$. From it we have two subsets of $A$ and $B$. The $Hash$ function translates $S$ into $Hash(S)$ - a finite set of hashes, and, accordingly translates $A$ into $...
0
votes
0answers
24 views

Construct Pearson hash that distributes over XOR

Is it possible to construct a Pearson hash $h$ such that the following holds true? $$ \forall a,b : h(a \oplus b) = h(a) \oplus h(b) $$ $a$ and $b$ are byte strings of equal length $n$ and $\oplus$ ...
1
vote
0answers
74 views

What is the formula for calculating load factor of hash table when collisions are handled by many different techniques?

I am in a rush to submit some assignment, may I have the formula for calculating the load factor of hash tables when collisions are handled by linear probing, quadratic probing and double hashing? I ...
1
vote
2answers
56 views

Probability of distribution using a discrete random function

Problem: Given P persons (say 1000) distribued among N rooms (say 50) using a discrete random distribution function. What would be the probability of a room having at least K persons (say 30 or more ...
0
votes
1answer
68 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 ...
-1
votes
1answer
19 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
1answer
49 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
54 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 ...
2
votes
1answer
98 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
38 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
1answer
664 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
24 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
54 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
140 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 ...
1
vote
0answers
212 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
200 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
41 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
215 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
36 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
52 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
170 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
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
145 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
146 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
30 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
328 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
389 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
54 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
97 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 ...