Paper 2012/198

Beyond the Limitation of Prime-Order Bilinear Groups, and Round Optimal Blind Signatures

Jae Hong Seo and Jung Hee Cheon


At Eurocrypt 2010, Freeman proposed a transformation from pairing-based schemes in composite-order bilinear groups to equivalent ones in prime-order bilinear groups. His transformation can be applied to pairing-based cryptosystems exploiting only one of two properties of composite-order bilinear groups: cancelling and projecting. At Asiacrypt 2010, Meiklejohn, Shacham, and Freeman showed that prime-order bilinear groups according to Freeman's construction cannot have two properties simultaneously except negligible probability and, as an instance of implausible conversion, proposed a (partially) blind signature scheme whose security proof exploits both the cancelling and projecting properties of composite-order bilinear groups. In this paper, we invalidate their evidence by presenting a security proof of the prime-order version of their blind signature scheme. Our security proof follows a different strategy and exploits only the projecting property. Instead of the cancelling property, a new property, that we call {\em translating}, on prime-order bilinear groups plays an important role in the security proof, whose existence was not known in composite-order bilinear groups. With this proof, we obtain a $2$-move (i.e., round optimal) (partially) blind signature scheme (without random oracle) based on the decisional linear assumption in the common reference string model, which is of independent interest. As the second contribution of this paper, we construct prime-order bilinear groups that possess both the cancelling and projecting properties at the same time by considering more general base groups. That is, we take a rank $n$ $\zp$-submodule of $\zp^{n^2}$, instead of $\zp^n$, to be a base group $G$, and consider the projections into its rank 1 submodules. We show that the subgroup decision assumption on this base group $G$ holds in the generic bilinear group model for $n=2$, and provide an efficient membership-checking algorithm to $G$, which was trivial in the previous setting. Consequently, it is still open whether there exists a cryptosystem on composite-order bilinear groups that cannot be constructed on prime-order bilinear groups.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. An extended abstract of this paper was presented at TCC 2012. This is the full version.
TransformationComposite-order Bilinear GroupsPrime-order Bilinear GroupsRound Optimal Blind Signatures
Contact author(s)
jhsbhs @ gmail com
2012-06-25: revised
2012-04-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jae Hong Seo and Jung Hee Cheon},
      title = {Beyond the Limitation of Prime-Order Bilinear Groups, and Round Optimal Blind Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2012/198},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.