撬开后量子的大门

Posted on Edited on

笔者刚开始接触后量子，这里是学习笔记

量子力学基础

量子叠加原理

概念：

一个量子系统可以同时处于多个可能状态的叠加状态，而不是像经典物理中那样只能处于一个确定的状态。这意味着，一个量子比特（qubit）可以同时表示0和1两种状态的叠加态，而不仅仅是0或1。这种量子叠加为量子计算提供了并行计算的能力，使得量子计算机能够在某些问题上比传统计算机更快地得出答案。

叠加原理可以用一个简单的例子来说明。假设我们有一个量子比特，它是一个自旋向上的电子和一个自旋向下的电子的叠加态。根据量子叠加原理，这个量子比特可以同时表示自旋向上和自旋向下的状态。当我们对这个量子比特进行测量时，它只会塌缩到一个确定的状态，即自旋向上或自旋向下，但测量前的状态是两者同时存在的。

数学表示：

假设一个量子比特有两个状态，记为 和 。量子叠加态可以用一个线性组合来表示：

其中 和 是复数，并且满足：

这是因为测量的概率必须等于1， 和 分别表示测量结果为 和 的概率。

量子纠缠原理

概念

量子纠缠是一种特殊的量子态，其中多个量子比特的状态是相互关联的，不能单独描述一个量子比特的状态。

纠缠态不能用独立的量子比特描述，纠缠的特性是量子信息传递中的重要资源，如量子通信和量子密钥分发（QKD）。

数学表示

对于两个量子比特系统，一个典型的纠缠态是Bell态，如：

这意味着两个量子比特的状态是共同决定的，如果测量第一个比特为0，那么第二个比特也必然是0，反之亦然。两者之间的状态是完全纠缠的。

量子测量

概念

量子测量是指对量子态进行观测，测量会导致量子态的坍缩（collapse），即量子系统从叠加态“坍缩”到一个确定的状态。

量子测量的不可预测性是量子力学的本质特性之一，测量后系统的叠加态消失，转变为经典状态。

数学表示

如果一个量子比特处于叠加态 ，测量后系统会以概率 得到结果 ，以概率 得到结果 ，测量会使系统坍缩到测量所得的状态。

量子态

概念

量子态是描述量子系统的完整信息，可以是单个粒子的状态，也可以是多个粒子的联合状态。

数学表示

单个量子比特的量子态如 。多个量子比特的量子态则是张量积，比如两个量子比特的状态可以表示为：

张量积是构建多比特系统的重要工具。

量子比特（qubit）

概念

量子比特是量子计算的基本单位，类似于经典计算中的比特。不同之处在于量子比特可以处于 、 或两者的叠加状态。

量子比特可以通过叠加、纠缠、操作等多种方式处理信息，具有比经典比特更强大的信息表达和处理能力。

数学表示

量子比特的状态 可以表示为：

其中 和 是满足 的复数。

量子门操作

概念

量子门是对量子态进行操作的基本单元，类似于经典计算中的逻辑门。量子门操作是可逆的，并且可以用矩阵来表示。

量子门可以实现各种量子态操作，是构建量子电路和量子算法的基础。

常见的量子门操作

  1. Hadamard门（H门）：将一个量子比特从经典态转变为叠加态：

    对状态 和 的作用为：

  2. Pauli门（X、Y、Z门）：

    • 门类似于经典的NOT门，交换 和 ：

    • 和 门分别进行不同的相位操作：

  3. CNOT门（控制非门）：一个两比特门，作用是翻转目标比特的状态，但仅当控制比特为 时才翻转：

量子计算原理

shor算法

Shor算法的高效性在于其量子部分能在多项式时间内找到周期，而这个周期信息又能用来找到大整数的因子。正因如此，Shor算法被视为量子计算对现有公钥密码体制（如RSA）的威胁。

目标：用于因式分解大整数，破解基于大数分解难题的公钥密码（如RSA）。

工作原理：

  1. 选择随机数：选择一个随机整数 ，使其小于待分解的整数 （即 ）。

  2. 计算最大公约数：计算 ，如果结果大于1，则找到了一个因子。这一步可以使用欧几里得算法在经典计算机上完成。

  3. 量子周期性：如果 ，则继续执行以下步骤：

    • 找到一个周期 ，使得
    • 这意味着 的 次幂模 为1。

  4. 使用量子计算找周期：利用量子傅里叶变换（QFT）找到周期 。具体步骤：

    • 初始化量子位：准备一个包含 个量子位的系统， 是 的位数。
    • 超位置态：将量子位置于超位置态，表示所有可能的结果。
    • 应用oracle：通过一个oracle函数来实现对 的计算，从而编码周期信息。
    • 量子傅里叶变换（QFT）：对量子位（一个周期函数）进行量子傅里叶变换，提取周期的信息，周期与整数因式相关联。

  5. 测量和计算：

    • 测量量子态，得到的结果可以用于估计周期 （即解决离散对数问题）
    • 使用继续的经典算法，验证找到的 是否符合 。

  6. 找到因子：

    • 确定 后，检查 是否为偶数。

    • 如果 ，则：

    • 如果这两个因子不等于1和，则它们即为 的非平凡因子。

Grover算法

  1. 目的：通过量子叠加和干涉，加速无结构（无序）数据库的搜索，常用于破解对称加密，可将搜索时间从 降低到 。

  2. 叠加态初始化：（将所有可能的候选解放入量子叠加态）

    • 准备 个量子位，表示 个可能的解的超位置态：

  3. Oracle：

    • 定义一个oracle函数 ，用于标记正确解 。对于任意输入 ，oracle的作用为：

    • 这意味着，如果输入是正确解，输出的相位会反转。

  4. 振幅增强：

    • 使用Grover的扩展步骤，通过应用两个操作增强标记解的概率幅度：

      1. 应用oracle：对所有量子位应用oracle 。

      2. 振幅增强：执行反射操作 ，通过以下步骤：

      其中 是当前的量子态， 是单位算符。

      • 这个步骤使得标记解的幅度增加。（逐步放大正确解的概率幅度）

  5. 重复步骤：

    • 重复执行oracle和振幅增强的过程 次。

  6. 测量：

    • 最后，测量量子态，得到的结果会更倾向于正确解 ，以概率接近1。

量子计算与经典计算的区别

经典计算使用经典比特，经典比特只能是0或1；量子计算使用量子比特（qubits），每个量子比特可以处于 和 的叠加态。

  • 叠加（Superposition）：量子比特可以同时处于多个状态的叠加态，允许量子计算并行处理多个计算路径。而经典比特只能处于确定的状态 或 。
    • 经典比特：单一状态，例如 或 。
    • 量子比特：叠加态，例如 。
  • 量子纠缠（Entanglement）：多个量子比特之间可以处于纠缠态，导致它们的状态是相互关联的。即使这些比特相距很远，测量一个比特的状态会影响另一个比特的状态。在经典计算中，位之间没有这种关联性。
    • 经典比特：独立的状态。
    • 量子比特：关联的纠缠态。
  • 量子干涉（Quantum Interference）：量子计算通过干涉效应增强正确解的概率幅度，抑制错误解的幅度。这是如Grover算法中用于加速搜索的关键原理。
    • 经典算法：没有干涉现象。
    • 量子算法：通过干涉增强正确解的概率。
  • 测量与坍缩（Measurement & Collapse）：量子计算在执行时，量子比特可以处于叠加态或纠缠态，但一旦测量就会坍缩到某个确定的状态。经典计算中的比特始终处于确定的状态。
    • 经典比特：一直是确定值。
    • 量子比特：测量时随机坍缩到一个状态，概率受叠加态系数控制。
  • 并行计算能力：量子计算可以并行执行多个计算路径（通过叠加态），从而显著提升某些问题的求解效率。
    • 经典计算模拟量子计算需要指数级的资源。
  • 量子算法的效率：量子算法可以提供指数或平方加速。例如，Shor算法对于因数分解问题的加速是指数级的，Grover算法对于无结构搜索问题的加速是平方级的。
    • Shor算法：经典复杂度为指数级，量子复杂度为多项式级。
    • Grover算法：经典复杂度为 ，量子复杂度为 。

数学基础

略

密码学基础

略

后量子密码学概念

本篇文章只是简单了解，具体实现见下一篇博客

后量子密码学的核心算法设计

基于格的密码（Lattice-based Cryptography）

  • 原理：基于格理论中的困难问题，如最短向量问题（SVP）和最接近向量问题（CVP）。
  • 特点：
    • 即使在量子计算机上，求解这些问题仍然非常困难。
    • 可以支持丰富的密码学功能，如全同态加密（Fully Homomorphic Encryption）和数字签名。
  • 常见算法：
    • NTRU加密算法：一种基于格的公钥加密方案，抗量子攻击。
    • LWE（Learning With Errors）：基于格的加密和签名方案，广泛应用于后量子密码学。
  • 优势：具有较强的抗量子攻击能力，并且可以高效实现。
  • 挑战：密钥和签名较大，效率与经典算法相比仍需优化。

代码密码（Code-based Cryptography）

  • 原理：基于纠错码的困难问题，如广义辛德尔（Goppa）码的解码问题。
  • 特点：
    • 主要基于解码随机线性码的难题，类似于求解高维空间中的矢量错误纠正问题。
    • 经典的McEliece公钥加密方案就是一种基于代码的密码。
  • 常见算法：
    • McEliece加密算法：基于纠错码，提出于1978年，至今未被破解。
    • Niederreiter加密算法：McEliece的变体，效率更高。
  • 优势：公钥加密方案历史悠久，具有极高的安全性。
  • 挑战：公钥非常大，使得在存储和传输上需要较多资源。

基于多变量多项式的密码（Multivariate Quadratic Cryptography）

  • 原理：基于多变量二次方程（MQ）问题的求解困难性，这在量子计算机上仍然是困难的。
  • 特点：
    • 主要用于数字签名方案，解决方程组中的未知数是NP困难问题。
  • 常见算法：
    • Unbalanced Oil and Vinegar（UOV）：一种多变量的数字签名算法。
  • 优势：签名过程非常快。
  • 挑战：公钥较大，且可能面临更高效的攻击手段。

哈希签名（Hash-based Cryptography）

  • 原理：基于哈希函数的安全性。
  • 特点：
    • 主要用于构建数字签名方案，依赖于现有的哈希函数安全性。
    • 由于哈希函数在量子计算下的安全性较好，因此可以通过扩展哈希长度来提高安全性。
  • 常见算法：
    • Lamport签名：一种经典的哈希签名方案。
    • XMSS（eXtended Merkle Signature Scheme）：一种高效的哈希签名方案，已经标准化。
  • 优势：可以使用现有的哈希函数构建，结构简单且易于实现。
  • 挑战：签名方案的使用次数有限。

基于同源映射的密码（Isogeny-based Cryptography）

  • 原理：基于椭圆曲线同源映射问题的困难性。
  • 特点：
    • 量子计算机在求解同源映射时没有明显优势，这使其成为一种抗量子攻击的潜在方案。
  • 常见算法：
    • SIDH（Supersingular Isogeny Diffie-Hellman）：一种基于同源映射的密钥交换协议。
  • 优势：密钥非常小，适用于需要高效传输的场景。
  • 挑战：计算复杂性较高，仍然需要进一步研究其安全性。

设计抵抗量子攻击的安全协议

量子攻击的威胁

量子计算主要依赖两种算法对现有加密协议构成威胁：

  • Shor算法：能高效解决大数分解和离散对数问题，威胁到RSA、ECC等基于这些问题的非对称加密方案。
  • Grover算法：能够加速无结构搜索任务，影响对称加密和哈希函数，但其影响相对较小。

后量子安全协议设计

在设计安全协议时，必须确保协议能够抵御量子计算攻击，这包括以下方面：

  • 密钥交换协议：
    • 经典方案的脆弱性：如DH密钥交换（基于离散对数问题）和RSA密钥交换（基于大数分解问题）都会被Shor算法破坏。
    • 后量子方案：可以使用基于格的加密方案（如Kyber）或基于同源映射的协议（如SIDH）来代替。
  • 数字签名协议：
    • 经典方案的脆弱性：RSA和ECDSA签名会被量子计算机破坏。
    • 后量子方案：哈希签名（如XMSS）或基于格的签名方案（如Dilithium）可用于构建安全的数字签名。
  • 对称加密：
    • 经典方案的安全性：对称加密算法（如AES）在量子攻击下的安全性会下降一半（通过Grover算法），例如AES-128的安全性会等效于AES-64。
    • 应对方案：通过增加密钥长度（如使用AES-256）来抵御量子攻击。
  • 混合方案：
    • 过渡方案：由于当前的量子计算机还不成熟，可以采用“混合”加密方案，即将现有的经典加密算法与后量子加密算法结合使用。这使得在量子计算技术未完全成熟前，依然可以保证协议的安全性。

协议设计原则

  • 安全性证明：设计基于难解数学问题的算法时，必须提供强有力的安全性证明。对于后量子密码学，安全性通常是基于现有的NP困难问题，且这些问题在量子计算机下仍然保持难解。
  • 效率考虑：后量子加密算法的效率往往低于经典算法，设计时应兼顾安全性和性能。例如，格密码虽然安全性高，但在实际应用中需要优化以减少密钥和签名的大小。
  • 灵活性与可扩展性：随着量子计算技术的进步，协议设计应具有灵活性，以便可以在未来采用新的、更安全的算法。

如何学习并模拟量子攻击

  • 量子计算模拟器：使用量子计算模拟器（如Qiskit、Cirq或Microsoft Quantum Development Kit）来模拟Shor算法和Grover算法的执行。这可以帮助研究人员理解量子算法如何对特定的加密方案（如RSA或对称加密算法）构成威胁。

  • 后量子密码学库：使用后量子密码学算法（如Lattice-based、Code-based、Multivariate等）进行对比，评估这些算法在量子攻击下的安全性。这可以通过对比量子算法与后量子算法在攻击成功率和计算复杂度上的差异。

  • 量子硬件：在可用的情况下，可以在真实的量子计算机上运行实验，比如IBM Q Experience。通过量子硬件，可以直接测试某些攻击场景，验证量子算法的实际效果。

  • 安全性分析工具：使用专门的安全性分析工具（如CryptoVerif、ProVerif等）来评估量子计算对现有加密协议的威胁。这些工具可以帮助研究人员分析加密协议在量子攻击下的脆弱性。

  • 公开挑战：参与量子密码学领域的公开挑战，如NIST的后量子密码学标准化项目，了解不同算法的竞争和实际应用情况。

addition

(1) Bell态

Bell态（Bell state）是两量子比特纠缠态的特定形式，是量子纠缠的经典示例。Bell态描述了一对量子比特的状态，这些量子比特之间存在极强的量子关联，无论它们相距多远，测量其中一个比特的状态都会影响另一个比特的状态。这种现象体现了量子纠缠的本质。

有四种Bell态，通常写为 和 ，它们的定义如下：

  1. ：

    这表示两个比特要么同时是 ，要么同时是 ，两种状态以相等的概率叠加。

  2. ：

    与 类似，但两个状态之间存在相位差（负号）。

  3. ：

    这表示一个比特是 而另一个比特是 ，或者反之，且两者叠加。

  4. ：

    与 类似，但在两个状态之间有相位差（负号）。

物理意义

  • Bell态是一种最大纠缠态，这意味着两个量子比特的状态是完全相关的，不能用单独的量子态来描述每个比特。
  • 如果我们测量其中一个量子比特并得到 ，另一个量子比特立刻处于对应的状态（即 或 ），即使它们相距很远。这种关联是量子纠缠的独特表现，爱因斯坦称之为“幽灵般的远距作用”。

应用

  • 量子隐形传态（Quantum Teleportation）：通过纠缠态和经典通信将量子信息从一个地方传送到另一个地方。
  • 量子密钥分发（QKD）：如BB84协议，使用Bell态的量子纠缠特性来保证通信的安全性。
  • 量子纠错：纠缠态在量子纠错码中可以用来检测和修正量子系统中的错误。