A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications

At Eurocrypt ‘02 Cramer and Shoup [7] proposed a general paradigm to construct practical public-key cryptosystems secure against adaptive chosen-ciphertext attacks as well as several concrete examples. Among the others they presented a variant of Paillier’s [21] scheme achieving such a strong security requirement and for which two, independent, decryption mechanisms are allowed. In this paper we revisit such scheme and show that by considering a different subgroup, one can obtain a different scheme (whose security can be proved with respect to a different mathematical assumption) that allows for interesting applications. In particular we show how to construct a perfectly hiding commitment schemes that allows for an on-line / off-line efficiency tradeoff. The scheme is computationally binding under the assumption that factoring is hard, thus improving on the previous construction by Catalano et al. [5] whose binding property was based on the assumption that inverting RSA[N,N] (i.e. RSA with the public exponent set to N) is hard.