容错学习问题

容错学习问题或是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]