Side-channel attack protected gates having low-latency and reduced complexity

1. A masked logic gate protected against side-channel attacks using Boolean masking with d+1 shares for each input variable, where d is an integer at least equal to 1 representing a protection order, the masked logic gate comprising:

a first input configured to receive a number of shares yj (j=0, 1, 2 . . . );

a second input configured to receive (d+1) 2 shares xi (i=0, 1, 2 . . . ) representative of an intermediate result output by one layer of a tree of gates implementing low-latency masking with the protection order of d; and

a (d+1)-share output obtained by applying a logic function of the masked logic gate to the shares of the first and second inputs using domain-oriented masking.

2. The masked logic gate of claim 1 , wherein the first input is also configured to receive (d+1) 2 shares representative of an intermediate result output by one layer of a tree of gates implementing low-latency masking with the protection order of d.

3. The masked logic gate of claim 1 , wherein the first input is configured to receive d+1 shares of an input variable.

4. The masked logic gate of claim 1 , having a structure representable by a matrix having (d+1) 2 rows assigned respectively to the shares xi of the second input, and a number of columns assigned respectively to the shares yj of the first input, the structure comprising:

for each cell (i, j) of the matrix, an elementary gate of a same type connected to operate on the shares xi and yj;

for each cell (i, j) in a subset of cells of the matrix, a random bit selected in a group of independent random bits (r 0 , r 1 , r 2 . . . ), and an XOR gate connected to inject the random bit in the output of the corresponding elementary gate, wherein the random bits are selected such that any random bit occurs an even number of times in the matrix; and

for each slice of d+1 rows of the matrix, a respective tree of XOR gates producing a corresponding output share (z 0 , z 1 , z 2 ) of the masked logic gate from all the cells of the slice.

5. The masked logic gate of claim 4 , wherein the XOR gates of the tree are connected such that any XOR gate of the tree receives at least one random bit an odd number of times.

6. The masked logic gate of claim 4 , where d=2 and the first input is configured to receive 9 shares, wherein the masked logic gate has three output shares (z 0 , z 1 , z 2 ) corresponding respectively to three slices of the matrix, and the matrix has 9 rows and 9 columns, and wherein:

the group of independent random bits includes 12 random bits r 0 , r 2 . . . r 11 ;

a same random bit from the range r 0 -r 8 occurs three times in each of two of the three slices and does not occur in the remaining slice; and

a same random bit from the range r 9 -r 11 occurs twice in each of the slices, but does not occur in the matrix an even number of times in a same column, nor in a same 3×3 square.

7. The masked logic gate of claim 6 , wherein:

each row of the matrix has a same number of random bits; and

the random bits in each row are distinct.

8. The masked logic gate of claim 4 , where d=2 and the first input is configured to receive 3 shares, wherein the masked logic gate has three output shares (z 0 , z 1 , z 2 ) corresponding respectively to three slices of the matrix, and the matrix has 9 rows and 3 columns, and wherein:

the group of independent random bits includes 6 random bits r 0 , r 2 . . . r 5 ;

each random bit in the range r 0 -r 2 occurs twice in each of two of the three slices and does not occur in the remaining slice;

each random bit in the range r 3 -r 5 occurs once in each of two of the three slices, and does not occur in the remaining slice;

the pair of used random bits from the range r 0 -r 2 is different in each slice; and

the pair of used random bits from the range r 3 -r 5 is different in each slice.

9. A masked logic gate comprising:

a first input configured to receive a number of shares yj (j=0, 1, 2 . . . );

a second input configured to receive (d+1) 2 shares xi (i=0, 1, 2 . . . ) representative of an intermediate result output by one layer of a tree of gates implementing low-latency masking with a protection order of d, where d is an integer at least equal to 1 representing the protection order; and

a (d+1)-share output obtained by applying a logic function of the masked logic gate to the shares of the first and second inputs using domain-oriented masking.

10. The masked logic gate of claim 9 , wherein the first input is also configured to receive (d+1) 2 shares representative of an intermediate result output by one layer of a tree of gates implementing low-latency masking with the protection order of d.

11. The masked logic gate of claim 9 , wherein the first input is configured to receive d+1 shares of an input variable.

12. The masked logic gate of claim 9 , having a structure representable by a matrix having (d+1) 2 rows assigned respectively to the shares xi of the second input, and a number of columns assigned respectively to the shares yj of the first input, the structure comprising:

for each cell (i, j) of the matrix, an elementary gate of a same type connected to operate on the shares xi and yj;

for each cell (i, j) in a subset of cells of the matrix, a random bit selected in a group of independent random bits (r 0 , r 1 , r 2 . . . ), and an XOR gate connected to inject the random bit in the output of the corresponding elementary gate, wherein the random bits are selected such that any random bit occurs an even number of times in the matrix; and

for each slice of d+1 rows of the matrix, a respective tree of XOR gates producing a corresponding output share (z 0 , z 1 , z 2 ) of the masked logic gate from all the cells of the slice.

13. The masked logic gate of claim 12 , wherein the XOR gates of the tree are connected such that any XOR gate of the tree receives at least one random bit an odd number of times.

14. The masked logic gate of claim 12 , where d=2 and the first input is configured to receive 9 shares, wherein the masked logic gate has three output shares (z 0 , z 1 , z 2 ) corresponding respectively to three slices of the matrix, and the matrix has 9 rows and 9 columns, and wherein:

the group of independent random bits includes 12 random bits r 0 , r 2 . . . r 11 ;

a same random bit from the range r 0 -r 8 occurs three times in each of two of the three slices and does not occur in the remaining slice; and

a same random bit from the range r 9 -r 11 occurs twice in each of the slices, but does not occur in the matrix an even number of times in a same column, nor in a same 3×3 square.

15. The masked logic gate of claim 14 , wherein:

each row of the matrix has a same number of random bits; and

the random bits in each row are distinct.

16. The masked logic gate of claim 12 , wherein d=2 and the first input is configured to receive 3 shares, wherein the masked logic gate has three output shares (z 0 , z 1 , z 2 ) corresponding respectively to three slices of the matrix, and the matrix has 9 rows and 3 columns, and wherein:

the group of independent random bits includes 6 random bits r 0 , r 2 . . . r 5 ;

each random bit in the range r 0 -r 2 occurs twice in each of two of the three slices and does not occur in the remaining slice;

each random bit in the range r 3 -r 5 occurs once in each of two of the three slices, and does not occur in the remaining slice;

the pair of used random bits from the range r 0 -r 2 is different in each slice; and

the pair of used random bits from the range r 3 -r 5 is different in each slice.