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
0
votes
0answers
23 views

Perfect Hash Function that detects invalid inputs?

I work in hardware/electronics where everything is power of 2. To avoid storing the key along with the value, I can find a perfect hash function for the known-in-advance keys. Nevertheless, the PHF ...
0
votes
1answer
25 views

Designing a hash function from a 3 integer tuple

I have a set of keys $K$ where each key is a 3 tuple of integers (both negative and positive). The keys are clustered, meaning that if $(i,j,k) \in K$ then there is a high likelihood of any of $(i\pm ...
0
votes
0answers
28 views

Create smaller products while guaranteeing uniqueness - Godel encoding

I was reading about Godel Numbering I was wondering if it is possible to create a unique number in a way (i.e. as a product), but with that the requirement the number does not grow at the rate of the ...
2
votes
1answer
55 views

Colliding pairs - hash functions

Let $h:D\to [m]$ be a hash function that maps some object from the set $D$ to a natural number $k$ ($1 \leq k \leq m$) with probability $1/m$ for every $k\in [m].$ A falsely colliding pair are two ...
0
votes
1answer
90 views

Radix 128 integer representation of a string

I am reading a textbook "Introduction to Algorithms" (Cormen, 3rd edition). In the text, the string 'pt' is converted to ASCII such that $p=112$ and $t=116$. The result is then converted to ...
0
votes
0answers
22 views

How to find the expected value before a bitarray is full?

If I have a bitarray of size $m$ with all $0$'s initially and one universal hash function $h: U \rightarrow [m]$ where each index in the bitarray has $\frac{1}{m}$ probability of being flipped to 1, ...
3
votes
1answer
60 views

Why is $a^{-1} \cdot a \equiv 1 \text{ mod } m$ a lemma in universal hashing? [duplicate]

I have been given the following lemma in a online lecture on universal hashing: Lemma: Let m be a prime. For any $a \in \{ 1, \dots, m-1 \} $ there exists a unique inverse $a^{-1}$ such that $a^{-1} \...
0
votes
0answers
11 views

A hash function on braid groups

I am reading group theoretic cryptography. I wanted an example of a hash function from the braid group $B_n$ to a fixed size string of $0$s and $1$s, say $\{0,1\}^k$. I am a group theorist and haven't ...
1
vote
1answer
29 views

Possibility of duplicates in hash table

I have a problem where I am trying to find the relationship between parts and the parts that make them up. Like if a boiler is made with two side plates and one bottom plate, and the side plates have ...
1
vote
1answer
46 views

How to overcome the wastefulness of uniform distributions in a hash function

Recently on the programming StackOverflow I posted a query about my hash function - I was looking for mistake when there was none. I was alarmed by an empty bucket count of around 36%, as I thought, ...
2
votes
1answer
57 views

Is the following function a bijection?

During my work on hash functions, I try to prove/disprove that the a linear map function $f:\mathtt{Z}_2^n\to \mathtt{Z}_2^n$, where $n=64$, is bijection. The function is defined as followed $$f(x_0,...
0
votes
0answers
53 views

Zobrist hashing collision probability 64-bit vs twice 32-bit

I've been thinking of the right site to post this, finally decided against SO and chess.stackexchange.com, since it's really more a mathematical question. I'm looking into how position databases in ...
0
votes
1answer
35 views

How to define a non-abelian group over the set of integers $S=\{0, \cdots, 2^{128}-1\}$ with no commutativities nor self-inverse elements?

I am trying to solve a problem since a while, adding the remaining constraints along the process of learning the concepts. It's been a long journey. The best approach (for the weak version of the ...
0
votes
1answer
62 views

some number theory method can be used to solve this example quickly? [closed]

I have extract some notes from my notes: one way to found which of four example is uniform function is that try by hand and take some examples. I will search for a method that we can easily infer ...
6
votes
1answer
225 views

Hash function and one near hard example?

Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
0
votes
1answer
75 views

Hash collision probability

I am trying to show that the probability of a hash collision with a simple uniform 32-bit hash function is at least 50% if the number of keys is at least 77164. I have figured out how to plot a graph ...
0
votes
0answers
39 views

LSH family based on p-stable distribution

I was reading a paper about p-stable distribution and hash functions (http://people.csail.mit.edu/nickle/pubs/pstable.pdf) and in paragraph 3.2 i found a proposition I'm not able to prove. In ...
0
votes
0answers
13 views

Approximate nearest neighbor algorithm using jaccard distance

Given have $h_\pi(A) = \text{argmin}_{a\in A} \pi(a)$, where $A$ is a set and Jaccard distance as $d = 1 - J$. I want to create an approximate nearest neighbor search using $h_\pi$ and $d$ however, I'...
1
vote
1answer
36 views

Proving hash function theorem

Let's say I have some set $X$ such that for any hash function $h$ and random permutation $\pi \in {1,2,..., n}$, we have $$h_\pi(X) = argmin_{x} \pi(x)$$ for $x \in X$. Equivalently $h_\pi(X)$ is the ...
0
votes
0answers
20 views

Let $X_v = (U \cdot v)\%2$. Prove that $E(X_{i_1}, \ldots, X_{i_k}]) \neq 0 $

Let $X_v = (U \cdot v)\%2$, where $U=(U_1,...,U_r)$ is uniformly distributed over $\lbrace 0,1\rbrace^r$ and $v \in \lbrace 0,1\rbrace^r/0$. I have a hard time proving that $$E(X_{i_1}, \ldots, X_{i_k}...
0
votes
0answers
50 views

Simple and fast homomorphic checksum - XOR MD5?

TL;DR; How bad is it to XOR MD5 checksums? Will this lose MD5's advantages and if so, what else can be used for making fast, online checksum on a key-value store with a good collision rate? We got a ...
2
votes
1answer
290 views

Expected number of probes in unsuccessful search in open addressing

I recently started studying algorithms on my own using nptel lectures in youtube. Kindly clarify how the professor wrote below equation for expected number of probes in unsuccessful search in open ...
2
votes
1answer
61 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
60 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$. ...
2
votes
0answers
43 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
28 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....
1
vote
0answers
12 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
70 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
35 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
831 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
48 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
37 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 ...
2
votes
0answers
27 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
123 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
41 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
67 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
394 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
25 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
102 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
120 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
36 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
78 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 $...
1
vote
0answers
215 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
57 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
218 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
20 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
62 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
56 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
124 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
57 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
2 3 4 5