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
0 answers
16 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
273 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
51 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
82 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
36 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
0 votes
0 answers
14 views

incremental hashing output size

I've recently been looking into incremental hash functions (namely, LtHash). My purpose is to check set membership using a hash of particular element (incremental hashing allows that). The problem is ...
user37741's user avatar
  • 101
1 vote
1 answer
63 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
133 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 itb hernandez rodriguez's user avatar
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
132 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
165 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.2k
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.2k
0 votes
0 answers
201 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.2k
0 votes
0 answers
58 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.2k
2 votes
1 answer
27 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
368 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
106 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
  • 13
0 votes
0 answers
24 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
28 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
123 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
142 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
370 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
57 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
111 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
139 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
76 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
152 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,149
1 vote
1 answer
131 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,859
1 vote
0 answers
288 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,149
1 vote
1 answer
651 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
165 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
17 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
38 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 ...
Alexis's user avatar
  • 101
1 vote
1 answer
2k 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,309
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,589
2 votes
1 answer
228 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,046
3 votes
1 answer
1k 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
  • 177
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
152 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,795
2 votes
1 answer
186 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, ...
FShrike's user avatar
  • 39k
2 votes
1 answer
59 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,...
user3563894's user avatar
0 votes
0 answers
534 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 ...
Demosthenes's user avatar
0 votes
1 answer
41 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 ...
dawid's user avatar
  • 333
0 votes
1 answer
63 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 ...
M K's user avatar
  • 27
6 votes
1 answer
231 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 ...
Mio Unio's user avatar
0 votes
1 answer
914 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 ...
acme_2020's user avatar
1 vote
1 answer
95 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 ...
Jonathan's user avatar
  • 736

1
2 3 4 5