具有最优坍塌安全性的双分组长度哈希函数
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP311

基金项目:

国家重点研发计划(2023YFA1011200); 国家自然科学基金(62372274)


Double-block-length Hash Function with Optimal Collapsing Security
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    双分组长度哈希函数是提高哈希函数具体安全性的一种经典方法, 该结构已被证明在一定条件下能达到最优的量子抗碰撞性. 然而, 针对坍塌性这一适用性更强的量子安全模型, 双分组长度哈希函数能否达到最优具体安全性还是一个开放性问题. 为了进一步研究此问题, 考虑在量子条件下抗碰撞性的扩展属性坍塌性, 并研究基于随机谕言机的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结构进行扩展, 扩展后的哈希函数仍具有坍塌性, 这为今后坍塌哈希函数的设计提供了理论基础.

    Abstract:

    Double-block-length hash functions are a classical approach for amplifying the concrete security of hash functions. This construction has been proven to achieve optimal quantum collision resistance under certain conditions. However, whether double-block-length constructions can still achieve optimal concrete security in the stronger and more applicable quantum security model of the collapsing property remains an open question. To conduct a further study on this issue, this study considers the collapsing property, which extends the notion of collision resistance in the quantum setting. This study focuses on the collapsing security of Nandi’s double-block-length construction based on a random oracle. This study proposes that when the permutations $ \pi $ within the construction is composed completely of a number of c-cycle permutations (i.e., for any $ {x}\in{{\{0, 1\}}}^{{m}} $, $ \pi^{{a}}{(x) =x} $ if and only if $ {a=c} $), the collapsing security of this construction is optimal. Constructing a permutation $ \pi $ composed solely of c-cycle permutations is straightforward. Optimal collapsing security implies that when the output size of the random oracle is n bits, the adversary can effectively distinguish between the two states, measuring the hash value of a quantum superposition of messages and measuring the message superposition itself, only after making at least $ \text{O(}{{2}}^{{2n/3}}\text{)} $ queries. The proposed optimal construction can also be extended by the Merkle-Damg?rd construction. The extended hash function retains the collapsing property. Therefore, this study provides a theoretical foundation for the design of collapsing hash functions in the future.

    参考文献
    相似文献
    引证文献
引用本文

张绍煊,郭淳.具有最优坍塌安全性的双分组长度哈希函数.软件学报,,():1-9

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-06-10
  • 最后修改日期:2025-09-18
  • 录用日期:
  • 在线发布日期: 2026-07-22
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号