《A Gentle Introduction to Lattice-Based Cryptography》格密码学温和入门是密码学界知名学者、滑铁卢大学University of Waterloo教授Alfred Menezes编写的一份高质量开源讲义。这份讲义专门为高年级本科生和初入学的研究生设计旨在用最通俗易懂、循序渐进的方式揭开后量子密码学Post-Quantum Cryptography, PQC中“格密码”的神秘面纱。目录3.1 问题陈述3.2 SIS 格3.3 SIS 的困难性 (Hardness of SIS)3.3.1 对 的对偶攻击3.3.2 SIS 的平均情况困难性3.1 问题陈述符号说明是一个质数是模的整数集是分量属于的长度为的列向量集是输入项属于的矩阵集而则表示所有分量均为区间内整数的长度为的列向量集。也就是说这里面所有的数字只要超过了就要执行“除以取余数”的操作。在这个世界里数字不会无限变大它们被限制在到的时钟循环里。这是一个列向量集合。它的长度维度是。这个向量里面的每一个数字分量都必须是前面提到的里面的成员即到之间的整数。矩阵里的每一个格子元素同样都必须是里面的成员。SIS问题由四个数值参数化正整数和且满足一个质数模数以及一个满足且的边界值。定义3.1短整数解问题Short Integer Solution记作其定义如下给定一个均匀随机生成的矩阵寻找一个非零向量使得且参见图 3.1。的意思是矩阵是从集合中均匀随机选取也就是公式中R的意思出来的。图 3.1SIS 问题矩阵必须是“矮胖”的并且“短整数解”一定存在可以通过鸽巢原理证明。示例 3.2SIS 实例设且。考虑以下 SIS 实例我们需要寻找一个非零向量使得。对矩阵在模 13 意义下进行高斯消元法可以得到最简行阶梯矩阵的每一行分别提供了一个方程因此的通解为其中。在空间的个通解当中存在 4 个符合条件的SIS 解通过试错法很容易找到示例3.3密码学哈希函数设且满足。定义哈希函数为在假设难以解决的前提下该函数是抗碰撞的collision resistant。输入。这是一个长度为的向量里面的数字只能是或。所以输入的总可能性有种。输出。这是一个长度为的向量里面的数字在到之间。输出的总可能性有种。因为所以输入的可能空间鸽子远大于输出的可能空间鸽巢数据确实被“压缩”了因此必然存在不同的输入映射到相同的输出即必然存在碰撞。虽然理论上有碰撞但在实际中任何攻击者想用计算机把这个碰撞找出来在计算上是不可能的。只要问题在现实中足够难那么这个哈希函数在现实中就绝对不可能被找出碰撞。定义3.4非齐次短整数解问题Inhomogeneous Short Integer Solution记作其定义如下给定均匀随机生成的矩阵和向量寻找一个向量使得且。此处满足。SIS 是“齐次”的方程的形式是。等号右边是零。ISIS 是“非齐次”的方程的形式是。等号右边是一个随机给定的目标向量。定理3.5SIS 问题与 ISIS 问题在计算上是等价的computationally equivalent计算等价Computationally Equivalent”是一个非常强力的结论。这意味着这两个问题在本质上是同等困难的。定义3.6标准形式的非齐次短整数解问题normal-form ISIS记作其定义如下给定均匀随机生成的矩阵和向量寻找一个向量使得且。在此处是的单位矩阵且满足。3.2 SIS 格定义3.7给定一个的实例矩阵其关联的 SIS 晶格SIS lattice定义为定理3.8设是一个秩rank为的自由阿贝尔群其-基为并设是的一个秩为的子群其-基为。对于每个设其中。那么商群quotient group是有限的且其阶元素个数为。自由阿贝尔群其实就是“格”的代数代名词。大格子我们可以把它看作一个稀疏程度为基础的格点阵。小格子它是的子群意味着它是从大格子里面挑选出一部分点构成的“更稀疏”的格子。过渡矩阵就是用大格子的基底来表达小格子的基底。商群的几何意义商群的阶在几何上代表大格子在小格子的“基本并胞Fundamental Domain”内部所包含的格点数量。这个点的数量刚好等于过渡矩阵的行列式的绝对值。定理 3.9SIS 晶格是一个满秩整数格full-rank integer lattice其体积volume为。定理 3.10假设矩阵的前列在模剩余系上是线性独立的。那么可以通过在上的行初等变换行化简化为如下形式其中。在这种情况下矩阵是 SIS 格的一个基矩阵Basis Matrix。3.3 SIS 的困难性 (Hardness of SIS)定义 3.11短整数解问题定义如下。给定一个均匀随机选取的矩阵寻找一个向量满足且该向量位于 SIS 格中其中是式 (10) 中定义的基矩阵。定义 3.12问题定义如下。给定一个均匀随机选取的矩阵寻找一个位于格中的向量使得。定义 3.11寻找一个落在以原点为中心、边长为的超正方体Hypercube内的非零格点。定义 3.12寻找一个落在以原点为中心、半径为的超球体Hypersphere内的非零格点。问题的输入。这是一个随机生成的矩阵用来作为这个格的“公开钥匙”或系统参数。这等价于方程。它要求向量必须在这个特定格的交点上。3.3.1 对的对偶攻击回想一下SIS 格的秩维数为体积行列式为。根据闵可夫斯基定理Minkowskis Theorem定理 2.14中最短非零向量的长度满足因此我们在此后假设边界满足这保证了问题必然存在解。根据高斯启发式Gaussian heuristic式 (8)人们期望最短非零向量的长度大约为令表示的解边界与高斯启发式预测的最短长度之间的比值即通过这种表示方法问题可以被看作是格上近似因子为的近似最短向量问题的一个实例。这种将规约降低为实例的策略被称为对偶攻击Dual attack。第 10.2 节中给出了一个具体示例。3.3.2 SIS 的平均情况困难性推测 SIS 在最坏情况worst case下是困难的这是很自然的。然而在加密应用中一个 SIS 实例是通过均匀随机选择一个矩阵来生成的。因此密码学所需要的不仅仅是最坏情况下的困难性而是要保证 SIS 总是困难的除去可以忽略不计的极小概率。换句话说我们需要 SIS 在平均情况on average下是困难的。关于 SIS 的另一个担忧是其对应的近似最短向量问题approx-SVP实例具有相当显着的结构。具体来说SIS 格允许一个如式 (10) 所示的特殊形式的基矩阵该矩阵是上三角的其左上对角块为右下对角块为。因此人们可能会担心即使 approx-SVP 在通常情况下是困难的但在由 SIS 实例产生的这种具有特定结构的受限格家族上它可能会变得明显更容易解决。阿杰泰Ajtai证明了在标准复杂度理论假设下SIS 在平均情况下是困难的。图 3.2证明 SIS 的平均情况难度Ajtai 的规约在技术上非常复杂超出了本入门教程的讨论范围。在非常宏观的层面上如图 3.2 所示该规约从一个具有基底的任意维格开始并高效地生成一个随机的 SIS短整数解问题实例。随后该 SIS 实例的解可以被高效地转化为由生成的格中 近似-SIVP最短独立向量问题的解。因此一个能够解决平均情况下的 SIS 的高效算法将意味着存在一个能够解决最坏情况下的 近似-SIVP 的高效算法。