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 (which provide canceling as well as useful parameter hiding features) to obtain a unified framework that simulates all of these composite-order features in the prime-order setting. We demonstrate the strength of this framework by providing two applications: one that adds dual pairing vector spaces to the existing projection in the Boneh-Goh-Nissim encryption scheme to obtain leakage resilience, and another that adds projecting to the existing dual pairing vector spaces in an IND- CPA-secure IBE scheme to "boost" its security to IND-CCA1. Our leakage-resilient BGN application is of independent interest, and it is not clear how to achieve it from pure composite-order techniques without mixing in additional vector space tools. Both applications rely solely on the Symmetric External Diffie Hellman assumption (SXDH).

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

Date: received 19 May 2013, last revised 18 Oct 2013

Contact author: smeiklej at cs ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20131019:025313 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]