ROS with auxiliary inputs ⇒ ROS

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

If ROS with auxiliary inputs is hard for a group generator , then the ROS problem is hard for , with the same advantage: for a fixed , an -ROS solver run on , a uniformly random function of , outputs pairwise distinct and with , so the pairs are pairwise distinct and solve - — folklore.