Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience

Computer Science > Cryptography and Security [Submitted on 17 Apr 2026] Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience Xinyuan Zhang, Anrin Chakraborti, Michael K. Reiter Blocklisting is a common technique for preventing the use of known malicious content. However, conventional blocklisting infrastructures require either the blocklist to be public or clients to reveal their queries to the blocklist server. In this work, we introduce a private blocklisting framework, Half-Moon Cookie, by which a client can check an item against a proprietary blocklist held by a server, to determine whether the item is close to any blocklist element in a metric space. Critically, our design separates the embedding step from the blocklist check, so that performance degrades with their sum and not their product. Still, this check might be too costly to perform on the critical path of using the item, and so our design also supports a very efficient check that an item previously passed the blocklist check. In doing so, we support applications where one client can perform the blocklist check on the item before sending it, and recipients can more efficiently confirm the previous result before using the item, thereby avoiding TOCTOU attacks. We demonstrate how Half-Moon Cookie can be instantiated for similarity-based malware detection, enabling effective identification of malicious executables without revealing client inputs or disclosing the underlying blocklist. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2604.15641 [cs.CR]   (or arXiv:2604.15641v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.15641 Focus to learn more Submission history From: Xinyuan Zhang [view email] [v1] Fri, 17 Apr 2026 02:35:57 UTC (432 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)