Half-Moon Cookie 让发送方一次性完成私有近似黑名单检查，接收方以低至 0.19 秒的隐式检查确认结果并抵御 TOCTOU 攻击
核心概要
该工作提出 Half-Moon Cookie 三方框架：发送方客户端对服务器持有的专有黑名单做隐私保护的近似（度量空间内）检查，通过后服务器在允许列表中存入一个隐藏且绑定的令牌，接收方随后可用更快的隐式检查确认该条目仍未被撤销，从而在不泄露客户端输入与黑名单的前提下缓解 TOCTOU 攻击；作者给出基于汉明距离的实例化并应用于相似性恶意软件检测，实验显示可复用混淆电路使嵌入阶段通信量下降两个数量级以上，隐式检查在 100 kB 输入上仅需 7.2e-3 MB 通信与 0.19 秒响应时间。
深度剖析
形式化定义了 Half-Moon Cookie 原语，并给出由显式检查（Embed-and-Map 与 Test-and-Commit 两个理想功能）与隐式检查（Implicit Check）组成的三方通用框架，显式检查通过后服务器才向允许列表写入隐藏且绑定的令牌。 此前私有黑名单匹配方案（如两服务器 PIR 的 Checklist、Private Hash Matching、OPPRF/OKVS）只做一次性匹配，不产生可在后续快速验证的隐藏绑定令牌；Half Moon 把嵌入与黑名单检查解耦，使两者可独立选择私有且高效的方法。 论文给出定义 1、三个理想功能（图 1）与定理 5.1 的安全性证明草图，并在附录 D 给出针对威胁模型 T1（恶意发送方）与 T2（半诚实服务器）的完整证明，将优势分别界定为 FAR + 2|F|/|KP| + (qH+1)/|F|^θ 与 1/2 + qH/|F|^θ。
给出可嵌入汉明距离的度量空间上的高效实例化：用 MX 映射把位向量嵌入有限域 F^θ，定义对称不共根（SUR）度量，使 F^θ 上的距离等价于原汉明距离，并据此改造无分布假设的模糊 PSI 协议完成私有距离检查。 既有结构感知 PSI 与近似 PSI 依赖数据分布假设，Blass–Noubir 直接作用于二进制向量而不兼容；本文通过 MX 与 SUR 度量把汉明距离检查转化为可用噪声多项式加法（Fnpa）计算的域上距离，从而在无分布假设下支持近似匹配。 定义 4、定义 5 与式 (6)–(9) 给出等价性推导，定理 6.2 表明 Test-and-Commit 以 O(nθ) 通信与计算代价实现，并依赖恶意安全的 OLE 与 Fnpa 构造。
用可复用混淆电路（基于 CRGC 框架）把嵌入阶段拆成可复用与非可复用部分，使电路代价与输入文件大小解耦，同时不泄露服务器持有的嵌入密钥 kf。 单体式混淆电路需随输入文件线性增长，作者报告其延迟是 Half Moon 嵌入的 231 倍、网络流量是 43,505 倍（194 kB 平均邮件附件）；本文按 CRGC 规范拆分功能并插入平衡门，使服务器端工作量与输入大小无关。 表 2 显示对 TLSH、ssdeep、sdhash 三种模糊哈希，启用可复用混淆电路后 ΠEM 通信量下降两个数量级以上、响应时间至少下降一个数量级；开源 CRGC 分析工具确认设计未暴露 kf 的任何比特。
将框架应用于相似性恶意软件检测，并给出端到端评测：显式检查在 |L|=100、10 kB 输入下单客户端 19.11 秒完成，约 250 并发请求时出现饱和拐点；隐式检查在 100 kB 输入上仅需 7.2e-3 MB 通信与 0.19 秒响应时间，比模糊 PSI 与精确 PSI 基线快至少两个数量级（通信少三个数量级），且代价与黑名单规模无关。 此前外包恶意软件检测（CloudAv、SplitScreen、RScam、PriMal）或只发送紧凑表示而无密码学保护，或只做精确匹配导致黑名单巨大、协议代价高；Half Moon 首次把昂贵的近似私有检查移到发送方、把廉价的允许列表确认留给接收方，并给出可复现的开源实现与吞吐量测量。 评测基于 Enron 数据集（133,127 个文件，附件均值 193.6 kB、中位数 98.8 kB，可执行文件均值 13.7 kB、中位数 3.8 kB）与 Ember 数据集（16,356,790 个恶意样本聚类），在 128 位素数阶域上实现，表 3、表 4 与图 6 给出不同 |L|、输入大小与并发度下的响应时间。
启示与展望
该结果面向发送方数量少于接收方、且发送方可离线执行昂贵检查的内容分发场景（如软件分发、邮件附件、CDN 交付），此时接收方只需在内容使用前做代价与黑名单规模无关的隐式检查。框架适用于任何可嵌入汉明距离的度量空间，作者也说明可扩展到其他度量。安全性目标设定为恶意发送方（T1）与半诚实服务器（T2）；论文明确不把恶意服务器纳入主要威胁模型，并指出通过把三个理想功能替换为恶意安全原语可扩展到偏离协议的服务器。允许列表在每次黑名单更新时清空，接收方被重定向回显式检查，因此隐式检查的摊销收益取决于黑名单刷新频率（公开黑名单从分钟到天不等）。
论文把 TOCTOU 窗口缩小到单次查询延迟而非完全消除，并承认服务器端更新与客户端检查之间存在不可避免的延迟，形成潜在的零日暴露；这一残余窗口在具体部署中的实际可利用性值得持续观察。设计会向服务器暴露发送方与接收方的对应关系，作者将其归因于底层系统架构而非协议弱点，但在对元数据敏感的场景中这一披露的影响仍需评估。允许列表存储随显式检查次数线性增长，其长期运维成本与清理策略是开放问题。此外，评测中的吞吐量拐点（约 250 并发、|L|=1000 时约 80 并发、|L|=10000 时约 20 并发）来自特定硬件配置（12 核 32GB 服务器、4 核 16GB 客户端），在其他部署条件下的表现需要进一步验证。