单向函数比特安全性的研究

姓    名：王  克    学科专业：信息安全

      研究方向：密码学    指导教师：吕克伟 副教授 

 摘  要 

 单向函数是现代密码学的基础。对于单向函数比特安全性的研究一直是一个热点的研究方向。利用比特安全性我们可以构建和改善很多密码学工具，如伪随机生成器和安全协议等等。本文主要对两个问题进行了研究，分别是OU函数比特安全性和Goldreich-Rosen算法的改进。具体的研究结果如下： 

 OU函数的比特安全性：在1998年欧密会上，Okamoto和Uchiyama提出了一种新的公钥加密系统，本文称之为OU体制，同时将OU体制的核心函数称为OU函数。对于OU函数，本文证明了在分解困难性假设下，其最小有意义比特是安全比特，同时O(logn)个最小有意义比特同时安全。如果使用更强的B-困难假设，那么OU函数可以有n-b-1个同时安全比特，其中b=logB 。

 Goldreich-Rosen算法的改进：在以往的研究中，在分解困难性假设下，模合数指数函数的上半比特和下半比特分别被证明是同时安全的。本文改进了Goldreich-Rosen算法的归约算法。通过改进Goldreich-Rosen算法，本文构造的新Goldreich-Rosen算法的效率比原算法提高了O(logne^-1)倍，同时算法的错误概率O(logne^-1/ne^-1) 仍保持在可接受范围内。如果可以容忍错误概率O((logne^-1)^(1/2c)-1)，本文的新算法的效率可以进一步提高至O((logne^-1)^(1/2c))倍，其中c是一个不小于2的常数。