Paper 2014/445
Polynomial Spaces: A New Framework for Composite-to-Prime-Order Transformations
Gottfried Herold, Julia Hesse, Dennis Hofheinz, Carla Ràfols, and Andy Rupp
Abstract
At Eurocrypt 2010, Freeman presented a framework to convert cryptosystems based on composite-order groups into ones that use prime-order groups. Such a transformation is interesting not only from a conceptual point of view, but also since for relevant parameters, operations in prime-order groups are faster than composite-order operations by an order of magnitude. Since Freeman's work, several other works have shown improvements, but also lower bounds on the efficiency of such conversions. 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).
Note: Instantiation details of Groth-Sahai proofs changed.
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in CRYPTO 2014
- Keywords
- bilinear mapscomposite-order groupsGroth-Sahai proofs
- Contact author(s)
- carla rafols @ rub de
- History
- 2015-08-31: revised
- 2014-06-13: received
- See all versions
- Short URL
- https://ia.cr/2014/445
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/445,
author = {Gottfried Herold and Julia Hesse and Dennis Hofheinz and Carla Ràfols and Andy Rupp},
title = {Polynomial Spaces: A New Framework for Composite-to-Prime-Order Transformations},
howpublished = {Cryptology {ePrint} Archive, Paper 2014/445},
year = {2014},
url = {https://eprint.iacr.org/2014/445}
}