基于格的密码学外文翻译资料

本科毕业设计（论文）

外文翻译

基于格的密码学

Lattice-based Cryptographylowast;

Daniele Micciancio Oded Regev

2008 年 11月 7日

November 7 , 2008

1导言

在这一章中，我们描述了基于格的密码学的一些最新进展。基于格的密码构造为后量子密码学带来了巨大的希望，因为它们基于最坏情况下的硬度、相对有效的实现以及极大的简单性享有非常强的安全性证明。此外，基于点阵的加密技术被认为对量子计算机是安全的。我们在这里的重点将主要放在基于格的密码学的实际方面，而不是用来建立其安全性的方法。关于基于网格的密码学主题的其他调查，参见，例如，[60，36，72，51]和[50，68]的课堂笔记。阮氏和斯特恩的调查[60]也描述了格在密码分析中的一些应用，这是我们这里不讨论的一个重要话题。另一个有用的资源是Micciancio和Goldwasser [53]的书，其中也包含了大量关于格问题计算复杂性方面的信息。

图1:一个二维格和两个可能的基底。

那么什么是格呢？格是具有周期性结构的n维空间中的一组点，如图1所示。更正式地说，给定n-线性独立向量b1，....，bnisin;R^n，它们生成的格是向量集

向量b1，....，bn被认为是格的基础。

格在密码学中的应用方式一点也不明显，这是Ajtai[4]在一篇突破性论文中发现的。到目前为止，他的研究成果已经发展成为一个完整的研究领域，其主要焦点是扩大基于格的密码系统的范围，并创建更实用的基于格的密码系统。在更详细地讨论这一研究领域之前，让我们首先描述涉及格的计算问题，格的假定硬度是基于格的密码学的核心。

1.1格问题和算法

基于格的密码构造基于格问题的假定硬度，其中最基本的是最短向量问题(SVP)。这里，我们给定一个由任意基表示的格作为输入，我们的目标是输出其中最短的非零向量。事实上，人们通常考虑SVP的近似变量，其目标是输出一个格向量，其长度至多是最短非零向量长度的某个近似因子gamma;(n)倍，其中n是格的维数。SVP和其他几个格问题的更精确的定义出现在第2节。

网格问题最著名和研究最广泛的算法是LLL算法，由伦斯特拉、伦斯特拉和洛夫·阿斯兹[39]于1982年开发。这是一个多项式时间算法，适用于SVP(和大多数其他基本格问题)，它实现了一个近似因子20(n)，其中n是格的维数。尽管这看起来很糟糕，但LLL算法非常有用，应用范围从有理数[39]上的因式分解多项式到整数规划[31]，以及密码分析中的许多应用(例如对基于背包的密码系统的攻击和特殊情况下的RSA)。

本章的编辑版本发表在《后量子密码术》上，伯恩斯坦；J. BuchmannE. Dahmen(编辑)，第147-191页，斯普林格(2009年2月)。这是作者的副本。

加利福尼亚大学圣地亚哥分校社会科学系，加利福尼亚州拉霍亚，92093，美国。部分由国家自然科学基金资助项目CCF 0634909资助。

以色列特拉维夫大学计算机科学学院，特拉维夫69978。由两国科学基金会、以色列科学基金会和欧洲委员会支持，QAP综合项目由IST管理局资助，合同号为015848。

1987年，施诺尔提出了LLL算法的一个扩展，导致了更好的近似因子[74]。施诺尔算法的主要思想是用更大的块来代替LLL算法的核心，它涉及2times;2个块。以增加运行时间为代价，增加块大小提高了近似因子(即，导致向量更短)。施诺尔的算法(例如，在舒普的NTL包[76])中实现的经常被实验者使用。施诺尔的算法有几个变种，比如伽马和阮最近的算法，它非常自然和优雅。不幸的是，所有这些变量都或多或少地实现了相同的指数近似保证。

如果一个人坚持SVP的精确解，或者甚至仅仅是在多(n)个因子内的近似值，那么最著名的算法的运行时间是[7]。不幸的是，这种算法的空间要求也是指数级的，这使得它基本上不切实际(但是参见[61])，因为最近的实现可以处理高达50的维度)。其他算法只需要多项式空间，但运行时间为20(n log n)(见[31]和[61]中的参考文献)。

以上讨论引出了下面的猜想。

猜想1.1没有多项式时间算法将格问题近似在多项因子内。

不太正式地说，据推测，将格问题近似到多项式因子内是一个困难的问题(也见[73])。正如我们将在后面看到的，许多基于格的密码结构的安全性是基于这个猜想的。作为这一猜想的进一步证据，我们注意到格算法的进展一直非常困难，自20世纪80年代以来性能没有显著提高。这与数论问题形成对比，如因子分解，我们有一些显著的次指数时间算法，如数域筛选[38]。然而，我们应该注意到，除非多项式时间层次瓦解了[37，19，2]；否则将格问题近似为大于 的因子并不是NP难的；格问题的NP-硬度结果仅在非常小的近似因子下才为人所知，例如氮氧比 (见[78、3、12、14、48、33、25]和调查[34])。

当应用于“现实生活”格或从一些自然分布中随机选择的格时，格简化算法的性能往往比最坏情况下的性能稍好。这一现象仍未得到充分解释，但已在许多实验中观察到。在最近的一项这样的研究中(见[16])，伽马和阮用几种格约简算法和格上的几种分布进行了广泛的实验。他们的结论之一是，已知的格约简算法提供了大约delta;n的近似比率，其中n是格的维数，delta;是一个依赖于在算法上。算法在合理的时间内运行所能达到的最佳delta;非常接近1.012 。此外，(1.01)n的近似比似乎超出了已知格约简算法的范围。关于伽马-阮实验的进一步讨论，见第3节。

1.2基于网格的密码术

正如本章开头所提到的，基于格的密码结构为后量子密码学带来了巨大的希望。其中许多相当有效，有些甚至与最著名的替代品竞争；它们通常很容易实现；当然，他们都被认为对量子计算机是安全的(我们将在下一小节详细讨论这个话题)。

就安全性而言，基于格的密码结构可以分为两种类型。第一个包括实际的建议，这些建议通常非常有效，但通常缺乏支持性的安全证据。第二种类型允许基于格问题最坏情况硬度的强可证明安全保证，但是只有少数几个足够有效以用于实践。我们将在这一章中考虑这两种类型，更强调后一种类型。

在本小节的其余部分，我们将详细阐述后一种类型的结构所提供的强大安全保障，即最坏情况下的硬度。这意味着破解密码结构(即使有一些不可忽略的小概率)至少和在最坏的情况下解决几个格问题(大约在多项式因子内)一样难。换句话说，破解密码结构意味着一个有效的算法来解决一些基础格问题的任何实例。在大多数情况下，潜在的问题是将像SVP这样的格问题近似为多项式因子，如上所述，这被推测是一个难题。

这种强大的安全保证是基于格的密码学的显著特征之一。事实上，所有其他加密结构都基于平均大小写硬度。例如，打破基于因式分解的密码系统可能意味着能够对根据某一分布选择的一些数字进行因式分解，但不能对所有数字进行因式分解

最坏情况下安全保障的重要性是双重的。首先，它向我们保证，对密码结构的攻击可能仅对参数的小选择有效，而不是渐近有效。换句话说，它向我们保证在我们的密码结构设计中没有根本的缺陷。事实上，在某些情况下，最坏的安全保证甚至可以指导我们做出设计决策。第二，原则上，最坏情况下的安全保证可以帮助我们选择密码系统的具体参数，尽管在实践中这会导致看起来过于保守的估计，并且正如我们将在后面看到的，人们经常基于最著名的攻击来设置参数。

1.3量子和格

如上所述，格问题通常相当困难。最著名的算法要么以指数时间运行，要么提供相当差的近似比率。基于格的密码学领域是在格问题很难解决的假设下发展起来的。但是基于格的加密技术适合后量子世界吗？格问题对量子计算机来说也很难吗？

对此的简短回答是“可能是的”:目前没有已知的量子算法来解决格问题，这些算法的性能明显优于最著名的经典(即非量子)算法(但见[41])。尽管格问题看起来像是试图用量子算法解决的自然候选:因为它们被认为对于典型的近似因子来说不是NP难的，因为它们的周期结构，并且因为傅立叶变换，在量子算法中被如此成功地使用，与格对偶的概念紧密相关。

自从肖尔在20世纪90年代中期发现量子因子分解算法以来，人们一直在尝试用量子算法来解决格问题，但迄今为止几乎没有成功。主要的困难是用于绍尔因子分解算法和相关量子算法的周期性发现技术似乎不适用于格问题。因此，很自然地要考虑下面的猜想，它证明了在后量子密码术中使用基于格的密码术是正确的:

猜想1.2没有多项式时间量子算法将格问题近似为多项式因子。

然而，上述讨论不应该被解释为说量子算法的出现对我们理解格问题没有影响。虽然目前还不知道格问题的实际量子算法，但是量子算法和格问题之间有一些非常有趣的联系。第一个这样的联系在[70]中得到证明，在那里证明了周期发现问题到非阿贝尔群的某种扩展可以用来给出格问题的量子算法。不幸的是，这种方法到目前为止还没有导致任何有趣的格问题量子算法。

一个可能更有趣的联系是在[71]的基于格的密码系统中使用量子硬度假设。第5.4小节将详细讨论这种密码系统及其应用。现在，我们简要讨论量子算法在那里的使用方式。在那里进行的主要观察是量子算法可以用于解决格问题，尽管有些不自然。考虑以下场景。我们得到了一个能够回答以下类型查询的oracle:在输入一个格L和一个有点接近L的点x时，它输出最接近x的格点。如果x不够接近L，oracle的输出是未定义的。从某种意义上说，这样一个预言似乎相当强大:执行这样一项任务的最著名的算法需要指数时间。然而，经典地看，似乎绝对没有办法用这个oracle做任何“有用”的事情！事实上，似乎生成oracle输入的唯一方法是:以某种方式选择一个格点yisin;L，并让x = y z作为一些小扰动向量z。我们现在可以将x馈送到oracle，因为它靠近格点。但是我们得到的结果，y，是完全无用的，因为我们已经知道了！

事实证明，在量子环境中，这样的预言是非常有用的。事实上，能够从x计算y允许不计算y。更准确地说，它允许以可逆(即酉)方式将量子态|x，ygt;转换为态|x, 0gt;。这种以可逆方式擦除存储单元内容的能力似乎仅在量子设置中有用。通过将此与傅立叶变换一起使用，[71]中展示了如何使用这样的预言，以便在对偶格中找到短格向量。

1.4组织

本章的其余部分组织如下。在第2节中，我们提供了一些关于格的预备知识。在第3节中，我们考虑一个特定的格问题，它是许多基于格的密码结构的核心，并讨论了解决它的最佳算法。当我们为基于网格的结构建议具体参数时，将使用这种方法。接下来的三节讨论三种主要的密码原语:散列函数(第4节)、公钥密码系统(第5节)和数字签名方案(第6节)。第7节提到了其他密码原语的一些最新构造。最后，在第8节中，我们列出了该领域的一些主要未决问题。

2预赛

除非另有说明，否则所有log都以2为基数。我们对向量使用列符号，并使用(x1，....，xn)来表示具有条目x1，....，xn。我们用方括号将矩阵和行向量括起来。

格:格被定义为所有整数组合的集合

n个线性独立向量b1，....，bn in R n (见图1)。向量集b1，....，bn被称为格的基础。基础可以用矩阵B = [b1，....，bn] isin;Rntimes;n有基础向量作为列。使用矩阵符号，矩阵B isin;R ntimes;n生成的格可以定义为L(B) = {Bx: x isin; Z n}，其中Bx是常用的矩阵向量乘法。

不难看出，如果U是单模矩阵(即，具有行列式1的整数平方矩阵)，则基数B和BU产生相同的格。(事实上，当且仅当存在单模矩阵U使得B′= BU时，L(B)= L(B′))特别是，任何格都允许多个基，这一事实是许多密码应用的核心。

格的行列式是基矩阵行列式的绝对值。行列式的值与基的选择无关，在几何上对应于R n中格点密度的倒数。R n中格点L的对偶，用L表示，是由满足hx的所有向量y isin;R n的集合给出的格点，对于所有向量x isin; L，lt;x,ygt; isin; Z。可以看出，对于任何B isin;R ntimes;n，L(B)*= L((B-1)T)。由此得出det(L)= 1/det(L)。

q元格:在基于格的密码学中特别重要的是q元格。这些格满足某些整数q(可能是素数)的qZ n sube; L sube; Z n。换句话说，l中向量x的隶属度由x模q决定。这种格与Z nq中的线性码一一对应。大多数基于格的密码构造使用q元格作为它们的硬平均问题。我们注意到，对于某些q，任何整数格L sube; Z n都是q元格，例如，每当q是行列式det(L)的整数倍时。然而，我们将主要关注q比det(L)小得多的q元格。

给定一些整数q，m，n的矩阵A isin; Z qntimes;m，我们可以定义两个m维q元格，<!--

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 33 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[273104]，资料为PDF文档或Word文档，PDF文档可免费转换为Word