PCD uses Marlin with Poseidon with hardcoded parameters that do not guarantee to be secure

[weikengchen]

This is a note that the current PCD uses the constraints branch of Marlin, which uses a hardcoded Poseidon parameters, regardless of the curves and fields of the proof systems. This has two problems:

(1) \alpha may not work for all the fields. Recall that Poseidon uses a nonlinear function y = x^\alpha. There is a requirement that \alpha does not divide the order of the field. This immediately means that the current parameters are "insecure" under a number of the curves and fields due to collisions.

(2) Hardcoded parameters are never a good practice. Ideally, we can replace it by running the ChaChaRng over a small seed, to generate all the parameters needed for Poseidon.

This, however, requires a general-purpose and nice Poseidon sponge implemented in arkworks.

[weikengchen]

So, the current implementation in this repo should be considered benchmark-purpose, though it is due to the upstream.

[weikengchen]

Some factoring result of p-1 for the MNT4/6-298/753. Factors > 100 are denoted by R.

It shows that choosing \alpha=17 is okay for these curves.

---

MNT4/6-298

475922286169261325753349249653048451545124878552823515553267735739164647307408490559963137 = 2^34 * 3^2 * 7^4 * 43^2 * R

475922286169261325753349249653048451545124879242694725395555128576210262817955800483758081 = 2^17 * 3 * 5 * 7^2 * 43 * 67 * R

MNT4/6-753:

41898490967918953402344214791240637128170709919953949071783502921025352812571106773058893763790338921418070971888458477323173057491593855069696241854796396165721416325350064441470418137846398469611935719059908164220784476160001 =2^30 * 3^2 * 5^4 * 7^2 * R

41898490967918953402344214791240637128170709919953949071783502921025352812571106773058893763790338921418070971888253786114353726529584385201591605722013126468931404347949840543007986327743462853720628051692141265303114721689601 = 2^15 * 3 * 5^2 * 7 * 11 * 23 * 71 * R

[weikengchen]

So, ideally, the next step to boost the security is:

• change the partial rounds from 29 to 31, which would match the official parameter search script, for providing 128-bit security.
• replace the MDS matrix from a near-MDS one to a more randomized one.

[weikengchen]

By the way, the current choice of \alpha = 17 by @ValarDragon is smart. It has few constraints for pow_by_constant and also reduces the number of rounds needed for security.

Though \alpha=5 is better for performance, it only works for very few curves (as we can see above).

[weikengchen]

The number of partial rounds has been increased to 31, and the round constants are now generated via a PRNG with a hardcoded seed.

This is still not good enough. Efforts to move this to a more formal treatment will continue.

[Pratyush]

I think maybe if one makes the seed dependent on the field in some way (maybe by being a hash of the modulus?), and uses instead of a PRNG a XOF derived from a random-oracle-like thing, it should suffice for security.

[weikengchen]

Yes. Citing a related issue in sponge about a more formal treatment: https://github.com/arkworks-rs/crypto-primitives/issues/95