Ring-LWE问题及其在加密中的应用 Ring-LWE(Learning with Errors over Rings)是格密码学中的一个重要原语,它是LWE(Learning with Errors Ring-LWE加密方案利用了一个单向性质:给定一个环元素a、一个噪声项e和另一个环元素s,计算as+e很容易,但从as+e中恢复s则非常困难。 Python代码示例:基于Ring-LWE的加密方案 以下是一个简化的基于Ring-LWE的加密方案的Python代码示例,实现了密钥生成、加密和解密的基本流程。
表3:抗量子密码分类 分类 数学困难问题 用途 举例 基于格的密码 基于格上的困难问题,主要有LWE(Learning with Errors)、Ring-LWE、SIS等 加密/签名/密钥交换等 NTRU Ring-LWE(环上带错误的学习)是LWE的变体。在基于Ring-LWE的密码中,密钥由若干个多项式表示,而不是LWE中的矩阵,因而减小了密钥大小,同时提高了加解密速度。 表4:各类抗量子密码特点 基于格的密码 多变量密码 基于Hash的密码 基于编码的密码 以NTRU为早期代表,已在欧洲成为标准;目前新算法多基于LWE或Ring-LWE 以Rainbow等为代表 以Merkle McEliece为代表 格密码可实现加密、签名、密钥交换、同态等功能 以加密和签名方案为主 仅能实现数字签名,可扩展性较差 以加密和签名方案为主 NTRU不满足可证明安全,但20年未被攻破;基于LWE或Ring-LWE
除了Soliloquy以外,他们的发现还表明,其他基于理想格的方案,构造单独短向量的方法也可以被攻破,而基于一般格的方案,如Ring-LWE和NTRU则不受影响。
基于格的密码学依赖于格中某些计算问题的难度,如最短向量问题(SVP)和学习错误问题(LWE): 主要方案: CRYSTALS-Kyber:NIST第一阶段密钥交换算法标准 NTRU:高效的公钥加密和密钥交换算法 Ring-LWE
主要的后量子密码算法类型: 基于格的密码学:如NTRU、Learning With Errors(LWE)和Ring-LWE 基于哈希的密码学:如SPHINCS+ 基于编码的密码学:如McEliece