Internal round matrix needs to be more complicated

[weikengchen]

In the Poseidon examples, currently dummy constants are used, but it has chosen the partial round matrix to be I + diag(2^{i+1}), aka a matrix full of 1 except for the diagonal, which would be 2+1, 4+1, 8+1, ..., 65536+1.
https://github.com/starkware-libs/stwo/blob/dev/crates/prover/src/examples/poseidon/mod.rs#L117

There are two todos left there.

• TODO(shahars): Check that these coefficients are good according to section 5.3 of Poseidon2 paper.
• TODO(andrew): Change to rotations.

This issue is to examine the first one and show that it is negative, but it can be remedied with a slight tweak to the matrix.

Consider the following Sage code. One can run it on https://sagecell.sagemath.org/.

from sage.rings.polynomial.polynomial_gf2x import GF2X_BuildIrred_list
from math import *
import itertools

p = 2^31 - 1 
t = 16
NUM_CELLS = t

PRIME_NUMBER = p
F = GF(PRIME_NUMBER)

def check_minpoly_condition(M, NUM_CELLS):
    max_period = 2*NUM_CELLS
    all_fulfilled = True
    M_temp = M
    for i in range(1, max_period + 1):
        if not ((M_temp.minimal_polynomial().degree() == NUM_CELLS) and (M_temp.minimal_polynomial().is_irreducible() == True)):
            all_fulfilled = False
            break
        M_temp = M * M_temp
    return all_fulfilled

M_circulant = matrix.circulant(vector([F(0)] + [F(1) for _ in range(0, NUM_CELLS - 1)]))
M = M_circulant + matrix.diagonal(vector(F, [3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537]))
print(M)

print(M.is_invertible())
print(check_minpoly_condition(M, NUM_CELLS))

It shows that the matrix is invertible, but it doesn't satisfy the minpoly condition.

This can be fixed, however, by changing the matrix slightly. One can change 3 to 4 or 65537 to 65538. Particularly,

M_circulant = matrix.circulant(vector([F(0)] + [F(1) for _ in range(0, NUM_CELLS - 1)]))
M = M_circulant + matrix.diagonal(vector(F, [4, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537]))
print(M)

this satisfies both conditions.

So, recommended solution is to treat the first one differently, by adding an additional one, and use shift to implement the functionality.

[weikengchen]

@shaharsamocha7