In this paper we explore a powerful extension of the notion of pseudo-freeness. We identify, motivate, and study pseudo-freeness in face of adaptive adversaries who may learn solutions to other non-trivial equations before having to solve a new non-trivial equation.
Our first contribution is a carefully crafted definition of adaptive pseudo-freeness that walks a fine line between being too weak and being unsatisfiable. We give generic constructions that show how any group that satisfies our definition can be used to construct digital signatures and network signature schemes.
Next, we prove that the RSA group meets our more stringent notion of pseudo-freeness and as a consequence we obtain different results. First, we obtain a new network (homomorphic) signature scheme in the standard model. Secondly, we demonstrate the generality of our framework for signatures by showing that all existing strong RSA-based signature schemes are instantiations of our generic construction in the RSA group.
Category / Keywords: public-key cryptography / pseudo-free groups, RSA, digital signatures Publication Info: This is the full version of the paper that will appear at Eurocrypt 2011 Date: received 27 Jan 2011 Contact author: dario fiore at ens fr Available format(s): PDF | BibTeX Citation Version: 20110128:025731 (All versions of this report) Short URL: ia.cr/2011/053 Discussion forum: Show discussion | Start new discussion