SPEAKER: Dario Fiore New York University TITLE: Adaptive Pseudo-Free Groups and Applications ABSTRACT: 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 cryptography. 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 equation. 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 construction. 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