Bloom Filters: Students at Some State University (SSU) select very bad passwords
ID: 3751456 • Letter: B
Question
Bloom Filters: Students at Some State University (SSU) select very bad passwords. The system administrator decided to use a Bloom Filter to prevent students from using the passwords “cat, dog, fish, and bear”. The Bloom Filter uses 3 hash functions (H1, H2, H3) and 10 bits in the hash table. When the hash functions are applied to the prohibited passwords, the results are:
H1(cat) = 8 H2(cat) = 1 H3(cat) = 2
H1(dog) = 1 H2(dog) = 9 H3(dog) = 1
H1(fish) = 2 H2(fish) = 8 H3(fish) = 2
H1(bear) = 2 H2(bear) = 4 H3(bear) = 1
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
Question 1B: List one value for H3(mouse) that would cause the "mouse" to be rejected as a password or explain why no value of H3(mouse) could cause this.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
Explanation / Answer
Although this question seems to be incomplete as there is no information about H1(mouse) and H2(mouse) while answering the question I will consider H1(mouse) and H2(mouse) as it exists.
Considering the values as:
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
Now if the value for H3(mouse) is either 1,2,4,8,9 any of this will prove that the mouse is a password that will get rejected. As here the concept of the "False positive of Bloom Filter" will come into the picture and will show that mouse belongs to the very bad password set. If we check the bit array, bits at these indices are set to 1 but we know that "mouse" was not in the very bad password set. As bits are already calculated and are set by the cat, dog, fish, and bear, hence bloom filter erroneously claim that "mouse" is present and thus generates a false positive result.
Bit 0
Bit 1
Bit 2
Bit 3
Bit 4
Bit 5
Bit 6
Bit 7
Bit 8
Bit 9
0 1 1 0 1 0 0 0 1 1