LWE 简单来说就是一组线性多项式中加入了噪声(errors)来让计算变得复杂甚至说不可解, 如下 图:
只要有足够的式子，那么使用常见的高斯消元法，在多项式时间内就能轻易求出(s1,s2,s3, s4). 误差的引入，导致如果你用高斯消元，那么所有的式子加到一起之后误差也加了起来，噪音过大，导致你无法从噪音中读取任何信息。这就是此问题的精华
仔细思考LWE 的过程, 我们可以把LWE 认为是一个trapdoor函数(只能正着计算, 不能逆运算) 基于此问题看天才的密码学家如何设计一套加密体系的. 在了解设计之前先来看几个简单的公式
下面几个公式q 为素数, a, s为自然数, e 就是errors 也是整数
1.
a===a%q (mod q) a%q === a%q%q这是显而易见的
2.
s*a === s * (a%q) (mod q) (s*a) % q == (s*a%q) % q
3.
u = a % q
v = (a*s) %q %q
(v -s * u) % q = (a*s % q %q - s * a % q) % q = 0
4.
u = a % q
v = (a*s e) % q % q
(v -s * u) % q = ((a*s e) % q % q - s * a % q) % q = e%q
5. 有了上面的结论看天才如何设计加密体系的
a, q 是公钥, s 是私钥, M 需要加密的数字0,1(这里只是一bit加密)e是errors
加密过程
u = a % q
v = (a*s e) % q %q q // 2 *M
密文(u,v)
解密过程
dec = (v-s*u) %q = (e q//2*M) % q
当dec 小于q//2 , M == 0 else M==1
如果仔细思考这个过程, 加密过程即使公私钥一样 但由于error的随机性对统一M(message)加密的结果也是不一样的. 解密过程也不同以往, 像RSA, DH的密文都是直接计算得到, 而LWE 却是判断大小. 而且这个噪声也不是随机选择的(如果e> q//2其实结果是错误的). 所以基于LWE的加解密参数q的选取, 噪声e的选择都是很重要的, 上述只是针对一个bit的加密过程, 后续会写基于LWE 实现的NTRU加密
,
