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 for groups and of composite order . 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- group onto the bilinear groups and requires knowledge of a trapdoor. This trapdoor, the square root of a certain number modulo , 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 and . 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.