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

2
votes
1answer
42 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
23 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
18 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$ ...
1
vote
0answers
40 views

Collision probability of string hashing algorithm

Consider the following string hashing algorithm which is based on the one listed on Wikipedia. aand INITIAL_VALUE are constants. ...
-1
votes
0answers
18 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 ...
6
votes
0answers
74 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
45 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
24 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
36 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
67 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
15 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
43 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
15 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
46 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
13 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
187 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
126 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 ...
0
votes
0answers
28 views

Probability of collision at given location for 2-independent hash function?

Assume a 2-independent hash function $h: [u] \rightarrow [m]$. What is the probability that for a given $i \in [u]$, a collision at location $h(i)$ occurs? In other words, what is the probability that ...
1
vote
0answers
50 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
76 views

Implementation of disjoint sets with union

I am looking at disjoint sets that support the function of the Union. The technique of height reduction of a tree: We always merge the smaller tree to the greater one, i.e. we make the root of the ...
0
votes
0answers
22 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
28 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 ...
0
votes
0answers
64 views

Conceptual hashing function with quadratic probing

Lengthy question here so please bear with me. When inserting keys 3,4,2,5,1 in the order given into the hash table of length m=5 using hash function $$h(k) = k^2 \mod m$$ Using $h(k)$ as the ...
1
vote
0answers
66 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 ...
0
votes
0answers
21 views

Calculating the distribution H, H(X) when H is chosen uniformly from a family of hash funcitions

Suppose I have a family $H$ of hash functions from $A$ to $B$ such that for all $x\in A$, $h(x)$ distributes uniformly in $B$ (the probability is taken over h) Now, if $X$ is some distribution over ...
1
vote
0answers
50 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
42 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
94 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
93 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
0answers
61 views

Proving modular hash function

I am having trouble getting started with the following problem : Suppose that keys are t-bit integers. For a modular hash function with prime M (the number of hash indexes), prove that each bit has ...
0
votes
1answer
38 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
134 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
0answers
28 views

Possibility for collision using 2 different Hash-Algorithms

I'm definitely no crack in mathematics so I hope you can help me. Hash algorithms provide functions for reducing big data to smaller ones. For instance, SHA-512 reduces a set of data down to 512 bit ...
0
votes
1answer
49 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
635 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(S1) = h(S2). If we imagine the rows permuted randomly, and we proceed from the top, ...
8
votes
6answers
598 views

Hide my invoice number

I'm not a mathematician, so please forgive any ignorance. I have a small business - I'm generating invoices incrementally. I'm currently on about invoice number 4000. I guess I don't want my ...
1
vote
1answer
68 views

hash function not using bitwise operations

I have a need for implementing an algorithm to validate that a given message is not altered after some operations (for instance after transmission over a medium). A typical way of doing this kind of ...
1
vote
1answer
86 views

Slot size bound for chaining

This is a question from CLRS Q) Suppose that we have a hash table with n slots, with collisions resolved by chain-ing, and suppose that $n$ keys are inserted into the table. Each key is equally ...
1
vote
1answer
116 views

Hash functions for unordered data

I am interested in stream hash functions for unordered data: Hash functions $g$ on lists which, given a two lists of integers $L_1, L_2$ where $L_2$ is a permutation of $L_1$, $g(L_1)=g(L_2)$. I can ...
1
vote
2answers
105 views

An “additive” cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data.

I want to use a cryptographic hash-function that allows calculating the hash of some data from the hashes of the parts of that data. This question was already asked on SO - "Additive" hash ...
2
votes
2answers
108 views

Is there a hashing algorithm that can be done on paper?

I often want to explain to non-computer literates about MD5, or why any sort of hashing is done. Is there any type of simple hashing algorithm that can be done with a pen and piece of paper (possibly ...
0
votes
0answers
74 views

describe a vector with a single unique number

Is there a way to uniquely describe a vector with a single ( = easy to store) value? e.g. have a function $H(\vec{v}): \mathbb{R}^{130} \rightarrow \mathbb{R} $ I have a lot of vectors in ...
1
vote
1answer
61 views

Does reducing 512-bit blocks to 128-bit hashes lead to 1/4 chance of collision?

This is a quote from a cryptography book called Implementing SSL / TLS Using Cryptography and PKI By Joshua Davies. MD5 operates on 512-bit(64 byte) blocks of input. Each block is reduced to a ...
0
votes
1answer
58 views

Number of combinations of balls in slots

Assume there are 9 identical balls, and each can be placed in one of 10 numbered slots. All balls must be placed in exactly one slot (i.e., you can't leave a ball out). How many combinations are ...
0
votes
1answer
34 views

Distinguishing between hash function digest and message corruption

As an initial disclaimer, I know virtually nothing about coding theory. I apologize in advice for incorrect or inappropriate terminology. The problem space I'm exploring is ensuring the integrity of ...
1
vote
0answers
48 views

Identity based encryption

I am implementing ID based encryption in c# right now i am having problem at the following mathematics $$H_1: \{0,1 \}^n \times \{0,1 \}^n \to \mathbb{Z}^*_p, \text{ what does this expression ...
0
votes
1answer
48 views

“Unique” number from several values

I'm trying to create a unique unsigned "long" number (64 bits) from a list of 4 other numerical values. Some function f(n1, n2, n3, n4) = x. The order of the values ...
2
votes
2answers
80 views

Calculate people needed to have all birthdays

for n people where n > 365, how can you calculate how many people you would need to expect that each of every distinct possible birthday would be had by at least one person at a given probability p? ...
1
vote
1answer
46 views

Polynomial division with reference to CRC32

The polynomials we're using will always have coefficients of either 1 or 0. We have a divisor polynomial which will always remain the same, we'll call this polynomial $D$. We have a dividend ...
1
vote
1answer
81 views

Calculate entropy of modified base32 hash

I am trying to develop a scheme for generating unique (probable within bounds) ids in a distributed application. I want the id to be easily remembered, easily spoken, and easily read. I chose base32 ...