💻 computer science

Quantum Hash Function Based on Spectral Properties of Graphs and Discrete Walker Dynamics

本文介绍了 QGH-256，一种新颖的量子哈希算法，它通过将消息映射到环面网格上的加权图，并利用量子相位估计提取能够捕捉结构与动力学特性的谱特征，从而生成 256 位指纹，并通过 Qiskit 模拟证明了其强大的密码学敏感性和可行性。

原作者： Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

发布于 2026-06-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Mohana Priya Thinesh Kumar, Pranavishvar Hariprakash

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

核心理念：一种全新的数字指纹

想象一下，你需要将一个冗长且杂乱的故事（比如一部小说）转化为一个单一且唯一的指纹。在数字世界中，我们通常使用“哈希函数”（如 SHA-256）来完成这项工作。但本文的作者担心，未来的量子计算机可能会破解这些旧有的指纹。

因此，他们创造了一种新型指纹，称为 QGH-256。这种方法不再仅仅是对数字进行数学运算，而是将你的信息转化为一张地图，向地图上发送一个行者（Walker），然后利用量子物理学来测量地图的“振动”，从而生成最终的指纹。

第一步：将文字转化为地图（行者）

类比： 想象一个在正方形网格（类似于棋盘格）上行走的小型机器人，这个网格是环绕自身的（如果你从右侧边缘走出去，你会出现在左侧）。这被称为“环面网格（Toroidal Grid）”。

运作方式： 你将你的信息（例如“Hello”）转化为二进制代码（0 和 1）。
行走过程： 机器人的行走并非随机。它逐位读取你的信息。
- 如果它看到 00，它向北走。
- 如果它看到 01，它向南走。
- 如果它看到 10，它向东走。
- 如果它看到 11，它向西走。
地图： 随着机器人的行走，它会留下痕迹。每当它跨越网格上的某条线（边）时，它都会根据信息中的数字为该线增加一个“权重”。
结果： 你最终得到了一张独特的、带有权重的地图。如果你改变了信息中的哪怕一个字母（比如将“Hello”改为“Hella”），机器人就会走上一条完全不同的路径，从而创造出一张完全不同的地图。

为什么这很重要： 论文声称，由于这张地图是无向的（机器人并不记录它当时面向哪个方向，只记录它跨越了多少次线），因此通过观察地图来推断出原始信息是极其困难的。这就像是试图仅通过观察被踩踏出的草地痕迹，就去猜出一位徒步旅行者具体的行走路径，而不知道他从哪里开始，也不知道他到哪里结束。

第二步：聆听地图的“音乐”（谱特征指纹）

现在我们已经拥有了这张独特的地图，那么如何将其转化为指纹呢？作者们使用了物理学中的一个概念——谱分析（Spectral Analysis）。

类比： 想象你的地图是一个巨大的鼓。如果你敲击它，它就会振动。每个鼓都有其特定的“音符”（频率）可以演奏，这取决于它的形状和鼓皮的紧绷程度。

在数学中，这些“音符”被称为特征值（Eigenvalues）。
地图的“紧绷度”和“形状”是由图拉普拉斯矩阵（Graph Laplacian）（一个描述地图连接和权重的复杂数学矩阵）决定的。

量子的奇妙之处：
通常，要听到这些音符，你需要解复杂的方程。但本文使用了**量子相位估计（Quantum Phase Estimation, QPE）**算法。

可以将 QPE 想象成一个超灵敏的麦克风，它能瞬间“聆听”这面鼓并准确告诉你它正在演奏哪些音符。
关键细节： 作者不仅仅是聆听一个音符。他们向系统中发送了一个“叠加态”（一种类似于所有可能起始点的混合状态）。这意味着量子计算机可以同时“听到”地图的整首乐曲，包括这些音符是如何相互作用的。

为什么这很特别：
两个不同的地图可能会偶然具有相同的音符集（这被称为“同谱性/Co-spectral”）。然而，由于作者通过聆听音符如何与地图的特定结构（特征向量）相互作用，他们能够分辨出两张虽然听起来相似但外观不同的地图。这防止了“碰撞”（即两个不同的信息产生相同的指纹）。

第三步：热迹（最终指纹）

一旦量子计算机识别出了这些“音符”（特征值），作者就会计算所谓的热迹（Heat Trace）。

类比： 想象将热水倒在你的地图上。热量会在网格中扩散（扩散过程）。

“热迹”衡量的是热量扩散的速度。
通过在不同时间测量热量扩散，他们得到了关于地图形状的独特签名。
这个签名随后被压缩成一个 256 位代码（由 256 个 0 和 1 组成的字符串）。这就是你的最终 QGH-256 哈希值。

为什么它是安全的？（“雪崩效应”）

论文通过以下规则测试了这种新方法的安全性：

确定性（Determinism）： 如果你两次输入“Hello”，你两次都会得到完全相同的指纹。
雪崩效应（Avalanche Effect）： 如果你只改变一个字母（例如将“Hello”改为“Hella”），机器人会走上一条完全不同的路径。这改变了地图，改变了“音符”，改变了“热量扩散”，从而导致一个完全不同的 256 位指纹。
原像抗性（Pre-image Resistance）： 如果有人偷走了指纹，他们无法通过逆向工程找回原始信息。因为数学过程过于复杂，且地图在生成过程中丢失了关于行走方向的信息。

局限性：这是一个模拟实验

论文承认，目前我们还没有足够大、足够安静的量子计算机来实际运行此程序。

问题所在： 真实的量子计算机是“有噪声的”（就像带有静电干扰的收音机）。如果你尝试在有噪声的机器上聆听地图的“音符”，结果可能会出错，导致每次运行得到的指纹都不同。
论文中的解决方案： 作者在模拟器（一个模拟完美量子计算机的计算机程序）上进行了测试。这证明了其数学理论在理论上是完美的。
未来展望： 他们相信，随着量子计算机变得更加强大且噪声更小，这种方法将成为抵御黑客（甚至是使用量子计算机的黑客）的有力防线。

总结

作者构建了一个新的数字锁。

他们将你的信息转化为网格上的一条独特行走路径。
他们使用量子计算机来聆听这条路径的振动。
他们将这些振动转化为一个 256 位代码。

他们声称，由于该方法依赖于图如何振动的复杂物理特性，因此它比现有方法更难破解，使得即使是未来的量子计算机也极难猜出原始信息或找到产生相同代码的两个不同信息。

技术摘要：基于图谱性质与离散行走动力学的量子哈希函数

问题陈述
本文针对经典密码学哈希函数（如 SHA-256、MD5）在量子计算威胁下日益增长的脆弱性进行了研究。具体而言，Shor 算法和 Grover 算法分别通过高效分解大整数和加速非结构化搜索，对当前的标准化标准构成了生存风险。虽然美国国家标准与技术研究院（NIST）正在推进后量子密码学（PC）的标准化，但仍需要一种能够抵御经典和量子攻击的量子原生或量子韧性哈希方案。现有的方法通常依赖于线性位运算，这可能无法提供足够的抗量子加速能力，或者可能无法区分具有相同特征值谱（共谱图）但结构不同的图。

方法论
作者提出了 QGH-256，一种新型的谱哈希算法，它将经典的离散行走动力学与量子谱图分析相结合。其工作流程通过以下阶段进行：

消息诱导的图构建：
- 输入消息被转换为 UTF-8 二进制格式并进行分块。
- 一个经典的离散行走者在一个固定的 $4 \times 4$ 环面网格上运行。与随机游走不同，行走者在每一步的方向是由消息位（具体而言，每个块的第一位和最后一位决定方向：北、南、东或西）确定性地驱动的。
- 每个块的十进制数值作为所经过边的权重。
- 这一过程为每个输入消息生成了一个唯一的、可重现的有向加权无向图 $G = (V, E, W)$ 。作者指出，由于无向边权重导致的定向信息丢失以及重建遍历序列的复杂性，从图中恢复原始消息在计算上是困难的。
通过量子相位估计（QPE）进行的谱指纹提取：
- 图的结构被编码进拉普拉斯矩阵 $L = D - A$ （度矩阵减去邻接矩阵）。
- 为了利用量子算法，通过矩阵指数化将 $L$ 转换为幺正算符 $U = e^{iLt}$ 。
- 量子相位估计（QPE） 被应用于 $U$ 。至关重要的是，QPE 电路的输入不是单个特征向量，而是在图的节点基底中定义的叠加态（ $|\psi\rangle = \sum \alpha_i |i\rangle$ ）。
- 由于输入态是拉普拉斯特征向量的叠加，QPE 过程充当了谱分析仪，将其分解为频率（相位）分量。测量特定相位的概率与输入态与相应特征向量之间的重叠程度的平方成正比。
热迹与哈希生成：
- 作者通过在多个时间尺度上评估热迹值 $h(t) = \sum |c_k|^2 e^{-t\tilde{\lambda}_k}$ 来计算“谱指纹”。该指标既捕捉了特征值信息，也捕捉了特征向量的贡献（通过系数 $c_k$ ）。
- 该特征向量经过后处理并压缩为固定的 256 位二进制哈希。

核心贡献

解决共谱碰撞： 该方法的一个主要理论贡献在于其区分共谱图（具有相同特征值谱但结构不同的图）的能力。通过使用叠加态作为 QPE 的输入，生成的谱指纹取决于特征向量的重叠度（ $|c_k|^2$ ），而不仅仅是特征值。这确保了即使是非同构图也会产生截然不同的指纹，即使它们共享相同的谱。
固定步长效率： 作者通过固定行走者步数（10,000 步）并根据消息长度调整块大小，改进了以往基于行走者的算法。这确保了图生成阶段的计算成本与输入消息的大小无关。
量子原生设计： 该算法利用量子力学的内在属性（叠加和相位估计）来生成高熵指纹，使其成为后量子安全性的候选方案。

结果与评估
作者使用 Seeded Qiskit Statevector Simulator 对 QGH-256 进行了评估，以确保结果是无噪声且确定性的，同时也承认当前的含噪声中规模量子（NISQ）硬件会引入影响确定性的波动。

确定性： 相同的输入始终产生相同的 256 位哈希。
雪崩效应： 输入的单比特变化（例如，“Hello” 与 “Hella”）导致输出产生显著高的汉明距离，证实了其对输入扰动的敏感性。
原像抗性： 作者认为，由于图逆特征值问题的复杂性以及无向性质引入的歧义性，反转哈希是不可行的。
计算时间： 由于采用了固定网格大小和固定行走步数，观察到的运行时间与消息长度几乎保持恒定。

意义与主张
论文声称 QGH-256 通过整合拓扑和动力学图属性，提供了对抗经典哈希的强有力替代方案。

量子韧性： 作者断言，该算法依赖于复杂的非线性谱计算（涉及矩阵指数化和深层 QPE 电路），这创造了一个“重型预言机（heavy oracle）”。这显著增加了攻击者尝试进行基于 Grover 的原像攻击时的单次迭代成本，从而可能抵消 Grover 算法提供的二次加速。
符合 NIST PQC 标准： 该方案被呈现为满足 NIST PQC 的安全性标准（抗量子攻击）、性能标准（相对于消息长度的常数时间）以及互操作性标准（256 位输出与现有基础设施兼容）。
未来展望： 作者总结道，虽然当前硬件限制（噪声、退相干）使得验证过程必须依赖模拟，但随着量子纠错和量子比特稳定性的成熟，该方法为开发稳健的密码原语提供了一条可行的路径。

本文并未声称能立即部署在真实的量子硬件上，而是将 QGH-256 定位为一个理论框架及经模拟验证的概念证明。