| 摘要: |
| 双分组长度哈希函数是提高哈希函数具体安全性的一种经典方法, 该结构已被证明在一定条件下能达到最优的量子抗碰撞性. 然而, 针对坍塌性这一适用性更强的量子安全模型, 双分组长度哈希函数能否达到最优具体安全性还是一个开放性问题. 为了进一步研究此问题, 考虑在量子条件下抗碰撞性的扩展属性坍塌性, 并研究基于随机谕言机的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结构进行扩展, 扩展后的哈希函数仍具有坍塌性, 这为今后坍塌哈希函数的设计提供了理论基础. |
| 关键词: 后量子安全性 哈希函数 双分组长度 压缩函数 坍塌性 |
| DOI：10.13328/j.cnki.jos.007646 |
| 分类号:TP311 |
| 基金项目:国家重点研发计划(2023YFA1011200); 国家自然科学基金(62372274) |
|
| Double-block-length Hash Function with Optimal Collapsing Security |
|
ZHANG Shao-Xuan1,2, GUO Chun1,2,3
|
|
1.School of Cyber Science and Technology, Shandong University, Qingdao 266237, China;2.Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education (Shandong University), Qingdao 266237, China;3.Shandong Research Institute of Industrial Technology, Jinan 250102, China
|
| 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. |
| Key words: post-quantum security hash function double-block-length compression function collapsing |
