容錯學習問題

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

簡述

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

一個簡單易懂的例子：
$14\cdot s_{1}+15\cdot s_{2}+5\cdot s_{3}+2\cdot s_{4}\approx 8{\bmod {1}}7$
$13\cdot s_{1}+14\cdot s_{2}+14\cdot s_{3}+6\cdot s_{4}\approx 16{\bmod {1}}7$
$6\cdot s_{1}+10\cdot s_{2}+13\cdot s_{3}+1\cdot s_{4}\approx 3{\bmod {1}}7$
已知類似含約等號的線性多項式，讓你來求 $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]

參考文獻

^ Oded Regev, 「On lattices, learning with errors, random linear codes, and cryptography,」 in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
^ Chris Peikert, 「Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,」 in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
^ Peikert, Chris. Mosca, Michele , 編. Lattice Cryptography for the Internet. Lecture Notes in Computer Science. Springer International Publishing. 2014-10-01: 197–219 [2018-10-09]. ISBN 978-3-319-11658-7. （原始內容存檔於2018-10-09）.
^ Oded Regev, The Learning with Errors Problem, https://cims.nyu.edu/~regev/papers/lwesurvey.pdf （頁面存檔備份，存於網際網路檔案館）, 於2018年10月9日訪問
^ https://arxiv.org/pdf/1804.01082

[regev05-1] Oded Regev, 「On lattices, learning with errors, random linear codes, and cryptography,」 in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.

[peikert09-2] Chris Peikert, 「Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,」 in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.

[3] Peikert, Chris. Mosca, Michele , 編. Lattice Cryptography for the Internet. Lecture Notes in Computer Science. Springer International Publishing. 2014-10-01: 197–219 [2018-10-09]. ISBN 978-3-319-11658-7. （原始內容存檔於2018-10-09）.

[4] Oded Regev, The Learning with Errors Problem, https://cims.nyu.edu/~regev/papers/lwesurvey.pdf （頁面存檔備份，存於網際網路檔案館）, 於2018年10月9日訪問

[5] ttps://arxiv.org/pdf/1804.01082

[1]

[2]

[3]

[4]

[5]