容錯學習問題

容錯學習問題或是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}$ 。這就是容錯學習問題。這一問題的關鍵就在於每個等式都是約等於，有一定誤差（所謂的「出錯」）。這個誤差可以遵循一個離散隨機分布，例如，有的時候左邊比右邊大1，有的時候左邊比右邊小1，還有的時候兩邊相等。如果假設所有式子都是直等，那這個問題就太簡單了。只要有足夠的式子，那麼使用常見的高斯消元法，在多項式時間內就能輕易求出 $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]