VeriFPHM: Robust and Trustworthy Harmful Media Detection in End-to-End Encrypted Communication

Private Hash Matching (PHM) enables the detection of harmful media in end-to-end encrypted communication by comparing user media hashes against a server-side set of known harmful hashes, without exposing the hash set to the client or revealing unmatched media to the server. However, existing PHM schemes struggle to detect slightly modified media, lack efficient support for dynamic updates, and fail to provide verifiable guarantees, thereby undermining public trust and transparency. This paper presents VeriFPHM, a verifiable fuzzy private hash matching scheme tailored for robust and trustworthy harmful content moderation. It employs multivariate polynomial commitments and adaptive Merkle trees to enable batch verification of the integrity and consistency of the hash set. To support efficient dynamic updates, it optimizes the index tree by mapping subtrees to Cuckoo hash buckets, allowing for updating partial trees instead of rebuilding the entire tree. To prevent over-censorship and maintain detection efficiency, we design a two-step fuzzy matching protocol. Specifically, coarse-grained matching filters out benign media using enhanced index trees with efficient bucket access, followed by distance-aware fine-grained matching using a lightweight Learning with Parity Noise (LPN)-based Vector Oblivious Linear Evaluation (VOLE) protocol. Security analysis confirms that VeriFPHM preserves the privacy of both user content and the server-side hash set. Experimental results show that VeriFPHM achieves up to 100x speedup in certification efficiency over the scheme proposed by Scheffler et al. and superior update performance with high detection accuracy compared to the state-of-the-art (SOTA) schemes.