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
19 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
502 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
votes
0answers
15 views

Combing properties of Random Hashes and passing the dieharder test

I have two streams of numbers, range A are 64 bit numbers and may be largely sequential. In fact one of the issues is I don't know the full range and properties of these numbers. The other range (B) ...
0
votes
1answer
25 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 ...
0
votes
0answers
28 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 ...
0
votes
0answers
20 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
47 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 ...
0
votes
0answers
12 views

random hash function, compute the expected number of empty table entries..

I am working on hash tables.In hash tables we have wastage of space due to empty table entries. can we have any hash function that can compute expected number of empty entries. I have seen the same ...
2
votes
2answers
80 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
51 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 ...
0
votes
1answer
47 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
36 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
26 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
0answers
27 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
0
votes
0answers
25 views

Universal hashing proof

So I tried doing this proof but I do not know how to start it properly. I know I have to show that the hash function family has the consistent and random property. The first is rather obvious to ...
1
vote
0answers
37 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
23 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
70 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
39 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 ...
0
votes
0answers
25 views

higher order hash functions

I am trying to find a functions which can efficiently transform (input) N number to and Integer K (and uniformly distribute it over some range - will use this as hash function). It is kind of a hash ...
1
vote
1answer
46 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 ...
1
vote
1answer
95 views

Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
1
vote
3answers
339 views

Calculate unique Integer representing a pair of integers

I have a pair of positive integers $(x, y)$, with $(x, y)$ being different from $(y, x)$, and I'd like to calculate an integer "key" representing them in order that for a unique $(x, y)$ there is an ...
0
votes
0answers
17 views

How many torrents are required to have a 50% chance of a duplicate infohash?

So I was wondering how many torrents would need to be created so there would be a 50% probability of two different torrents having identical info-hashes. If you could give a general formula for ...
3
votes
0answers
66 views

Finding collision for a hash function

Is there a way to find a collision for a given hash function without brute forcing? The particular hash function I'm talking about is the one used by Python (simplified version given below). It ...
0
votes
0answers
51 views

Hash functions that produce a point on an elliptic curve.

I see in some cryptographic papers, that the authers of those papers utilize of a hash function such that that hash function converts an integer value or octet-string value as input, to a point on an ...
1
vote
1answer
79 views

How can one gurantees the intersection of two set is empty with respect to its hash value?

Let's say we have sets A = {1,2,3} and B = {1,3,10} and our hash function is h(x) = 2x + 1(mod9) therefore H(A) = {3,5,7} H(B) = {3,7} Therefore if there is no intersection between the ...
1
vote
1answer
211 views

Probability of a slot having exactly K elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
0
votes
3answers
148 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
0answers
81 views

Is Hash(bG) equal to b(Hash(G))?

Assume b is an integer, G is a basepoint in an elliptic curve, and Hash is a one-way hash function. Is Hash(bG) equal to b(Hash(G)) ? or not? Note: A hash function is any algorithm or subroutine ...
1
vote
1answer
135 views

Bit permutations and collisions of compression function

I'm having trouble finding a good method for solving the following problem: If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation ...
2
votes
1answer
458 views

Can someone offer an intuitive understanding of linear/quadratic probing and double hashing?

I'm reading through Introduction to Algorithms, and I'm having trouble grasping intuitively how linear probing, quadratic probing, and double hashing exactly work. I suspect my confusion lies within ...
2
votes
3answers
240 views

Birthday Problem applied to collisions

I'm trying to extend the birthday problem to detect collision probability in a hashing scheme. Here is my problem. I use the letters and numbers [A-Z][a-z][0-9] to make a set of keys by randomly ...
3
votes
1answer
325 views

“Additive” hash function

I need a hash function that is easily computable in parallel(think of MapReduce framework), so such hash function must be "additive". I.e. given such function f, ...
1
vote
1answer
118 views

How to create 2048 random bits from 256 bits?

Would merely repeating the same value 8 times be sufficient ? Or is there a more clever approach for doing this ? The 256 bit values would be generated from SHA256 of files.
2
votes
1answer
136 views

Difference between universal and k-universal

After reading definitions of universal and k-universal (or k-independent) hash function families, I can't get the difference between them. Also, I couldn't find any examples of hash function families ...
1
vote
1answer
93 views

probability of repeating values in a hashmap

Suppose you have a hashmap where you store values. The hashmap is of size m and supports chaining. The hash function is simple uniform hashing assumption. I understand that the average length of a ...
0
votes
1answer
125 views

Universal hashing (bijection) with multiplication

I came across this question while thinking about a CS problem: Given a set $S = [a,b]$ , and a string $x \in S^{n}, x = r_1r_2 \cdots r_n$, under what conditions is $H(x) = r_1 * r_2 * \cdots * r_n$ ...
1
vote
1answer
53 views

Function for unique hash code

I am interested in finding $F(x,y)$, such that $x$ and $y$ $\in \mathbb Z^+$ and $F(x,y)$ is one to one function i.e., $F(x,y)$ is unique for any unique unordered pairs of $x$ and $y$. Regards, ...
1
vote
0answers
96 views

Collision resistant hash function

A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$. ...
0
votes
1answer
61 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: ...
2
votes
1answer
204 views

Is the product of 2 unique prime number unique?

I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? ...
0
votes
1answer
99 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
166 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 ...
3
votes
1answer
478 views

Do hashing functions have a probability distribution calculated for their output?

This question might look strange, so I will try to be clear. Consider a hashing function $f : M \mapsto H$ which takes a message with arbitrary length $m \in M$ as input and returns a hash $h \in H$ ...
1
vote
1answer
811 views

hash function for matrices over finite field (Matlab)?

What is a good hash function for small nonsingular matrices over a field $\mathbb{F}_p$ for $p$ prime? I'm looking for an integer function which is close to being injective (but not necessarily ...
0
votes
1answer
571 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 ...
1
vote
1answer
2k views

Why choose a prime number as the number of slots for hashing function that uses divison method?

The division method is one way to create hash functions. The functions take the form: h(k) = k mod m Where k is a key and m is the number of slots Edit: If this is my hash function why should ...
1
vote
2answers
87 views

How to implement a hash function intentionally prone to preimage attacks? (and hence pseudo-reversible)

I need to design a hash function such that it is possible to enumerate all possible 'candidate' input strings (preimages) for a given hash (image). It must otherwise be a normal hash function [i.e. ...
3
votes
1answer
398 views

Help in understanding the properties of prime numbers

I was reading about hashing. The oldest/standard approach is to use a prime number to produce the hash. At first I couldn't get why use a prime when I came to this Why hash functions use primes: ...