# Adaptive pseudo-free groups and Applications

Dario Catalano, Dario Fiore, Bogdan Warinschi, Adaptive pseudo-free groups and Applications. Advances in Cryptology - EUROCRYPT 2011, pp. 207–223. May 2011. No electronic version available.

## Abstract

In this paper we explore a powerful extension of the notion of pseudo-free groups, proposed by Rivest at TCC 2004. We identify, motivate, and study pseudo-freeness in face of {\em 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 {\em 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 {\em all} existing strong RSA-based signature schemes are instantiations of our generic construction in the RSA group.