Proceedings of the 8th ACM Conference on Computer and Communications Security
(Nov 5-8, 2001, Philadelphia, USA),
Published by the
ACM.
Abstract:
We re-examine Paillier's cryptosystem, and show that by choosing a
particular discrete log base g, and by introducing an alternative
decryption procedure, we can extend the scheme to allow an arbitrary
exponent e instead of N. The use of low exponents substantially
increases the efficiency of the scheme, at the expense of the homomorphic property.
The semantic security is now based on
a new decisional assumption, namely the hardness of deciding
whether
an element is a ``small'' e-th residue modulo N^2.
We also show how to use Paillier's original cryptosystem
to build a trapdoor
commitment scheme. This new scheme is information-theoretically private,
and computationally binding (this property holds under the assumption
that the RSA function with exponent N is hard to invert). A novel
property of this new commitment scheme is that most of the work can
be done offline before knowing the message one wants to commit
to.
Once the message is known only two multiplications are required.
This is the first trapdoor commitment scheme with this
online-offline efficiency property which is also length-preserving.