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 are useful for both constructing cryptographic primitives and enabling security reductions. Despite these convenient features, however, composite-order bilinear groups are less desirable than prime-order bilinear groups for reasons of both efficiency and security. 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 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 the concept of 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

Original Publication (with major differences): IACR-PKC-2015

Date: received 19 May 2013, last revised 5 Feb 2015

Contact author: s meiklejohn at ucl ac uk

Available format(s): PDF | BibTeX Citation

Note: Updated with publication information.

Version: 20150205:103904 (All versions of this report)

Short URL: ia.cr/2013/300

Discussion forum: Show discussion | Start new discussion