容錯學習問題

容錯學習問題或是LWE問題（英語：Learning with errors，LWE）是一個機器學習領域中的懷疑難解問題。由Oded Regev在2005年提出，他因此贏得2018年哥德爾獎。這是一個極性學習問題的一般形式。Regev同時證明了LWE問題至少比幾個最壞情況下的格問題要難。這個問題在最近^[1][2]被用作一種難度假設以創建後量子公鑰密碼系統，例如Peikert提出的容錯環學習密鑰交換。^[3]

簡述

雖然來自機器學習領域，錯誤學習問題實際上是理論計算機科學中的計算複雜度問題。

一個簡單易懂的例子：

${\displaystyle 14\cdot s_{1}+15\cdot s_{2}+5\cdot s_{3}+2\cdot s_{4}\approx 8{\bmod {1}}7}$
${\displaystyle 13\cdot s_{1}+14\cdot s_{2}+14\cdot s_{3}+6\cdot s_{4}\approx 16{\bmod {1}}7}$
${\displaystyle 6\cdot s_{1}+10\cdot s_{2}+13\cdot s_{3}+1\cdot s_{4}\approx 3{\bmod {1}}7}$

已知類似含約等號的線性多項式，讓你來求${\displaystyle s_{1}\cdots s_{4}}$。這就是容錯學習問題。

容錯學習的關鍵在於存在誤差項。誤差可能遵循一個離散隨機分布，噪聲過大時難以從噪聲得到信息，這就是此問題的精華。^[4]

密碼學上的應用

A是一個m x n矩陣，s是一個n維向量，e是一個m維向量。我們定義LWE_A(s,e) := b := As + e。由此可以構造一個對稱加密算法。加密算法定義如下:

• s作為密鑰k使用；
• (A,e)這一組數據在加密時隨機生成；
• 由s, A, e所求得的值b作為一次性密碼本的密鑰使用，同密文m進行異或操作。

這一算法和傳統對稱密鑰加密算法的區別的關鍵在於，加密方不將誤差數據e傳送給解密方，導致解密方所解得明文存在一個小的誤差。

量子計算

2018年10月，斯坦福研究院的學生利用LWE問題作為基礎解決了經典計算機如何驗證量子計算機是否進行了量子計算這一問題。^[5]