Cryptology ePrint Archive: Report 2013/300

A Profitable Sub-Prime Loan: Obtaining the Advantages of Composite-Order in Prime-Order Bilinear Groups

Allison Lewko and Sarah Meiklejohn

Abstract: Composite-order bilinear groups provide many structural features that have proved useful for both constructing cryptographic primitives and as a technique in security reductions. Despite these convenient features, however, composite-order bilinear groups are less desirable than prime-order bilinear groups for reasons of efficiency. A recent line of work has therefore focused on translating these structural features from the composite-order to the prime-order setting; much of this work focused on two such features, projecting and canceling, in isolation, but a recent result due to Seo and Cheon showed that both features can be obtained simultaneously in the prime-order setting.

In this paper, we reinterpret the construction of Seo and Cheon in the context of dual pairing vector spaces, a tool previously used to simulate other desirable features of composite-order groups in the prime-order setting. In this way, we are able to obtain a unified framework that simulates all of the known composite-order features in the prime-order setting. We demonstrate the strength of this framework by showing that the addition of even a weak form of projecting on top of the pre-existing uses of dual pairing vector spaces can be leveraged to "boost" a fully IND-CPA secure identity-based encryption scheme to one that is fully IND-CCA1 secure.

Category / Keywords: foundations / bilinear groups, prime-order groups

Date: received 19 May 2013

Contact author: smeiklej at cs ucsd edu

Available formats: PDF | BibTeX Citation

Version: 20130525:134716 (All versions of this report)

Discussion forum: Show discussion | Start new discussion