MDS matrices are essential in symmetric-key cryptography since they provide optimal diffusion in block ciphers. Many MDS matrices are known, but a problem remains which gathers a lot of attention: finding lightweight MDS matrices.

Several approaches exist, namely reducing the cost of already-known MDS matrices (to improve existing ciphers) and finding new MDS matrices lighter than the known ones (to make new ciphers).

We focus on the second case and, contrarily to the usual approach, we will not look for matrices whose coefficients are lightweight to implement. Rather than this local optimization, we will prefer a global optimization of the whole matrix, which allows reusing of intermediate values.

We propose an algorithm to search for lightweight formal MDS matrices on a polynomial ring, by enumerating circuits until we reach an MDS matrix. This approach allows us to get much better results than previous works. We also adapt this algorithm to look for almost-MDS matrices, which offer a trade-off between cost and security.