格密码基础:SIS问题的困难性

发布时间:2024年01月15日

目录

一. SIS问题的困难性

二. SIS问题归约的性质

2.1 2004年 [MR04]

2.2 2008年 【GPV08】

2.3 2013年【MP13】

三. 归约证明

3.1 核心理解

3.2 归约步骤

3.3 性质理解


一. SIS问题的困难性

推荐先阅读:

格密码基础:SIS问题的定义与理解-CSDN博客

借鉴1996年Ajtai的工作,大量的工作开始研究最坏情况下的SIS问题的困难性。SIS问题中一共有四个参数n,q,\beta,m,需要满足如下:

m=poly(n)\quad \beta>0\quad q>\beta\cdot poly(n)

如果能以不可忽略的概率解决SIS问题,那么就可以在随机的n维格上,解决近似GapSVP和SIVP问题。此处的近似因子取值为:

\gamma=\beta\cdot poly(n)

GapSVP:decisional approximate shortest vector problem,判定性近似最短向量问题

SIVP: approximate shortest indenpendent vectors problem

需要注意的是m和q的值会极大影响SIS问题的困难性,而且根据归约准则,当范数上限\beta值越大时,GapSVP和SIVP问题的近似因子也会变大。整个多项式时间复杂度的归约分成两步:

  1. 假设存在一个oracle可以解决SIS问题
  2. 利用此oracle尝试在任意n维格上解决近似的GapSVP和SIVP问题

二. SIS问题归约的性质

理论上,我们希望归约时的模q和近似因子(approximation factor)\gamma越小越好,因为这样可以产生更小的实例(instance)和密码学的公私钥,以及更强的网络安全性保证。接下来,我们来看几个SIS问题归约时重要的发展历程:

2.1 2004年 [MR04]

在2004年,Micciancio 和?Regev引入了格上高斯分布和调和分析(harmonic analysis),从而导出了格密码中重要的概念,叫做光滑参数(smoothing parameter),写做:

\eta(L)

如果在格点周围外加一个噪声,该噪声分布服从高斯分布。当分布的方差大于格的光滑参数时,离散的格点就可以变成连续的均匀分布。对于光滑参数有一种直观的形式化语言,如下:

The amount of Gaussian error needed to “smooth out” the discrete structure of a lattice.

借助此理论便可以产生均匀且随机的SIS实例,从而对任意输入的格均满足推论。在此论文中,近似因子的取值为:

\gamma=\beta\cdot \tilde O(\sqrt n)

当选择合适的\beta值时,近似因子可取:

\gamma=\tilde O(n)

此时模q可取:

q=\beta\cdot \tilde O(n\sqrt m)

可以看到以上两者的取值都相对较小。

2.2 2008年 【GPV08】

在2008年,Gentry, Peikert 和Vaikuntanathan将模数q的值优化到:

q=\beta\cdot \tilde O(\sqrt n)

此时的近似因子与2004年的工作类似:

\gamma=\beta\cdot \tilde O(\sqrt n)

此论文创新性提出了离散高斯分布(discrete Gaussian),待会我们会简单分析此理论。

2.3 2013年【MP13】

在2013年,Micciancio 和?Peikert将模数q优化到:

q=\beta\cdot n^\epsilon

其中\epsilon为大于0的常数。

如果把n^\epsilon看成固定的常数的话,此时的q已经是最优的了。因为SIS问题中,总存在平凡解就是q。

借助卷积引理(convolution lemma),在利用SIS的oracle进行归约时,此理论需要使用到l_\infty范数,而不是常规的l_2范数。

三. 归约证明

SIS问题的困难性涉及到最坏情况和平均情况(worst case/average case)的归约证明。该归约的思路:给定任意n维格L的格基B,已知一个平均情况的SIS的oracle,目标是解决SIVP问题。

在这里简单解释下近似的SIVP问题:

给定近似因子\gamma=poly(n),尝试找出n个线性独立的格向量,它们的长度都小于:

\gamma\cdot \lambda_n(L)

3.1 核心理解

首先输入格基B,从此格中随机选择一部分独立的格向量S,也就是:

S\subseteq L

将此处的S看成一个矩阵。接着利用SIS oracle不断对该矩阵进行归约运算,使其长度至少缩短一半以上,也就是:

||S'||\leq \frac{||S||}{2}

备注:此处矩阵的长度代表其中最长向量的长度,也就是:

||X||=max_i||x_i||\quad X=\lbrace x_i\rbrace

不断迭代重复,直到最终的结果符合SIVP问题的要求。

3.2 归约步骤

第一步:取样

借助格L上的离散高斯分布,采样出m个随机的格点,形成集合S,也就是:

v_i\in L

这些初始向量不会太长。接着将这m个向量形成矩阵V

第二步:形成SIS oracle的输入

运算得到:

a_i=B^{-1}v_i\quad mod\ qZ^n

重复运算m次,由此可得:

A=B^{-1}V\quad mod\ qZ^{n\times m}

需要注意的是,因为v_i是格点,所以B^{-1}v_i一定是整数的。

接着从此时的矩阵A输入到SIS的oracle中。

第三步:运算

SIS的oracle会输出一个解,也就是:

z\in Z^m

那么可得:

v=Vz/q

很明显发现此时的向量长度在变小。

3.3 性质理解

(1)SIS oracle分析

根据以上归约过程,给定一个矩阵A,z为其SIS问题的答案。因为v_i是格点,所以可得:

v_i=Ba_i\quad mod\ qL

由此可运算:

所以可得以下运算出的v为L格点:

v=Vz/q\in L

SIS求解出的z长度是有上限的,也就是:

||z||\leq \beta

在产生向量v时,使其满足:

||v_i||\leq ||S||\cdot poly(n)

两者结合可得:

||Vz||\leq ||S||\cdot \beta\cdot poly(n)

当我们选择模数q如下:

q=\beta\cdot poly(n)

即可以得到:

||v||=||Vz||/q\leq ||S||/2

第一轮迭代完成。

(2)矩阵A均匀分布

借助光滑参数,v_i在一定条件下均匀分布:

\gamma\geq \beta\cdot poly(n)\geq q

也就是:

v_i\quad mod\ qL\quad L/qL

此处说明v在模qL上为均匀分布,再根据:

a_i=B^{-1}v_i

B是确定的,也就是a和v之间是双射运算,所以可得矩阵A也是均匀分布(严格来讲应该是跟均匀分布不可区分)。

文章来源:https://blog.csdn.net/forest_LL/article/details/135588231
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。