格密码:隐藏超平面问题与uSVP问题 (Ajtai密码)

发布时间:2023年12月28日

目录

一. 技术发展

二.?隐藏超平面问题(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与该超平面很接近。这个接近程度被隐藏了。

48a101685a544d4dbebb45180b26c68b.jpeg

由此以上问题被称之为隐藏超平面问题(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

文章来源:https://blog.csdn.net/forest_LL/article/details/135257777
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。