Paper 2016/1061

Changing of the Guards: a simple and efficient method for achieving uniformity in threshold sharing

Joan Daemen

Abstract

Since they were first proposed as a countermeasure against differential power analysis (DPA) in 2006, threshold schemes have attracted a lot of attention from the community concentrating on cryptographic implementations. What makes threshold schemes so attractive from an academic point of view is that they come with an information-theoretic proof of resistance against a specific subset of side-channel attacks: first-order DPA. From an industrial point of view they are attractive as a careful threshold implementation forces adversaries to DPA of higher order, with all its problems such a noise amplification. A threshold scheme that offers the mentioned provable security must exhibit three properties: correctness, incompleteness and uniformity. A threshold scheme becomes more expensive with the number of shares that must be implemented and the required number of shares is lower bound by the algebraic degree of the function being shared plus 1. Defining a correct and incomplete sharing of a function of degree d in d+1 shares is straightforward. However, up to now there is no generic method to achieve uniformity and finding uniform sharings of degree-d functions with d+1 shares is an active research area. In this paper we present a simple and relatively cheap method to find a correct, incomplete and uniform d+1-share threshold scheme for any S-box layer consisting of degree-d invertible S-boxes. The uniformity is not implemented in the sharings of the individual S-boxes but rather at the S-box layer level by the use of feed-forward and some expansion of shares. When applied to the Keccak-p nonlinear step Chi, its cost is very small.

Note: The techniques proposed in this paper were first presented at the Theory of Implementation workshop in Vienna on October 24, 2016. https://www.cosic.esat.kuleuven.be/events/acm-ccs2016/programme/