• 【格密码基础】详解ZSVP问题

    目录

    一. 引入

    二. ZSVP问题的定义

    三. 对ZSVP问题的理解

    四. 与ZSVP问题相关的归约

    写在最后

    一. 引入

    我们知道最简单的n维格就是整数格Z^n，这个格的格基就是单位阵。

    在格密码领域，我们也都认为整数格最简单，为啥这样讲呢？

    格Z^n中最短的非零向量就是标准的格向量\pm e_1,\cdots,\pm e_n，每个向量的长度都是1.想想就开心，这相当于我们解决了这个格上的SVP问题。

    备注：SVP:Shortest Vector Problem

    很明显在整数格Z^n其他所有计算性格基本问题都会变得很简单。但，如果现在我们把问题难度提升一点，先看一个格基B：

    我的问题是请找出该格上最短的非零向量？

    很明显，这是一个四维的格。好像问题还不是很容易解决。

    那如果我接着补充，这个格其实是将整数格Z^n进行旋转得到的。所谓旋转其实就是使用了一个n维的正交矩阵（orthogonal matrix）R，记为：

    R\in O_n(R)

    旋转后的格可以记为：

    RZ^n

    我们知道旋转是不改变向量的长度的，那么在这个旋转格上，最短的非零向量长度肯定还是1，但具体是哪个向量就没那么好找了。

    先公布前面那个问题的答案，将最短的非零格向量记为BZ，其中向量Z其实是：

    Z=(59,396,225,-326)^T

    其中T代表转置。

    我们今天就是尝试分析，在旋转格上找出最短的非零向量。

    二. ZSVP问题的定义

    先给一个方便理解的定义。

    首先第一步对整数格Z^n进行旋转；

    怎么旋转是未知的。接着第二步在旋转后的格上寻找最短的非零向量。

    这个定义已经很好理解了，再给一个官方定义吧。

    Given a basis for L, find a shortest non-zero vector in the rotation L of Z^n。

    三. 对ZSVP问题的理解

    在格密码学界，是否存在一个多项式时间算法来解决ZSVP目前还是一个开放性问题。

    polynomial-time algorithm： 多项式时间算法  

    open question：开放性问题

    接着回忆起来，我们知道最原始的SVP问题肯定是NP-困难的。所以解决SVP问题目前最快的算法，其时间复杂度为：

    2^{n+o(n)}

    当然，从定义来看ZSVP问题还是有点特殊的。所以，不难看出ZSVP问题肯定要比SVP问题简单那么一丢丢。已有的研究表明，目前最快解决ZSVP问题的算法，其计算复杂度为：

    2^{\frac{n}{2}+o(n)}

    两个一对比就看出来，不管SVP还是ZSVP都挺难的。

    我们知道在格密码领域，解决困难问题的第一步通常都是格基约化算法。比如把刚才那个格基约化得“好看”一点。

    格基约化算法本质是将格基变得更加正交，对整个格进行旋转是不影响格基的正交性质。所以在实际算法分析中，对格Z^n或格RZ^n进行格基约化是等效的。也就是论文中最喜欢用的“rotation invariant”。研究表明BKZ算法非常好用。

    格密码之所以这么引入注意，其中一个原因就是它可以实现最坏情况到一般情况的归约：

    worst case to average case

    （这里先挖个坑吧，以后有时间再补上）

    易得，ZSVP跟SVP类似，都是最坏情况下的格困难问题。

    ZSVP问题虽然不知道最短的非零向量到底是哪一个，但其长度肯定是1.那么有没有什么算法可以用来攻击ZSVP问题呢？

    启发式的筛法（sieve）是最直接用来攻击ZSVP问题的，其中比较好用的就是Gauss筛法了。

    如果旋转角度比较特殊的话，比如90度，很明显ZSVP问题就会变得很简单，也就当然存在多项式时间算法了。

    四. 与ZSVP问题相关的归约

    论文[Szy03]近似解决ZSVP问题的方法是找到了一大堆长度为c\sqrt n的格向量，其中c为常数。

    这个方法的本质就是实现了ZSVP问题到c\sqrt n- SVP问题的归约，其中c\sqrt n- SVP为近似（approximate）SVP问题。

    [Szy03] Michael Szydlo. Hypercubic lattice reduction and analysis of GGH and NTRU signatures. InEUROCRYPT, 2003. 1, 4

    但目前大多用的还是从ZSVP到\gamma-uSVP的归约。其中\gamma为近似系数，通常会影响到归约的时间复杂度，也就是：

    (\frac{n}{\gamma^2})^{\gamma^2}\quad \gamma\leq \frac{\sqrt n}{2}

    以上所提到的ZSVP，SVP和uSVP问题都是格基本问题的search版本。另外，GapSVP问题是decision版本。

    在这些归约中，格稀疏化算法都非常好用（sparsification based reduction）。

    写在最后

    本文章的核心内容主要参考2023年密码学顶会欧密论文：

    Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N. (2023). Just How Hard Are Rotations of \mathbb {Z}^n? Algorithms and Cryptography with the Simplest Lattice. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14008. Springer, Cham. https://doi.org/10.1007/978-3-031-30589-4_9

  • 相关阅读:
    手写 Promise（2）实例方法与静态方法的实现
    【React-Router】路由导航
    软件测试|MySQL WHERE条件查询详解：筛选出需要的数据
    百乐钢笔维修（官方售后，全流程）
    深度学习：YOLO环境搭建
    【LeetCode 力扣】1.两数之和 Java实现 哈希表
    C#中关于 object,dynamic 一点使用心得
    揭秘源代码加密方案，完美支持Jenkins代码自动化部署发布
    BiConsumer的使用
    代码随想录第43天|416. 分割等和子集，1049. 最后一块石头的重量 II， ​494.目标和，​ 474.一和零（一窍不通）
  • 原文地址：https://blog.csdn.net/forest_LL/article/details/140363510