纠错码与基于格的密码

Question

我不是PQ密码方面的专家，但据我所知，纠错码和基于格密码的密码假设非常相似。对我来说，最重要的区别是噪音的本质。在一种情况下，噪声是由“物理噪声”激发的，而在另一种情况下，它是更数学的，考虑一个更复杂的距离(欧几里得距离而不是汉明距离)。

从直觉上讲，这个理由是有意义的，因为我所知道的每一个涉及格密码的应用都比那些基于纠错密码的应用更有效。

1. 你觉得我的直觉对吗？
2. 如果是的话，是否有一个定理可以证明，基于纠错码假设的每一个密码协议都可以转换成一个更有效的基于格的协议(即，具有相同的安全性，并且基于较弱的格假设)？
3. 如果没有，是否有更非正式的说法认为现有的研究考虑到了这个问题？或者比较这两个系列的假设是没有意义的？

Answer 1

关于第一段，我不会说关键的区别是噪声的类型，因为基于格的密码学(LBC)使用了许多不同的噪声:高斯、二进制、三元等(也见这个SE线程：带误差环学习中的均匀和离散高斯采样)。然而，在LBC中非常有用的一点是，您可以使用您正在处理的环q的模数\mathbb{Z}_q。LBC中的许多问题可以通过简单地增加q来解决，这当然对基本假设的硬度有影响，但在许多情况下影响是可控的。

另一方面，在基于代码的密码学(CBC)中，大多数情况下模数固定在2(例如自行车)。当这种情况发生时，模量是CBC可以利用的少一个工具。结合模数，度量当然有影响。例如，假设使用相同的欧氏范数(resp )添加维数n向量x_i (维数n )。(汉明重量)：

• 用欧几里德范数，你可以得到\|\sum_i x_i \| \leq \sum_i \|x_i\|。因此，如果你把模数q设置为足够大，你仍然可以认为和是短的，这对安全性和正确性都是有用的。
• 类似地，对于Hamming重量w，您有w(\sum_i x_i) \leq \sum_i w(x_i)。因此，如果你加上n向量的Hamming重量1，你不能说任何有意义的重量的和。

关于问题1，2，3，目前最先进的LBC方案确实比CBC更有效。但是不能保证这是真的，因为CBC已经存在了40多年，所以密码分析人员有足够的时间找到优化的攻击。LBC更近一些(20~ 20年)。请注意，当正确地参数化时，这两个家族似乎在其参数中提供了指数硬度：

• 对于CBC：O(2^{0.0885 \cdot n})，其中n是一个系统参数，请参见本论文。
• 对于LBC：\tilde{O}(2^{0.295 \cdot B})，B是一个要计算的烂摊子，但似乎与系统参数的增长大致是线性的，参见本论文。

正如您所提到的，这两个家族的假设是相似的(例如，基于QC-MDPC的方案使用的假设看起来非常类似于NTRU和Ring-LWE，参见本演示文稿第4页)，并且大多数简单的LBC方案都具有CBC等效项，并且是对等的。在某种程度上，我们甚至可以使用画类比 在更深的层次，我认为这在概念上是令人满意的。

Answer 2

广义地说，“基于密码的密码”假设和“基于格”假设之间的主要区别是噪声分布。当然也有例外，例如使用秩度量的基于代码的密码系统，或二进制LPN，其中噪声可以描述为小汉明重量或较小的欧氏距离。

在一种情况下，噪声是由“物理噪声”激发的，而在另一种情况下，它更数学，并考虑一个更复杂的距离(欧几里得距离，而不是汉明距离)。

我不确定这些“物理”和“数学”噪音的类比。这两种类型的噪声在不同的物理场景中都可能是有用的数学模型，例如低汉明重量噪声可以建模在传输过程中翻转的比特，而高斯噪声可以建模来自噪声传感器的图像中的小扰动。无论如何，这些类比与密码学并没有真正的关系。

是否有定理证明基于纠错码假设的每一个密码协议都可以转化为基于格的更有效的协议(即具有相同安全级别和基于较弱格假设的协议)？

我不知道像这样的一般定理。虽然基于格的协议通常更高效，但情况并不总是如此，这在很大程度上取决于密码应用程序。

一个自然的例子，其中格击败码是密钥交换。在这里，基于格的协议(如凯伯 )比基于代码的类似物(如自行车 )要简单和快速得多，这很大程度上是因为在基于代码的设置中有一个昂贵的纠错步骤，而与纠正格设置中错误的廉价舍入技术相比。

另一个例子是构造线性同态加密方案的挑战。使用格是相当简单的，但从基于代码的假设来看，这仍然是一个尚未解决的问题。甚至有证据表明，使用自然的“算术”技术是不可能实现的--参见Applebaum，Avron和Brzuska的论文；这项工作只研究特定的应用程序，但可能包含您感兴趣的定理的类型。

另一方面，在一些情况下，小汉明重量的噪音可以带来效率的好处.最近的一个例子是在安全多方计算协议中生成私有的、相关的随机性(例如乘法、三重或随机的不经意传输)。使用基于代码的假设，有一些有效的技术可以将相关的随机性压缩到更短的种子，这可以在以后扩展。这种压缩技术在很大程度上依赖于稀疏噪声的分布，而在格点设置中的类似方法则要昂贵得多。(例如，请参见这些 作品)

Answer 3

只是想补充另一个快速答案，但是我们可以在这个列表中添加"Mersenne“-based密码，它最初被定义为一种基于格型密码的变体，在这种情况下，你可以使用”大整数“算法而不是多项式算法(见本论文)。一些作者试图将它们都相似的抽象意义正式化，例如在线性代数密码问题的一个框架中，它指出，通过改变：

• 底层的环算术发生在(通常可以认为是for \mathbb{Z}[x] / (f(x), g(x))，其中g(x)通常是相当小的程度，即0或1)。
• “小”的概念(你似乎已经明白了)
• 硬度假设(大致有LWE型、LWR型、SIS型和NTRU型)，尽管定义得当，但人们甚至可以将LWR型假设视为LWE型假设和非I.I.D型假设的特例。(噪音)

一个人可以得到各种各样的计划。我不认为这篇论文在这个抽象的框架中给出了具体的构造，但是将现有的方案推广到这个抽象的设置并不太困难。

这并不意味着它们都是完全等价的，在不同的假设下实例化一个“模板”方案会导致相同的效率方案，甚至在所有潜在的硬度假设中，格最终都是最有效的(用具体参数探讨这个问题会很有趣)。但这三个领域之间至少有一些总体概念上的相似之处，这可能有助于记住这一点，至少在构造密码系统的层面上是这样的(但在密码分析的背景下，虽然“LLL-for codes”论文当然是朝这个方向工作的)。