Quantum hash function using discrete-time quantum walk on Hanoi network

本文提出了一种基于汉诺威网络上离散时间量子行走的量子哈希函数，该方案利用消息比特控制长程边和条件位移算符，不仅具备高抗碰撞性，还能有效处理比传统循环图方案更短的消息长度。

要点

这篇论文介绍了一种利用量子力学原理来制造“数字指纹”（哈希函数）的新方法。为了让你轻松理解，我们可以把这项技术想象成在一个特殊的迷宫里玩一场量子弹珠游戏。

1. 什么是“哈希函数”？（数字指纹）

想象一下，你有一封很长的信（消息），你想给它贴上一个独一无二的标签（哈希值），用来证明这封信没有被篡改过。

• 传统方法：就像把信扔进一个巨大的搅拌机，打碎后重新拼成一个固定的小纸条。如果信里改了一个字，搅拌出来的纸条就会完全不同。
• 问题：现在的超级计算机（量子计算机）可能会破解旧的搅拌机配方（比如 SHA-256 等），所以我们需要更安全的“新搅拌机”。

2. 核心创意：量子弹珠与特殊迷宫

这篇论文提出了一种新的“搅拌机”，它基于量子行走（Quantum Walk）。

• 量子弹珠：想象你有一颗神奇的弹珠，它不像普通弹珠那样只能走一条路，而是像幽灵一样，同时走在所有的路上（这叫“叠加态”）。

• 普通迷宫（旧方法）：以前的量子哈希函数通常让弹珠在一个普通的环形跑道（一维周期晶格）上跑。

  • 缺点：如果跑道长度是偶数，弹珠在某些时间点会神奇地“消失”在奇数或偶数格子上，导致很多不同的信会生成相同的标签（碰撞），这很不安全。而且，如果信太短，弹珠还没跑够圈数，标签就生成了，也不安全。

• 我们的新迷宫：河内网络（Hanoi Network）：

  • 作者设计了一个特殊的迷宫，叫河内网络（HN4）。
  • 结构：它看起来像一条普通的环形跑道，但上面加了很多“捷径”（长距离边）。就像在城市里，除了主干道，还有很多连接不同街区的“空中走廊”或“传送门”。
  • 优势：这些“捷径”打破了普通跑道的规律。即使跑道长度是偶数，弹珠也不会规律性地消失。这让弹珠的分布更加混乱、不可预测，从而极大地提高了安全性。

3. 消息如何控制游戏？（双管齐下）

在旧的方法中，你的消息（比如"1010"）只是控制弹珠的**“硬币”**（决定它向左还是向右转）。

• 比喻：就像你只能告诉弹珠“左转”或“右转”，但路还是那条死路。

在这篇论文的新方法中，消息不仅控制**“硬币”，还控制“传送门”**（移位算子）：

• 当消息位是 0 时：弹珠使用一套特定的“硬币”规则，并且通过某些特定的“捷径”移动。
• 当消息位是 1 时：弹珠使用另一套“硬币”规则，并且通过完全不同的“捷径”移动。
• 效果：这就像你不仅改变了弹珠的转向指令，还直接改变了迷宫里的传送门位置。哪怕消息只变了一个比特（比如从 0 变 1），弹珠最终到达的位置分布也会发生天翻地覆的变化。

4. 为什么它很厉害？（三大优点）

1. 极低的“撞车”率（抗碰撞性）：

   • 比喻：想象有 100 个人拿着不同的信进入迷宫。在旧迷宫里，可能有 2 个人最后站在了同一个格子上（这就叫“碰撞”，是不安全的）。
   • 结果：在这个新迷宫里，经过测试，10000 次尝试中，几乎没有两个人站在同一个格子上。它的“撞车率”低到几乎可以忽略不计（0.05%），比以前的量子方法好得多。

2. 短消息也能用：

   • 比喻：以前的迷宫很大，如果信太短（比如只有几个字），弹珠还没跑完一圈就停了，导致标签不够乱。
   • 结果：因为有了“捷径”（长距离边），即使信很短，弹珠也能迅速通过捷径跑遍整个迷宫，生成高质量的标签。

3. 对噪声的鲁棒性：

   • 虽然量子计算机容易受干扰（噪声），但作者发现，只要参数设置得当，这种特殊的迷宫结构对随机干扰有一定的抵抗力。

5. 总结：这就像什么？

如果把生成哈希值比作制作一杯特调鸡尾酒：

• 旧方法：你在一个普通的杯子里搅拌，如果冰块（消息）太少，或者搅拌时间不够，味道（哈希值）就不均匀，甚至不同的人能调出味道一样的酒（碰撞）。
• 新方法（本文）：你换了一个带有特殊管道和传送带的调酒机。
  • 你倒入的冰块（消息）不仅决定搅拌的方向，还决定冰块通过哪条管道。
  • 哪怕只加了一粒盐（改变一个比特），整杯酒的味道都会彻底改变。
  • 无论冰块多少，都能调出完美混合、独一无二的味道。

一句话总结：
这篇论文发明了一种利用带有“传送门”的特殊量子迷宫来生成数字指纹的新方法。它比以前的方法更安全、更灵活，即使是很短的信息也能生成极其难以伪造的“量子指纹”，为未来的量子安全通信打下了坚实基础。

技术摘要

以下是基于论文《Quantum hash function using discrete-time quantum walk on Hanoi network》（基于汉诺网络离散时间量子行走的量子哈希函数）的详细技术总结：

1. 研究背景与问题 (Problem)

• 经典哈希函数的局限性：现有的经典哈希函数（如 SHA-1, MD5 等）面临量子计算算法（如 Shor 算法和 Grover 算法）的潜在威胁，存在被破解的安全风险。
• 现有量子哈希方案的不足：
  • 大多数基于量子行走（Quantum Walk, QW）的哈希函数仅在一维周期性晶格（Cycle）上运行。
  • 消息长度限制：在一维周期性晶格上，为了获得良好的扩散性，消息的比特长度通常需要大于晶格的顶点数。对于短消息，这些方案往往表现不佳。
  • 碰撞问题：在一维偶数长度晶格上，量子行走的概率分布存在周期性的零概率点（Predictable zero probability distributions），导致极高的碰撞率（Collision Rate），使得偶数长度晶格难以用于哈希生成。
  • 控制机制单一：现有方案通常仅利用消息比特控制演化算符中的“硬币算符”（Coin Operator），对“位移算符”（Shift Operator）的控制较少，限制了概率幅的调控能力。

2. 方法论 (Methodology)

本文提出了一种基于**汉诺网络（Hanoi Network, HN4）**的离散时间量子行走（DTQW）哈希函数生成方案。

• 底层图结构：汉诺网络 (HN4)

  • 该网络由一维周期性晶格（$N_v = 2^n$ 个顶点）和特定形式的**长程边（Long-range edges）**组成。
  • 每个顶点除了连接两个最近邻的常规边外，还连接两条长程边，形成小世界结构。
  • 优势：长程边的引入打破了偶数长度晶格的周期性零概率分布问题，使得即使在偶数顶点数的情况下也能获得均匀的概率分布，从而允许处理短消息。
  • 量子比特需求：HN4 仅需 2 个量子比特来编码硬币空间（Coin Space），适合在含噪声中等规模量子（NISQ）设备上实现。

• 演化算符的消息控制机制

  • 与传统方案不同，本文提出的方案中，消息比特同时控制硬币算符（Coin Operator）和位移算符（Shift Operator）。
  • 比特值 = 0：使用算符 $U_0 = S_0 (C_0 \otimes I)$。其中 $C_0$ 是基于特定硬币态的 Grover 算符，$S_0$ 是包含常规边和长程边的翻转 - 翻转（flip-flop）位移算符。
  • 比特值 = 1：使用算符 $U_1 = S_1 (C_1 \otimes I)$。其中 $C_1$ 是另一种 Grover 算符，$S_1$ 是标准位移算符。
  • 通过消息比特序列 $b_s \dots b_0$ 依次应用 $U_{b_i}$，最终状态为 $|\psi_f\rangle = U_{b_0} U_{b_1} \dots U_{b_s} |\psi_{in}\rangle$。

• 哈希值生成流程

  1. 初始化：选择初始量子态（硬币态和顶点态的叠加）。
  2. 量子行走：根据消息比特序列执行 $s$ 步演化。
  3. 测量：在计算基下测量最终量子态，得到顶点位置的概率分布 $P(x_v, m)$。
  4. 后处理：将概率幅 $\sqrt{P(x_v, m)}$ 乘以 $10^l$并取模$2^k$，将每个顶点的概率转换为$k$ 位二进制串。
  5. 拼接：将所有顶点的哈希片段拼接，生成长度为 $L = N_v \times k$ 的最终哈希值。

3. 关键贡献 (Key Contributions)

1. 引入汉诺网络 (HN4)：首次将 HN4 网络应用于量子哈希函数。利用其长程边结构，成功解决了偶数长度一维晶格中存在的周期性零概率分布问题，显著降低了碰撞率。
2. 双重控制机制：提出同时利用消息比特控制硬币算符和位移算符。这种双重控制极大地增加了概率幅流动的复杂性，增强了哈希函数的混淆（Confusion）和扩散（Diffusion）特性。
3. 支持短消息：打破了传统一维晶格量子哈希方案要求“消息长度 > 晶格顶点数”的限制。实验表明，该方案在消息比特长度小于顶点数时仍能保持极低的碰撞率。
4. 高碰撞抗性：通过参数优化（长程边权重），实现了接近理论极限的极低碰撞率。

4. 实验结果 (Results)

• 碰撞分析 (Collision Analysis)：

  • 在 $N=10000$ 次随机消息对的测试中，实验碰撞率仅为 0.05%，与理论碰撞率 0.02% 非常接近。
  • 相比之下，文献中其他基于量子行走的方案（如 Ref [24], [30], [26] 等）的实验碰撞率在 1.46% 到 23.12% 之间，本文方案表现最优。
  • 长程边权重的随机选择对碰撞率影响很小，表明方案具有良好的鲁棒性。

• 敏感性与扩散性 (Sensitivity & Diffusion)：

  • 雪崩效应：对原始消息进行微小的比特翻转、插入或删除，生成的哈希值会发生巨大变化（汉明距离接近理想值 50%）。
  • 均匀分布：哈希值中的比特翻转在空间上呈现均匀分布，无明显统计特征泄露原始消息信息。

• 抗生日攻击 (Resistance to Birthday Attack)：

  • 生成的哈希长度为 256 位（$16 \times 16$），需要$2^{128}$ 次尝试才能以 0.5 的概率找到碰撞，具有极高的安全性。
  • 方案可扩展至 512 位或更长，通过增加晶格顶点数 $N_v$ 即可实现。

• 状态可分性：

  • 不同消息对应的输出量子态之间的迹距离（Trace Distance）满足 $D \ge 1 - \epsilon$（$\epsilon \le 0.25$），表明输出态具有强可分性，进一步保证了哈希值的区分度。

5. 意义与展望 (Significance)

• 安全性提升：该方案基于量子力学原理（叠加态、纠缠），其安全性由 Holevo 定理保障，理论上比依赖计算复杂度的经典哈希函数更能抵抗量子攻击。
• NISQ 友好性：仅需 2 个量子比特编码硬币空间，且能在有限步数内完成，非常适合当前及近期的 NISQ 设备实现。
• 通用性：解决了短消息哈希生成的难题，扩展了量子哈希函数的应用场景。
• 未来工作：
  • 目前分析基于无噪声假设。未来需深入研究单位噪声（Unitary noise）和退相干对哈希性能的影响。
  • 探索通过减少迭代步数（如每步控制多位消息比特）来减轻噪声影响，同时保持哈希性能。

总结：本文提出了一种基于汉诺网络 HN4 和双重控制机制的量子哈希函数。该方法通过引入长程边和同时控制硬币/位移算符，成功克服了传统一维晶格量子哈希在短消息处理和偶数长度晶格上的缺陷，实现了极低的碰撞率和优异的统计特性，为后量子时代的哈希算法设计提供了新的有效途径。