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)
- 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
-
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}, url = {https://eprint.iacr.org/2014/950} }