  At CRYPTO 2017, Bela\"id et al presented two new private multiplication
algorithms over finite fields, to be used in secure masking schemes. To date,
these algorithms have the lowest known complexity in terms of bilinear
multiplication and random masks respectively, both being linear in the number
of shares $d+1$. Yet, a practical drawback of both algorithms is that their
safe instantiation relies on finding matrices satisfying certain conditions. In
their work, Bela\"id et al only address these up to $d=2$ and 3 for the first
and second algorithm respectively, limiting so far the practical usefulness of
their schemes.
  In this paper, we use in turn an algebraic, heuristic, and experimental
approach to find many more safe instances of Bela\"id et al's algorithms. This
results in explicit such instantiations up to order $d = 6$ over large fields,
and up to $d = 4$ over practically relevant fields such as $\mathbb{F}_{2^8}$.
