Questions tagged [hash-function]

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.

Filter by
Sorted by
Tagged with
1
vote
0answers
67 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 mean?}$...
1
vote
1answer
58 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
2answers
1k views

Proof of calculating MinHash

I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for ...
0
votes
1answer
1k views

Is this function reversible?

I have a function which takes an integer from within a range (for example, 0-9999 with a range of 10,000) which outputs another integer within the same range. To my understanding, this is a perfect ...
0
votes
1answer
2k views

Analogy of Binary subtraction to decimal subtraction [duplicate]

Possible Duplicate: How to do +, -, *, / with number in a base b? Subtraction of numbers with arbitrary bases This is a very basic question. But I come from non computer science background and ...
0
votes
2answers
82 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
1answer
74 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
116 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
1answer
119 views

Unique $C = \operatorname{hash}(A, B)$

I want to derive a non-associative operation $\circ$ such that $C = A \circ B$ and that same $C$ can not be obtained by any other combination(s) of $A$ and $B$ e.g. much like $C = \operatorname{hash}(...
0
votes
1answer
27 views

Universal hashing family

I'm not really sure this question is proper for MathExchange but I have found it more suitable than StackOverFlow. So, I'm taking the course of Data Structures and Algorithms and we got some example ...
0
votes
1answer
72 views

What is the probability that the first collision occurs at the Kth insertions?

Question Consider a hash table with $n$ buckets, where external (overflow) Chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a ...
0
votes
1answer
40 views

How to calculate Pool reward for Race of Work?

I invented a new concept called Race of Work. It's based on Proof of Work, except there is no difficulty. Instead, there is a predefined time in each hour that consider being Block time. During the ...
0
votes
1answer
55 views

Finding all keys that hash to the same index

In my algo class, we discussed how uniform hashing algorithms aren't the best since it is possible to generate many keys that all hash to the same location. Take this hashing algorithm for example: ...
0
votes
1answer
169 views

Beginner level understanding concept on how to derive probability of hash collision

A hash function indexes all items in hash tables and searches for near items via hash table lookup. The hash table is a data structure that is composed of buckets, each of which is indexed by a hash ...
0
votes
2answers
124 views

Understanding locally sensitive hashing

I recently studied about locally sensitive hashing an a follow explanation was given to me. To produce a hash for a particular vector X with dimensions 5, Draw 10 random vectors to form a plane ...
0
votes
1answer
97 views

How to associate a unique integer to a matrix with integer elements in $[-1 , 100]$ [closed]

I have a $n \times m$ matrix $A$ with entries $A_{i,j} \in [0 , 100] \cap \mathbb{Z}$. with a great likelihood of 0 I would like to represent this matrix by the smallest integer value possible. What ...
0
votes
1answer
68 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 ...
0
votes
3answers
1k views

Chance that first 6 characters of a SHA-1 hash matching another SHA-1 hash?

Just what the question says -- what is the chance that the first six characters of a SHA-1 hash will match the first six characters of any given SHA-1 hash?
0
votes
2answers
52 views

Sum of weighted integers.

I have to calculate hash value for an array of integers. The array has $8$ integers always, and the integers are a permutation of the integers from $1$ to $8$. For example, the array can be like this: ...
0
votes
2answers
1k views

Are there any reversible hash function?

I read about hash function and I know that there can be some $x$ values which lead to the same $y$ ($x$ is the parameter of the hash function, $y$ is the result). Is there a way, given a $y$ and a ...
0
votes
1answer
12 views

Equivalance of statement

I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika Inside specifically had this ...
0
votes
1answer
932 views

is it possible to hash a range?

OK. I am not a math guy. I'm a programmer, so forgive me for the non-math lingo. let's say I have 3 ranges ...
0
votes
1answer
68 views

Generating hash function from given hash table?

I need help with understanding the following problem: In a factory, machines are making cars (1-n) along the production line. One machine is making one part on the existing construction (part 1 is ...
0
votes
1answer
149 views

Probability of collision in linear hashing?

Take an $u × m$ matrix $A$ filled with random bits(0,1). Given a non-zero vector $x$ in $\{0,1\}^u$, what is the probability that $x$ is in null space of $A$. All calculations are done modulo 2. ...
0
votes
1answer
465 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
1answer
48 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
1answer
39 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
1answer
157 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 ...
0
votes
1answer
117 views

Hash Functions and Probabilty

We are considering bit strings of length 160. Let there be some input x, and hash function $H(x) \rightarrow \left \{ 0,1 \right \}^{160}$. How many turns at least it takes to make collision: $H(x_{1})...
0
votes
1answer
69 views

Discreet bounding/mapping function with convergence/uniformity

Firstly, I was sent here from cstheory.stackexchange.com's FAQ, please tell me if this too is the wrong board (this board's FAQ indicates that I have to goto stackoverflow ??) This is my first ...
0
votes
0answers
20 views

A more general case of pairwise hash functions

I want to find a set $H = \{x\mid x=(x_1, x_2, \ldots, x_k), x_i \in \{0, 1, \ldots, k-1\}\}$, which is pairwise independent(every $x_i$ and $x_j$ of the vector $\mathbf x$ in the set, it's $k^2$ ...
0
votes
0answers
13 views

perfect hashing when not knowing the keys

knowing only the number of keys, n, how can you create a data structure of some sort that satisfies the following: initialization takes O(n) time after being initialized, you can insert and search ...
0
votes
0answers
13 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
0
votes
0answers
16 views

ElGamal Hash Function

The ElGamal signature scheme presented is weak to a type of attack known as existential forgery. Here is the basic existential forgery attack. Choose $u,v$ such that $\gcd(v, p — 1) = 1$. Compute $r = ...
0
votes
0answers
15 views

Probability of Hashing function to be perfect

Suppose we have a table of size M and we want to map N elements using a hashing function. This question had a lot of sub parts - The first one was that find the expected number of collisions which I ...
0
votes
1answer
31 views

True or False: After inserting '(2/3)m' elements into a hash table of size 'm', the probability of a collision upon the next insertion is at least 1/2

I was asked this question today, and my initial thought was - let's check a numeric example. So $m$ is obviously a multiple of $3$, and the smallest possible value is $m=3$. I divided the sample ...
0
votes
1answer
219 views

Expected maximum number of collisions for universal hash function

If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide? We break down this computation into a sequence ...
0
votes
1answer
20 views

Hash function that describe solid tetromino in the table

I'm trying to find a hash function that describes solid tetromino in a matrix 4x4 consisting of '0' and '1'. Here is what I mean: 1) 1111 0000 0000 0000 - solid tetromino, all this ones have the same ...
0
votes
1answer
31 views

Distinguishing cryptographic properties: hiding and collision resistance

I saw from Another question the following definitions, which clarifies somewhat: Collision-resistance: Given: $x$ and $h(x)$ Hard to find: $y$ that is distinct from $x$ and such that $h(y)=h(x)$. ...
0
votes
0answers
54 views

What enables hash function to produce uniform distribution given any distribution of input

I always take the uniformity of hash output as a given and didn't think much of it. Now I am kind of curious, how does good hash function like sha guarantees output uniformity. Intuitively, given 1:1 ...
0
votes
1answer
108 views

Universal hash function with probabilty of multiple collisions

The problem is: Consider the universal hash function: $h(x, r) = x_1 r_1 + ... + x_d r_d \mod m$, with $m$ prime, where for an integer dimension d>0 you break up the key $x=(x_1,x_2, . . .,x_d), 0 \...
0
votes
1answer
55 views

Expected number of unique selections

If I'm selecting $N$ elements uniformly at random (with replacement) from $\{1, \dots, M\}$, what is the expected number of values that are selected exactly once? The basis for this question ...
0
votes
0answers
423 views

Why is this hash function for english words is perfect hash?

I have a question that seems really intuitive to me but I can't think of a way to prove it. Assume we a have a file with words that are different from each other and contain digits only for example ...
0
votes
1answer
71 views

Hash Table Dynamical Resizing

I read the concept about dynamical resizing hash table from this lecture. And for my understanding, it claims that the average run time of all insertions is $O(1)$ for each iteration. Now, suppose we ...
0
votes
0answers
128 views

Generalization of Birthday Problem over Sets of Dates

At the classic version of the birthday problem we check for collisions of scalars $ b_i $ sampled from a uniform distribution. How can this be generalised over sets with more than one samples per ...
0
votes
0answers
88 views

Ordinal hash function

Suppose I have a set of integers from 0 to 100. Is there a non-invertible operation where the result is guaranteed to have the same ordinality as the input? In other words, given ...
0
votes
1answer
75 views

Why do we pick ax + b when doing universal hashing?

Why can't we pick just $x + b$ for example? I know that for universal hashing the Pr[$h(x) == h(y)$] $\leq 1/|n|$ But with the same hash function, just without the $a$ we can get $h(k) = (($k$ + b$ ...
0
votes
1answer
98 views

Hash function that can determine set similarity

I'm trying to come up with an effective way of handling slight variations in sets of numbers when hashing in an Information Retrieval system. I have a simple solution that is reasonably effective and ...
0
votes
0answers
65 views

Calculating 2 unknowns in mod 2^32 addition?

My question is fairly simple. Given equation: r = ( a + b + c ) mod m Where m = 2^32, and values r and a are known values. Assuming: Edit: b + c < m Is it possible to calculate a specific ...
0
votes
0answers
82 views

Hash table are collision events independent

Say I have some universal hash table of size $m$ and random input data set of size $n$. Let's define $I_{i}$ indicator RV as probability that while inserting ith key to the table collision happened. ...