LWE笔记.doc

一、格理论基础1、定义。格是中()个线性无关的向量的所有整系数线性组合，记为：。其中称为格的基，称为格的维数。且当时称其为满秩格。一般只考虑满秩格，因为非满秩格的问题可以转化为满秩格额问题。2、基。同一个格可以有不同的基。和都是格的基，当且仅当存在幺模矩阵，使得。3、近似最短向量问题()：给定格，找一个非零格向量，满足对任意零向量，。4、最近向量问题(Closest Vector Problem (CVP)：给定一个格和目标向量，求距离最近的格向量。5、近似最短向量问题：给定格，一个有理数和一个近似因子，若格中最短向量的长度，回答“是”，若，则回答“否”。其他情况随机返回是或否。6、格基约化算法。目标是找到一组尽量短并且几乎正交的格基。7、格密码学的优点： 安全性可以基于最坏情况的困难性假设？ 貌似可以对抗量子计算机攻击。 效率很高。 目前有些高级应用，如全同态加密等，只有格密码学能够满足要求。8、统计距离。两个离散域上的分布和。定义其统计距离为：。关于统计距离，有两个结论：定理1 如果对于所有的，等式都成立，则和的统计距离最大为。 D. Aldous and P. Diaconis. Strong uniform times and finite random walks. Adv. in Appl. Math.,8(1):6997, 1987. ISSN 0196-8858. doi:10.1016/0196-8858(87)90006-6.定理2 (leftover hash 引理) 设为(实数模1加法群)的阶循环子群。为整数，。以上参数满足。，则如下两个分布和的统计距离最大为。 J. Hastad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from anyone-way function. SIAM J. Comput., 28(4):13641396, 1999.9、归约。一个从问题到问题的归约是一个有效的(多项式时间的)算法，该算法能够保证如果找到一个解决问题的喻示(Oracle)，就可以解决问题。二、LWE问题1、连续型高斯分布密度函数：。若令，记，则有，其中，。离散高斯分布：，。若令，则有：，。2、LWE问题(Regev05)。由Regev于2005年给出了第一个量子规约，证明了该问题的安全性至少与格上（最坏情况下）近似最短向量问题的难度相当。主要有两种描述方式：对，记，。搜索版本：给出任意多抽样，寻找。判断版本：以不可忽略的优势，区分与，或与。即对某个常数，要求优势不小于。任何困难问题的搜索版本比判定版本困难。搜索版本的例子：从下面的近似方程组中，求解，可以要求任意多个方程。矩阵形式：输入矩阵和向量，满足。其中为扰动变量，服从上的某种公开分布，且与均依均匀分布选择。判定版本的LWE问题旨在区分由LWE实例构造的和在中按均匀分布随机选择的。搜索版本的LWE问题要求恢复。特别情况：I 以概率1取0方程变成无误差方程高斯消元法可解(或不可解)II 非常困难III 通常，我们取，其中与为大于0的常数。注：如果为素数，Reg05证明了在搜索版本LWE和判定版本LWE之间存在多项式规约。3、Regev05提出的公钥加密方案，分为以下几个算法：