💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

本文引入了一种符号模型，通过将十个 NIST 轻量级密码学决赛入围算法分解为初始化、数据处理和结束阶段，从而正式推导出它们的计算复杂度，进而提供了一个统一的理论框架，以指导在资源受限环境中选择高效的基元。

原作者： Najmul Hasan, Prashanth BusiReddyGari

发布于 2026-02-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Najmul Hasan, Prashanth BusiReddyGari

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

想象一下，你拥有一支由微型、电池供电的机器人（比如智能传感器或物联网设备）组成的编队，它们需要发送秘密信息。这些机器人非常小巧，能量极低，因此它们无法背负沉重的背包，也无法进行复杂的马拉松式长跑。它们需要一种“锁与钥匙”系统（密码学），这种系统既要超级安全，又要极其轻量且快速。

美国国家标准与技术研究院（NIST）举办了一场竞赛，旨在为这些微型机器人寻找 10 个最佳的“锁”。他们在现实世界中对这些算法进行了测试，但并没有一个统一的数学公式来解释为什么有些算法在理论上比其他算法更快。

Najmul Hasan 和 Prashanth BusiReddyGari 的这篇论文填补了这一空白。以下是他们所做工作的简单解释：

1. 问题所在：测量“锁”的重量

把这 10 个入围者想象成 10 种不同类型的背包。有的由轻质泡沫制成，有的则由沉重的钢材制成。NIST 已经通过实验测试（经验测试）称量了它们的重量，但作者们想要编写一套**“配方”**，能够根据你放入的东西多少来预测背包会有多重，而无需每次都实际打包测试。

他们想要创建一个“时间复杂度”图谱。简单来说，这是一个公式，可以告诉你：“如果消息很短，这个锁的速度有多快？如果消息变长了，它会变慢多少？”

2. 解决方案：三阶段流水线

作者将每一个加密算法都分解成了三个简单的阶段，就像工厂的流水线一样：

阶段 1：初始化（设置）： 在你可以打包任何东西之前，你必须先设置好机器。你需要插入密钥和“nonce”（用于该会话的唯一数字）。这需要固定的时间，无论你的消息有多大。这就像启动汽车引擎；无论你行驶 1 英里还是 100 英里，启动时间都是一样的。
阶段 2：数据处理（打包）： 这是实际加密消息和额外数据的地方。这是最繁重的体力活。这里所需的时间完全取决于你有多少数据。作者创建了公式来精确计算每个数据块需要多少个“步骤”（数学运算）。
阶段 3：最终化（封印）： 一旦打包完成，你需要封好盒子并贴上安全标签，以证明它未被篡改。这又是另一项固定强度的工作，就像在包裹上贴上最后的贴纸一样。

3. 结果：谁最轻？

通过将这种三阶段模型应用于所有 10 个入围算法，作者创建了一个描述每个算法“重量”的公式“菜单”（如其表 I 所示）。

以下是他们使用新公式发现的一些有趣结论：

“简单线性”型选手： 像 GIFT-COFB、Grain-128AEAD 和 ISAP 这样的算法就像一条笔直的高速公路。它们的时间增长与消息大小完美同步。如果你将消息增加一倍，时间也会增加一倍。它们没有额外的“税收”或复杂的乘数。GIFT-COFB 特别简单，使其在处理大消息时非常高效。
“分块”型选手： 像 TinyJambu 和 Romulus 这样的算法运作起来就像一条只接受特定尺寸盒子的传送带。如果你的消息不能完美契合盒子，它们就必须添加“填充”（空余空间）来填满它。这会带来一点额外的开销，尤其是在处理小消息时，但它们非常有结构性。
“置换”型选手： 像 ASCON（NIST 最终选中的获胜者）和 Xoodyak 这样的算法使用一种“洗牌”方法。它们获取数据并在特定的模式中进行混合。它们的公式显示，它们非常高效，时间成本主要来自于它们需要洗牌数据的次数。
“混合”型选手： ISAP 是不同技术的结合体。它为每次会话创建一个临时密钥，这会增加一点点设置时间，但也使其对某些类型的黑客攻击具有极高的防御力。

4. 为什么这很重要

这篇论文不仅仅是说“算法 A 更快”，它通过观察设计背后的数学逻辑来解释“为什么”。

设计选择： 作者展示了算法的“形状”如何决定其速度。有些算法构建得像单车道道路（流密码），而另一些则构建得像带有收费站的多车道高速公路（分组密码）。
可预测性： 现在，设计这些微型设备的工程师可以查看这些公式，在他们甚至还没制造出设备之前，就能预测该算法会消耗多少电池寿命。

核心结论

这篇论文提供了一个密码学性能的**“通用翻译器”**。工程师不再需要靠猜测或进行无休止的测试，现在可以使用这些符号公式来挑选最完美的“锁”。

如果你需要处理巨大消息时绝对最简单、最轻量级的路径，数学指向 GIFT-COFB。
如果你需要平衡安全性与速度以进行通用用途，数学强调了 ASCON。
如果你需要逐位处理数据而不必等待完整的数据块，Grain-128AEAD 是明确的选择。

作者总结道，通过理解这些理论上的“重量”，我们可以更好地保护物联网的安全，确保我们的微型设备在保持安全的同时，不会耗尽电池。他们计划在数字 ID 卡等现实场景中测试这些公式，以观察这些数学理论在现实世界中是否站得住脚。

技术摘要：NIST 轻量级密码学决赛入围算法的时间复杂度特征研究

问题陈述
随着数字身份系统和物联网（IoT）中的新兴技术日益依赖处理能力、内存和能量受限的设备，对轻量级密码学（LWC）的需求变得至关重要。尽管美国国家标准与技术研究院（NIST）完成了一个评估十种决赛入围算法的标准化过程，但现有文献主要依赖于经验基准（执行时间和吞吐量），而非统一的理论理解。对于 Ascon、ISAP 和 TinyJAMBU 等决赛入围算法，现有文档侧重于实现优化，但缺乏形式化的时间复杂度表达式。这种理论框架的缺失阻碍了系统地区分算法效率以及预测在不同受限环境下性能扩展性的能力。

方法论
作者提出了一个符号模型，将密码方案的时间复杂度分解为三个不同的阶段：初始化、数据处理和结束化。该框架允许推导出独立于特定硬件平台的正式时间复杂度表达式。

总时间复杂度（ $T_{total}$ ）被建模为以下各项之和：

初始化 ( $T_{init}$ )：密钥和临时值（nonce）设置的固定成本（$ck + cn$），与输入大小无关。
数据处理 ( $T_{process}$ )：处理关联数据（ $A$ ）和消息块（ $M$ ）的相关成本。这被进一步分解为 $T_A$ 和 $T_M$ ，根据块计数、置换时间（ $T_p$ ）和操作开销进行计算。
结束化 ( $T_{finalize}$ )：用于生成或验证认证标签的常数时间成本（ $c_f$ ）。

通过这种三阶段分解法，作者根据包括状态大小、置换设计和运行模式在内的算法规格，为十种 NIST 决赛入围算法（Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU, Xoodyak）推导出了符号复杂度表达式。

核心贡献与结果
本文对十种决赛入围算法的计算扩展性进行了比较分析，并根据其底层架构策略对其进行了分类：

基于置换的算法：五种决赛入围算法（Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak）采用基于海绵（sponge-based）或以置换为中心的构造。其复杂度通常由置换成本（ $b$ ）和处理的块数主导。例如，Ascon 通过精简的 12 轮初始化实现了高效扩展（ $O(l_A \cdot b + l_P \cdot b)$ ），而 SPARKLE 则包含了额外的常数项以支持加密和哈希功能。
基于分组密码的算法：三种决赛入围算法（GIFT-COFB, Romulus-N, TinyJAMBU）采用分组密码或基于寄存器的构造。GIFT-COFB 的特点是具有显著简单的线性扩展性（ $O(\ell_A + \ell_M)$ ），且不含乘法因子，这使其在处理大型消息时非常高效。TinyJAMBU 对不同阶段使用双重置换（ $P_{640}$ 和 $P_{1024}$ ），引入了特定的固定初始化成本以及针对关联数据和消息的独立处理成本。
流密码与混合算法：Grain-128AEAD 是唯一的流密码决赛入围算法，其复杂度（$O(|M| + |AD|)$）直接随比特数扩展，从而消除了填充开销。ISAP 将基于海绵的加密与会话密钥派生相结合，实现了线性扩展（ $O(|A| + |M|)$ ），同时通过密钥分离提供针对侧信道攻击的抵抗力。

分析表明，虽然所有算法都表现出随输入长度线性扩展的特性，但其系数因设计参数（如块大小、速率和置换复杂度）的不同而存在显著差异。没有一种算法能在所有指标上都占据主导地位；相反，在简洁性、功能性和安全裕度之间存在权衡。

意义
本文声称，这种统一的符号框架为评估轻量级密码原语提供了必要的理论基础。通过阐明设计参数如何塑造计算扩展性，该模型使研究人员和从业者能够比仅依靠经验基准更严谨地区分算法效率。作者指出，这项工作指导了如何选择能够支持受限环境（如移动和嵌入式设备）中安全系统的原语。论文最后指出，这些理论结果为未来在特定现实场景（如移动驾驶执照环境）中的验证奠定了基础，尽管目前的工作仍侧重于符号模型的推导本身。

1. 问题所在：测量“锁”的重量

2. 解决方案：三阶段流水线

3. 结果：谁最轻？

4. 为什么这很重要

核心结论

类似论文