# Password Similarity Using Probabilistic Data Structures
## 3 Password Similarity
### Bloom Filters for Text Similarity  
A Bloom Filter, denoted in this paper as \(\beta\), is a probabilistic data structure which can be used to cache data and speed up operations such as lookup in databases [16; 17; 18]. It is composed by:  
* a bucket which can be an array of bits initially set to the false value (0), we reference to its size in the number of bits as \(\kappa\);
* \(\Gamma\), a set of hash functions which will be used to insert and check values. The relevant operations on a filter to measure similarity are:
* \(Create(\Gamma,\kappa)\rightarrow\beta\) which generates a Bloom Filter \(\beta\) using the hash functions present in the set \(\Gamma\) with a bucket of size \(\kappa\). * \(Insert(\beta,s)\) which inserts the bit string \(s\) in the Bloom Filter. * \(Check(\beta,s)\to Boolean\) which checks if the value \(s\) is not present in the filter or if it collides with a value which is already there. * \(QInsert(\beta,s,\
u)\) that inserts the string \(s\) splitting it in \(\
u\)-grams. * \(Distance(\beta_{1},\beta_{2})\to Real\) that returns the distance between two Bloom Filters. To be comparable, two Bloom Filters must have the same bucket size \(\kappa\), and need to use the same set of hash functions \(\Gamma\). An insertion operation (\(Insert(\beta,s)\)) of a string \(s\) in a Bloom Filter \(\beta\) is performed according to the following steps:  
* the value that must be inserted into the bucket is hashed using the set of hash functions; The hash functions output must be re-mapped to provide indexes in the co-domain of cardinality \(\kappa\). * every bucket slot indexed by the keys got using the hash functions is set to the true value (1). This operation therefore inserts the hashed value into the filter, setting the corresponding hash values to the true value. The process is described in Figure 1 which pictures an insertion of the strings _password_1234 and _password_123!. The verification process of the string \(s\) presence in the filter \(\beta\left(Check(\beta,s)\to Boolean\right)\) is analogous to the insertion case:  
* The element \(s\) is hashed against all the functions to get a list of indexes;
* If any index points to a false value, then the element is not present in the filter for sure. The Bloom Filter never exhibits false negatives. * Otherwise the value could be present in the filter, but due to the collision possibility of the hash functions, the result can be a false positive. This procedure is illustrated in Figure 2.  
Bloom filters can be used for text similarity using distance-sensitive hash functions [19] such the ones introduced by [PERSON] et al. in [20], or using an n-gram approach. This latter technique divides the string in n-grams and hashes every resultant n-gram with the hash functions present in the set, constructing a solution similar to locality-sensitive hashing [21, 22]:  
The hashing procedure to enable the measure of distance is presented in Figure 3. The similarity of the two sets can be calculated by using various distance definitions, by extending the check procedure to yield the number of n-grams which are the same in the two strings, independently of the order. The similarity distance of two Bloom Filters can be expressed using distance and similarities coefficients [23]. The main ones are The Jaccard coefficient [24] (which we will denote with \(J\)), the Dice coefficient [25] (which we will denote with \(\delta\)) and the Cosine similarity [26] (denoted by \(\phi\)).