格密码:傅里叶矩阵

发布时间:2023年12月25日

目录

一. 铺垫性介绍

1.1 傅里叶级数

1.2 傅里叶矩阵的来源

二. 格基与傅里叶矩阵

2.1 傅里叶矩阵详细解释

2.2 格基与傅里叶矩阵


写在前面:有关傅里叶变换的解释太多了,这篇博客主要总结傅里叶矩阵在格密码中的运用。对于有一定傅里叶变换基础的同学,可直接跳转2.2看结论。

一. 铺垫性介绍

1.1 傅里叶级数

傅里叶级数的表达如下:

f(x)=a_0+\sum_{k=1}^\infty (a_kcoskx+b_ksinkx)

傅里叶级数可以看成无限维度的线性代数。这个过程可以看成将函数f(x)投影成很多的sin与cos,与此同时产生傅里叶系数a_kb_k.

反过来,借助无限的sin与cos序列,乘以对应的傅里叶系数,也能够重建原始的函数f(x)。

当然,格密码中我们更加关心有限维度的离散傅里叶变换。

1.2 傅里叶矩阵的来源

将傅里叶级数右边的函数改为输入n个值y_0,\cdots,y_{n-1},由此输出n个值c_0,\cdots,c_{n-1}。这两个向量,y与c之间的关系一定是线性的,数字信号处理过程中也经常会用到此性质。既然是线性关系,那我们可以将其构建为一个矩阵,由此便出现了傅里叶矩阵F。比如,给定输出y有四个值2,4,6,8,求解输入c的本质就是:已知Fc=y,求解c,如下:

c_0+c_1+c_2+c_3=2\\ c_0+ic_1+i^2c_2+i^3c_3=4\\ c_0+i^2c_1+i^4c_2+i^6c_3=6\\ c_0+i^3c_1+i^6c_2+i^9c_3=8

二. 格基与傅里叶矩阵

2.1 傅里叶矩阵详细解释

先从4维的离散傅里叶矩阵(后续记为DFT)F说起:

F=\left[ \begin{array}{cccc} 1 & 1 & 1&1 \\ 1 & i& i^2&i^3\\ 1 & i^2 & i^4&i^6\\ 1&i^3&i^6&i^9 \end{array} \right]

离散傅里叶矩阵的共轭矩阵记为\bar F,熟悉线性代数的都知道,DFT矩阵满足如下:

排除系数4的影响,也就是矩阵乘以本身的共轭矩阵为单位阵,这不就类似正交阵(准确来讲应该叫酉矩阵)。

给定任意的维度n,傅里叶矩阵可以将输入c与输出y联系起来。这个过程可以写成n个线性方程,当然也可以写成离散级数,包含n个傅里叶系数,n个输出点,如下:

c_0+c_1e^{ix}+\cdots

当x取0时,也就是系数全为1,第一个线性方程往往比较简单,如下:

c_0+\cdots+c_{n-1}=y_0

将1的N次方根主值记为\omega,其实就是复数根,以上变换过程推广到n维为:

注意左边第一个矩阵即为傅里叶矩阵。将行数与列数记为从0到n-1,傅里叶矩阵中的元素可以总结为F_{jk}=\omega^{jk}。比如第一行就是j=0,第一列就是k=0,这两个的元素均为\omega^0=1

在利用傅里叶矩阵时,很多时候需要求逆。根据复数的性质,易知:

\frac{1}{i}=-i

我们知道\omega的角度为+2\pi/n,w^{-1}的角度为-2\pi/n,类似如下:

也就是可以得出:

\omega^{-1}=\bar w

也就是傅里叶矩阵的逆长这个样子:

第一个等号代表,傅里叶矩阵的逆。第二个等号代表逆矩阵与共轭矩阵的关系。

如果用3维举例子的话,三维的傅里叶矩阵如下:

三维的逆傅里叶矩阵如下:

F的第j行,F^{-1}的第j列,相乘计算:

\frac{1+1+\cdots+1}{n}=1

其实就是单位阵的对角线元素。

F的第j行乘以F^{-1}的第k列,计算:

1\cdot 1+\omega^j\omega^{-k}+\omega^{2j}\omega^{-2k}+\cdots+\omega^{(n-1)j}\omega^{-(n-1)k}=0\quad j\neq k

除了对角线元素,其他位置均为0(单位阵)。

如果我们将W=\omega^j\omega^{-k},以上方程即可改写为:

1+W+W^2+\cdots+W^{n-1}=0

因为\omega^n=1,W满足如下:

W^n=\omega^{nj}\omega^{-nk}=1^j1^{-k}=1

也就是W也为1的单位根。

2.2 格基与傅里叶矩阵

格基的本质是一个矩阵,通常格点为实数的向量点。如果将其推广到复数域,格基B也可以取复数。

根据以上讨论,傅里叶矩阵:

  1. N维方阵;
  2. 对称矩阵(关于对角线);
  3. 正交阵(注意差N倍系数,严格叫酉矩阵);

已经出现论文讨论将傅里叶矩阵作为格基,之所以这样是有如下好处:

  1. 格基为正交阵,格基良好,可解决很多格上困难问题(CVP,LWE等);
  2. 逆矩阵容易求,很容易导出对偶格;

格密码中很多时候需要利用“环版本”,比如RLWE或者Ring-SIS问题。一个环元素本质是一个多项式,两个多项式相乘的计算复杂度为n^2,但如果借助快速傅里叶变换(FFT),其复杂度可以降低到O(nlogn)

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