# Would the Fiat Shamir identification scheme be more secure if I design it with an exponents higher than 2?

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?

## 2 Answers

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.

• But in the FS identication protocol, the factorisation of modulus is kept secret for both the proover and the challenger. The secret is composed by k secret numbers which are stored in an Smart Card and allow the proover to identicate himself with a high level of probability. Otherwise I suggested in that time to take a look to the GQ identication protocol wich was introduced to reduce the number of interactive exchange steps, from which the security level can be adapted. – Robert NACIRI Mar 30 '15 at 16:27

In this case, take a look to the GQ identication scheme, from Guillou and Quisquater.