Abstract
Identifying the most popular items in a dataset—"heavy hitters"—is crucial for security tasks like blacklisting weak passwords. However, collecting this data traditionally compromises user privacy. This paper introduces a privacy-preserving system that combines local differential privacy (LDP) with secure two-party computation (2PC) to identify heavy hitters without revealing individual user data. The protocol is designed to be resilient against malicious users who attempt to manipulate results through "undercounting" attacks. Evaluations on massive real-world datasets and low-power IoT hardware demonstrate that the system is both accurate and practical for large-scale deployment.
Introduction
Weak passwords are a systemic threat to internet infrastructure. For instance, the Mirai botnet exploited common passwords across millions of IoT devices to launch massive DDoS attacks. To mitigate this, service providers aim to blacklist "over-popular" passwords. However, identifying these passwords typically requires a central server to collect and analyze user credentials, creating a significant privacy risk and a potential "honeypot" for attackers.
Furthermore, existing privacy-preserving methods often assume users are "semi-honest." In a real-world adversarial setting, a malicious actor might control a botnet and attempt to "undercount" specific weak passwords to prevent them from being blacklisted. This paper addresses the dual challenge of maintaining individual privacy while ensuring robustness against active manipulation.
Methodology
The proposed protocol operates in the local model, where data is processed on the user's device before transmission.
1. Domain Reduction and Fourier Identification
Passwords are first hashed into shorter $\ell$-bit strings (e.g., 16 or 32 bits). The core identification mechanism relies on the mathematical property that finding heavy hitters is equivalent to identifying large Fourier coefficients of the data distribution. The server sends a random vector $r$ to the device, which responds with the inner product of its password hash and $r$.
2. Secure Two-Party Computation (2PC)
To prevent malicious users from lying about their inner products (the "undercounting attack"), the authors employ 2PC. Two variants are provided:
- Garbled Circuits: An interactive method based on Yao’s protocol, optimized for speed.
- Quadratic Residuosity (QR): A number-theoretic approach allowing for a non-interactive message from the device.
3. Differential Privacy (DP)
To ensure the server cannot infer an individual's password from the single bit of information shared, the device uses randomized response (flipping the bit with a specific probability). Additionally, the server adds Laplacian noise to the aggregated counts before publishing the blacklist, protecting against coalition attacks.
Datasets and Evaluation
The system was evaluated using three large-scale leaked password databases: LinkedIn (174 million), Yahoo! (70 million), and RockYou (33 million).
As shown in the figure above, password popularity follows a Zipfian (power-law) distribution. This distribution is advantageous for the protocol: because a small number of passwords account for a vast majority of users, the "heavy hitters" remain distinguishable even after the addition of privacy-preserving noise.
To test real-world feasibility, a proof-of-concept was implemented on a Raspberry Pi 3 Model B, representing a typical low-power IoT device.
Key Results and Insights
- Accuracy: In simulations, the protocol identified the top 25 passwords in the LinkedIn database with 92% of the coverage achieved by an "ideal" non-private system.
- Performance: The interactive protocol runs in just 0.4 seconds on a Raspberry Pi. The non-interactive version, while more complex, requires less than 15 seconds of preprocessing, making both versions practical for IoT environments.
- Adversarial Resilience: By focusing on the "undercounting" threat, the paper addresses a critical gap in security-focused heavy hitter identification, where attackers have an incentive to hide the popularity of exploitable passwords.
- Quantified Privacy: Using a "Password Guessing Game" framework, the authors demonstrate that while sharing any information technically aids guessing, Differential Privacy keeps this risk within strictly controlled and acceptable bounds.
Conclusion
This work demonstrates that it is possible to identify globally popular weak passwords without compromising the privacy of individual users, even in the presence of malicious actors. The combination of cryptographic techniques and differential privacy provides a robust defense against both server-side spying and client-side manipulation. Future work includes exploring defense mechanisms that do not rely on heavy cryptographic primitives and extending the protocol to other domains, such as anonymizing traffic analysis in the Tor network.
Summary updated