HarryR / ethsnarks

A toolkit for viable zk-SNARKS on Ethereum, Web, Mobile and Desktop
GNU Lesser General Public License v3.0
240 stars 57 forks source link

Reduce exponent to 3 for LongsightF #31

Closed HarryR closed 6 years ago

HarryR commented 6 years ago

As per §5.3 of https://eprint.iacr.org/2016/492.pdf

Remember that for MiMC-n/n, d has to satisfy the condition gcd(d, 2^n − 1) = 1 in order to be a permutation, while in the case of MiMC-2n/n (that is, for Feistel Networks) this condition is not necessary.

...

Thus, the number of rounds to guarantee the security against the algebraic attacks doesn’t change choosing exponent of the form 2^t + 1 for t > 1. That is, both from the security point of view and from the implementation one, there is no advantage to choose exponents of the form 2^t + 1 greater than 3.

I think it's safe to say that the current exponent 5 can be reduced to 3.

However, there is ambiguity in the MiMC paper...