格(Lattice)学习笔记之一:历史与基本概念

本文作者东泽,来自安比技术社区的小伙伴,目前就读于斯坦福大学,研究方向密码学。

Lattice的历史

Lattice(格)在很早以前就被各大数学家研究了一遍。代表人物有Lagrange,Gauss和Minkowski等等。最近的几十年内,Lattice在密码学、通讯、密码分析上有了很大的应用价值,是非常火的一个领域。

近代Lattice时间线:

  • 1982:LLL basis reduction theorem

    • 使用Lattice来做Cryptanalysis
  • 1996:Ajtai-Dwork

    • 第一次把Lattice中Average-case与Worst-case的复杂度问题关联起来
    • 提出了使用Lattice构造的One-way Function与CRHF(Collision Resistant Hash Function)
  • 2002:找到了Average-case/worst-case复杂度之间的关系,基于Lattice的协议变得更加高效

  • 2005:Regev提出了LWE,并且发现其量子抵抗性

    • 提出PKE,IBE,ABE,FHE等等的可能性

Lattice是什么

Lattice与Bases(格与基)

如果系统性的定义一下Lattice的话,那么我们可以说Lattice是这个空间中的一个离散的、具有加法运算的子群(A discrete additive subgroup)。

Lattice的基本属性

Lattice的密度

最短距离

距离函数(Distance Function)与覆盖半径(Covering Radius)

直到所有的圆正好完美的覆盖了所有的空间的时候,这个时候的半径,就是我们之前得到的了。这就是覆盖半径这一名字的由来。

Lattice的Smoothing

Minkowski凸集定理(Convex body theorem)

Minkowski第二定理