The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm
The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm
复制标题
亨塞尔提升的难度：RSA 和离散对数的案例
DOI：
10.1007/3-540-36178-2_19
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
J. Stern
中科院分区：
文献类型：
--
作者：
D. Catalano;Phong Q. Nguyen;J. Stern
在ACM CCS' 01上，Catalanoet等人提出了RSA密码系统与来自Eurocrypt '99的Paillier密码系统的混合。由此产生的计划，我们称之为RSAP，是一个概率密码系统，这是语义安全的一个适当的决策假设下，有效的RSA，但没有同态性质的Paillier计划。有趣的是，Sakurai和Takagi在PKC '02上证明了RSAP的单向性等价于RSA假设。然而，我们在本文中注意到，上述证明并不完全正确（它只在给出完美预言的情况下有效，即总是提供正确答案的预言）。我们修复的证明，提出了一个新的证明的基础上低维格。新的证明，灵感来自樱井和高木的工作，是有点相关的Hensel提升和theN-adic分解的整数指数。粗略地说，我们考虑的问题，计算f（x）modMlgivenf（xmodM和一个指数1> 1。通过对RSAP的单向性与RSA假设等价的研究，证明了RSAP的单向性与RSA假设是等价的，并由此推测原Paillier方案的单向性与RSA假设不等价.通过类比，我们还研究了离散对数的情形，即当f（x）= gx且M是素数时，我们证明了相应的问题与g所张子群中的离散对数问题是奇异等价的.
At ACM CCS’ 01, Catalanoet al.proposed a mix of the RSA cryptosystem with the Paillier cryptosystem from Eurocrypt ’99. The resulting scheme, which we call RSAP, is a probabilistic cryptosystem which is both semantically secure under an appropriate decisional assumption and as efficient as RSA, but without the homomorphic property of the Paillier scheme. Interestingly, Sakurai and Takagi presented at PKC ’02 a proof that the one-wayness of RSAP was equivalent to the RSA assumption. However, we notice in this paper that the above proof is not completely correct (it works only in the case when a perfect oracle - i.e. an oracle that always provides correct answers - is given). We fix the proof by presenting a new proof based on low-dimensional lattices. The new proof, inspired by the work of Sakurai and Takagi, is somewhat related to Hensel lifting and theN-adic decomposition of integer exponentiation. Roughly speaking, we consider the problem of computingf(x) modMlgivenf(xmodMand an exponentl> 1. By studying the casef(x) =xeandMis an RSA-modulus, we deduce that the one-wayness of RSAP is indeed equivalent to the RSA assumption, and we are led to conjecture that the one-wayness of the original Paillier scheme may not be equivalent to the RSA assumption with exponentN. By analogy, we also study the discrete logarithm case, namely whenf(x) =gxandMis a prime, and we show that the corresponding problem is curiously equivalent to the discrete logarithm problem in the subgroup spanned byg.