RSA/Rabin-Paillier陷门函数的比特安全性

单向(陷门)函数是现代密码学的基础,与单向(陷门)函数紧密相关的一个概念是硬核谓词,即不可预测的比特。所谓单向(陷门)函数的比特安全性即是在得到函数值的前提下研究明文中比特的不可预测性,从而把函数的单向性归约到明文中比特的不可预测性。本文将加密方案视为单向陷门函数,研究了Paillier单向陷门函数的两个变体RSA-Paillier函数和Rabin-Paillier函数的比特安全性。Catalano等人在2001年和Galindo等人在2003年分別提出Paillier加密方案(函数)两个变体RSA-Paillier和Rabin-Paillier加密方案(函数)。这两个加密方案达到语义安全且与Paillier加密方案相比效率更高。我们分別简称为RSA-Paillier和Rabin-Paillier函数。首先,本文将基于明文的二元展开式和明文分数二元展开式的关系,分析RSA/Rabin-Paillier函数的最大有意义比特的安全性,即,证明了求解它们等价于求解整个明文。该结果不仅改进了Su等人在2010年利用隐藏数问题得到的结果,即求解Rabin-Paillier函数明文的前「3 2N/2」+「2N」个最大有意义比特等价于求解整个明文,而且本文所用方法摆脱了他们所用的复杂的隐藏数问题方法:此外,本文通过这两类函数的分数最大有意义比特和明文最小有意义比特的转换关系,研究了Rabin/RSA-Paillier函数的明文最小有意义比特的安全性,证明了计算它们也等价于求解整个明文。

Paillier陷门函数的两个变体的比特安全性分析

文中对Paillier陷门函数两个变体——Rabin-Paillier和RSA-Paillier进行了比特安全分析.对于Rabin-Paillier陷门函数,文中证明了从密文计算其明文的3 2n/2+log2n个最高有效位与对这个函数求逆一样困难,其中n为RSA模数N的二进制长度.该结论的证明基于Boneh等人提出的素数域上的隐藏数问题的一个变体.文中使用Malykhin在2007年得到的指数和的界把该变体扩展到了Paillier模数N2的情况.对于RSA-Paillier陷门函数,该文完善了Morillo等人对于该函数明文最低有效位的困难性证明.通过设计一个随机化的算法使得Morillo等人提出的明文恢复算法在使用不完美的LSB预言机的时候也能工作.