深入浅出格密码理论（五）｜基于SIS的OWF

图片来自于Daniele Micciancio的讲座ppt。

1

CVP与对偶格

在开始详细学习SIS之前，不妨再来重新回顾一下CVP问题。

2

CVP构造的One-way Function

知道了CVP问题可以被转化为在一个Lattice的基础空间（即Determinant构成的空间）中搜索一个短向量e之后，我们可以根据短向量的和Lattice的基础空间（即Determinant组成的空间），尝试构造出如下的OWF。

更多关于单向函数（One-way Function）的定义和安全性可以参见密码学基础｜单向函数 (One-way Function)。

3

Ajtai提出的OWF：SIS问题

上文提出的OWF构造的精髓我们其实已经get到了：我们把一个短向量映射到格当中，然后这个映射可以被看作是一个单向的映射，因为很难通过映射本身来找回原始的输入值。但是我们之前看到的体系是基于几何意义上的OWF，在计算机系统中很难被有效的运用。

1996年，密码学家Ajtai基于这一思路，提出了在整数格中实现的OWF，即SIS问题（Short Integer Solution）。在前面的笔记中对于SIS已经有所介绍了，我们这里再稍微回顾一下，详情可见深入浅出格密码理论（二）｜格密码中的困难问题。

4

SIS的单向性证明

5

SIS的Collision Resistance证明

来源：https://zhuanlan.zhihu.com/p/163168725

作者：Steven Yue

分享仅供学习参考，若有不当，请联系我们处理。

END

热文推荐