On the Minimal Assumptions of Group Signature Schemes

One of the central lines of cryptographic research is identifying the weakest assumptions required for the construction of secure primitives. In the context of group signatures the gap between what is known to be necessary (one-way functions) and what is known to be sufficient (trapdoor permutations) is quite large. In this paper, we provide the first step towards closing this gap by showing that the existence of secure group signature schemes implies the existence of secure public-key encryption schemes. Our result shows that the construction of secure group signature schemes based solely on the existence of one-way functions is unlikely. This is in contrast to what is known for standard signature schemes, which can be constructed from any one-way function.