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

1
vote
1answer
45 views

What math do I need to know for MD5?

This could fit into a lot of areas of SO but I feel like mathematics will know best. What area of math is used for something like an MD5 or SHA algorithm? Is there a mathematical equation/skeleton ...
0
votes
1answer
19 views

Girth of directed graphs

The definition of girth of an undirected graph is defined as the length of the smallest cycle in the graph. Some directed graphs have no cycle (a directed path that stars and ends at the same vertex) ...
0
votes
0answers
18 views

Calculation of the avalanche effect coefficient.

Given a strict avalanche criterion matrix/dependence matrix for a hash function,how do I calculate the avalanche coefficient for it. I want to calculate a single parameter(value) which represents the ...
0
votes
1answer
15 views

does calculating the arithmetic mean of a serie of standar deviation measures make sense?

I'm trying to test if a hash function mantains a even distribution of values. My plan is to generate a set X of hashes and a integer Y symbolizing "slots" to see how many of the hashes maps to the ...
0
votes
0answers
3 views

Does this function satisfy the Uniform Difference Property?

Does $h_{a,b}(x) = ((ax + b) \bmod 2^w)/2^{w-M}$ satisfy the Uniform Difference Property: given constant integers $w, M: w >= M$, and for any choice of distinct $x$ and $y$ in $[0, 2^w]$, $h(x) - ...
0
votes
2answers
22 views

permutation symmetric hash function

I'm searching for good hash-function for N-dimensional vector of M-bit integer numbers with a property that any permutation of the coordinates gives the same result. e.g. $ h(x,y,z) = h(x,z,y) = ...
1
vote
1answer
47 views

How can I convert this unique string of characters into a unique number?

I have an unusual programming problem and the math side of it has me stumped. It's probably a simple answer but math isn't my strongest area. I've generated a unique string of 7 characters which are ...
2
votes
1answer
48 views

probability of collision from hashing

So i have a hash table that can hold 100 elements. It currently stores 30 elements. What is the probability that the next 2 inserts will result in at least one collision? What i did was figure out ...
0
votes
1answer
22 views

Special-purpose hash functions

I am trying to create a special purpose hash function that will have as few collisions as possible. $99\%$ of the input will be sequential numbers, from $1$ to $N$. The size of the hash table will be ...
0
votes
2answers
57 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 ...
0
votes
0answers
10 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
1answer
18 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
58 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
33 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 ...
3
votes
0answers
178 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
25 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
62 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
23 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
53 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
109 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
43 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
67 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
50 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
42 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
33 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
20 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
20 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
87 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
112 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
57 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
31 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
86 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
123 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
53 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
49 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: ...
1
vote
1answer
137 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? ...
2
votes
0answers
91 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
19 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
53 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
21 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
74 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 ...
2
votes
2answers
305 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
167 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
66 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
39 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
36 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
90 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
67 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 ...