Kyber-512后量子密码中消息分组优化：基于静态编码与霍夫曼码、Base-64及ASCII方法的对比研究

《IEEE Access》：Message Group Optimization in Kyber-512 Post-Quantum Cryptography: Comparing Proposed Static Encoding with Huffman Code, Base-64 and ASCII Methods

本文针对Kyber-512在后量子密码应用中需将明文转换为256次多项式而带来的计算资源消耗问题，提出了一种基于自定义映射表的静态编码方法，通过将字符固定为6位编码，显著减少了封装与解封装过程所需的分组数量。实验结果表明，所提方法在保证安全性的同时，有效降低了处理开销，尤其适用于物联网等资源受限场景，为后量子密码的轻量化实现提供了新思路。

　　

随着量子计算技术的快速发展，传统公钥密码体系面临严峻挑战。Shor算法等量子攻击手段能够有效破解RSA等广泛使用的加密算法，促使后量子密码（PQC）成为研究热点。其中，基于格密码学的Kyber算法已被美国国家标准与技术研究院（NIST）采纳为国际标准。Kyber-512作为该家族中参数规模最小、处理速度最快的变体，特别适合嵌入式系统和物联网（IoT）设备等资源受限环境。然而，Kyber-512在实际应用中存在一个关键瓶颈：在进行封装（encapsulation）过程前，必须将原始消息转换为一个256次的多项式。若采用传统的ASCII编码（每个字符8位），每32个字符就需要进行一次封装操作。对于较长的消息，需分割成多个分组进行处理，这不仅增加了计算开销，也影响了通信效率。因此，如何优化消息的编码方式，减少封装与解封装（decapsulation）的次数，成为提升Kyber-512实用性的关键问题。

为了解决上述问题，泰国乌隆他尼皇家大学技术工程学院的Kritsanapong Somsuk在《IEEE Access》上发表了一项研究，题为“Message Group Optimization in Kyber-512 Post-Quantum Cryptography: Comparing Proposed Static Encoding with Huffman Code, Base-64 and ASCII Methods”。该研究提出了一种新颖的静态编码方法，旨在降低每个字符的比特长度，从而减少Kyber-512所需的处理分组数量。

研究人员开展此项研究的主要技术方法包括：首先，设计了一个包含54个字符（大写英文字母、数字及常用符号）的自定义映射表，为每个字符分配一个固定的6位二进制码，替代传统的8位ASCII码。其次，提出了两种具体的编码解码方案：MEKyber-512/MDKyber-512（方法一）将消息按42个字符分组（42×6=252位，不足256位部分补零），以及MEKyber-512-V2/MDKyber-512-V2（方法二）将整个消息的6位码流连续拼接后再按256位分组，以减少比特浪费。此外，还引入了Pre-Check-Tailing (PRT)和Post-Check-Tailing (PST)两种校验技术，用于在封装前和解封装后自动检测并修正尾部的填充错误，确保消息的完整还原。研究还纳入了来自公开文献摘要的真实文本作为测试样本，以评估方法的普适性。

研究结果部分通过多个实验对比了所提方法与ASCII、Base-64及霍夫曼码（Huffman Code）的性能。

在分组数量方面，对于500字符的消息，所提方法一和方法二均只需12个分组，而ASCII码需要16组，Base-64更是需要21组。霍夫曼码在字符频率分布不均的文本中表现最佳，仅需9组，但在字符分布均匀的文本中，其分组数增至12组，与所提方法相同。这表明霍夫曼码的压缩效率高度依赖于文本的统计特性，而所提静态编码方法则表现稳定。

在处理时间上，所提方法一的编码时间约为2毫秒，解码时间约为2.3-3.26毫秒，均优于Base-64（编码5.1-5.15毫秒，解码5.22-5.4毫秒），但略慢于ASCII码（编码约2毫秒，解码约1.16毫秒）和霍夫曼码（解码最快，仅0.8毫秒）。然而，霍夫曼码需要附带传输霍夫曼树，这会暴露原始明文的字符频率统计特征，存在潜在的安全风险。虽然可以将霍夫曼树一同封装，但这会导致双重加密，增加计算开销，违背了在PQC中最小化处理需求的初衷。

图2展示了不同方法在不同消息长度下的封装时间对比。可以看出，所提方法的封装时间始终低于Base-64和ASCII码，但高于霍夫曼码。

图3的解封装时间对比也呈现相似趋势。所提方法在安全性和效率之间取得了良好平衡。

在安全性方面，所提方法采用固定长度编码，字符与码字一一对应，不会泄露任何统计信息。而霍夫曼码的可变长编码特性使其容易受到基于频率分析的攻击。PRT和PST算法的测试结果显示，它们在处理带有不同数量尾部'A'的明文时，均能达到100%的准确率，且处理延迟在微秒级别，验证了其在自动化系统中处理尾部填充的可靠性。

研究结论强调，所提出的静态编码方法成功地将Kyber-512中每个字符的表示从8位减少到6位，显著降低了处理长消息时所需的封装和解封装次数。与ASCII和Base-64相比，该方法在保证相同安全级别的前提下，提高了处理效率。虽然其压缩率不及霍夫曼码，但避免了因传输树结构而带来的安全风险和处理开销，为资源受限设备应用后量子密码提供了更实用、安全的解决方案。研究的局限性在于其映射表目前仅支持54个字符，未来可扩展字符集并评估不同比特长度的安全性。这项工作为后量子密码算法的轻量化优化提供了重要参考。