Cryptography and Security (cs.CR)

Abstract: In July 2022, we organized a workshop (with the title Differential privacy (DP): Challenges towards the next frontier) with experts from industry, academia, and the public sector to seek answers to broad questions pertaining to privacy and its implications in the design of industry-grade systems. This document is the only public summary of the conversations from the workshop. There are two potential purposes of this document, which we envision: i) it serves as a standing reference for algorithmic/design decisions that are taken in the space of privacy, and ii) it provides guidance on future research directions. The document covers a broad array of topics, from infrastructure needs for designing private systems, to achieving better privacy/utility trade-offs, to conveying privacy guarantees to a broad audience. Finally, the document also looks at attacking and auditing these systems.

Abstract: Stubborn mining attack greatly downgrades Bitcoin throughput and also benefits malicious miners (attackers). This paper aims to quantify the impact of block receiving delay on stubborn mining attack severity in imperfect Bitcoin networks. We develop an analytic model and derive formulas of both relative revenue and system throughput, which are applied to study attack severity. Experiment results validate our analysis method and show that imperfect networks favor attackers. The quantitative analysis offers useful insight into stubborn mining attack and then helps the development of countermeasures.

Abstract: Legislators and policymakers worldwide are debating options for suppressing illegal, harmful and undesirable material online. Drawing on several quantitative datasets, we show that deplatforming an active community to suppress online hate and harassment, even with a substantial collective effort involving several tech firms, can be hard. Our case study is the disruption of the largest and longest-running harassment forum Kiwi Farms in late 2022, which is probably the most extensive industry effort to date. We collected complete snapshots of this site and its primary competitor Lolcow Farm, encompassing over 14.7M posts during their lifespan over the past decade. These data are supplemented with a full scrape of the Telegram channel used to disseminate new updates when the forum was down, tweets made by the online community leading the takedown, and search interest and web traffic to the forum spanning two months before and four months after the event. Despite the active participation of several tech firms over a few months, this campaign failed to shut down the forum and remove its objectionable content. While briefly raising public awareness, it led to rapid platform displacement and traffic fragmentation. Part of the activity decamped to Telegram, while traffic shifted from the primary domain to previously abandoned alternatives. The community leading the campaign lost interest quickly, traffic was directed back to the main domain, users quickly returned, and the forum was back online and became even more connected. The net effect was that forum activity, active users, threads, posts and traffic were all cut by about half. Deplatforming a dispersed community using a series of court orders against individual service providers appears unlikely to be very effective if the censor cannot incapacitate the key maintainers, whether by arresting them, enjoining them or otherwise deterring them.

Abstract: We present a general compiler to add the publicly verifiable deletion property for various cryptographic primitives including public key encryption, attribute-based encryption, and quantum fully homomorphic encryption. Our compiler only uses one-way functions, or more generally hard quantum planted problems for NP, which are implied by one-way functions. It relies on minimal assumptions and enables us to add the publicly verifiable deletion property with no additional assumption for the above primitives. Previously, such a compiler needs additional assumptions such as injective trapdoor one-way functions or pseudorandom group actions [Bartusek-Khurana-Poremba, ePrint:2023/370]. Technically, we upgrade an existing compiler for privately verifiable deletion [Bartusek-Khurana, ePrint:2022/1178] to achieve publicly verifiable deletion by using digital signatures.

Abstract: Data obfuscation deals with the problem of masking a data-set in such a way that the utility of the data is maximized while minimizing the risk of the disclosure of sensitive information. To protect data we address some ways that may as well retain its statistical uses to some extent. One such way is to mask a data with additive noise and revert to certain desired parameters of the original distribution from the knowledge of the noise distribution and masked data. In this project, we discuss the estimation of any desired quantile and range of a quantitative data set masked with additive noise.

Abstract: Behavioral data generated by users' devices, ranging from emoji use to pages visited, are collected at scale to improve apps and services. These data, however, contain fine-grained records and can reveal sensitive information about individual users. Local differential privacy has been used by companies as a solution to collect data from users while preserving privacy. We here first introduce pool inference attacks, where an adversary has access to a user's obfuscated data, defines pools of objects, and exploits the user's polarized behavior in multiple data collections to infer the user's preferred pool. Second, we instantiate this attack against Count Mean Sketch, a local differential privacy mechanism proposed by Apple and deployed in iOS and Mac OS devices, using a Bayesian model. Using Apple's parameters for the privacy loss $\varepsilon$, we then consider two specific attacks: one in the emojis setting -- where an adversary aims at inferring a user's preferred skin tone for emojis -- and one against visited websites -- where an adversary wants to learn the political orientation of a user from the news websites they visit. In both cases, we show the attack to be much more effective than a random guess when the adversary collects enough data. We find that users with high polarization and relevant interest are significantly more vulnerable, and we show that our attack is well-calibrated, allowing the adversary to target such vulnerable users. We finally validate our results for the emojis setting using user data from Twitter. Taken together, our results show that pool inference attacks are a concern for data protected by local differential privacy mechanisms with a large $\varepsilon$, emphasizing the need for additional technical safeguards and the need for more research on how to apply local differential privacy for multiple collections.

Abstract: We propose a new approach, termed Hybrid DLT, to address a broad range of industrial use cases where certain properties of both private and public DLTs are valuable, while other properties may be unnecessary or detrimental. The Hybrid DLT approach involves a system where private ledgers, with limited data block dissemination, are collaboratively created by nodes within a private network. The Notary, a publicly auditable authoritative component, maintains a single, official, coherent history for each private ledger without requiring access to data blocks. This is achieved by leveraging a public DLT solution to render the ledger histories tamper-proof, consequently providing tamper-evidence for ledger data disclosed to external actors. We present Traent Hybrid Blockchain, a commercial implementation of the Hybrid DLT approach: a real-time, data-intensive collaboration system for organizations seeking immutable data while also needing to comply with the European General Data Protection Regulation (GDPR).

Abstract: Recently, the first feature-rich NTFS implementation, NTFS3, has been upstreamed to Linux. Although ensuring the security of NTFS3 is essential for the future of Linux, it remains unclear, however, whether the most recent version of NTFS for Linux contains 0-day vulnerabilities. To this end, we implemented Papora, the first effective fuzzer for NTFS3. We have identified and reported 3 CVE-assigned 0-day vulnerabilities and 9 severe bugs in NTFS3. Furthermore, we have investigated the underlying causes as well as types of these vulnerabilities and bugs. We have conducted an empirical study on the identified bugs while the results of our study have offered practical insights regarding the security of NTFS3 in Linux.

Abstract: Two party differential privacy allows two parties who do not trust each other, to come together and perform a joint analysis on their data whilst maintaining individual-level privacy. We show that any efficient, computationally differentially private protocol that has black-box access to key agreement (and nothing stronger), is also an efficient, information-theoretically differentially private protocol. In other words, the existence of efficient key agreement protocols is insufficient for efficient, computationally differentially private protocols. In doing so, we make progress in answering an open question posed by Vadhan about the minimal computational assumption needed for computational differential privacy. Combined with the information-theoretic lower bound due to McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan in [FOCS'10], we show that there is no fully black-box reduction from efficient, computationally differentially private protocols for computing the Hamming distance (or equivalently inner product over the integers) on $n$ bits, with additive error lower than $O\left(\frac{\sqrt{n}}{e^{\epsilon}\log(n)}\right)$, to key agreement. This complements the result by Haitner, Mazor, Silbak, and Tsfadia in [STOC'22], which showed that computing the Hamming distance implies key agreement. We conclude that key agreement is \emph{strictly} weaker than computational differential privacy for computing the inner product, thereby answering their open question on whether key agreement is sufficient.