Paper 2014/950

Tree-Structured Composition of Homomorphic Encryption: How to Weaken Underlying Assumptions

Koji Nuida, Goichiro Hanaoka, and Takahiro Matsuda

Abstract

Cryptographic primitives based on infinite families of progressively weaker assumptions have been proposed by Hofheinz-Kiltz and by Shacham (the n-Linear assumptions) and by Escala et al. (the Matrix Diffie-Hellman assumptions). All of these assumptions are extensions of the decisional Diffie-Hellman (DDH) assumption. In contrast, in this paper, we construct (additive) homomorphic encryption (HE) schemes based on a new infinite family of assumptions extending the decisional Composite Residuosity (DCR) assumption. This is the first result on a primitive based on an infinite family of progressively weaker assumptions not originating from the DDH assumption. Our assumptions are indexed by rooted trees, and provides a completely different structure compared to the previous extensions of the DDH assumption. 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Homomorphic encryptionComposite Residuosity assumptiontree-shaped assumption familygeneric construction
Contact author(s)
k nuida @ aist go jp
History
2014-11-20: received
Short URL
https://ia.cr/2014/950
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/950,
      author = {Koji Nuida and Goichiro Hanaoka and Takahiro Matsuda},
      title = {Tree-Structured Composition of Homomorphic Encryption: How to Weaken Underlying Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/950},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/950}},
      url = {https://eprint.iacr.org/2014/950}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.