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

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, the authors give evidence for the existence of limits to such transformations. Specifically, they 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.