A new public key cryptosystem based on higher residues 论文

摘要

This paper describm a new pub~c-key cryptosystem based on the hardnxs of computing higher residuw modulo a composite MA integer. We introduce two versions of our scheme, one deterministic and the other probabi~stic. The deterministic version is practically oriented encryption amounts to a single exponentiation w.r.t. a modulus with at least 768 bits and a 160-bit exponent. Decryption can be suitably optimized so as to become less demanding than a couple RSA decryptions. Although slower than MA, the new sdeme is still reasonably competitive and has several specific applications. The probabilistic version exhibits an homomorphic encryption scheme whose expansion rate is much better than previously proposed such systems. Furthermore, it has se mantic security, relative to the hardness of computing higher residu~s for suitable moduE.