  With the accelerated adoption of end-to-end encryption, there is an
opportunity to re-architect security and anti-abuse primitives in a manner that
preserves new privacy expectations. In this paper, we consider two novel
protocols for on-device blocklisting that allow a client to determine whether
an object (e.g., URL, document, image, etc.) is harmful based on threat
information possessed by a so-called remote enforcer in a way that is both
privacy-preserving and trustworthy. Our protocols leverage a unique combination
of private set intersection to promote privacy, cryptographic hashes to ensure
resilience to false positives, cryptographic signatures to improve
transparency, and Merkle inclusion proofs to ensure consistency and
auditability. We benchmark our protocols -- one that is time-efficient, and the
other space-efficient -- to demonstrate their practical use for applications
such as email, messaging, storage, and other applications. We also highlight
remaining challenges, such as privacy and censorship tensions that exist with
logging or reporting. We consider our work to be a critical first step towards
enabling complex, multi-stakeholder discussions on how best to provide
on-device protections.
