Skip to main content

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
1 vote
0 answers
58 views

Hashing pointers against the largest prime

In another forum someone asked for a hash-function to hash pointers. I suggested to multiply the pointer with the lagest prime fitting into an uintptr_t and ignore the overflow. Someone said that this ...
Edison von Myosotis's user avatar
0 votes
0 answers
12 views

k-independent hash functions vs. orthogonal arrays

In some randomised algorithms, such as Alon-Matias-Szegedy (AMS) algorithm, two different strategies are used for the generation of a family of random numbers with some special correlation properties: ...
yarchik's user avatar
  • 1,191
0 votes
0 answers
25 views

Expected number of collsions in hashing

Suppose we use a hash function h to hash n keys into m slots. Assuming simple uniform hashing, what is the expected number of collisions? (CLRS, 3rd edition, problem 11.2-1) My solution is as follows: ...
Equinoccio's user avatar
3 votes
1 answer
231 views

UPD: Structure of subgroups of $S_{2^n}$ generated by $\langle x \mapsto ax \mod 2^n \rangle$ and linear groups

It's a very well known result by Gauss that $(\mathbb{Z}/2^n \mathbb{Z})^\times = \langle -1 \rangle \times \langle 3 \rangle \cong C_2 \times C_{2^{n-2}}$. Consider a faithful action $\mathrm{mul}: (\...
Aleksei Averchenko's user avatar
1 vote
1 answer
56 views

Collision probability of hash function $(ax + b)\bmod m$

I'm trying to calculate the probability of collision for the following family of hash functions: $$h_{a, b}(x) = (ax+ b) \mathrm{mod}{m} \quad \quad m\in\mathrm{Z}_p, \ a\in\{0, 1, \ldots, m - 1\}, \ ...
John Katsantas's user avatar
1 vote
0 answers
34 views

Proof of Strong Universality of a Hash Function

I read about a Strongly universal hash function from 64-bit keys to 32 bits, in this paper. It uses the following function: $h(x) = ((a_1 + x) \cdot (a_2 + (x \gg 32)) + b) \gg (64 - \ell)$ Where $...
John Smith's user avatar
0 votes
0 answers
34 views

Proving pairwise independence for random matrix hash functions

Let $H_n^m$ be the family of hash functions with $h(x) = Ax + b$ for $A \in \mathbb{Z}_2^{m \times n}$ and $b \in \mathbb{Z}_2^m$. I'm trying to prove that this family of hash functions is pairwise-...
Germ's user avatar
  • 260
0 votes
1 answer
38 views

Uniform Distribution of a mod hash function

I wonder if there is any efficient way to determine whether the hash values of $h(x)=3x\ mod\ 2^{64}$ are uniformly distributed for $x$ being uniformly distributed in $[0,2^{512}-1]$? I try to ...
Jerry's user avatar
  • 135
0 votes
0 answers
44 views

Scaling a threshold for anomaly detection depending on the sample size

I'm trying to study and test 32-bit hash functions - specifically probability of collision (repeated results for different inputs). And I'm struggling in defining a threshold for outliers/anomalies, ...
bryc's user avatar
  • 101
0 votes
0 answers
21 views

Minimum Number of Functions for a Universal Hash Family Mapping {a, b, c, d} to {0, 1}

Determining the Minimum Size of a Universal Hash Family I'm working on understanding universal hash families and encountered a problem that I'm struggling to solve. The problem is as follows: Consider ...
Iman Mohammadi's user avatar
0 votes
0 answers
21 views

Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2]

I came upon the following hash function (pseudo-code): ...
bd55's user avatar
  • 13
2 votes
1 answer
280 views

What is the probability that the hash of a hash is the same hash?

Given an $n$-bit uniform cryptographic hash function (128-bit md5, 256-bit sha-256, etc), what is the probability that the input ...
hioqobipb's user avatar
1 vote
1 answer
54 views

Bucket loads with hashtable

I have a math problem that derives from the frequency with which buckets are occupied in a hash table. Suppose we have a hash table that has as many buckets as there are nodes, i.e. the nominal load ...
Edison von Myosotis's user avatar
1 vote
1 answer
119 views

Probability of collision in a hash function.

Let $T = {1,...,m-1}$ be a hash table with open addressing, and for i = 1,...,n with $n \leq \frac{m}{2}$ let $X_i$ be a random variable denoting the number of probes for the i-th entry being added ...
Newbie1000's user avatar
0 votes
0 answers
41 views

Coupon Collector's problem, but coupons are distributed by a universal hash function

I am familiar with the Coupon Collector's problem. But what if instead coupons are distributed by a universal hash function? In other (more formal) words, if you hash set $S$ with function $h$ to ...
Gustav's user avatar
  • 1
1 vote
1 answer
66 views

Counting number of keys hashed to each slots

Suppose $K= \{ k^2:1\leq k\leq 100 \} $ as the set of keys that hashed by two hash functions $$ a)\;\; h(k)=k\mod 12 $$ $$b)\;\; h(k)=k\mod 11 $$ I want to show that $a$ is not a good choice because ...
tstt's user avatar
  • 341
1 vote
2 answers
152 views

How can I do Gaussian elimination of a $32 \times 32$ bit matrix?

I have been looking at how to reverse the sigma operation in the sha256 hash and in several places I have seen that you have to make a $32 \times 32$ bit matrix and then solve it with Gaussian ...
jefrey's user avatar
  • 13
2 votes
2 answers
51 views

What notions of independence exist for these random variables?

I think I've gotten a bit confused about the notions of independence that the following random variables satisfy. Any help would be greatly appreciated. Let $x_1, ..., x_k \in \mathbb{Z}_q^n$, each ...
J1996's user avatar
  • 311
0 votes
0 answers
149 views

Finding time complexity of the minimal element in hash table?

I want to understand and solve the next task: If we draw elements from a universal set U and insert n (different) elements into ...
kollleey's user avatar
0 votes
1 answer
170 views

What is the purpose of the "diffusion" property of a hash function? [closed]

https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec21.html says For a hash table to work well, we want the hash function to have two properties: Injection: for two keys k1 ≠ k2, the hash ...
Tim's user avatar
  • 47.7k
0 votes
1 answer
48 views

How is the diffusion property of a hash function stronger than the injection property?

https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec21.html says For a hash table to work well, we want the hash function to have two properties: Injection: for two keys k1 ≠ k2, the hash ...
Tim's user avatar
  • 47.7k
0 votes
0 answers
253 views

What is the uniformity property of a hash function?

https://en.wikipedia.org/wiki/Hash_function#Uniformity says: A good hash function should map the expected inputs as evenly as possible over its output range. That is, every hash value in the output ...
Tim's user avatar
  • 47.7k
0 votes
0 answers
59 views

Can bounded operator concept extend from topological vector space to metric space?

Wikipedia says: In functional analysis and operator theory, a bounded linear operator is a linear transformation ${\displaystyle L:X\to Y}$ between topological vector spaces (TVSs) ${\displaystyle X}$...
Tim's user avatar
  • 47.7k
2 votes
1 answer
28 views

Convert an arbitrary string of bits to a 3D color such that strings with more bits in common have more similar colors

I am toying with a genetic algorithm for the first time to evolve a very simple neural network. For the purpose of rendering, I would like to assign my agents a color based on their 'genome', such ...
cebo's user avatar
  • 121
4 votes
2 answers
416 views

Why does double hashing create a permutation?

Question Let $\mathbb{N} = \{0, 1, 2, \dots \}$, $\mathbb{N}^+ = \mathbb{N} - \{0\}$, $m \in \mathbb{N}^+$, $[m] := \{0, 1, \dots, m-1\}$ and define the function $f:[m]\to[m]$ as below $$f(i) = (a + i ...
Hosein Rahnama's user avatar
1 vote
1 answer
111 views

2-wise vs k-wise independence for Count-Min Sketching

My question is about a proof shown below (full paper) Image of the proof If I expand the last line of the proof, i.e., $Pr[\forall_j X_{i,j} > e{\mathbb E}(X_{i,j}) ] < e^{-d}$, then it occurs ...
KRG's user avatar
  • 15
0 votes
0 answers
25 views

Does storing the password in two separate bcrypt hashes with different keys make it easier to crack the password?

I use bcrypt to hash and store user passwords, and then again to generate unique access tokens, both of which are salted. In the first case, I simply hash the password + a salt (one randomly generated ...
moonman239's user avatar
0 votes
0 answers
39 views

Generate a function f() which maps a known set to another known set

I have a set S of random positive integers that is of known size n. Is there a way to generate a hashing function which ...
TheBat's user avatar
  • 101
2 votes
1 answer
134 views

What is the expectation value of the minimum 'distance' between two random 64-bit numbers out of a set of N?

Assume we have a set of N random integer numbers in the interval [0, 2^64> (or equivalent, consider N randomly chosen corners (vectors) of a 64-dimensional ...
Carlo Wood's user avatar
3 votes
1 answer
146 views

universal and $k$-universal hash functions

In my Datastructures and Algorithms lecture, $k$-universal hash functions have been defined differently than on, e.g., Wikipedia and I have trouble finding both definitions equivalent. My lecture: A ...
Bob Aiden Scott's user avatar
4 votes
1 answer
425 views

Reversible hash function for mapping a set of integers to another set

I'm looking for a reversible hash function that would map any 64-bit integer to another, with 1-to-1 correspondence, i.e. one number in one set maps to only one number in another set, both ways. It is ...
mojuba's user avatar
  • 183
1 vote
0 answers
59 views

Is $(i+1) \text{ mod } n$ a hash algorithm with strong universality?

Please correct me if I got it wrong. I am trying to learn MinHash algorithm by implementing one. The hash function needs better to be min-wise independent instead of pairwise independent. I'm testing ...
dz902's user avatar
  • 113
0 votes
0 answers
126 views

Is it possible to construct a hash function that accepts multiple keys and returns the same value if at least one key is the same?

How to construct a hash function that accepts multiple keys as input and returns the same value if at least one input key is the same, no matter which keys are identical? For example, the desired hash ...
Lizhi Liu's user avatar
6 votes
1 answer
1k views

Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
Abhishek Ghosh's user avatar
0 votes
0 answers
181 views

Time Complexity Baby Steps Giant Steps

This has been driving me mad. On wikipedia's page on baby steps giant steps it gives the time complexity of the algorithm as $O(\sqrt n)$. It even gives looking up a value in a hash table as how you ...
guywholovesmath's user avatar
0 votes
1 answer
85 views

What system has modular inverses for non primes too?

Is there a system that has modular inverses for non prime mods? Ultimately what I am trying to do is design a hash function that given a list of n outputs (mod m) and inputs (large arbitrary integers),...
Darren Smith's user avatar
1 vote
1 answer
180 views

Prove that if hash function $h_2(k)$ and $m$ are coprimes, then they produce a probe sequence that is a permutation of $(0, \cdots, ,m-1)$

Question: Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m} $. Show that the probe sequence $<h(k, 0), h(k, 1), \...
Avv's user avatar
  • 1,189
1 vote
1 answer
139 views

Domain of hash function

I am reading Buchmann's Introduction to Cryptography, 2nd ed. On page 267, $G$ is a finite cyclic group of prime order $q$. $a\in\mathbb{Z}_{q}=\mathbb{Z}/q\mathbb{Z}$. $h:\{0,1\}^{*}\to G$ is a hash ...
Delong's user avatar
  • 1,889
1 vote
0 answers
307 views

Analysis of multiplication method for hashing

Given two hashing functions, namely: division method versus multiplication method disadvantages. Multiplication method: Given that we have hash function $f(k)=⌊N\times(kA−⌊kA⌋)⌋$, where $N,k\in Z$ and ...
Avv's user avatar
  • 1,189
1 vote
1 answer
726 views

Produce a unique integer out of list of integers with constraints

Problem I am a computer programmer looking for a mathematical function (or a more advanced algorithm) able to produce a 32bits integer out of a list of integers with the following constraints: Each ...
Flo's user avatar
  • 53
2 votes
1 answer
180 views

Is it possible to efficiently solve a system of Boolean equations only containing XOR?

Let $h$ and $x$ be vectors of Boolean variables. Given a system of Boolean equations like $$ h_0 = x_0 \oplus x_2 \oplus x_4 \\ h_1 = x_0 \oplus x_3 \oplus x_5 \\ h_2 = x_1 \oplus x_2 \oplus x_5 \\ ...
Julian's user avatar
  • 123
0 votes
1 answer
19 views

Conditioning on the output of a function from Universal set, find input that causes collision

We have a Universal set of functions that map the universe of inputs to $\mathbb{Z_{p}}$ with prime $p$, in the sense that for any two non-equal $x$ and $y$ inputs into a uniformly randomly chosen one,...
heckeop's user avatar
  • 273
0 votes
0 answers
44 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 ...
None's user avatar
  • 101
2 votes
1 answer
3k 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 ...
Makogan's user avatar
  • 3,439
0 votes
0 answers
130 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 ...
Jim's user avatar
  • 1,609
2 votes
1 answer
242 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 ...
Hilberto1's user avatar
  • 1,048
3 votes
1 answer
2k 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 ...
AdamsK's user avatar
  • 197
0 votes
0 answers
24 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, ...
GoldenRetriever's user avatar
3 votes
1 answer
82 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} \...
DenLilleMand's user avatar
1 vote
1 answer
178 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 ...
kleineg's user avatar
  • 1,805

1
2 3 4 5 6