容錯學習問題

容錯學習問題 （通常稱LWE問題，是 Learning with errors 的縮寫）是一個機器學習領域中的懷疑難解問題。

基本介紹

• 中文名：容錯學習問題
• 又稱：LWE問題
• 學科：電子工程

介紹

容錯學習問題由 Oded Regev 在2005年提出，他因此贏得2018年哥德爾獎。這是一個極性學習問題的一般形式。Regev同時證明了LWE問題至少比幾個最壞情況下的格問題要難。這個問題在最近被用作一種難度假設以創建公鑰密碼系統，例如 Peikert 提出的環學習時出錯密鑰交換。

簡述

雖然來自機器學習領域，但是學習時出錯問題實際上是理論計算機科學中的計算複雜度問題。用簡單易懂的方式來說，問題如下。

我提供類似的許多的線性多項式，讓你來求{\displaystyle s_{1}\cdots s_{4}}。這就是學習時出錯問題。這一問題的關鍵就在於每個等式都是約等於，有一定誤差（所謂的“出錯”）。這個誤差可以遵循一個離散隨機分布，例如，有的時候左邊比右邊大1，有的時候左邊比右邊小1，還有的時候兩邊相等。如果假設所有式子都是直等，那這個問題就太簡單了。只要有足夠的式子，那么使用常見的高斯消元法，在多項式時間內就能輕易求出。誤差的引入，導致如果你用高斯消元，那么所有的式子加到一起之後誤差也加了起來，噪音過大，導致你無法從噪音中讀取任何信息。這就是此問題的精華。

量子計算

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

公開密鑰加密

公開密鑰加密（英語：Public-key cryptography），也稱為非對稱加密（英語：asymmetric cryptography），是密碼學的一種算法，它需要兩個密鑰，一個是公開密鑰，另一個是私有密鑰；一個用作加密的時候，另一個則用作解密。使用其中一個密鑰把明文加密後所得的密文，只能用相對應的另一個密鑰才能解密得到原本的明文；甚至連最初用來加密的密鑰也不能用作解密。由於加密和解密需要兩個不同的密鑰，故被稱為非對稱加密；不同於加密和解密都使用同一個密鑰的對稱加密。雖然兩個密鑰在數學上相關，但如果知道了其中一個，並不能憑此計算出另外一個；因此其中一個可以公開，稱為公鑰，任意向外發布；不公開的密鑰為私鑰，必須由用戶自行嚴格秘密保管，絕不透過任何途徑向任何人提供，也不會透露給要通信的另一方，即使他被信任。