安全芯片常被称为“关键数据的保险箱”，这一形容毫不为过。在不知不觉中，它已深入我们日常生活的方方面面。然而，随着5G、物联网、车联网等技术的快速演进，安全芯片正被推向更广阔的舞台——新应用场景层出不穷，随之而来的挑战也日益严峻。

今天，我们将重点探讨安全芯片的核心技术之一——后量子密码认证。

1、安全认证技术概述

首先，我们来梳理安全认证技术的主流方案。安全认证的核心目标是防止信息被篡改、删除、重放或伪造，确保接收方能够确认消息的来源与真实性。当前常见的安全认证技术主要有四种：数字摘要、数字摘要+对称密钥认证、数字摘要+非对称密钥认证，以及数字证书认证。

需要特别注意的是，随着量子计算的发展，目前绝大多数公钥密码算法——例如RSA、Diffie-Hellman、椭圆曲线等——在足够强大且稳定的量子计算机面前，都存在被攻破的风险。换言之，现有基于非对称密钥的认证技术正面临重大威胁。因此，基于后量子密码的认证技术已成为研究热点。

1.1 数字摘要

最基础的认证方式是“数字摘要”。其原理简单：使用单向HASH函数，将待发送的消息压缩成一串固定长度的数据，然后连同原始消息一并发送给接收方。

具体步骤：

（1）发送方利用Hash函数计算消息摘要，并将摘要与原始消息一同发出。

（2）接收方Bob收到后，采用同样的算法重新计算摘要，再与收到的摘要进行比对。

优点：一旦消息发生改动，摘要必然随之变化；且由于是单向函数，无法从摘要反推出原文。

缺点：仅靠Hash无法保证完整性——攻击者完全可以篡改消息，再重新计算一个摘要替换原摘要，接收方很难察觉。

1.2 数字摘要+对称密钥认证

该方案引入了共享的对称密钥，具体逻辑是：用共享密钥加密一个随机数，再对密文进行HASH运算，最后将HASH值发送给对方。

具体步骤：

（1）通过安全通道，Bob和Alice事先协商好一个共享密钥。

（2）Bob向Alice发送一个随机数。

（3）Alice用共享密钥加密该随机数，接着对密文做HASH运算，并将HASH值发送给Bob。

（4）Bob同样用共享密钥加密随机数，再对结果做HASH运算，然后将计算结果与收到的HASH值进行比对——若一致，则说明消息来自Alice。

优点：只要密钥不泄露，就能有效防止信息篡改；对称加密性能也很高效。

缺点：双方必须通过安全通道共享密钥；而且任一方的密钥泄露，整个系统就会失效。

1.3 数字摘要+非对称密钥认证

该方案采用非对称密钥体系，核心思路是：发送方用私钥对信息签名，接收方用公钥验证签名。

具体步骤：

（1）Bob获取Alice的公钥，然后向Alice发送一个随机数。

（2）Alice使用自己的私钥对该随机数签名，并将签名结果返回给Bob。

（3）Bob用Alice的公钥验证收到的签名——若验证通过，就能确认信息确实来自Alice。

优点：公钥可以公开，无需保密；私钥仅由发送方自行保管。

缺点：关键问题在于——如何确保你拿到的公钥确实是Alice的？这容易遭受中间人攻击。

1.4 数字证书认证

为解决公钥可信问题，需要引入一个权威第三方——CA（认证中心）。Alice向CA申请证书，CA确认其身份后，生成并颁发Alice的数字证书。证书通常包含以下内容：

· 主题Subject：需要鉴别的用户Alice
· Alice的公钥public key
· 数字签名digital signature：CA对证书的签名
· 发布者Issuer：验证并签发证书的实体
· 签名算法Signature Algorithm

具体步骤：

（1）Bob请求获取Alice的证书公钥。

（2）Alice将证书发给Bob，Bob用CA的公钥验证证书真伪，并从中提取Alice的公钥。

（3）Bob获得Alice公钥后，向Alice发送一个随机数。

（4）Alice用自己的私钥对随机数签名，将签名结果发给Bob。

（5）Bob用Alice的公钥验证签名——若通过，则确认消息来自Alice。

优点：能够有效抵御中间人攻击，确认Alice公钥的真实性。

缺点：这套体系在量子计算机面前，依然存在被攻破的风险。

2、后量子密码算法概述

后量子密码，顾名思义，就是能够抵抗量子计算机攻击的新一代密码算法。目前实现后量子密码主要有四条技术路线：

（1）基于哈希（Hash-based）：最早出现于1979年，主要用于构建数字签名。代表算法有Merkle哈希树签名、XMSS、Lamport签名等。

（2）基于编码（Code-based）：最早出现于1978年，主要用于构建加密算法，代表是McEliece。

（3）基于多变量（Multivariate-based）：最早出现于1988年，可用于构建数字签名、加密和密钥交换。代表方案包括HFE、Rainbow（UOV方法）、HFEv-等。

（4）基于格（Lattice-based）：最早出现于1996年，用于构建加密、数字签名、密钥交换，以及众多高级密码学应用——如属性加密、陷门函数、伪随机函数、全同态加密等。代表算法包括NTRU系列、NewHope（已被Google测试过），以及一系列同态加密算法（BGV、GSW、FV等）。基于格的计算速度快、通信开销相对较低，还能构造多种密码学原语，因此被认为是最有前景的后量子密码技术路线。

当参数选取恰当时，目前没有已知的经典或量子算法能够快速求解这些底层问题。需要再次强调：这些算法的安全性完全依赖于是否存在能快速求解其底层数学问题或直接攻击算法本身的高效手段——这正是量子计算机对传统公钥密码构成巨大威胁的根本原因。

除上述四种外，还有基于超奇异椭圆曲线、量子随机漫步等技术构建的后量子密码方法。另外，对称密码算法在密钥长度足够大的情况下（例如AES-256），也可视为后量子安全的。

至于为何这四类最为重要？因为它们最能构造出公钥密码学现有各种算法的后量子版本，甚至还能实现超出原有功能的应用（如基于格的全同态加密）。

2.1 基于哈希（Hash-based）

基于哈希的签名方案最初由Ralph Merkel提出，被视为RSA、DSA、ECDSA等传统数字签名的一种可靠替代方案。它由一次性签名方案演变而来，借助Merkle哈希树认证机制实现。哈希树的根即为公钥，一次性认证密钥是树中的叶子节点。其安全性依赖于哈希函数的抗碰撞性。由于目前没有有效的量子算法能快速找到哈希函数的碰撞，因此采用足够长输出的哈希构造可以抵抗量子计算机攻击。此外，该签名方案还有一个优点：安全性不依赖于某个特定哈希函数——即使当前使用的哈希函数被攻破，也可以直接更换为更安全的哈希函数。

2.2 基于编码（Code-based）

基于编码的算法利用错误纠正码引入随机性错误，并进行纠正和计算。McEliece是一个著名实例，它使用随机的二进制不可约Goppa码作为私钥，而公钥则是经过变换后的一般线性码。后来，Courtois、Finiasz和Sendrier又利用Niederreiter公钥加密方案构造了基于编码的签名方案。这类算法的主要缺点是公钥尺寸过大，但在加密、密钥交换等场景中仍有应用价值。

2.3 基于多变量（Multivariate-based）

该方案的核心逻辑是：使用有限域上多个变量的二次多项式组来构造加密、签名和密钥交换算法。其安全性依赖于求解非线性方程组的难度——即多变量二次多项式问题。该问题已被证明属于非确定性多项式时间困难，目前没有已知的经典或量子算法能快速解出有限域上的多变量方程组。与经典的基于数论问题的密码算法相比，多变量方案计算速度快很多，但公钥尺寸偏大，因此更适合不频繁传输公钥的应用场景，如物联网设备。

2.4 基于格（Lattice-based）

基于格的算法在安全性、公私钥尺寸和计算速度之间达到了最佳平衡，是最有前景的后量子密码技术之一。与基于数论问题的传统算法相比，它的计算速度更快、安全强度更高，而通信开销只有小幅增加。与其他后量子方案相比，格密码的公私钥尺寸更小，安全性和计算速度等指标也更出色。更重要的是，它能实现加密、数字签名、密钥交换、属性加密、函数加密、全同态加密等各种现有密码学构造。其安全性建立在求解格中问题的困难性之上。

在达到相同甚至更高安全强度的情况下，基于格算法的公私钥尺寸比前三种方案都小，计算速度更快，且能构造多种密码学原语——因此更适合实际应用。近年来，基于LWE（带错误学习）问题和RLWE（环LWE）问题的格密码学发展迅速，被认为是最有希望被标准化的技术路线之一。

3、格密码算法概述

简单来说，格是一种数学结构，定义为一组线性无关的非零向量（称为“格基”）的整系数线性组合。例如，给定一组格基X1, X2, …, Xn，对任意整数C1, C2, …, Cn，C1X1 + C2X2 + … + CnXn都是属于该格的向量，n是格的维数。下图中展示的是一个二维格和两组不同的格基：

一个格的格基不一定唯一。例如((2,1), (1,1))和((1,0), (0,1))都是二维整数格的格基。从上图可以看出，即使是定义同一个格的两组格基，它们的长度也可能相差很大。数学家和密码学家的共识是：对于维数足够高的格，通过一组随机选取的格基找到一组短格基，或者得到一组线性无关的短格向量，是极其困难的。这个问题称为最短独立向量问题（SIVP）。此外还有gap-SVP、BDD等困难问题。这些属于数学理论范畴。而在实际密码学应用中，格密码算法更倾向于采用容错学习（LWE）问题来构建困难性基础。

LWE问题的表述如下：给定随机矩阵A和向量As+e mod q，其中e是一个小误差项，q是模数（通常取较大的质数），要从这个组合中恢复出随机的s是非常困难的。我们把(A, b=As+e mod q)称为LWE样本，把s称为LWE秘密。你可能会想，如果没有误差项e，这其实就是求解一组线性方程组，很容易解出。但引入误差e后，LWE问题可以归约到SIVP等格上的困难问题——换言之，求解LWE问题的难度不低于求解格上的困难问题。

LWE问题有一个巨大优势：它存在“最坏情况到平均情况的归约”——求解平均情况下的LWE问题，难度不低于最难的SIVP问题实例。这在密码学中非常罕见。早期一些公钥密码算法，如基于背包问题的体制，由于存在一些容易求解的背包实例，参数选择不当时很容易被攻破。而基于LWE的格密码由于存在这种归约关系，就能避免此类攻击，安全性更有保障。

不过，直接用LWE问题构造密码学方案效率并不高。更多时候，我们会用多项式替换整数向量，得到多项式LWE，即环LWE。一个环LWE样本是(a, b=as+e mod q)，其中a、s、e都是多项式。环LWE的安全性建立在理想格对应数学问题困难性的基础上。虽然人们认为这些问题的可靠性不如格问题高，但目前也没发现能高效求解它们的算法。此外，还有介于LWE和环LWE之间的模LWE问题，以及它们的变种LWR、环LWR、模LWR问题。格密码的安全性基本都建立在解决这些问题的困难性上。

3.1 基于格的公钥加密算法

在基于LWE问题设计的密码算法中，通常将LWE样本作为公钥使用，将LWE秘密作为私钥使用——这样公钥就不会泄露关于私钥的信息。假设公钥为(a, b=as+e mod q)，私钥为s，这里a、b、s、e都是多项式，且s和e的系数相对于q来说都是很小的值（理论上应取离散正态分布，但实际应用中为兼顾效率和安全性，往往用二项分布或均匀分布来模拟）。下面描述最简单的格公钥加密方案。

对于需要加密的消息，我们会将其表示为系数为0-1的多项式m：

（1）先随机选取系数较小的多项式r、e1、e2。

（2）计算密文c = ar+e1 mod q和d = br+e2+m(q-1)/2 mod q。

可以想见，由于as约等于b mod q，所以ars约等于br mod q，且(ar+e1)s约等于br+e2 mod q。只要s、e、r、e1、e2都足够小，就能保证br+e2-(ar+e1)s mod q的系数都不超过(q-1)/4。因此，d-cs与m(q-1)/2的每个系数之差也都不超过(q-1)/4。这样一来，我们就可以从d-cs中还原m：如果d-cs的第i个系数更接近0，则将m的第i位设为0；如果更接近(q-1)/2，则将m的第i位设为1。如此，用私钥s就能成功解密密文(c, d)，得到原始消息m。该方案的安全性来自两方面：一是私钥的安全性——公钥本身就是LWE样本，不会泄露私钥信息；二是消息的安全性——密文也是LWE样本，没有私钥就不可能从密文中获知消息内容。当然，这里描述的简单方案仅满足选择明文安全，而非选择密文安全。用于实际应用时，还需借助著名的Fujisaka-Okamoto变换，将其转化为选择密文安全的方案。

3.2 基于格的数字签名算法

在RSA、椭圆曲线等传统密码体系中，公钥加密与数字签名存在一定的对偶性——简单交换公私钥就能将公钥加密算法转化为数字签名算法。但在格密码中，这种对偶性并不存在，必须通过全新的方式构造数字签名。密码学家广泛采用的方法是：通过零知识证明协议来构造数字签名。

如果你初次接触零知识证明，可能会觉得不太真实——它解决的是这样一个问题：我能否向你证明一个命题成立，却不让你了解证明该命题所需的任何知识？听起来有违直觉，但确实可行。要实现安全的数字签名，最根本的需求是让验证者能够认证签名者的身份。这恰好等价于一个零知识证明：证明者可以证明自己拥有与公钥匹配的私钥，但完全不向验证者泄露关于私钥的任何信息。这是一类最简单的零知识证明协议，通常称为∑协议。

∑协议由三个步骤组成：

（1）证明者给出承诺w：先随机选择y，通过y生成承诺w，交给验证者。

（2）验证者提出挑战c：验证者给出一个均匀随机的挑战c。

（3）证明者给出应答z：用第一步中的y、挑战c以及自己的私钥，计算出应答z（且要求z在整个值域上均匀随机）。验证者利用证明者的公钥、挑战c和承诺w，确认z是否由证明者合法生成。

我们将(w, c, z)这个三元组称为抄本。在一个具备零知识性的∑协议中，通常要求：在不知道私钥的情况下，（1）通过w和c得到z是困难的；（2）通过c和z得到w是容易的。这意味着，即便不知道私钥，也可以这样生成抄本：先随机选取c和z，再算出w。由于生成过程不需要私钥参与，所以抄本中不包含任何关于私钥的知识——零知识性由此得以保证。

∑协议需要证明者和验证者之间实时交互，因此不能直接用于构造数字签名。但我们注意到，∑协议要求挑战c均匀随机选取——而安全的哈希函数，其输出与随机值无法区分。因此，我们可以将承诺w和待签名的消息m一起输入哈希函数H，用输出结果来模拟挑战c。这样既不需要额外的验证者，又因为有签名消息的参与，消息与抄本被牢牢绑定在一起。这种方法称为Fiat-Shamir变换。可以证明：安全的∑协议经过Fiat-Shamir变换，能得到安全的数字签名方案。

下面简要说明如何基于LWE问题构造∑协议，进而构造数字签名。与公钥加密算法一样，公钥为(a, b=as+e mod q)，私钥为s。

（1）先随机选取一个较小的y。

（2）令承诺w为ay的高比特位——这是为了排除误差项的影响。

（3）对于挑战c，令应答z = y + cs（这里需要保证z均匀随机，因此要排除一些使z不随机的边缘值；如果z落在边缘范围，就重新选y再算一次，细节不再展开）。

由于ay = az – cas ≈ az – cb mod q，因此只需验证w是否是az–cb的高比特位即可。对于需要签名的消息m和哈希函数H，令c = H(w || m)，就可以将这个协议转化为实际可用的签名算法（验签时，需要验证c = H(w || m)是否成立）。