软件学报:jos:7646 · 记录 #1

具有最优坍塌安全性的双分组长度哈希函数

来源日期 2026-07-22

来源记录日期 2026-07-22

雷达观测 2026-11-05 00:19

摘要

双分组长度哈希函数是提高哈希函数具体安全性的一种经典方法, 该结构已被证明在一定条件下能达到最优的量子抗碰撞性. 然而, 针对坍塌性这一适用性更强的量子安全模型, 双分组长度哈希函数能否达到最优具体安全性还是一个开放性问题. 为了进一步研究此问题, 考虑在量子条件下抗碰撞性的扩展属性坍塌性, 并研究基于随机谕言机的Nandi之双分组哈希结构的坍塌性. 提出当结构内的置换$ \pi $完全是由若干个c-循环(c-cycle)置换(即对于任意$ x\in {\{0, 1\}}^{m} $, $ {\pi }^{a}(x)=x $当且仅当$ a=c $)组成时, 该结构的坍塌性达到最优, 而构造满足由若干个c-循环置换组成的置换$ \pi $是简单的. 最优的坍塌性意味着当随机谕言机输出大小为$ n $比特时, 敌手至少进行$ {\mathrm{O}}({2}^{2n/3}) $次查询, 才能有效区分测量量子叠加信息的哈希值与测量量子叠加信息本身两个状态. 该最优结构也可由Merkle-Damg?rd结构进行扩展, 扩展后的哈希函数仍具有坍塌性, 这为今后坍塌哈希函数的设计提供了理论基础.