Patent ID: 8091139

Claim:
A method of protecting secret data, which is intended to be processed by an original function, from being deduced by a side-channel attack upon execution of the original function by an electronic computing device, the method comprising: creating hardware circuitry which replaces the original function with one or more pairs of replacement functions, by applying a predetermined masking algorithm which performs a recursive protection process which comprises: (i) receiving as input a description of a Boolean function F of one or more variables, wherein N denotes the number of said one or more variables; (ii) generating a pair of replacement functions, denoted F′ and F*, wherein, if N equals one, then: for the function F which receives as input a single variable, denoted X, defining two additive variables denoted X′ and X* wherein X′ XOR X* equals to X; defining the pair of replacement functions F′ and F* such that F ′( X ) XOR F *( X )= F ( X ); wherein, if N is greater than one, then: generating a pair of intermediate functions, denoted G and H, wherein intermediate function G has N−1 input variables, wherein intermediate function H has N−1 input variables, wherein the intermediate function G, upon receiving the N−1 input variables, yields the same result as the function F yields upon receiving zero and the N−1 input variables, wherein the intermediate function H, upon receiving the N−1 input variables, yields the same result as: a result of a XOR operation between (a) the result of the function F upon receiving zero and the N−1 input variables; and (b) the result of the function F upon receiving one and the N−1 input variables; recursively applying the protection process to the intermediate function G and its N−1 variables, to generate a pair of replacement functions G′ and G*; recursively applying the protection process to the intermediate function H and its N−1 variables, to generate a pair of replacement functions H′ and H*; generating a pair of replacement functions, denoted F′ and F*, wherein F′ is a function of G′ and H′ and H* and a random number R, wherein F* is a function of G* and of H′ and of H* and the random number R, wherein F=F′ XOR F*; (iii) combining the replacement functions F′ and F* according to a predetermined scheme such that the combined masked function, upon execution by said hardware circuitry in said electronic device, generates the same result of the function F and also protects the input variables of the masked combined function from being deduced by a side-channel attack.