Our construction of a HE scheme is generic; based on a tree structure, we recursively combine copies of building-block HE schemes associated to each leaf of the tree (e.g., the Paillier cryptosystem, for our DCR-based result mentioned above). Our construction for depth-one trees utilizes the "share-then-encrypt" multiple encryption paradigm, modified appropriately to ensure security of the resulting HE schemes. We prove several separations between the CPA security of our HE schemes based on different trees; for example, the existence of an adversary capable of breaking all schemes based on depth-one trees, does not imply an adversary against our scheme based on a depth-two tree (within a computational model analogous to the generic group model). Moreover, based on our results, we give an example which reveals a type of "non-monotonicity" for security of generic constructions of cryptographic schemes and their building-block primitives; if the building-block primitives for a scheme are replaced with other ones secure under stronger assumptions, it may happen that the resulting scheme becomes secure under a weaker assumption than the original.
Category / Keywords: public-key cryptography / Homomorphic encryption, Composite Residuosity assumption, tree-shaped assumption family, generic construction Date: received 20 Nov 2014 Contact author: k nuida at aist go jp Available format(s): PDF | BibTeX Citation Version: 20141120:161203 (All versions of this report) Short URL: ia.cr/2014/950 Discussion forum: Show discussion | Start new discussion