Dario Fiore
New York University

Adaptive Pseudo-Free Groups and Applications

A computational group is {\em pseudo-free} if an adversary cannot find
solutions in this group for equations that are not trivially solvable
in the free group.
This notion was put forth by Rivest at TCC 2004 as a unifying abstraction of
multiple group-related hardness assumptions commonly used in
Rivest's conjecture that the RSA group is pseudo-free had been settled
by Micciancio for the case of RSA moduli that are the product of two
safe primes.
This result holds for a static setting where the adversary is only
given the description of the group (together with a set of randomly
chosen generators) and has to come up with the equation and the solution.

In this paper we explore a powerful extension of the notion of pseudo-freeness.
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

We present a novel, carefully crafted definition of {\em adaptive}
pseudo-freeness that walks a fine line between being too weak and
being unsatisfiable. 
We show that groups that satisfy our definition yield, via a
generic construction, digital and network coding signature schemes. 

Finally, we obtain concrete constructions of such schemes in the RSA group
by showing this group to be adaptive pseudo-free.  In particular, we
demonstrate the generality of our framework for signatures by showing
that most existing schemes are instantiations of our generic

This is a joint work with Dario Catalano and Bogdan Warinschi.
An extended abstract appears in the proceedings of Eurocrypt 2011. 
A preliminary full version is available at http://eprint.iacr.org/2011/053