Let's say both Prover and Verifier would use nth power instead of 2nd when creating public keys and when verifying. I know it would slow it down but would that cause the protocol to be more secure?
No, it wouldn't.
Very simply put: If you can compute square roots wrt. a composite modulus, then you can calculate other fixed roots, too. This is based on the fact, that being able to compute square roots allows you to factor the modulus:
- Choose random $x$.
- Compute $x^2$.
- apply your square root algorithm to $x^2$.
- The result $y$ will be a different square root than $x$ with probability 3 out of 4. And 2 out of 4 will allow you to directly factor the modulus.
When you know the factorization, calculating any arbitrary root higher than 2 is easy.
The other way around is not known: When you can calculate roots for any degree with injective functions, then you can break the RSA assumption. But it is unknown, if that allows you to factorize the modulus or allow the computation of square roots.