  Social media and other platforms rely on automated detection of abusive
content to help combat disinformation, harassment, and abuse. One common
approach is to check user content for similarity against a server-side database
of problematic items. However, this method fundamentally endangers user
privacy. Instead, we target client-side detection, notifying only the users
when such matches occur to warn them against abusive content. Our solution is
based on privacy-preserving similarity testing. Existing approaches rely on
expensive cryptographic protocols that do not scale well to large databases and
may sacrifice the correctness of the matching. To contend with this challenge,
we propose and formalize the concept of similarity-based bucketization~(SBB).
With SBB, a client reveals a small amount of information to a database-holding
server so that it can generate a bucket of potentially similar items. The
bucket is small enough for efficient application of privacy-preserving
protocols for similarity. To analyze the privacy risk of the revealed
information, we introduce a framework for measuring an adversary's confidence
in inferring a predicate about the client input correctly. We develop a
practical SBB protocol for image content, and evaluate its client privacy
guarantee with real-world social media data. We then combine SBB with various
similarity protocols, showing that the combination with SBB provides a speedup
of at least 29x on large-scale databases compared to that without, while
retaining correctness of over 95%.
