Differentially Private Password Frequency Lists

By Jeremiah Blocki, Anupam Datta, Joseph Bonneau. 2016

62 citations recorded by the source corpus.

Given a dataset of user-chosen passwords, the frequency list reveals the frequency of each unique password. We present a novel mechanism for releasing perturbed password frequency lists with rigorous security, efficiency, and distortion guarantees. Specifically, our mechanism is based on a novel algorithm for sampling that enables an efficient implementation of the exponential mechanism for differential privacy (naive sampling is exponential time). It provides the security guarantee that an adversary will not be able to use this perturbed frequency list to learn anything of significance about any individual user’s password even if the adversary already possesses a wealth of background knowledge about the users in the dataset. We prove that our mechanism introduces minimal distortion, thus ensuring that the released frequency list is close to the actual list. Further, we empirically demonstrate, using the now-canonical password dataset leaked from RockYou, that the mechanism works well in practice: as the differential privacy parameter varies from 8 to 0.002 (smaller implies higher security), the normalized distortion coefficient (representing the distance between the released and actual password frequency list divided by the number of users N ) varies from 8.8 × 10−7 to 1.9 × 10−3. Given this appealing combination of security and distortion guarantees, our mechanism enables organizations to publish perturbed password frequency lists. This can facilitate new research comparing password security between populations and evaluating password improvement approaches. To this end, we have collaborated with Yahoo! to use our differentially private mechanism to publicly release a corpus of 50 password frequency lists representing approximately 70 million Yahoo! users. This dataset is now the largest password frequency corpus available. Using our perturbed dataset we are able to closely replicate the original published analysis of this data.

Subfields: Applied Psychology, Information Systems, Sociology and Political Science, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Psychology

In Information Systems

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning (2017, background): “Several works have adopted DP as an efficient defense mechanism such as [5, 7, 11, 12, 18, 23, 24, 37, 53, 60, 65, 72, 86].”
Discrete Distribution Estimation under Local Privacy (2016, methodology): “r releases randomized data (e.g., NIH releasing medical records) to protect sensitive user information (Dwork, 2006; Dwork et al., 2006; Dwork & Lei, 2009; Dwork, 2008; Diakonikolas et al., 2015; Blocki et al., 2016). 2. Preliminaries 2.1. Local differential privacy Let Xbe a private source of i”
Practical Differential Privacy for SQL Queries Using Elastic Sensitivity (2017, background): “Recent work has evaluated differential privacy mechanisms on real-world data [11,23,24], however this work uses a limited set of queries representing a single, special-purpose analytics task such as histogram analysis [11] or range queries [23].”
Plausible Deniability for Privacy-Preserving Data Synthesis (2017, background): “However, as several researchers have pointed out [12, 29, 6], a direct application is too costly to be practical for high-dimensional datasets due to the complexity of sampling, which grows exponentially in the dimension of the data records.”
Towards Practical Differential Privacy for SQL Queries (2017, background): “In contrast with previous evaluations of differential privacy [15, 32, 33], our dataset includes a wide variety of real queries executed on real data.”
Differentially Private Hierarchical Group Size Estimation (2018, background): “The work most closely related to our problem are unattributed histograms [19, 8] which are most often used to study degree sequences in social networks [24, 21].”
Differentially private anonymized histograms (2019, methodology): “Anonymized histograms are also referred to as histogram of histograms [1], histogram order statistics [2], profiles [3], unattributed histograms [4], fingerprints [5], and frequency lists [6].”
Differentially Private Hierarchical Count-of-Counts Histograms (2018, background): “The work most closely related to our problem are un-attributed histograms [19, 8] which are often used to study degree sequences in social networks [24, 21].”