Abstract:
|
Comunicació presentada a: CRYPTO 2014. 34th Annual Cryptology Conference, celebrada a Santa Barbara, Califòrnia, Estats Units d'Amèrica, del 17 al 21 d'agost de 2014 |
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
e ciency improvements, and enables us to circumvent previous
lower bounds. Specifically, we show how to verify 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). |