格密码：隐藏超平面问题与uSVP问题 (Ajtai密码）

一. 技术发展

二. 隐藏超平面问题（hidden hyperplanes problem,HHP）

三. 唯一最短向量问题，unique shortest vector problem，uSVP

四. Ajtai-Dwork密码系统（改进版）

4.1 公钥

4.2 私钥

4.3 加密过程

4.4 解密过程

4.5 总结

一. 技术发展

一个密码系统需要依赖困难问题。如果需要精心设计参数，让问题最难才能变成密码系统的话，我们会觉得很麻烦。能不能一般困难问题也能实现安全呢？

这就是所谓的worst case与average case之间的归约。格密码中，Ajtai在1996年第一次实现了这种归约，基于此就可以实现密码学中要求的安全性归约证明。借此，Ajtai设计出了第一个密码学想要的单向陷门函数。

Ajtai提出了所谓的隐藏超平面问题（hidden hyperplanes problem,HHP），后续人们发展这个问题的本质就是平均情况下的SIS问题(short integer solution)。

同年，1997年Ajtai和Dwork设计出了一个基于格的公钥密码方案，当然2007年他们又做了一些改进。后续密码学家设计的格公钥密码方案的大体框架都是遵循于此。此公钥密码方案可以实现语义安全。随后一年，1998年有人对此密码方案进行攻击发现，只有当格维度达到几百以上时，该公钥系统才是安全的。

二. 隐藏超平面问题（hidden hyperplanes problem,HHP）

假如我拥有一个n维的密码向量 $eq?s%5Cin%20R%5En$ ,我再取一个n维的向量 $eq?y_1%5Cin%20R%5En$ ，两者相乘得到一个数：

$eq?b_1%3D%5Clangle%20s%2Cy_1%5Crangle$

我把 $eq?y_1%5Cin%20R%5En$ 和向量相乘的结果告诉你，你能求出密码向量 $eq?s%5Cin%20R%5En$ 吗？

密码向量有n个未知数，你只给一个方程，答案显然是求不出来的。

据此，类推如果我取n个 $eq?y_i$ 得到n个向量相乘的结果，也就有了n个方程，这个时候就可以求密码向量 $eq?s%5Cin%20R%5En$ 了！

但现在很讨厌，我如果告诉你的是向量相乘的近似值（就近取值），比如我告诉你向量相乘为5，实际结果4.5~5.5之间的数都有可能，这个时候这个问题就很难了。当你发现一个问题很难时，就可以尝试拿它来构建密码系统了。

讲了这么多，我们来看下隐藏超平面问题（hidden hyperplanes problem,HHP）比较正规的表述：

随机取足够多的 $eq?y_i%5Cin%20R%5En$ ，并公开。接着告诉你 $eq?%5Clangle%20s%2Cy_i%5Crangle$ 接近一个整数，并告诉你这个整数的值，数学表达为：

$eq?%5Clangle%20s%2Cy_i%5Crangle%5Capprox%200%5Cquad%20mod%5C%201$

最后让你求向量s

接下来，我们将从矩阵的角度来解释这个问题为什么被叫做隐藏超平面问题（hidden hyperplanes problem,HHP）。

把s看成一个1行n列的矩阵，来看一个方程求解问题：

$eq?%5Clangle%20s%2Cz%5Crangle%3Dj%2C%5Cquad%20j%5Cin%20Z$

因为矩阵s只有一行，所以矩阵s的行空间为1维。整个空间维度为n维，根据线性代数的知识，如果我将所有满足方程解的z集合在一起，形成一个解空间，那么该解空间的维度则为n-1维。

这个被称之为n-1维超平面。

因为 $eq?y_i%5Cin%20R%5En$ 与s相乘的结果只是接近整数，所以 $eq?y_i$ 与该超平面很接近。这个接近程度被隐藏了。

由此以上问题被称之为隐藏超平面问题（hidden hyperplanes problem,HHP）。

因为这个里面的秘密s和点 $eq?y_i%5Cin%20R%5En$ 都是随机取的，没有过多特殊要求，所以这就是一个平均情况的困难问题。

三. 唯一最短向量问题，unique shortest vector problem，uSVP

一个格 $eq?L%5Csubset%20R%5En$ 的最短向量叫 $eq?%5Clambda_1%28L%29$ ，连续第二短的向量叫 $eq?%5Clambda_2%28L%29$ ，如果这两个满足如下条件：

$eq?%5Clambda_2%28L%29%5Cgeq%20%5Cgamma%5Ccdot%20%5Clambda_1%28L%29$

则称该格拥有 $eq?%5Cgamma$ 倍的最短向量，也就是该格最短的非零向量 $eq?v%5Cin%20L$ 的长度，比其他任何非平行向量的长度还要小 $eq?%5Cgamma$ 倍。

$eq?uSVP_%5Cgamma$ 问题定义为：

给定一个随机格L的格基，尝试求出最短向量。

这个问题的本质与基础的SVP问题类似。因为此处的格与格基没有限定任何分布，所以这个问题是一个最坏情况问题。

四. Ajtai-Dwork密码系统（改进版）

4.1 公钥

一个实例 $eq?%5Clbrace%20y_i%5Crbrace$

4.2 私钥

隐藏超平面问题（hidden hyperplanes problem,HHP）的解s

4.3 加密过程

明文是一个比特0或1：

（1）如果需要对0进行加密:

从 $eq?R%5En$ 中真随机选取一个点

（2）如果需要对1进行加密:

随机选取 $eq?%5Clbrace%20y_i%5Crbrace$ 中部分的点，进行求和，得到一个新的点

4.4 解密过程

因为解密的人拥有私钥s，那么就可以检验： $eq?%5Clangle%20s%2Cy%5Crangle$ 是否接近一个整数，来判断是情况（1）还是情况（2）。换句话说，如果发现密文点与刚才谈到的n-1维超平面很接近的话，就发现明文为1；反之为0.

4.5 总结

密码学中的decision问题：

从两个不同分布中取一个数，来判断该结果来自于哪个分布。比如这个地方就需要分辨收到的y是情况1还是情况2.

密码学中的search问题：

给定隐藏超平面问题（hidden hyperplanes problem,HHP），让你求向量s。

这两个问题之间可实现归约，也就是所谓的search-decision归约。

该方案的语义安全可以归约到HHP问题。紧接着，HHP问题又可以归约到最坏情况下的 $eq?uSVP_%5Cgamma$ 问题，其中 $eq?%5Cgamma%3Dpoly%28n%29$

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/276429.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！