Public-Key Cryptosystems with Primitive PowerRoots of Unity

摘要

We first consider a variant of the Schmidt-Samoa-Takagi encryption scheme without losing additively homomorphic properties. We show that this variant is secure in the sense of IND-CPA under the de-cisional composite residuosity assumption, and of OW-CPA under the assumption on the hardness of factoring n = p~2q. Second, we introduce new cryptographic properties "affine" and "pre-image restriction", which are closely related to homomorphism. Intuitively, "affine" is a tuple of functions which have a special homomorphic property, and "pre-image restriction" is a function which can restrict the receiver to having information on the encrypted message. Then, we propose an encryption scheme with primitive power roots of unity in (Z~(s+1))~×. We show that our scheme has the above cryptographic properties.