Z/ns+1). We show that our scheme has, in addition to the additively homomorphic property, the above algebraic properties. In addition to the properties, we also show that the encryption scheme is secure in the sense of OW-CPA and IND-CPA under new number theoretic assumptions." />


Primitive Power Roots of Unity and Its Application to Encryption

Takato HIRANO  Koichiro WADA  Keisuke TANAKA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.8   pp.1836-1844
Publication Date: 2009/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1836
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Theory
Keyword: 
Paillier's encryption scheme,  factoring,  homomorphism,  power roots of unity,  

Full Text: PDF>>
Buy this Article




Summary: 
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 decisional composite residuosity assumption, and of OW-CPA under the assumption on the hardness of factoring n=p2q. Second, we introduce new algebraic properties "affine" and "pre-image restriction," which are closely related to homomorphicity. 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/ns+1). We show that our scheme has, in addition to the additively homomorphic property, the above algebraic properties. In addition to the properties, we also show that the encryption scheme is secure in the sense of OW-CPA and IND-CPA under new number theoretic assumptions.