容错学习问题

容错学习问题 （通常称LWE问题，是 Learning with errors 的缩写）是一个机器学习领域中的怀疑难解问题。由 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}}$ 。这就是容错学习问题。这一问题的关键就在于每个等式都是约等于，有一定误差（所谓的“出错”）。这个误差可以遵循一个离散随机分布，例如，有的时候左边比右边大1，有的时候左边比右边小1，还有的时候两边相等。如果假设所有式子都是直等，那这个问题就太简单了。只要有足够的式子，那么使用常见的高斯消元法，在多项式时间内就能轻易求出${\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]

参考文献

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.
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. https://arxiv.org/pdf/1804.01082