Half-Moon Cookie lets a sender run a one-shot private approximate blocklist check while receivers confirm it with an implicit check as fast as 0.19 s, resisting TOCTOU attacks

It formally defines the Half-Moon Cookie primitive and provides a general three-party framework consisting of an explicit check (the Embed-and-Map and Test-and-Commit ideal functionalities) and an implicit check (Implicit Check), where the server writes a hiding and binding token to an allowlist only after the explicit check passes. Prior private blocklist matching schemes (e.g., two-server PIR Checklist, Private Hash Matching, OPPRF/OKVS) perform one-shot matching and do not produce a hiding and binding token for fast later verification; Half Moon separates embedding from the blocklist check so each can be computed privately and efficiently with independently chosen methods. The paper gives Definition 1, three ideal functionalities (Fig. 1), and a security proof sketch for Theorem 5.1, with full proofs in Appendix D for threat models T1 (malicious sender) and T2 (semi-honest server), bounding advantages by FAR + 2|F|/|KP| + (qH+1)/|F|^θ and 1/2 + qH/|F|^θ respectively.

It provides an efficient instantiation over metric spaces embeddable into Hamming distance: an MX map embeds bit vectors into a finite field F^θ, a symmetric uncommon roots (SUR) metric is defined so that distance in F^θ equals the original Hamming distance, and an assumption-free fuzzy PSI protocol is adapted to perform the private distance check. Existing structure-aware PSI and approximate PSI rely on data-distribution assumptions, and Blass–Noubir operates directly on binary vectors and is incompatible; via MX and the SUR metric the Hamming-distance check becomes a field-distance computation realizable with noisy polynomial addition (Fnpa), supporting approximate matching without distribution assumptions. Definitions 4 and 5 and equations (6)–(9) establish the equivalence, and Theorem 6.2 shows Test-and-Commit achieves O(nθ) communication and computation assuming secure OLE and Fnpa.

It uses reusable garbled circuits (grounded in the CRGC framework) to split the embedding phase into reusable and non-reusable parts, decoupling circuit cost from input file size while not leaking the server's embedding key kf. A monolithic garbled circuit scales linearly with the input file; the authors report its latency is 231× and its network traffic 43,505× that of Half Moon's embedding for an average 194 kB email attachment, whereas this design keeps server-side workload independent of input size by splitting functionality per CRGC and inserting balanced gates. Table 2 shows that for TLSH, ssdeep, and sdhash, enabling reusable garbled circuits reduces ΠEM communication by over two orders of magnitude and response time by at least one order of magnitude; the open-source CRGC analysis tool confirms no bits of kf are exposed.

It applies the framework to similarity-based malware detection with end-to-end evaluation: the explicit check completes a single-client request in 19.11 s at |L|=100 and 10 kB input, saturating around 250 concurrent requests, while the implicit check needs only 7.2e-3 MB and 0.19 s on a 100 kB input, at least two orders of magnitude faster in response time and three orders of magnitude lower in communication than fuzzy PSI and exact PSI baselines, with cost independent of blocklist size. Prior outsourced malware detection (CloudAv, SplitScreen, RScam, PriMal) either sends only compact representations without cryptographic protection or performs exact matching requiring a very large blocklist and high protocol cost; Half Moon is the first to move the expensive approximate private check to the sender and leave a cheap allowlist confirmation to receivers, with a reproducible open-source implementation and throughput measurements. Evaluation uses the Enron dataset (133,127 files; attachments mean 193.6 kB, median 98.8 kB; executables mean 13.7 kB, median 3.8 kB) and the Ember dataset (16,356,790 malware instances clustered), implemented over a 128-bit prime-order field, with Tables 3 and 4 and Fig. 6 reporting response times across |L|, input size, and concurrency.

The result targets content-distribution settings where senders are outnumbered by receivers and can perform the expensive check off the critical path (e.g., software distribution, email attachments, CDN delivery), so receivers only need an implicit check whose cost is independent of blocklist size before use. The framework applies to any metric embeddable into Hamming distance, and the authors note extension to other metrics. Security is framed for a malicious sender (T1) and a semi-honest server (T2); the paper explicitly does not treat a malicious server as the main threat model and notes that instantiating the three ideal functionalities with maliciously secure primitives extends protection to a deviating server. The allowlist is cleared whenever the blocklist is updated, redirecting receivers to the explicit check, so the amortized benefit of the implicit check depends on blocklist refresh frequency (public blocklists range from minutes to days).

The paper reduces the TOCTOU window to a single query latency rather than eliminating it, and acknowledges an unavoidable delay between server-side updates and client-side checks that creates potential zero-day exposure; how exploitable this residual window is in a given deployment remains worth watching. The design reveals the sender–receiver correspondence to the server, which the authors attribute to the underlying system architecture rather than a protocol weakness, but the impact of this disclosure in metadata-sensitive settings still needs assessment. Allowlist storage grows linearly with the number of explicit checks, and its long-term operational cost and cleanup strategy are open questions. In addition, the throughput inflection points in the evaluation (about 250 concurrent requests, about 80 at |L|=1000, and about 20 at |L|=10000) come from a specific hardware configuration (12-core 32GB server, 4-core 16GB clients), so behavior under other deployment conditions needs further verification.