The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

该论文通过引入映射选定水平结构的额外约束，提出了一个基于水平结构推广 SQIsign 签名方案的通用框架，并在此基础上构建了带水平结构的超奇异椭圆曲线显式 Deuring 对应关系，同时解决了新的受约束范数方程问题。

要点

这篇论文介绍了一种名为 SQInstructor 的新型数字签名技术。为了让你轻松理解，我们可以把这项技术想象成是在后量子时代（即量子计算机可能破解现有密码的时代）建造的一座更坚固、更灵活的“数字保险箱”。

以下是用通俗语言和比喻对这篇论文核心内容的解读：

1. 背景：为什么要发明 SQInstructor？

想象一下，现在的互联网安全（如银行转账、微信登录）依赖于一种叫“椭圆曲线”的数学迷宫。传统的密码学家认为，即使量子计算机来了，这个迷宫也很难被破解。

目前，最先进、最紧凑的候选方案叫 SQIsign。它的工作原理有点像“走迷宫”：

• 公钥：是一个迷宫的入口。
• 私钥：是你知道的一条秘密路径。
• 签名：你向验证者证明你知道路径，但又不直接展示路径，而是通过一系列复杂的数学变换（叫“等距同构”，Isogeny）来证明。

SQIsign 的痛点：虽然它很紧凑，但生成签名（也就是“走迷宫”）的过程非常慢，而且数学证明有点复杂，就像是在用一把生锈的钥匙开锁，虽然能开，但很费劲。

2. 核心创新：引入“层级结构” (Level Structures)

这篇论文提出了一个聪明的新视角：SQInstructor。

什么是“层级结构”？
想象一下，原来的迷宫里，验证者只问：“你能从 A 点走到 B 点吗？”
SQInstructor 引入了“层级结构”，这就像是给迷宫里的某些特定区域（比如“红色地砖”或“蓝色柱子”）贴上了标签。

• 旧模式：只要走到终点就行。
• 新模式：不仅要走到终点，还要保证你走过的路径必须把“红色地砖”映射到“红色地砖”，或者把特定的“柱子”移动到另一个特定的位置。

比喻：
这就好比以前你进大楼只需要刷脸（公钥）。现在，大楼升级了，你不仅要刷脸，还得在进门时把左手戴的戒指（层级结构）展示给保安，并且证明你能把戒指从左手“变”到右手，同时保持戒指的样式不变。

SQInstructor 的妙处：
通过增加这个“戒指”的约束，作者发现可以设计出一套更通用的框架。它不再局限于一种特定的走法，而是允许我们选择：

1. 1 维走法：像以前一样，一步一步走（适合做高级功能，如环签名）。
2. 2 维走法：像开飞机一样，直接飞过去（速度更快，适合日常使用）。

3. 两大突破：数学上的“翻译”与“解题”

为了实现这个新框架，作者做了两件大事：

A. 德林对应 (Deuring Correspondence) 的升级

• 原来的理论：数学家发现，椭圆曲线（迷宫）和一种叫“四元数代数”的抽象数学结构（迷宫的地图）是可以互相翻译的。
• SQInstructor 的升级：作者把这种翻译能力扩展了。以前只能翻译“普通迷宫”，现在可以翻译“带有特定标签（层级结构）的迷宫”。
• 比喻：以前我们只能把“中文”翻译成“英文”。现在，我们发明了一种新词典，能把“带口音的中文”精准翻译成“带特定语气的英文”。这让我们可以更灵活地处理问题。

B. 解决“受约束的范数方程”

• 问题：在生成签名时，需要解一个非常难的数学方程，就像在巨大的数字海洋里找一根特定的针。
• 突破：作者改进了现有的算法（KLPT 算法），让它在有“层级结构”约束的情况下，依然能快速找到那根针。
• 比喻：以前找针需要把整个海洋抽干（计算量巨大）。现在，作者发明了一个“磁吸网”，专门吸住带有“红色标签”的针，瞬间就能把针捞出来。

4. 两种“驾驶模式”：1 维 vs 2 维

论文展示了两种使用 SQInstructor 的方法，就像汽车有“手动挡”和“自动挡”：

• 1 维模式（手动挡/传统派）：

  • 特点：使用传统的、一步一步的数学变换。
  • 优势：虽然慢一点，但它能实现一些高级功能，比如环签名（一群人里谁签的，外人看不出来，但能证明是这群人里的人签的）。
  • 适用：需要极高隐私保护的特殊场景。

• 2 维模式（自动挡/现代派）：

  • 特点：利用高维数学技巧，像开飞机一样直接跨越障碍。
  • 优势：速度极快，签名生成和验证都非常高效。
  • 结果：作者通过实验证明，这种模式的速度和现有的 SQIsign 几乎一样快，甚至略快，而且签名大小差不多。

5. 安全性：为什么它值得信赖？

• 更难被攻破：因为引入了“层级结构”，攻击者不仅要破解迷宫，还要破解“戒指”的变换规则。这增加了攻击的难度。
• 数学证明：作者证明了，如果有人能伪造签名，那他就一定能解决一个目前被认为“不可能解决”的数学难题（找到特定曲线的自同构环）。
• 零知识证明：就像魔术师表演，观众（验证者）看到了结果（戒指变到了右手），但完全不知道魔术师（签名者）具体是怎么变的（私钥路径），从而保护了隐私。

总结

SQInstructor 就像是给现有的 SQIsign 密码系统装上了一个智能导航仪。

1. 它通过引入“层级结构”（给迷宫加标签），让系统变得更灵活、更通用。
2. 它升级了底层的数学翻译工具，让计算更快、更精准。
3. 它提供了两种模式：一种为了极致的隐私功能（1 维），一种为了极致的速度（2 维）。

一句话概括：这是一篇关于如何给后量子密码学“升级引擎”的论文，让数字签名在保持小巧精悍的同时，跑得更快、更稳，还能适应更多复杂的任务。

技术摘要

SQInstructor：基于层级结构的 SQIsign 与 Deuring 对应推广技术总结

1. 研究背景与问题定义

背景：
基于同构（Isogeny-based）密码学是后量子密码学的重要候选方案。其中，SQIsign 是目前参与 NIST 后量子标准化进程中最紧凑的数字签名方案。SQIsign 的核心依赖于 Deuring 对应（超奇异椭圆曲线与四元数代数极大阶之间的等价性）。

现有挑战：

• 原始 SQIsign 的局限性： 原始版本基于 KLPT 算法解决四元数代数中的二次方程，虽然签名紧凑，但签名过程复杂且缓慢，且其 EUF-CMA（选择消息攻击下的不可伪造性）安全性证明存在困难。
• 高维同构的引入： 后续研究引入了高维（HD）同构技术，显著提升了 SQIsign 的速度和可证明安全性，但主要仍聚焦于特定的同构构造。
• 层级结构（Level Structures）的潜力： 层级结构（即挠子群的基，模去特定矩阵群的作用）在 SIDH 等协议中隐含使用，但尚未被系统地用于构建通用的签名框架。现有的 SQIsign 响应通常被理解为“消灭”某个挠点（即核），而本文提出了一种更通用的视角：响应应是一个将特定层级结构映射到另一个层级结构的同构。

核心问题：
如何构建一个通用的签名框架，利用层级结构将挑战定义为“寻找一个将公钥曲线上的特定层级结构映射到承诺曲线上特定层级结构的同构”，并在此基础上实现高效、安全的签名方案？

2. 方法论与核心框架

本文提出了 SQInstructor，一个基于层级结构的通用签名框架。

2.1 理论基石：推广的 Deuring 对应

作者首先将经典的 Deuring 对应推广到带有层级结构的超奇异椭圆曲线上：

• 定义： 给定一个超奇异椭圆曲线 $E$ 和一个 $\Gamma$-层级结构 $S$（$\Gamma$ 是 $GL_2(\mathbb{Z}/N)$ 的子群），定义其自同态环为保持该层级结构的子环 $\mathcal{O}(E, S)$。
• 对应关系： 建立了带有层级结构的曲线与四元数代数 $B_{p,\infty}$ 中的局部主左理想（locally principal left ideals）之间的对应关系。
• 显式构造： 论文给出了一个显式的算法（Algorithm 1: InStructIdeal），能够将四元数代数中的理想转换为满足特定矩阵约束（即映射特定基到特定基）的同构。这使得即使对于大且非光滑的层级，也能建立显式的对应。

2.2 协议流程 (SQInstructor Identification Protocol)

SQInstructor 是一个 Sigma 协议，其流程如下：

1. 密钥生成： 秘密密钥是一个左理想 $I_{sk}$，公钥是曲线 $E_{pk}$ 及其上的随机层级结构 $S_{pk}$。
2. 承诺 (Commitment)： prover 生成随机理想 $I_{com}$，计算承诺曲线 $E_{com}$ 并发送。
3. 挑战 (Challenge)： Verifier 在 $E_{com}$ 上选择一个随机的 $\Gamma$-层级结构 $S_{com}$ 并发送。
4. 响应 (Response)： Prover 计算一个同构 $\phi_{rsp}: E_{pk} \to E_{com}$，使得 $\phi_{rsp}(S_{pk}) = S_{com}$。
5. 验证： Verifier 检查同构的有效性以及层级结构的映射关系。

2.3 两种具体实现路径

论文详细探讨了两种实现该框架的路径：

1. 一维同构 (1D Isogenies)： 使用 KLPT 算法的变体（推广版）在四元数代数中寻找具有光滑范数的理想。这适用于需要模拟性的高级原语（如环签名）。
2. 二维同构 (2D Isogenies)： 利用高维同构技术（如 Kani 菱形构造），直接构造大度数的同构。这提供了与当前 NIST 候选方案 SQIsign 相当的性能。

3. 主要贡献

1. Deuring 对应的显式推广：

   • 将 Deuring 对应从普通超奇异曲线推广到带有 Borel、分裂 Cartan 和标量（Scalar）层级结构的曲线。
   • 解决了在四元数代数中求解受层级结构约束的范数方程（Constrained Norm Equations）的问题，特别是针对标量和 Borel 层级结构设计了高效的算法（如 ScalarSigningKLPT 和 BorelSigningKLPT）。

2. SQInstructor 通用框架：

   • 提出了一个灵活的签名框架，允许自由选择层级结构类型（Borel, Scalar, Split Cartan）和同构表示方法（1D 或 2D）。
   • 证明了该框架在特定假设下的安全性，其安全性基础与 SQIsign 相同（即求解自同态环问题的困难性）。

3. 算法实现与优化：

   • 一维实现： 改进了 KLPT 算法，使其能够处理层级结构约束，并提供了概念验证实现。
   • 二维实现： 基于最新的高维同构技术（参考 [1]），实现了高效的 SQInstructor 签名方案。
   • 安全性证明： 在 $\Gamma$-均匀目标 Oracle (Γ-UTO) 和固定度数同构 Oracle (FIDIO) 模型下，证明了协议的统计非中止诚实验证者零知识性，并推导了 EUF-CMA 安全性。

4. 性能基准测试：

   • 实现了基于 2D 同构的 SQInstructor，并与 SQIsign 进行了对比。结果显示，SQInstructor 在密钥生成、签名和验证时间上与 SQIsign 非常接近，签名大小略有增加（由于额外的 (2,2)-同构链），但整体性能具有竞争力。

4. 关键结果

• 安全性： 证明了 SQInstructor 的 EUF-CMA 安全性可归约到带有层级结构的自同态环问题（RΓ-OneEnd），该问题在随机输入曲线上与标准的超奇异同构问题多项式时间等价。
• 效率：
  • 一维方案： 虽然效率低于 2D 方案，但它是构建环签名和变色龙哈希等高级原语的唯一已知途径。
  • 二维方案： 在 NIST I, III, V 安全级别下，SQInstructor 的性能与 SQIsign 几乎持平。例如，在 NIST I 级别，SQInstructor 的签名大小为 174 字节（SQIsign 为 148 字节），签名时间 78.9 Mcycles（SQIsign 为 76.8 Mcycles）。
• 参数选择： 论文详细分析了参数选择，指出对于 2D 实现，取 $N$ 为 2 的幂次最为高效，且 $N$ 的大小由挑战空间决定（约为 $2^\lambda$）。

5. 意义与影响

• 理论深化： 本文首次系统地建立了带有层级结构的超奇异曲线与四元数代数之间的显式对应，并解决了相关的约束范数方程问题，填补了理论空白。
• 框架通用性： SQInstructor 提供了一个统一的视角，将现有的 SQIsign 及其变体（如 SQIprime）视为特定层级结构下的特例。这为未来设计更灵活、更安全的后量子签名方案奠定了基础。
• 高级原语支持： 通过提供一维同构的高效实现，SQInstructor 为构建基于同构的环签名、群签名和变色龙哈希等高级密码学原语提供了新的、更自然的构造路径。
• 后量子标准化潜力： 鉴于其性能与 SQIsign 相当且安全性基础坚实，SQInstructor 展示了作为 NIST 后量子签名标准候选方案的潜力，特别是在需要灵活性和高级功能的应用场景中。

总结：
SQInstructor 不仅是对 SQIsign 的简单扩展，而是通过引入层级结构概念，从根本上重新审视了基于同构的签名构造。它成功地将理论上的 Deuring 对应推广到更广泛的场景，并提供了从理论到高效实现的完整路径，为后量子密码学的发展做出了重要贡献。