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
1 answer
14 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 ...
  • 121
-1 votes
0 answers
10 views

Need to create Minimal Perfect Hash Function

The Task: Let, on a given set of words, two hash functions $h_1, h_2$ give the values ​​indicated in the table. It is necessary to construct the minimal perfect hash function for this set of words. ...
0 votes
0 answers
22 views

Number of possible values of n bit hash function

I was going through the hash function and its properties, The main strength of the hash function depends on the number of bits $n$. While calculating the collision it considered that there are $2^n$ ...
4 votes
2 answers
246 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 ...
1 vote
1 answer
44 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 ...
  • 13
0 votes
0 answers
20 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 ...
0 votes
0 answers
17 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 ...
  • 101
2 votes
1 answer
59 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 ...
0 votes
0 answers
19 views

Why do we need the $+b$ in the family of hash functions $h(x) = ((ax+b)\bmod p)\bmod n$?

What properties of hash functions (i.e. distinct inputs can't collide in $\bmod p$ space, universality in $\bmod n$ space, all mappings equally likely, etc.) would dropping the $+b$ violate?
3 votes
1 answer
69 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 ...
  • 407
0 votes
0 answers
41 views

What is the probability of a hash collision for concatenated strings from two disjoint sets?

Let's suppose we have two disjoint sets of distinct strings: $S=\{s_1, s_2, ..., s_n\}$ and $R=\{r_1, r_2, ..., r_m\}$. The length of any string in both sets varies from 1 up to 31 characters from the ...
4 votes
1 answer
100 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 ...
  • 173
0 votes
0 answers
36 views

How likely is an MD5 hash a UUIDv4?

There are $2^{128}$ possibilities for an MD5 hash and $2^{122}$ for an UUIDv4 (source: https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random)). A UUIDv4 has two characteristic ...
  • 101
1 vote
0 answers
54 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 ...
  • 113
0 votes
0 answers
50 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 ...
5 votes
1 answer
304 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$. ...
0 votes
0 answers
46 views

Generating a sequence of n random numbers without duplicates with a space complexity of O(log(n))

I would like to generate a sequence of $n$ random integers in the interval $[1,n]$ without duplicates, i.e. a permutation of the sequence $[1,2,...,n]$ with $O(log(n))$ space complexity (or a ...
0 votes
0 answers
39 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 ...
0 votes
0 answers
39 views

Efficient hashing algorithm for 2-dimension array.

We all know that, to find string $A$ in $B$, we could use hashing. For exapmle, find 'abba' in 'abbababsbdbabababba'. We use hashing with base $29$ and modulo $10^9+7$: 'abba' -> $1\times29^3+2\...
  • 437
0 votes
1 answer
50 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),...
1 vote
1 answer
56 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), \...
  • 1,103
1 vote
1 answer
56 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 ...
  • 1,787
1 vote
0 answers
119 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 ...
  • 1,103
1 vote
1 answer
191 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 ...
  • 53
2 votes
1 answer
66 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 \\ ...
  • 23
0 votes
1 answer
14 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,...
  • 173
0 votes
0 answers
24 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 ...
  • 101
0 votes
1 answer
803 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 ...
  • 2,321
0 votes
0 answers
129 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 ...
  • 1,561
2 votes
1 answer
105 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 ...
  • 1,036
1 vote
1 answer
719 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 ...
  • 71
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, ...
3 votes
1 answer
76 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} \...
1 vote
1 answer
36 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,725
2 votes
1 answer
99 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, ...
  • 14k
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,...
0 votes
0 answers
258 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
1 answer
40 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 ...
  • 311
0 votes
1 answer
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 ...
  • 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 ...
0 votes
1 answer
296 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 ...
1 vote
1 answer
57 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 ...
  • 728
0 votes
0 answers
139 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
1 answer
777 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
1 answer
65 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
0 answers
156 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
0 answers
88 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, ...
  • 21
1 vote
1 answer
37 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,225
1 vote
0 answers
13 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
2 answers
91 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
2 3 4 5