Practical Private Set Intersection Protocols for Privacy-Preserving Applications

Private set intersection (PSI) protocols are cryptographic protocols that allow two parties to securely compute the intersection of their private input sets without disclosing elements outside of the intersection. While this simple functionality turns out to be instrumental for many real-world applications, existing protocol designs and implementations unfortunately incur an impractical computation and/or communication overhead. As a consequence, service providers currently deploy insecure alternatives that threaten users' privacy at a large scale. Therefore, in this thesis, we design, implement, and evaluate practical PSI protocols to provide viable privacy-preserving alternatives for three specific application scenarios: mobile contact discovery, mutual authentication for Apple AirDrop, and database intersection analytics. Mobile Contact Discovery. Mobile messengers commonly offer a feature that allows users to discover their existing contacts on the platform based on the phone numbers stored in their address book. Unfortunately, we find that popular messengers implement contact discovery either by uploading the users' entire address books in the clear or by using simple hashing-based protocols. As we show that such hashing-based protocols are vulnerable to brute-force attacks, the users' entire social graphs are exposed to anyone with access to the service providers' infrastructure. To instead perform the matching procedure between address books and user databases in a privacy-preserving manner, we develop and optimize two PSI protocols that are significantly more efficient than the state-of-the-art protocols of Kiss et al. (PoPETs'17) while also providing security against malicious clients. By closely investigating the contact discovery implementation of three popular messengers (WhatsApp, Telegram, and Signal), we also find that due to insufficient rate limits, attackers can crawl the global user databases simply by enumerating phone numbers. For this problem, we propose multiple mitigation techniques, including a novel PSI-compatible rate-limiting scheme that strictly improves over the approach currently deployed by Signal. This part of the thesis is based on the following two publications: [KRS+19] D. KALES, C. RECHBERGER, T. SCHNEIDER, M. SENKER, C. WEINERT. "Mobile Private Contact Discovery at Scale". In: 28. USENIX Security Symposium (USENIX Security'19). Website: https://contact-discovery.github.io. Full version: https://ia.cr/2019/517. USENIX Association, 2019, pp. 1447–1464. CORE Rank A*. Appendix B. [HWS+21] C. HAGEN, C. WEINERT, C. SENDNER, A. DMITRIENKO, T. SCHNEIDER. "All the Numbers are US: Large-scale Abuse of Contact Discovery in Mobile Messengers". In: 28. Network and Distributed System Security Symposium (NDSS'21). Website: https://contact-discovery.github.io. Full version: https://ia.cr/2020/1119. Internet Society, 2021. CORE Rank A*. Appendix A. Mutual Authentication for Apple AirDrop. Based on the reverse-engineering efforts of Stute et al. (USENIX Security'19), we identify two privacy vulnerabilities in Apple's proprietary offline file sharing service AirDrop. They are rooted in the exchange of vulnerable hash values of contact identifiers during the authentication handshake that determines whether two device owners are mutual contacts. We demonstrate both attacks with a proof-of-concept implementation called "AirCollect" that can almost instantly recover the mobile phone numbers of nearby Apple users who open the sharing pane on their devices. As a privacy-preserving alternative, we develop "PrivateDrop". Our solution is based on two consecutive executions of optimized PSI protocols that provide security against malicious parties and additionally enforce authentic inputs. We implement PrivateDrop in Apple's native programming language Swift and show in an empirical performance evaluation on real Apple devices that the overall authentication delay of below one second preserves the user experience of the original insecure AirDrop protocol. This part of the thesis is based on the following two publications: [HHS+21a] A. HEINRICH, M. HOLLICK, T. SCHNEIDER, M. STUTE, C. WEINERT. "DEMO: AirCollect: Efficiently Recovering Hashed Phone Numbers Leaked via Apple AirDrop". In: 14. ACM Conference on Security and Privacy in Wireless and Mobile Networks (WiSec'21). Website: https://privatedrop.github.io. Full version: https://ia.cr/2021/893. ACM, 2021, pp. 371–373. Appendix C. [HHS+21b] A. HEINRICH, M. HOLLICK, T. SCHNEIDER, M. STUTE, C. WEINERT. "PrivateDrop: Practical Privacy-Preserving Authentication for Apple AirDrop". In: 30. USENIX Security Symposium (USENIX Security'21). Website: https://privatedrop.github.io. Full version: https://ia.cr/2021/481. USENIX Association, 2021, pp. 3577–3594. CORE Rank A*. Appendix D. Database Intersection Analytics. Scenarios where two companies or governmental agencies want to conduct analyses on data subjects they have in common without revealing their entire database are usually addressed with generic circuit-based PSI protocols that can compute arbitrary functions of the database intersection. The best prior circuit-based PSI protocols of Pinkas et al. (USENIX Security'15 and ACM TOPS'18) have a complexity of O(n log n/ log log n), where n is the number of database entries. In our work, we create the first circuit-based PSI protocol with almost linear ω(n) complexity that also significantly outperforms prior works in terms of concrete performance. Our construction is based on a novel hashing scheme called "2D Cuckoo hashing", which we analyze experimentally by spending millions of core hours on a high-performance computer. This part of the thesis is based on the following publication: [PSWW18] B. PINKAS, T. SCHNEIDER, C. WEINERT, U. WIEDER. "Efficient Circuit-Based PSI via Cuckoo Hashing". In: 37. Advances in Cryptology – EUROCRYPT'18. Vol. 10822. LNCS. Code: https://encrypto.de/code/2DCH. Full version: https://ia.cr/2018/120. Springer, 2018, pp. 125–157. CORE Rank A*. Appendix E. Overall, this thesis contributes to make private set intersection protocols sufficiently practical to provide privacy-preserving solutions for three widely-used real-world applications.