  Given a cryptographic group action, we show that the Group Action Inverse
Problem (GAIP) and other related problems cannot be NP-hard unless the
Polynomial Hierarchy collapses. We show this via random self-reductions and the
design of interactive proofs. Since cryptographic group actions are the
building block of many security protocols, this result serves both as an upper
bound on the worst-case complexity of some cryptographic assumptions and as
proof that the hardness in the worst and in the average case coincide. We also
point out the link with Graph Isomorphism and other related NP intermediate
problems.
