掩藏数问题及其应用

本课题研究掩藏数问题（HNP问题）及其应用的如下内容：.1）研究HNP具体实例，如，T-HNP、EC-HNP和HNP-HM，分析验证点的选取集合的大小、验证点个数以及需要有意义比特串的长度之间的关系，以及对算法效率的影响，找出最优有效算法的设计方法，得到这些实例的更实际有效算法。2）研究高次掩藏数问题及其相关应用。3）将新得到HNP问题的结果用于分析目前所用的困难问题的单向性和现有若干密码系统的安全性分析，将其归约到困难问题的某些相关比特的安全性，或者对其给出攻击。4）研究一般代数数域或有限域上的HNP问题,将现有结果推广基于素域的向量空间上（或代数整环的模上）；利用扩域的Galois群的结构及其表示论结果，将问题转化为线性代数问题；给出算法的设计。特别地，现在特征2的有限域上的研究结果很少，希望能够对T-HNP和EC-HNP问题给出给出相关结果。

在课题进行中，我们主要对如下内容展开研究，并取得一系列新的成果，部分成果达到国际先进水平：. 1）HNP问题的一些具体实例研究：首先讨论l=1时的情形，即一些具体单向陷门函数的hardcore谓词和比特的同时安全,如,Paillier陷门函数及其变体、OU函数、ax+b mod p的比特安全性等；其次，我们研究l>1 时一些函数的HNP问题，得到l个最大有意义比特与函数单向性之间的归约关系。. 2）HNP一般求解研究：首先，对HNP问题与Hensel提升问题展开研究，作为高次掩藏数问题研究的部分结果，研究了HNP与Hensel提升问题之间的关系，证明HNP与离散对数情形的Hensel提升问题的难度是等价的；其次，研究HNP的确定性求解方法。通过讨论分数的二进制展开式中比特与整数的最大有意义比特、最小有意义比特的关系，给出一个确定解法，可以有效用于有一定同态性密码函数的比特安全性研究。. 3）椭圆曲线上困难问题研究：分析比较椭圆曲线上类背包DH问题k-CAA'、k-wCDHP和DLP的难度关系，并对给出[10]的基于k-CAA'的加强短签名的攻击，并给出一个改进的基于k-CAA'的安全签名。. 另外，本课题还对Σ-PIR、可验证签名分享等展开研究，首次提出Σ-PIR的定义，并给予实现，然后讨论分布式OT与Σ-PIR的关系，证明二者等价。. 总之，在本项目执行期间发表论文10篇，录用2篇，研究报告1篇，共计13篇，其中在国际会议论文集发表5篇，国内会议论文集1篇，杂志4篇，杂志录用2篇，研究报告1篇；另外，还有编著两部：《代数、组合与线性码》和《计算复杂性理论基础》。项目进行顺利，填补国内空白，圆满完成预定目标。