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加密

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!