New Instantiations of the CRYPTO 2017 Masking Schemes
This work addresses a practical limitation in cryptographic masking schemes for secure implementations, though it is incremental as it builds on existing algorithms.
The paper tackled the problem of finding safe instantiations for CRYPTO 2017 masking schemes, which were previously limited to low orders, by using algebraic, heuristic, and experimental methods to extend instantiations up to order d=6 over large fields and d=4 over fields like 𝔽_{2^8}.
At CRYPTO 2017, Belaïd 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ïd 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ïd 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}$.