Paper 2009/540

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

David Mandell Freeman


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)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
pairing-based cryptographycomposite-order groupscryptographic hardness assumptions
Contact author(s)
dfreeman @ cs stanford edu
2009-11-08: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.