In this work, we present a new framework for composite-to-prime-order conversions. Our framework is in the spirit of Freeman's work; however, we develop a different, ``polynomial'' view of his approach, and revisit several of his design decisions. This eventually leads to significant efficiency improvements, and enables us to circumvent previous lower bounds. Specifically, we show how to implement Groth-Sahai proofs in a prime-order environment (with a symmetric pairing) almost twice as efficiently as the state of the art.
We also show that our new conversions are optimal in a very broad sense. Besides, our conversions also apply in settings with a multilinear map, and can be instantiated from a variety of computational assumptions (including, e.g., the $k$-linear assumption).Category / Keywords: bilinear maps, composite-order groups, Groth-Sahai proofs Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 10 Jun 2014, last revised 31 Aug 2015 Contact author: carla rafols at rub de Available format(s): PDF | BibTeX Citation Note: Instantiation details of Groth-Sahai proofs changed. Version: 20150831:130027 (All versions of this report) Short URL: ia.cr/2014/445 Discussion forum: Show discussion | Start new discussion