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
The work introduces Half-Moon Cookie, a three-party framework in which a sending client performs a privacy-preserving approximate (metric-space) check of an item against a server's proprietary blocklist; on success the server stores a hiding and binding token in an allowlist, and a receiving client can later confirm via a much faster implicit check that the item still passes, mitigating TOCTOU attacks without revealing client inputs or the blocklist; the authors instantiate it for Hamming-distance blocklists and apply it to similarity-based malware detection, showing reusable garbled circuits cut embedding communication by over two orders of magnitude and that the implicit check needs only 7.2e-3 MB and 0.19 s on a 100 kB input.