Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups

David Mandell Freeman

Abstract

We develop an abstract framework that encompasses the key properties of bilinear groups of composite order that are required to construct secure pairing-based cryptosystems, and we show how to use prime-order elliptic curve groups to construct bilinear groups with the same properties. In particular, we define a generalized version of the subgroup decision problem and give explicit constructions of bilinear groups in which the generalized subgroup decision assumption follows from the decision Diffie-Hellman assumption, the decision linear assumption, and/or related assumptions in prime-order groups. We apply our framework and our prime-order group constructions to create more efficient versions of cryptosystems that originally required composite-order groups. Specifically, we consider the Boneh-Goh-Nissim encryption scheme, the Boneh-Sahai-Waters traitor tracing system, and the Katz-Sahai-Waters attribute-based encryption scheme. We give a security theorem for the prime-order group instantiation of each system, using assumptions of comparable complexity to those used in the composite-order setting. Our conversion of the last two systems to prime-order groups answers a problem posed by Groth and Sahai.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
pairing-based cryptographycomposite-order groupscryptographic hardness assumptions
Contact author(s)
dfreeman @ cs stanford edu
History
Short URL
https://ia.cr/2009/540

CC BY

BibTeX

@misc{cryptoeprint:2009/540,
author = {David Mandell Freeman},
title = {Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups},
howpublished = {Cryptology ePrint Archive, Paper 2009/540},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/540}},
url = {https://eprint.iacr.org/2009/540}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.