perf: use inverse as a bijection for bw6-761 mimc

[yelhousni]

Description

Currently BW6-761 MiMC hash uses pow5 as a bijection. This PR suggests to use the Inverse function instead. This reduces the number of constraints needed for the plonk verifier gadget in gnark (see https://github.com/Consensys/gnark/pull/949) but increases the out-circuit execution time.

TODO:

• [ ] Security analysis of the number of rounds.

Type of change

Please delete options that are not relevant.

• [x] New feature (non-breaking change which adds functionality)
• [x] Breaking change (fix or feature that would cause existing functionality to not work as expected)
• [x] This change requires a documentation update

How has this been tested?

Same tests as in the master branch.

How has this been benchmarked?

Please describe the benchmarks that you ran to verify your changes.

• [ ] Benchmark A, on Macbook pro M1, 32GB RAM
• [ ] Benchmark B, on x86 Intel xxx, 16GB RAM

Checklist:

• [ ] I have performed a self-review of my code
• [ ] I have commented my code, particularly in hard-to-understand areas
• [ ] I have made corresponding changes to the documentation
• [ ] I have added tests that prove my fix is effective or that my feature works
• [ ] I did not modify files generated from templates
• [ ] golangci-lint does not output errors locally
• [ ] New and existing unit tests pass locally with my changes
• [ ] Any dependent changes have been merged and published in downstream modules

[yelhousni]

Changes look good, but I'm not sure about the security analysis. Is there a reference which supports using inverse as a encryption function?

And in that case I'm not sure if we should keep it as MiMC or instead define a new hash function MiMC-Inverse?

@ThomasPiellard, do you have thoughts?

Well we just need the s-box to be a bijection so given that 1/x == x^(p-2) and gcd(r-1,p-2)==1 then it should work. Now the security analysis part regarding the number of rounds is what I'm not sure about. For some reference, the inverse s-box is discussed in the Poseidon paper. But now that I am rereading the paper, I found that this dicussion was dismissed in the new updated version (old version vs . new version).

From the Section "Previous Versions" in the Abstract of the new version, one can read:

We emphasize that both (i) the entire family of STARKAD and (ii) POSEIDON instantiated with x → 1/x are considered as dismissed, and we advice against using them.

I am not sure if it is fair to translate blindly the security analysis of Poseidon to MiMC but I think it would be safe to revert the use of the inverse s-box in MiMC. For the record, if we revert commit https://github.com/Consensys/gnark/pull/949/commits/bdab848e33f2305224d266fa1cf792c4bc40e1dd in PR https://github.com/Consensys/gnark/pull/949, the total nb of constraint is 342k instead of 317k for the 2-chain case (emulated case not impacted). So that's not terrible.

[ivokub]

Changes look good, but I'm not sure about the security analysis. Is there a reference which supports using inverse as a encryption function? And in that case I'm not sure if we should keep it as MiMC or instead define a new hash function MiMC-Inverse? @ThomasPiellard, do you have thoughts?

Well we just need the s-box to be a bijection so given that 1/x == x^(p-2) and gcd(r-1,p-2)==1 then it should work. Now the security analysis part regarding the number of rounds is what I'm not sure about. For some reference, the inverse s-box is discussed in the Poseidon paper. But now that I am rereading the paper, I found that this dicussion was dismissed in the new updated version (old version vs . new version).

From the Section "Previous Versions" in the Abstract of the new version, one can read:

We emphasize that both (i) the entire family of STARKAD and (ii) POSEIDON instantiated with x → 1/x are considered as dismissed, and we advice against using them.

I am not sure if it is fair to translate blindly the security analysis of Poseidon to MiMC but I think it would be safe to revert the use of the inverse s-box in MiMC. For the record, if we revert commit Consensys/gnark@bdab848 in PR Consensys/gnark#949, the total nb of constraint is 342k instead of 317k for the 2-chain case (emulated case not impacted). So that's not terrible.

Yup, skimming the different versions I think I have the same impression. I think for safety now we can revert bdab848 in 949 (to use pow5 instead of inv). With https://github.com/Consensys/gnark/pull/960 we get additional savings when batching and I think we already can fit many proofs in 2-chain currently.

I think we can save quite a lot more when going to 8- or 16-bit decomposition when marshalling G1 points. Right now the overhead is quite significant. And we can still look into implementing Pedersen instead of using MiMC.

But just in case I would leave this PR open. It may still work out after reconsidering nb of rounds.