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
0answers
41 views

Probability that an arbitrary element of a field has a specific structure.

This question is related to : http://crypto.stackexchange.com/questions/37351/encoding-an-element-in-r-rhr-way that I asked couple of weeks ago. The difference is that I did not take the collision ...
0
votes
0answers
8 views

How to prove pairwise independence of a family of hash functions?

I want to prove pairwise independence of a family of hash functions, but I don't know where to start. Given the family of hash functions: H with h(x) = a * x + b (mod M). ( Say h: U -> V, then: M ...
-2
votes
0answers
29 views

Probability of collision of some family of hash functions

Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $ h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some ...
0
votes
0answers
9 views

Need help in Hashing to create a fingerprint

Given a pattern P of length m and a text T of length n (n >= m), in which all characters ...
1
vote
1answer
34 views

Bijective function from $\Bbb N ^{n \times m}$ to $\Bbb N$?

I'm working on a hash function and I was wondering if there is a function which can tansform a matrix into a natural being bijective. For example: $A=\begin{bmatrix} 0&0&1\\ 2&0&1\\ 0&...
0
votes
0answers
14 views

Double hashing collision

I have these hash functions: $h_1 (x)=(5x+1) mod 13$ $h_2 (x)=1+(x mod 12)$ I have to insert 15 in this hashtable with indexes starting from 0 and x = empty: ...
1
vote
0answers
27 views

An m-dimensional space with each 'point' in the space having an n-dimensional value

Say I have an $m$-dimensional space (continuous or discrete) such that every point in that space has a value, and that value is an $n$-dimensional vector (continuous or discrete). My question is how ...
1
vote
1answer
14 views

Why the upper bound on parameters of a Linear Congruential Generator?

The Linear Congruential Generator used as a basis for Universal Hashing is defined by the equation using parameters $a$, $c$ and $m$: $$X_{n+1} = (a\cdot X_{n} + c) \mod m$$ with the following ...
1
vote
1answer
61 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
46 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
24 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
21 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
10 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) - h(...
0
votes
2answers
33 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) = h(y,...
1
vote
1answer
83 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
65 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
26 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
58 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
13 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
19 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
60 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
195 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
30 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
69 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
32 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: $$P(\...
0
votes
1answer
56 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
17 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
115 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
45 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
75 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
52 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
44 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
39 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
22 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 http://www.math....
0
votes
0answers
21 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
93 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
114 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
63 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
32 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
99 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
174 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
54 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 ...
1
vote
1answer
164 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
92 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
20 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
54 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 ≡ mr_1r^{−1}...
2
votes
0answers
76 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 ...