The hash function h maps binary vectors of dimension m to binary vectors of dimension n, where m > n, with the help of an n×m matrix H with binary elements that are generated randomly.

computer science

Description

Q1. (25 points - part (a) and (b) are purely written questions, part (c) requires implementation and code submission) In this question, you will analyze the empirical and theoretical collision probability for a new hash function.

The hash function h maps binary vectors of dimension m to binary vectors of dimension n, where m > n, with the help of an n×m matrix H with binary elements that are generated randomly. More specifically, given the matrix H, the hash function h : {0,1} m → {0,1} n provides the following hash value for a key x ∈ {0,1} m :


where the mod operator is applied element-wise (to the obtained vector Hx). 

For instance, if m = 3, n = 2, H is the matrix consisting of all ones, x is the vector of all ones, then the obtained vector Hx will be the vector of all threes, and when the element-wise mod 2 is applied, the two-dimensional vector h(x) will be obtained as the vector of all ones.


Related Questions in computer science category