Paper 2013/657

New Trapdoor Projection Maps for Composite-Order Bilinear Groups

Sarah Meiklejohn and Hovav Shacham

Abstract

An asymmetric pairing over groups of composite order is a bilinear map $e: G_1 \times G_2 \to G_T$ for groups $G_1$ and $G_2$ of composite order $N=pq$. We observe that a recent construction of pairing-friendly elliptic curves in this setting by Boneh, Rubin, and Silverberg exhibits surprising and unprecedented structure: projecting an element of the order-$N^2$ group $G_1 \oplus G_2$ onto the bilinear groups $G_1$ and $G_2$ requires knowledge of a trapdoor. This trapdoor, the square root of a certain number modulo $N$, seems strictly weaker than the trapdoors previously used in composite-order bilinear cryptography. In this paper, we describe, characterize, and exploit this surprising structure. It is our thesis that the additional structure available in these curves will give rise to novel cryptographic constructions, and we initiate the study of such constructions. Both the subgroup hiding and SXDH assumptions appear to hold in the new setting; in addition, we introduce custom-tailored assumptions designed to capture the trapdoor nature of the projection maps into $G_1$ and $G_2$. Using the old and new assumptions, we describe an extended variant of the Boneh-Goh-Nissim cryptosystem that allows a user, at the time of encryption, to restrict the homomorphic operations that may be performed. We also present a variant of the Groth-Ostrovsky-Sahai NIZK, and new anonymous IBE, signature, and encryption schemes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
bilinear groups
Contact author(s)
smeiklej @ cs ucsd edu
History
2013-10-15: received
Short URL
https://ia.cr/2013/657
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/657,
      author = {Sarah Meiklejohn and Hovav Shacham},
      title = {New Trapdoor Projection Maps for Composite-Order Bilinear Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2013/657},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/657}},
      url = {https://eprint.iacr.org/2013/657}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.