格密码:离散高斯与子高斯分布

2023-12-18 06:41:54

高斯分布我们都很熟悉,但在格密码中会用到一种特殊的高斯分布,将其取名离散高斯分布(discrete Gaussian)。

一. N维连续高斯分布

给定一个正整数n,代表维度。一个正实数s>0,代表标准差(高斯分布的标准差决定着图像的胖瘦,所以这个参数有的时候也叫“宽度”)。N维连续高斯分布的输入是N维向量,输出是一个正实数,也就是\rho_s:R^n\to R^+,概率密度函数如下:

\rho_s(x)=exp(-\pi ||x||^2/s^2)

可以想到,如果把||x||/s看成一个整体的话,新的高斯分布的标准差则为1,如下:

\rho_s(x)=\rho(x/s)

写成N个维度的话,可得:

\rho_s(x)=\prod_{i=1}^n\rho_s(x_i)

这个公式成立的前提是高斯分布不同维度上的标准差要求一样。这也就是所谓的\rho_s(x)R^n上抗旋转(\rho_s?is invariant under rotations of R^n)。

格密码偶尔会用到一个很有意思的现象:当选择合适的归一化因子时,高斯分布的傅里叶变换是其本身。

二. 离散高斯分布

先提一句,离散高斯是格密码中才会出现的概率。另外,补充一个重要的高斯积分结论,如下:

\int_{R^n}\rho_s(z)dz=s^n

先引出一个新的高斯分布通常写作D_s,概率密度函数与原始的\rho_s成正比,如下:

f(x)=\rho_s(x)/\int_{R^n}\rho_s(z)dz=\rho_s(x)/s^n

格陪集(lattice coset)c+L\subset R^n(其实就是把格L进行平移c),如果将以上f(x)中的x改为格点的话,便得到了对应的离散高斯分布,如下:

D_{c+L,s}(x)=\left\{ \begin{aligned} \rho_s(x) \quad if \ x\in c+L\\ 0 \quad otherwise\\ \end{aligned} \right .

这一段话可能有些官方,简单对这个概念谈谈自己的理解。离散高斯分布的输入是一个一个点,直观上就是把高斯分布的函数图像,抠成一个一个点,但是整体趋势还是高斯分布。这种离散的点,就可以直接套用格点,带进去所得到的函数值能直观反映取这个点对应的概率大小。

三. 光滑参数

谈格上高斯分布,不得不说光滑参数(smoothing parameter)。

我们知道,“格”是一个一个孤立的点,重点强调是离散的。那我们在想,能不能同时对这些格点加一个小小的扰动,神奇的化离散为连续呢?更进一步,如果加的扰动是一个高斯分布,那对这个高斯分布要啥要求呢?

可以想到,如果高斯分布的方差越大,那么它就越接近一个均匀分布,这种效果就越好。

将刚才谈到的格陪集c+L全部带入高斯分布,可以得到求和(gaussian mass),如:

\rho_s(c+L)=\sum_{x\in c+L}\rho_s(x)

光滑参数其实是定义在对偶格上的,满足下列不等式最小的s即为光滑参数的值:

\rho_{1/s}(L^*)\leq 1+\epsilon

可以看到右边有个参数\epsilon,所以光滑参数通常记作\eta_{\epsilon}(L)。这个\epsilon在格密码中通常是很小的值,也就是计算复杂性通常所说的可忽略函数,比如n^{-\omega(1)},其中n可以看成格的维度。

光滑参数在格上,本质就是一个数,那这个数有多大呢?

光滑参数的上限与对偶格最短的向量长度相关,请看一个定理。

定理1

对任意的满秩格L\subset R^n,都有\eta_{2^{-n}}(L)\leq \sqrt{n}/\lambda_1(L^*)

可以看到这个定理中的\epsilon就是取2^{-n},这个值是很小的。

怎么老谈对偶格,弄得很玄幻。当然,其实也有直接定义在原始格上光滑参数的结论。

对任意格的格基可以进行高斯-斯密斯(Gram-Schmidt)正交化,来让格基更加“漂亮”。格基记为B=\lbrace b_i\rbrace,正交化后记为\tilde B=\lbrace \tilde b_i\rbrace。格基正交化后的长度满足如下性质:

min_\lbrace {basis\ \tilde B\ of\ L}\rbrace \leq \lambda_n(L)

现在来看另一个定理

定理2

对任意的满秩格L\subset R^n,以及\epsilon \in (0,1/2),格的光滑参数有上界结论:

\eta_\epsilon(L)\leq min ||\tilde B||\cdot \sqrt{log\ O(n/\epsilon)}\leq \lambda_n(L)\cdot \sqrt{log\ O(n/\epsilon)}

回到主题,也就是光滑参数可以让离散的分布看起来像连续分布。也就是当高斯分布的标准差满足s\geq \eta(L)时,离散高斯分布D_{c+L,s}就跟连续高斯分布很像。这个很想指的是分布的矩(moments)和尾数(tails)很像(这两个概念是统计学的专有名词)。

另外,统计独立的离散高斯分布的和依旧为离散的高斯分布。

四. 子高斯分布

这个概念也经常出现在格密码中,尤其是在一些困难问题的规约证明中很常见。

先谈正式的定义。给定一个参数s,以及实数t\geq 0,满足如下不等式的变量X就可以称之为子高斯分布:

Pr[|X|>t]\leq 2exp(-\pi t^2/s^2)

这个定义想说,一个变量大于一个数所得到的概率与高斯分布有关,英文一些文献可能会这样表达"a random variable is subgaussian if it is dominated by a Gaussian”。

注意这个地方的x也是一个n维的向量,实际上,对任意的单位向量u\in R^n,如果x为子高斯分布,那么\left \langle x,u\right\rangle也为子高斯分布。

子高斯分布的理解还太粗糙,后期会补上的。

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