公钥加密误差学习思想在LowMC高阶差分分析中的应用

1. 项目概述：当公钥加密遇上轻量级块密码

最近在密码学安全分析领域，一个挺有意思的交叉研究方向引起了我的注意，那就是将公钥加密（PKE）方案中的分析思想，应用到像LowMC这样的轻量级块密码的高阶差分分析上。这个方向听起来有点跨界，但仔细琢磨，内核逻辑是相通的：都是在处理“噪声”或“误差”，并试图从中提取出决定性的信息。公钥加密里，我们常面对的是由随机性引入的“学习误差”；而在对LowMC这类采用部分非线性层（S-box层稀疏）的密码进行高阶差分分析时，我们处理的则是经过多轮加密后，那些非线性操作产生的、难以线性逼近的“高阶误差”。把前者的数学工具和建模思路借鉴过来，往往能给后者带来新的分析视角和更高效的攻击路径。这不仅仅是两个术语的简单拼接，而是一种方法论上的迁移与融合。

对于从事密码设计、密码分析或者对前沿密码学进展感兴趣的朋友来说，理解这个交叉点非常有必要。它不仅能帮你更深刻地把握LowMC这类后量子时代热门密码的结构特性，也能让你领略到现代密码分析中“它山之石，可以攻玉”的巧妙。本文我将结合自己的理解，拆解“基于指数学习误差的公钥加密与LowMC块密码高阶分析”这个命题，聊聊背后的核心思想、技术实现的关键步骤，以及在实际操作中需要绕开的那些“坑”。

2. 核心思想拆解：误差学习与高阶差分的内在联系

2.1 公钥加密中的“指数学习误差”是什么？

在基于格（Lattice）的公钥加密方案，特别是那些基于学习有误（Learning With Errors, LWE）问题及其变种的方案中，“学习误差”是一个核心概念。简单来说，在LWE问题中，攻击者（或分析者）面对的是形如b = A * s + e的方程组，其中A是公开的矩阵，s是秘密向量，e是一个小的随机误差向量。这里的“误差”e，就是“学习误差”。之所以叫“学习”，是因为问题可以理解为：给定A和b，去“学习”或恢复出秘密s，而这个过程被误差e所干扰。

“指数学习误差”则是对这种误差分布或误差引入方式的一种特定刻画或假设。它可能指的是误差服从某种指数衰减的分布（如离散高斯分布），也可能指在安全性归约中，区分“有误差的样本”和“完全均匀随机样本”的困难性是指数级的。其核心在于，这个误差是小的、有界的，但又不可或缺，正是它提供了方案的计算安全性。分析这类加密方案，很大程度上就是在分析误差e如何掩盖了秘密信息s，以及多大的误差仍然能保证攻击者无法有效学习s。

2.2 LowMC块密码与高阶差分分析挑战

LowMC是近年来为后量子密码学，特别是多方计算（MPC）、全同态加密（FHE）等场景设计的一族轻量级块密码。它的一个显著特点是采用了非常稀疏的非线性层——每一轮只使用极少数的S-box（例如3比特S-box），其余部分均为线性变换。这种设计使得它在保持必要安全性的同时，在布尔电路中的计算深度很浅，非常适合上述复杂密码协议。

然而，这种稀疏非线性设计也给传统的密码分析带来了新挑战，同时也创造了新机会。高阶差分分析是一种强大的选择明文攻击方法，它通过追踪高阶差分（即多个明文差分之间的运算结果）在密码函数中的传播，来构建有效的区分器或恢复密钥。对于非线性组件密集的密码，高阶差分会随着轮数增加迅速变得复杂而不可用。但LowMC的稀疏S-box层意味着，在多数比特路径上，数据只是经历了线性处理，这在一定程度上“保持”了差分的某些代数结构。

挑战在于，尽管线性层多，但那些零星分布的S-box就像电路中的“非线性噪声源”，会破坏差分的高阶线性关系。经过多轮迭代后，这些局部非线性效应累积起来，构成了分析中需要处理的“高阶误差”。这个“误差”与LWE中的误差e在概念上扮演了相似的角色：它们都是使得从输出反推输入（或密钥）变得困难的“干扰项”。

2.3 思想迁移：用误差学习的框架看待密码分析

那么，如何将两者联系起来呢？关键洞察在于建模的转化。

1. 将密码算法视为一个“带噪声的函数”：在对LowMC进行高阶差分分析时，我们可以尝试将经过r轮加密后的某个比特（或一组比特）的函数值，表达为一个关于明文差分和密钥的多元多项式。其中，线性操作（密钥加、线性层）贡献了多项式的主体线性/仿射部分，而稀疏的S-box操作则引入了高阶项（如二次项、三次项）。这些高阶项相对于我们想构建的线性区分器而言，就是“误差”。
2. 定义“分析误差”：我们可以定义一个“分析误差”项，它包含了所有由S-box引入的、阶数高于我们当前分析所考虑阶数的差分效应。理想情况下，如果我们能完全精确建模，这个误差应为零。但实际上，由于S-box的非线性和迭代，这个误差是存在且复杂的。
3. 借鉴LWE的分析范式：在LWE分析中，我们研究需要多少样本（即多少个(A, b)对）才能以显著概率从误差e中“学习”到s。类似地，在LowMC的高阶分析中，我们可以研究：需要多少选择明文对（对应样本），才能使得高阶差分统计量能够以显著概率“区分”出密码算法和一个随机置换，尽管存在由稀疏S-box产生的“分析误差”。这里的“分析误差”类似于LWE中的e，而密钥信息或算法的非随机性特征则类似于s。
4. 指数级安全性的类比：在安全的公钥加密方案中，区分真实密文和随机串的优势（advantage）通常被证明是忽略不计的，或者更理想的是，攻击者的成功概率随安全参数呈指数级下降。当我们说“基于指数学习误差”时，可能暗示我们试图证明：对于LowMC的某种高阶差分攻击，随着轮数增加或S-box数量调整，攻击者成功构建有效区分器的概率（或优势）也呈指数级下降。这就将密码算法的具体安全性与一个抽象的、已被深入研究的计算困难问题（带误差学习）的难度联系了起来，提供了一种形式化或半形式化的安全论证思路。

这种思想迁移的价值在于，它允许我们利用格密码和LWE问题中成熟的复杂性理论工具和证明技术，来量化评估LowMC这类特定结构密码对抗高阶差分分析的安全性。我们不再仅仅依靠具体的攻击实验和复杂度估算，而是可以尝试建立更一般的、基于计算困难假设的安全边界。

3. 技术实现路径：从理论框架到具体分析步骤

将上述思想落地，需要进行一系列具体的建模、计算和实验步骤。下面我以一个简化的研究流程为例，说明如何操作。

3.1 第一步：精确建模LowMC的差分传播

首先，需要对目标LowMC实例（特定的参数集，如块大小、S-box数量及位置、线性层矩阵、轮数等）进行精确的代数描述。

1. 状态表示：将每一轮的内部状态表示为比特向量。设状态长度为n。
2. 轮函数分解：明确每一轮的三个子步骤：AddRoundKey（密钥加，通常是异或）、SboxLayer（稀疏S-box应用）、LinearLayer（矩阵乘法）。其中S-box层只作用于少数几个（比如k个）特定的比特位置。
3. 差分表示：对于选择明文攻击，我们考虑一组明文，并计算它们在某些特定比特位置上的差分（通常是异或差分）。设我们关注一个d阶差分，即涉及2^d个明文。
4. 追踪差分经过线性层：线性变换（异或和矩阵乘法）对差分的处理是线性的，可以直接通过矩阵运算推导出输出差分。这是模型中“干净”的、可预测的部分。
5. 处理S-box引入的非线性：这是关键也是难点。每个3比特S-box是一个非线性函数。当差分传播经过S-box时，输出差分不再是输入差分的确定性函数，而是一个分布（差分分布表，DDT）。在构建确定性区分器时，我们通常寻找概率为1的差分特征。但在高阶差分分析中，我们更关心的是，经过S-box后，某个高阶差分（例如，所有2^d个明文经过S-box输出值的异或总和）是否恒为0。对于某些低阶输入差分和特定的S-box，这个和可能恒为0，这被称为高阶差分的“零和”性质。

注意：LowMC使用的S-box通常经过精心挑选，具有好的密码学性质，但针对高阶差分“零和”的性质需要单独验证。这是分析的基础，需要查阅该LowMC实例的具体设计文档或进行预计算。

3.2 第二步：构建带“误差”的高阶差分等式

我们的目标是构建一个关于最终密文状态某些比特的、涉及高阶差分的等式，这个等式在密码算法下以高概率成立（或高概率不成立），而在随机置换下以不同的概率成立。

1. 选择目标比特和差分路径：基于第一步的传播分析，选择密文状态的若干比特作为观测点。同时，选择明文差分模式（即哪些比特位置参与构造高阶差分），使得差分路径尽可能多地通过线性部分，减少经过S-box的次数。
2. 推导理想等式：假设所有S-box对高阶差分的传播都是“理想”的（例如，总是保持某种线性关系或零和特性），我们可以推导出一个理论上的等式。例如，SUM over all plaintexts in the delta-set (Ciphertext_bit_i) = 0，其中求和是异或和。这个等式在“无误差”的理想模型中应始终成立。
3. 引入“误差项”：现在，将每个S-box在差分传播中可能破坏上述理想等式的因素，建模为一个布尔变量或一个小概率事件。这个破坏因素就是我们的“分析误差”。由于S-box稀疏，误差项的数量是可控的。最终，我们得到形如理想等式 XOR (误差项1 OR 误差项2 OR ...) = 0的实际预测。也就是说，只有当所有相关S-box都没有引入破坏时，理想等式才成立。
4. 误差的概率化分析：计算每个“误差项”发生的概率。这需要对每个涉及的S-box，分析其在高阶差分输入下的输出和分布。这个概率通常取决于S-box的DDT和具体的输入差分值。将所有误差项的影响综合起来，可以得到实际等式成立的概率p_cipher。

3.3 第三步：应用“指数学习误差”框架进行分析

在这一步，我们将第二步的概率结果，放入一个类似LWE问题分析的框架中。

1. 定义区分游戏：攻击者可以查询一个“黑盒”，黑盒要么是目标LowMC实例（使用随机密钥），要么是一个真正的随机置换。攻击者的目标是区分两者。
2. 构建区分器：攻击者使用我们构造的高阶差分等式。他准备一个特定的d阶差分明文集合，查询黑盒得到密文，然后计算等式是否成立。
3. 计算区分优势：
   • 对于真正的LowMC，等式成立的概率是p_cipher（我们计算出的，通常明显偏离0.5）。
   • 对于一个随机置换，任何基于固定比特位置的、非平凡的布尔函数等式，其成立的概率期望是0.5（或非常接近0.5，取决于等式具体形式）。
   • 攻击者通过多次独立实验（使用不同的差分基底或密钥），可以检验等式成立的概率是否显著偏离0.5。这个偏离的程度就是区分优势。
4. 关联到“学习误差”：我们可以将|p_cipher - 0.5|视作一个“信号强度”。而攻击者从有限次查询中准确估计出p_cipher的过程，类似于从带有“噪声”的样本中学习一个参数。这里的“噪声”来源于：1）当黑盒是随机置换时，其本身输出的随机性；2）即使黑盒是LowMC，由于“误差项”的存在，等式成立与否也是概率性的。
5. 样本复杂度与安全参数：基于统计学习理论或LWE问题分析中常用的引理（如Chernoff bound, Hoeffding inequality），我们可以估算出，为了以接近1的概率成功区分，攻击者需要多少组查询（即样本量，或选择明文量）。这个样本复杂度N应该是1 / (p_cipher - 0.5)^2的量级。
   • 如果随着LowMC轮数r增加，|p_cipher - 0.5|呈指数级衰减（例如，2^{-cr}），那么所需的样本量N就呈指数级增长（2^{2cr}）。这就将LowMC的安全性与一个“指数学习误差”问题联系了起来：攻击者需要指数级多的样本才能从指数级小的偏差中学习到足够的信息进行区分。
   • 这为LowMC抵抗高阶差分分析提供了形式化的安全论据：只要p_cipher以足够快的指数速度趋近于0.5，那么任何实际可行的攻击者（其查询量有上限）的区分优势都是可以忽略不计的。

3.4 第四步：工具辅助与实验验证

理论分析需要工具和实验的支撑。

1. 符号计算工具：使用如SageMath、Python的sympy库或专门的密码分析框架（如CryptoMiniSat的代数接口），对小型参数（如状态n较小，轮数r较少）的LowMC进行精确的代数建模。这可以帮助我们验证高阶差分等式的推导，并精确计算小规模实例下的p_cipher。
2. 概率模拟：对于参数较大的实例，精确符号计算可能不可行。可以采用蒙特卡洛模拟方法：随机生成大量密钥和符合差分模式的明文集，运行LowMC加密，统计等式成立的概率，以此估算p_cipher。
3. 验证指数衰减：通过模拟不同轮数下的p_cipher，绘制其与轮数r的关系曲线（通常在对数坐标下）。如果观察到接近线性的下降，则支持了偏差指数衰减的假设，从而佐证了基于指数学习误差的安全论证。

4. 实操要点与避坑指南

在实际操作这个分析流程时，有几个关键点需要特别注意，它们直接决定了分析的可行性和结论的可靠性。

4.1 要点一：S-box高阶差分性质的精确预计算

这是整个分析的基石，绝对不能想当然。LowMC使用的3比特S-box虽然小，但其高阶差分性质（特别是针对“零和”性质）必须逐一验算。

• 操作：对于选定的S-box，枚举所有可能的低阶输入差分（例如，1阶、2阶差分），对于每一种输入差分，计算所有可能输入值在该差分下的输出集合，然后检查输出值的异或总和（即高阶差分）是否为0。
• 工具：可以写一个简单的脚本来自动化这个过程。输入S-box的查找表，输出一个字典或表格，记录哪些输入差分能保证输出高阶差分为0。
• 避坑：不要只检查S-box本身的零和性质，还要检查在具体差分路径中，S-box的输入是否确实是你预计算的那些“友好”差分。由于线性层的扩散，到达S-box的输入差分可能是多个明文差分位的线性组合，这可能超出你预计算的简单差分情况。必须根据具体的线性层矩阵进行反向推导。

4.2 要点二：误差项的独立性假设与处理

在第三步的概率分析中，我们常常需要假设不同的“误差项”（即不同S-box破坏等式的事件）是相互独立的，这样才能方便地将它们的概率相乘或相加。

• 风险：这个假设不一定成立。由于密码算法的迭代结构，不同轮的S-box输入可能通过线性层相关联，导致误差事件之间存在相关性。
• 处理：
  1. 保守估计：在无法证明独立性的情况下，采用最坏情况假设，即所有误差事件完全相关。那么整体失败的概率就是单个最大误差概率的上界。这会导致估算出的p_cipher更接近0.5，从而给出一个更保守（更安全）的安全边界。
  2. 深入分析相关性：对于小型实例，可以通过符号计算或详尽的模拟来直接估算多个误差事件联合发生的概率，避免独立性假设。
  3. 利用结构特性：LowMC的线性层通常是最大距离可分（MDS）或具有良好扩散性的，这有助于在几轮之后使状态比特充分混合，从而可能使得不同位置的误差在统计上趋近于独立。但这需要论证。

4.3 要点三：区分优势的统计估计与样本量

即使理论计算出了p_cipher，在实际区分攻击中，如何用有限样本做出可靠判断也是个技术活。

• 假设检验：这本质上是一个假设检验问题。零假设H0: 黑盒是随机置换 (p=0.5)，备择假设H1: 黑盒是LowMC (p=p_cipher)。
• 确定样本量N：给定我们希望达到的区分优势（成功概率）和可接受的错误概率（第一类错误α，第二类错误β），可以利用统计公式（如基于正态近似的公式）反推出需要的样本量N。N与(p_cipher - 0.5)^2成反比。当p_cipher非常接近0.5时，N会变得巨大，攻击在实践中不可行。
• 避坑：不要仅仅因为一次实验中等式成立/不成立就下结论。必须进行足够多次的独立实验，并采用严格的统计检验（如计算p-value）。否则，很容易被随机波动所误导。

4.4 要点四：寻找最优的差分路径与观测点

分析的成功与否和效率，极大程度上取决于第一步中差分路径和密文观测点的选择。

• 策略：这通常是一个搜索优化问题。目标是让差分路径尽可能少地通过S-box（减少误差源），同时让最终的观测等式尽可能敏感（即|p_cipher - 0.5|尽可能大）。
• 自动化搜索：可以尝试使用混合整数线性规划（MILP）或可满足性模理论（SMT）等工具，将差分传播的规则（线性层确定性传播，S-box概率性/确定性传播约束）建模为约束条件，以最小化激活S-box数量或最大化理论偏差为目标进行搜索。
• 经验：通常，选择那些从明文差分位开始，经过线性层能“绕过”许多S-box直接传播到密文某些位的路径。观测点也常选择在状态的最后几轮，因为那里的非线性累积效应更复杂，可能产生更独特的统计特征。

5. 案例推演：对一个简化LowMC模型的攻击模拟

为了让大家更有体感，我们设想一个极度简化的模型（请勿用于真实设计）。

假设一个微型LowMC变种：4比特状态，每轮使用1个3比特S-box（作用于前3比特），线性层是一个4x4的随机可逆矩阵（但固定），共3轮。我们的目标是构造一个2阶差分区分器。

1. 建模：我们选择明文的第0、1比特参与构造2阶差分（4个明文）。通过跟踪，我们发现，由于线性层的特性，在第三轮S-box的输入中，来自第0比特差分的影响被抵消了，因此第三轮的S-box输入差分恒为0（对于这个特定的差分模式）。这意味着，对于这个差分集合，第三轮的S-box实际上没有引入任何非线性效应（输出差分也为0）。
2. 构建等式：我们选择密文状态的所有4个比特作为观测。由于第三轮S-box无误差，且之前轮次的S-box影响可以通过线性层推导，我们最终得到一个理论预测：对于这个特定的2阶差分明文集，4个密文比特的异或和始终为0。即p_cipher = 1。
3. 分析：对于随机置换，4个比特异或和为0的概率是0.5。因此，我们有一个完美的区分器 (|1-0.5| = 0.5)。
4. 样本复杂度：只需要1组（4个明文）查询，就能以100%的概率区分。这显然是不安全的。
5. 现实意义：这个例子展示了如果差分路径能完全避开S-box的非线性（即“误差”为0），攻击会非常高效。真实LowMC的设计会通过更复杂的线性层和更多的轮数来避免这种简单路径的存在，确保任何非平凡的高阶差分路径都会激活足够多的S-box，从而使p_cipher快速指数趋近于0.5。

6. 高阶分析中的常见问题与排查

在实际研究过程中，你可能会遇到以下典型问题：

7. 延伸思考：方法论的局限与未来方向

基于指数学习误差的框架为分析LowMC等高阶差分安全性提供了有力的理论工具，但它也有其适用范围和局限。

局限：

1. 模型简化：将复杂的S-box非线性传播抽象为独立的“误差事件”是一个强简化。实际的相关性可能更复杂，导致安全估计过于乐观或悲观。
2. 寻找路径的难度：对于全参数规模的LowMC，自动化搜索最优高阶差分路径本身就是一个计算难题。当前工具（MILP/SMT）在处理多轮、多S-box时可能遇到状态爆炸问题。
3. 其他攻击向量：该方法专注于高阶差分分析。LowMC还可能面临其他类型的攻击，如代数攻击、立方攻击、积分攻击等。一个全面的安全分析需要多角度评估。

未来方向：

1. 更精确的误差建模：发展更精细的概率模型来刻画S-box误差项之间的相关性，例如使用马尔可夫链或更复杂的随机过程。
2. 结合机器学习：利用机器学习方法自动学习差分传播的模式，甚至直接预测高阶差分等式的有效性，辅助或替代部分搜索过程。
3. 形式化验证：将整个分析过程，从差分传播规则到概率计算，用形式化验证工具（如EasyCrypt, CryptoVerif）进行编码和验证，确保推导过程无漏洞，安全边界可靠。
4. 应用于其他密码：将此框架推广到其他具有稀疏非线性层的轻量级密码或密码组件（如ARX结构中的模加运算可视为一种非线性）的安全性分析中。

在我个人看来，这种跨领域的思路融合是密码学研究的魅力所在。把公钥密码中深刻的计算复杂性思想，用来剖析对称密码的具体结构，往往能照亮那些单纯依靠传统对称密码分析难以看清的角落。虽然具体操作起来满是细节和计算，但当你看到通过这种建模，能够为一段精巧的密码算法勾勒出一个清晰的安全边界时，那种感觉是非常扎实和满足的。最后一个小建议是，动手做的时候，一定要从最小的、可完全验证的实例开始，把每一步的中间结果都打印出来核对，确保你的建模和代码与算法的实际行为严丝合缝，这是避免在复杂分析中迷失方向的最有效方法。