张明军，杨思华，姚 兵

1.兰州财经大学 中国西北金融研究中心，兰州730020

2.兰州财经大学 信息工程学院，兰州730020

3.甘肃省电子商务技术与应用重点实验室，兰州730020

4.西北师范大学 数学与统计学院，兰州730070

1 研究背景及预备知识

1.1 格密码

研究发现，格（lattice）理论在密码分析和设计中有着广泛的应用，由于格上的运算大多是线性运算，基于格理论的格密码是一类抗量子计算攻击的公钥密码体制[1]。因此，利用格理论所构建的新型公钥密码体质比现有方案运算速度更快[2]。清华大学的密码专家王小云等人在文献[2]中总结到：（1）格密码学（lattice cryptology）的学科交叉所带来的许多数学问题不仅成为密码领域重点研究的内容，也被数学领域与计算机科学领域所关注。（2）格密码体制（lattice cryptosystem）的体制安全性基于NP-Hard、NP-C 问题，目前还不存在解决某些格困难问题的多项式量子算法，使得格密码体制成为抗量子攻击的密码体制中最核心研究领域。（3）由于格运算具有同态（homomorphism）特性，因此设计格同态加密密码体制对于解决安全云计算环境下的密文检索、加密数据处理等方面具有潜在的应用价值。

一个格是m维欧式空间Rm的n(m≥n)个线性无关向量组的所有整系数线性组合，即：

称B为格基（lattice base），m称为格的维数，n称为格的秩，且满足m=n的格称为满秩的。格是欧式空间Rm中一类具有周期性结构离散点的集合，同一个格可以用不同的格基表示。为防止混淆，以下称式（1）中的格L(B) 为传统格（traditional lattice）。当格基B中每个向量的分量为非负整数，每个系数xi为非负整数时，得到非负整数传统格，特记为L(Z0B)。……