# Password Similarity Using Probabilistic Data Structures
## 3 Password Similarity
### Privacy Guarantees  
To size the filter, some criteria can be derived from the following formula, as stated in the \"classical\" work by [PERSON] [16],  
\[fpp=\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^{k} \tag{1}\]  
where \(fpp\) is the false positive probability of the filter. This can be calculated a-priori from the variables \(m\), \(k\) and \(n\), defined as:  
* \(m\), the cardinality of the set on which the filter is built;
* \(k\), the number of different hash functions that are used to hash values into the filter;
* \(n\), the number of elements which will be inserted into the filter.  
The formula is derived from the evaluation of the probability of an item to be represented by only 0 in the Bloom Filter set. In cases of uniform distribution, as it happens with hash functions used by a Bloom Filter, this probability is defined as \(1-\frac{1}{m}\). This value needs to be exponentiated to the number of hash functions \(k\) multiplied by the number of elements. That is a consequence of the construction of the _Insert_ operation: an operation of this kind is required for every inserted value. A single _Insert_ operation will hash a single input string for every hash function in the hash-set \(\Gamma\). The resultant false positive probability is therefore the probability of having only value set to 1 for every result of our hash function set.  
From this formula we can derive the optimal values for the filter size and the number of hash functions to use. For a specific number of elements, that will be inserted in the filter, we can choose a fixed \(fpp\) to get a desired percentage of false positives. To get the formulae to calculate these optimal values, we first need to approximate the value of fpp to \(fpp\approx(1-e^{-kn/m})^{k}\). As explained in [32]  
Figure 3: n-gram insertion procedure with two strings. The strings are divided into n-grams (in this case bi-grams) and hashed using an Insert operation for every n-gram.  
the optimal number of hash functions can be found from the derivative of the \(fpp\). Let us declare \(g=k\ ln(1-e^{\frac{-km}{m}})\), minimizing this function \(g\) will lead us to the optimal (minimum) number of hash function. Therefore we can find that the global minimum is defined as: \(k^{\prime}=\frac{m}{n}ln(2)\). From this formula we can derive the optimal value for the size of the array. Replacing k' to k in the Equation (1) we find  
\[fpp\approx(1-e^{\frac{-km}{m}})^{k}=(1/2)^{\frac{m}{n}\ln(2)}\]  
Which can be resolved for \(m\), obtaining its optimal value, which is:  
\[m_{opt}=-\frac{n\ \ln(fpp)}{(\ln 2)^{2}}\]  
Obviously, these values must be integers, therefore we can apply a ceil to the result of the formulae, obtaining:  
\[m^{\prime}=\left\lceil m_{opt}\right\rceil=\left\lceil-\frac{n\ln fpp}{(\ln(2) )^{2}}\right\rceil\qquad\qquad k^{\prime}=\left\lceil\frac{m^{\prime}}{n}\ln( 2)\right\rceil\]  
The rationale behind these sizing formulae comes from the observation that as the size of buckets increases, the probability of collisions decreases. Using this approach, a Bloom Filter with a controllable number of false positives can be tuned to fit any specific scenario. Conversely, as it is useful for the proposed application in order to enhance password confidentiality, a Bloom Filter can be designed in such a way to have a big number of false positives, thus obfuscating data by forcing collisions. Password confidentiality could be protected also by adopting privacy-preserving approaches, such as \(\delta\)-presence [33] or differential privacy [34]. These approaches take in consideration the amount of data stored into a database, or the filter in this case, and try to anonymize the data among many false positives. In this case the approach is directly applicable to the filter which can gain a lot of advantages in terms of privacy from this approach. Specific metrics for these scenarios were studied by [PERSON] et al. in [35], which proposed \(\gamma\)-deniability and after [PERSON] et al. in [36].