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
11 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 ...
1
vote
1answer
35 views

Why hash table size is prime? [closed]

In computer science, the size of the hash table is recommended to be prime. What is the property of prime number that makes it recommended to be the size of hashtable?
0
votes
0answers
14 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
22 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
74 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
43 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
24 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
48 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. ...
0
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
80 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
47 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
25 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
41 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
68 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
16 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
44 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
48 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
198 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
130 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
31 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
52 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
80 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
23 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
67 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
70 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
22 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
51 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
43 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
100 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
98 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
63 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
142 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
50 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
672 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
603 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
87 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
118 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
111 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
112 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
62 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
60 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 ...