基于因子分解假设的伪随机提取和公钥加密方案

出站报告摘要 

 在标准模型下，在较弱的假设下设计出高效的密码系统是富有意义的工作。在公钥密钥学中，因子分解假设是最为广泛认可的假设之一。本报告集中于在因子分解假设下构造高效实用的密码学方案。

 本报告第一部分研究怎样在因子分解假设下有效地提取复合模数上的广义菲赫尔曼问题的伪随机比特串。我们证明了Blum-Blum-Shub 生成器是一个合适的广义菲赫尔曼问题提取器。每提取一个比特，只需要一次模平方运算。从而可以将在因子分解假设下只具有单向安全性的复合模上的ElGamal 加密转为为（选择明文攻击下）不可区分意义下的实用的加密方案。也可以得到（被动攻击下）不可区分意义下的实用的（两方和多方）密钥交换协议。

 本报告第二部分，基于Hofheinz 和Kiltz 在2009 年欧密会上提出的方案，在因子分解假设下，另外构造了两个抗选择密文攻击的公钥加密方案（不需要随机预言机）。其中之一是Hofheinz-Kiltz 09 在半平滑子群（一种比平方剩余群小得多的子群）上的实现。由于指数的范围要比原来的HK09小得多，因而效率有明显的提高。另外一个方案由复合模数上的ElGamal加密转化得到，当在半平滑子群实现时，比HK09的子群实现相比，解密速度更高。