LPN不像LWE和SVP那么重要吗？

Question

我一直在学习格密码学，并注意到大多数资源，如这是克里斯·佩卡特的调查、格点密码学冬季派等，都不包括关于LPN的资料，而且通常只讨论SIS和LWE。根据这篇文章，和LWE问题是等价的吗？，LWE是LPN的一个推广。据我所知，SVP (源自SIS)和LWE是常见的格子陷阱门。LPN不是一个重要的格子陷阱值得讨论吗？如果不是，为什么会这样呢？

Answer 1

LPN是基于代码的问题，而不是格问题.它们非常相似，但定义是针对“距离”的不同概念(Hamming vs \ell_p-norm)。一般来说，虽然格和码的世界之间有着广泛的相似之处，但这些平行并不是精确的。

一个特别的例子是计算代码/格的“最小元素”的硬度。对于码，它是最小距离问题，格是最短向量问题。更强的硬度结果是众所周知的MDP (SVP的最佳硬度结果需要随机降低，MDP是确定性的)。其他的数学问题在难度上也会有很大的差异--代码的“球形填充”问题比格问题要简单得多。

与密码学相关的是从最坏情况到平均情况的缩减。自90年代S创立以来，这一直是格型密码学的一个很大的激励因素，但类似的密码结果只开发了去年 (我认为结果本身有点弱，但不是专家)。本文指出，这是\mathsf{LPN}第一次构造抗碰撞散列函数，这可能有助于突出基于格的密码学与基于代码的密码学(某些原语的构造)技术上的差异。