LWE算法分类及基本加解密算法示例

LWE（Learning With Errors）算法是一种基于格（lattice）的密码学原语，广泛应用于构建抗量子计算的加密方案。LWE算法的安全性基于最坏情况下的格问题（如最短向量问题SVP和最近向量问题CVP），这些问题的求解在经典计算机上被认为是困难的。由于LWE的安全性和灵活性，它已经被标准化并应用于实际的密码学协议和系统中，尤其是在需要抗量子计算的场景下。

LWE算法的特点主要包括：

（1）抗量子攻击：LWE算法被认为是抗量子计算的，即即使量子计算机出现，它仍然能够提供安全保障。这与基于因子分解（如RSA）或离散对数问题（如DSA、ECC）的传统加密算法不同。
（2）引入错误分布：LWE算法引入了一个小量的随机误差（errors），这些误差通常来自一个离散高斯分布。误差的引入使得直接求解LWE问题变得非常困难。
（3）可用于构建各种密码学原语：LWE可以用来构建多种密码学原语，包括公钥加密（Public Key Encryption）、密钥交换（Key Exchange）、签名方案（Signature Schemes）和全同态加密（Fully Homomorphic Encryption）等。
（4）参数灵活性：LWE算法允许通过调整参数（如模数q、误差分布的标准差σ、向量维度n等）来平衡安全性和效率。不同的应用场景可能需要不同的参数设置。
（5）可证明安全：在适当的参数选择下，LWE问题可以被证明是困难的，从而为基于LWE的加密方案提供可证明的安全性。

LWE算法目前包括多种类型变体，简要如下表所列。

序号	名称	特点
1	标准LWE（Standard LWE）	最原始的LWE问题定义，涉及一个秘密向量和一个小误差项的线性方程。标准LWE通常用于构建最基本的加密和密钥交换方案。
2	Ring-LWE（环LWE）	Ring-LWE是对标准LWE的一种重要扩展，它将LWE问题定义在一个环（如多项式环）上，从而减少了计算复杂度和存储需求。Ring-LWE广泛用于构建高效的加密方案，如全同态加密（FHE）。
3	Module-LWE（模LWE）	Module-LWE是LWE问题的另一种扩展形式，它涉及模上的子空间。Module-LWE在某些特定的应用场景下可以提供更好的效率和安全性。
4	Regev’s LWE-based Encryption	由Oded Regev提出的基于LWE的公钥加密方案，是最早的基于LWE的加密方案之一。该方案的安全性依赖于LWE问题的困难性。
5	GGH（Gentry-Gorbunov-Halevi） Cryptosystem	由Craig Gentry、Shai Halevi和Vinod Vaikuntanathan提出。GGH方案具有较好的效率和灵活性，适用于多种应用场景。
6	NTRUEncrypt	虽然NTRUEncrypt主要基于格的近似最短向量问题（SVP），但它也可以看作是一种LWE的变体。NTRUEncrypt是一种高效的公钥加密方案，适用于资源受限的设备。
7	TFHE（Torus Fully Homomorphic Encryption）	基于环LWE的全同态加密方案，具有极高的效率和灵活性，适用于实时加密计算。
8	FrodoKEM	基于LWE的密钥封装机制（KEM），设计用于抗量子计算的安全通信。它具有中等的安全性和效率，适用于广泛的实际应用。
9	Kyber	基于LWE的密钥交换协议，设计用于抗量子计算的安全通信。它具有较高的效率和安全性，已经被标准化并广泛应用于实际系统。

下面给出一个简单LWE算法加解密示例（LWE属于非对称密码算法，采用明文公钥加密，密文私钥解密）。

首先给出参数说明：

n（明文的bit位长度，这里我们简单点取n=4）
q（模数取q=67）
e（随机误差向量，元素随机取0-1。e在构造公私钥对时使用，取e = [[0], [1], [1], [0]]）
s（随机密钥（私钥），随机取s = [[14], [33], [55], [35]]）
A（随机nxn矩阵，A也是在构造公私钥对时使用，取A = [[28, 64, 20, 27], [34, 56, 36, 27], [47, 43, 64, 51], [36, 20, 4, 1]]）
b（公钥向量，b = (A * s + e) % q = [[60], [24], [13], [12]]）

下面可以使用LWE算法对明文m（b'0100'）加密，公钥为（A,b,n,q），具体加密过程如下步骤：

（1）将明文m转换成0-1矩阵形式，转换后的m=[[0], [1], [0], [0]]
（2）生成随机nxn矩阵，x = [[4, 0, 4, 4], [1, 2, 4, 4], [1, 2, 1, 2], [0, 2, 4, 2]]
（3）生成随机误差，e1 = [[0], [1], [0], [1]]
（4）计算c1 = (x * A) % q = [[42, 39, 17, 48], [26, 26, 29, 21], [14, 58, 30, 0], [60, 56, 1, 59]]
（5）计算c2 = (x * b + e1 + m*(q//2)) % q = [[5], [41], [11], [58]]
（6）密文即为c1||c2

私钥为s，具体解密过程如下步骤：

（1）计算t = (c2 - c1 * s) % q = [[4], [40], [3], [7]]
（2）依次处理t矩阵中每个元素tt，round（2*tt/q)%2
（3）得到p = [[0], [1], [0], [0]]，即还原明文为b'0100'，解密完成。