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函数的明文最小有意义比特的安全性,证明了计算它们也等价于求解整个明文。