Abstract:
At ACM CCS '01, Catalano et 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 the $N$-adic
decomposition of integer exponentiation.
Roughly speaking, we consider the problem of computing $f(x) \bmod M^\ell$
given $f(x) \bmod M$ and an exponent $\ell>1$.
By studying the case $f(x)=x^e$ and $M$ is 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 exponent $N$.
By analogy, we also study the discrete logarithm case, namely
when $f(x)=g^x$ and $M$ is a prime,
and we show that the corresponding problem is curiously
equivalent to the discrete logarithm problem in the subgroup spanned by $g$.