Paper 2010/474

Limitations on Transformations from Composite-Order to Prime-Order Groups: The Case of Round-Optimal Blind Signatures

Sarah Meiklejohn, Hovav Shacham, and David Mandell Freeman

Abstract

Beginning with the work of Groth and Sahai, there has been much interest in transforming pairing-based schemes in composite-order groups to equivalent ones in prime-order groups. A method for achieving such transformations has recently been proposed by Freeman, who identified two properties of pairings using composite-order groups--"cancelling" and "projecting"--on which many schemes rely, and showed how either of these properties can be obtained using prime-order groups. In this paper, we give evidence for the existence of limits to such transformations. Specifically, we show that a pairing generated in a natural way from the Decision Linear assumption in prime-order groups can be simultaneously cancelling and projecting only with negligible probability. As evidence that these properties can be helpful together as well as individually, we present a cryptosystem whose proof of security makes use of a pairing that is both cancelling and projecting. Our example cryptosystem is a simple round-optimal blind signature scheme that is secure in the common reference string model, without random oracles, and based on mild assumptions; it is of independent interest.

Note: Fixed a bug in the proof of Proposition 6.4.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. To appear at Asiacrypt 2010; this is the full version.
Keywords
blind signaturespairingscomposite-order groups
Contact author(s)
smeiklej @ cs ucsd edu
History
2010-09-20: revised
2010-09-08: received
See all versions
Short URL
https://ia.cr/2010/474
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/474,
      author = {Sarah Meiklejohn and Hovav Shacham and David Mandell Freeman},
      title = {Limitations on Transformations from Composite-Order to Prime-Order Groups: The Case of Round-Optimal Blind Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2010/474},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/474}},
      url = {https://eprint.iacr.org/2010/474}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.