Adaptive Pseudo-Free Groups and Applications
A computational group is 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 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.