格密码培训 王鲲鹏 04 平均困难性

信息安全国家重点实验室王鲲鹏格理论与密码学平均困难性Copyrightby©kpwangkpwang@is.ac.cn平均困难性Copyrightby©kpwangkpwang@is.ac.cnSIVP 线性无关 Copyrightby©kpwangkpwang@is.ac.cnSIVP>SVP.n然后用用转移定理！Copyrightby©kpwangkpwang@is.ac.cn抗碰撞函数族定义2.抗碰撞函数族是一个序列，其元素是函数族，其中的函数满足以下条件 对任意的，从中多项式时间可抽样； 任意函数多项式时间可计算； 对任意的，没有多项式时间算法以至少的概率给出，符合使得。Copyrightby©kpwangkpwang@is.ac.cnCRHF定义2.对任意的，定义函数如下定义函数族为全体，其中Copyrightby©kpwangkpwang@is.ac.cnGauss分布Copyrightby©kpwangkpwang@is.ac.cnCopyrightby©kpwangkpwang@is.ac.cn摞起来的高斯分布差不多就是一致分布引理5.设是以为基的格，则上一致分布和Gauss分布模后得到的分布之间的统计距离小于Copyrightby©kpwangkpwang@is.ac.cn考虑上的两个分布函数由Poisson求和公式有故而Copyrightby©kpwangkpwang@is.ac.cn光滑参数定义6.对任意的，格的光滑参数定义为使得成立的最小Copyrightby©kpwangkpwang@is.ac.cn的光滑参数是使最小的Copyrightby©kpwangkpwang@is.ac.cn对任意，有对任意，有Copyrightby©kpwangkpwang@is.ac.cn对任意对任意Copyrightby©kpwangkpwang@is.ac.cnSIVP<CRHF定理4.假定存在多项式时间算法：以概率解决此问题，则有多项式时间算法解决问题Copyrightby©kpwangkpwang@is.ac.cn输入:格Λ的LLL基B，及满足的输出:格Λ的一个短向量，或者FAIL1.Fori=1；i<m;i++1.1从方差为的高斯分布中选取xi；1.2令；1.3把基本区域按照每个基向量都等分成q份，共有qn个小n维立体，每个立体用{0..q1}n中向量自然编码。设yi所在的立体的编码为ai，其左下角元素为zi。2.3.输出Copyrightby©kpwangkpwang@is.ac.cn(0,0)(0,1)(0,2)(0,3)(1,0)(1,3)(2,0)(2,1)(2,2)(2,3)(3,0)(3,1)(3,2)(3,3)Copyrightby©kpwangkpwang@is.ac.cnCopyrightby©kpwangkpwang@is.ac.cnCopyrightby©kpwangkpwang@is.ac.cnx1x2x3高斯抽样的结果Copyrightby©kpwangkpwang@is.ac.cnx1x2x3x1+x2+x3比较近的格点，但怎么找？x4Copyrightby©kpwangkpwang@is.ac.cnx1x2x3y1y3y2a4=(0,0)a2=(0,1)a1=(1,1)a3=(0,1)x4y4Copyrightby©kpwangkpwang@is.ac.cna1,a2,a3,a41,1,1,0a1+a2+a30(modq)Copyrightby©kpwangkpwang@is.ac.cnx1x2x3x1+x2+x3y1y3y2z2z1z3a2=(0,1)a1=(1,1)a3=(0,1)Copyrightby©kpwangkpwang@is.ac.cnx1x2x3x1+x2+x3y1y3y2z2z1z3a2=(0,1)a1=(1,1)a3=(0,1)Copyrightby©kpwangkpwang@is.ac.cnx1x2x3x1+x2+x3y1y3y2z2z1z3a2=(0,1)a1=(1,1)a3=(0,1)目标点Copyrightby©kpwangkpwang@is.ac.cn的性质 成功的时候输出的向量以很大的概率长度小于 成功的概率大于 输出是全维度的Copyrightby©kpwangkpwang@is.ac.cn输出格点断言11.成功时输出的是格点证明：算法成功时输出地是其中是格点；另外由于是个整向量，因此也是个格点Copyrightby©kpwangkpwang@is.ac.cn输出短向量断言12.则算法输出长度的向量的概率小于证明：Copyrightby©kpwangkpwang@is.ac.cn成功概率断言13.如果，则算法成功的概率至少是证明：Copyrightby©kpwangkpwang@is.ac.cn全维度输出断言14.对于，对任意的，以及任意的n–1维超平面H，都有