Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold

该论文研究一个源自密码学理论的基础问题：关于哈希函数的结构性知识，能否加速对它的黑盒碰撞检测？作者从「实例最优性」（instance optimality）这一超越最坏情况分析的极端标准切入。实例最优性要求存在单一算法，使其在每一个具体输入

历史摘要 · 未重新核验 · arXiv cs.CR