Poseidon: Evaluate security of short Montgomery matrices

[UlrichHaboeck75]

As seen from our implementation for the MNT4/6-753, Poseidon is significantly improved using MDS matrices supporting short Montgomery multiplication: The entries of such matrices $M=(m_{i,j})$ are such that the field elements $m_{i,j} * 2^64$ are only 64 bit long, and matrix multiplication is improved by a factor of roughly
$$
1/num_words,
$$
where $num_words$ is the field size in 64-bit words. For large field sizes, as in the case of the above MNTs, the short Montgomery approach outperforms the optimization strategy in Appendix B of the Poseidon paper, and even for smaller fields with $num_words =4$ (e.g., Tweedle or Pasta curves) the advantage is significant.

Using MDS matrices supporting short Montgomery multiplication seems no threat to the attacks in the paper:

• The analysis of statistical attacks relies on the number active S-Boxes only, and these are the same as as long as the matrix still passes Algorithm 1, 2 and 3 in the parameter generation script, and
• the algebraic attacks seem not to benefit from short representations either.

However, strongly recommend to contact hash experts in this regard: even though withstanding linear and differential cryptanalysis, short Montgomery multiplication is much less "dispersive" than ordinary multiplication, possibly allowing new types of attacks.

[UlrichHaboeck75]

I have asked the Poseidon authors about their opinion. They think it's ok, but we should double-check the cryptanalysis from their paper once again.