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.

learn more… | top users | synonyms

0
votes
2answers
23 views

equation to create unique value

I have a list of n objects say [ apple, orange, carrot, cherry, banana ] Now I am trying to come up with an equation which will generate an unique number for ...
1
vote
0answers
9 views

Determining next hash [on hold]

Given a series of hashes, were one hash is determined from the previous hash. i.e seed 0 => seed 1 => seed 2 => seed 3 Is it possible to determine the next seed or even the hash function itself?
0
votes
0answers
8 views

Pairwise independent hash functions vs. p-wise independent hash functions, what is the difference?

I am reading a paper and it mentions how pairwise independent hash function gives weaker, but still sufficient results, comparing to p-wise independent hash functions. I am not very familiar what ...
0
votes
0answers
11 views

What does “4-universal hash function” mean?

I encountered the notion of 4-universal hash function and I cannot understand what exactly it means. This article https://en.wikipedia.org/wiki/Universal_hashing did not really help to clarify it. ...
4
votes
2answers
47 views

Where do hash functions come from?

I have some basic understanding of how hash functions work, however, I have no idea of how mathematicians created them. Were them a byproduct of a non cryptografics related research or were them a ...
0
votes
0answers
31 views

If the hash of the multiplication is equal to the multiplication of the hash, how can this be used to leverage an attack?

Assume a hash function $H:\left\{0,1\right\}^*\to G$ where $G$ is a group and assume that finding an inverse in $G$ is easy. How can a preimage efficiently be found using the fact that $H(M_1\cdot ...
2
votes
0answers
151 views

Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
1
vote
0answers
19 views

How to calculate the expectation $E[\sigma(1)\sigma(2)\sigma(3)]$, given a 2-wise hash function $\sigma: [d] \rightarrow \{-1,+1\}$

Given a 2-wise hash function $\sigma: [d] \rightarrow \{-1,+1\}$, i.e., $\sigma(a)$ will map any positive integer $a\leq d$ into real number $-1$ or $+1$ with equal probability. Then how to calculate ...
0
votes
0answers
56 views

Cyclic Group permutations

I am working on the following exercise question: Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)). Gen : On input 1n , ...
2
votes
0answers
15 views

The hash collision probability approximation

I am comparing the actual probability of no collisions to the probability approximation formula of no collisions from the Understanding Cryptography text. The approximation is as follows: ...
0
votes
1answer
44 views

Likelihood for a random hash function not to be surjective

Let us define a hash function $$\begin{align*} H \colon A &\to B\\ a &\mapsto b \end{align*}$$ $$|A| \geq |B|$$ Assuming it is perfectly random (Hyp 1), we estimate the probability that ...
0
votes
0answers
16 views

Probability of x modulus a prime = a

I am working on a project that involves analyzing the distribution of simple hash functions. One such construction relies on the fact that given a primes $p,q$, the unit group for $p$ $U_p$, a random ...
1
vote
0answers
93 views

Balls and Bins- Hash Table: a Concrete Example

My question is related to this: http://cs.stackexchange.com/questions/49027/balanced-allocation-hash-table-overflow-probability/49030#49030 In [1,2], it is said that if we throw $n$ balls into ...
0
votes
0answers
29 views

How do I design a hash function for this given case?

My professor gave me the following problem. You are to store objects identified by integers from the interval $[0..10^9 − 1]$. You expect never to have to store more than 1400 objects. Design ...
0
votes
2answers
58 views

Solve for n: 1 - e^((-k (k - 1))/(2 n)) - z = 0?

With the knowledge that the probability of a hash collision is (see: Hash Collision Probabilities): 1 - e^((-k * (k - 1)) / (2 * n)) Where k is the number of input values and n is the number of ...
-1
votes
1answer
47 views

How to prove the probability of 2 times expectation is less than 1/2? [closed]

Suppose X is a non-negative random variable and E(X) = m. Then how to prove the probability P[X ≥ 2m] ≤ 1/2, more generally P[X ≥ cm] ≤ 1/c, where c > 1?
0
votes
1answer
38 views

A Hashing Problem

Hashing: You are to store objects identified by integers from [0..N − 1]. You expect never to have to store more than K objects. How would you design the hash function? Describe a general approach to ...
0
votes
0answers
29 views

How to create the smallest possible unique number from one or many unordered numbers?

What I am looking for is very similiar to this question and that one, too. I need to connect two SQL tables by a many-to-many relationship (artists and song names). To achieve what I'm trying to do I ...
1
vote
0answers
19 views

the meaning of 4-wise hash function

If someone says: 4-wise independent sign (hash) functions $s_1,s_2, s_3 : [d] → \{+1, −1\}$, then what does it means? I cannot use k-wise Independence variables (the definition 1 ...
0
votes
0answers
19 views

Type(s) of Hashing function that keeps the ordering information

I am asking this question from a perspective that we need to store a set of hashed data that can be queried later for in an ordered fashion. My situation is that some data has to be encrypted, I am ...
0
votes
0answers
61 views

KoreK's ChopChop Attack (Inverse Arbaugh Inductive Attack)

I would like to know how KoreK's "ChopChop" attack on the WEP protocol works on a basic mathematical level. His original source code provides little clue as it uses precomputed values, the origins of ...
3
votes
2answers
94 views

An efficient way to find anagrams

Consider a set of words where you want to divide the set into subsets of words, where all members of each subset are anagrams (same letters, different arrangement). You can do this computationally in ...
2
votes
1answer
49 views

Finding a path in a graph by its hash value

Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$. Question: ...
0
votes
0answers
25 views

general hash function question

The question: let it be two data structures that are represented by hash tables $T_1,T_2$ with chaining ($T_1,T_2$ are arrays of linked lists), and hash functions h1,h2 accordingly. Suppose that the ...
0
votes
1answer
39 views

Hashing: Quadratic Probing

I have the following to prove, unfortunately I am not able to do so. Let h, h' be hash functions: $h(k,i) = (h'(k) + c_{1}i + c_{2}i^2)$ mod $m$. Show the following: if m is prime and $c_{2} \neq 0$ ...
0
votes
0answers
21 views

Average operations on a hashtable

Suppose we are given an empty hash table of size $n$, where collisions are resolved by re-hashing (open addressing). Next, $n/2$ items are randomly inserted into the table using a hash function that ...
7
votes
0answers
110 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
3
votes
1answer
51 views

Are there any applications of checksums and/or cryptographic hash functions in pure mathematics?

Are there any applications of checksums and/or cryptographic hash functions in pure mathematics? I've tried Googling this and haven't found anything. If you've got any other application of ...
0
votes
0answers
41 views

What's the mathematical model of Consistent Hash?

What's the mathematical model of Consistent Hash? There are several implementations: Karger's implementation using a bucket cycle: Jump Consistent Hash [Highest Random Weight (HRW)][3] hashing: ...
0
votes
1answer
96 views

Math behind perfect hash

I am reading material on cryptographic hash functions and it says "Collision resistant property : for a hash of length L, a perfect hash would take $2^{L/2}$ attempts." Can someone explain why? ...
1
vote
0answers
81 views

Minimal perfect hash function

If I have list of $n$ unbounded different random integers, is it always possible to find such integers $\alpha$, $\beta$ and $\gamma$, that function $$f(x)=((\alpha\times x+\beta)\mod\gamma)\mod n$$ ...
0
votes
0answers
18 views

Find all groups that meets the condition

I have $n$ elements, each of them have two unsigned int attributes $x$ and $y$. Now I'd like to find out all the groups that fit the following condition: $A.x \geq B.y$ and $B.x \geq A.y$. The ...
0
votes
1answer
48 views

Exponentiation for hash function & associativity

Some cryptographic papers use $H^n(x)$ to mean $H(H^{n-1}(x))$ where $H^0(x) = x$ and $H$ is a cryptographic hash. So $H^3(x)$ would be $H(H(H(x)))$. Is this definition formally correct? It seems to ...
0
votes
0answers
17 views

Elgamal signature scheme

Suppose that $(m, r, s)$ is a message signed with an Elgamal signature scheme. Choose $h$ with $(h, p − 1) = 1$, and let $r_1 ≡ r^h\pmod p$, $s_1 ≡ sr_1h^{−1}r^{−1}\pmod {p − 1}$, and $m_1 ≡ ...
2
votes
0answers
69 views

Hashing Probability

I have just started to learn about the topic of hashing. I understand how it works and the difference between closed address and open address, but do not know how to calculate the probability of a ...
0
votes
0answers
15 views

n people and n saved seats - basic probability question [duplicate]

There are n people, each has a ticket for specific seat among the n seats in the theater. First person loses his ticket, and seats in a random seat. From now on each person 2,...,n tries to seat in ...
2
votes
2answers
278 views

Hash with Chaining Problems

I ran into an example in Computer Science Course. suppose we use Hashing with chanining and use table of size m. the hash function map record with key ...
1
vote
2answers
156 views

Probability of $k$ collisions

Say we have $m$ buckets. We select a random bucket and put a ball in it, we repeat this $n$ times. In the end what is the probability of having at least one bucket with exactly $k$ balls? I have ...
1
vote
0answers
61 views

provably secure hash function

I have the following question related to proving a hash function is secure if discrete log in group $\mathbb{G}$ is hard. The hash function (Gen,H) goes as follows: Gen: on input $1^n$, run to obtain ...
0
votes
0answers
31 views

Universal hash function when size of hash is p^m

Can we define universal hash function from $U \rightarrow T$ when $T=\{0,1,2,..,m-1\}$ and $m=p^a$? (where $p$ is a prime and a is an integer) I know that we can define universal hash funciton when ...
1
vote
1answer
34 views

Number of uniform hash functions

how many uniform hash function I can create when I want to hash elements from $U$ where $|U|=m \cdot r$ , $m,r$ are integers. a hash function $h:U \rightarrow T $ , $|T|=n$ is uniform if ...
1
vote
0answers
85 views

Is MD5 hash a bijection for input length < $2^{128}$ bits

The MD5 hashes have a length of 128 bits. It seems therefore obvious that if we could get all hashes from MD5 for more than $2^{128}$ inputs, at least 2 hashes would be identical. But what if we ...
1
vote
0answers
58 views

Consistent hashing using modulo

Following my answer here: Suppose I have n servers, and I want to distribute files evenly between them (same number of files on each server). Initially n=2 and I use the following function to map a ...
1
vote
0answers
52 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, ...
2
votes
2answers
121 views

Probability of 8 or 9 digit sequence colliding in the same place in two 65 digit numbers

I have two numbers: 3032643431333337636238613038343231383364303731376566303037663231 3861663464383131656131653461343961343364303737663565356561653361 36430373 ...
3
votes
1answer
131 views

Toy cryptographic hash function for education purposes?

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for ...
0
votes
1answer
44 views

Find a function that maps x,y to $[0, n ( n + 1) / 2)$

Can you find me a bijective function that maps positive integers $x, y$ such that $0 \leq x < y \leq n$ to integers in $[0, n(n+1)/2)$ to use as a hash function?
1
vote
1answer
217 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
0
votes
1answer
70 views

Hashing function probability of collision, is this solution wrong?

We hash n keys into k=1000 memory locations one by one. What is the probability that the first i records do not produce a collision. Assume each key is independently and uniformly hashed into the ...
1
vote
1answer
946 views

How Jaccard similarity can be approximated with minhash similarity?

In Page 81 of this book, Mining of Massive Data Sets. It says the following: Now, consider the probability that $h(S_1) = h(S_2)$. If we imagine the rows permuted randomly, and we proceed from the ...