Constant time secure arithmetic-to-Boolean mask conversion

Patent metadata

Field	Value
Publication number	US-11822704-B2
Application number	US-201917290027-A
Country	US
Kind code	B2
Filing date	Oct 28, 2019
Priority date	Oct 29, 2018
Publication date	Nov 21, 2023
Grant date	Nov 21, 2023

Abstract

A first arithmetic input share and a second arithmetic input share of an initial arithmetically-masked cryptographic value are received. A sequence of operations using the arithmetic input shares and a randomly generated number is performed, where a current operation in the sequence of operations generates a corresponding intermediate value that is used in a subsequent operation. At the end of the sequence of operations, a first Boolean output share and a second Boolean output share are generated. The arithmetic-to-Boolean mask conversion is independent of the input bit length.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving an indication that an initial cryptographic value created using an arithmetic operation is to be converted into a modified cryptographic value that is compatible with Boolean operations, wherein the initial cryptographic value comprises an underlying secret value that is arithmetically masked using a first random number as a mask;
receiving a first arithmetic input share and a second arithmetic input share of the initial cryptographic value, wherein each of the first and the second arithmetic input shares has a bit length equal to a bit length of the initial cryptographic value;
generating a second random number whose bit length is the same as the bit length of each of the first and the second arithmetic input shares;
performing a sequence of operations using the arithmetic input shares and the second random number to generate a first Boolean output share and a second Boolean output share at the end of the sequence of operations, wherein a current operation in the sequence of operations generates a corresponding intermediate value that is used in a subsequent operation in the sequence of operations; and
performing the Boolean operations on both the first Boolean output share and the second Boolean output share independently to create the modified cryptographic value that is Boolean masked.

2. The method of claim 1 , wherein the initial cryptographic value is obtained by arithmetically adding the first random number ‘r’ with the underlying secret value ‘x’.

3. The method of claim 2 , further comprising:
prior to performing the sequence of operations, fixing a least significant bit of the initial cryptographic value to be 1 to ensure that both the initial cryptographic value and the underlying secret value ‘x’ are odd irrespective of a value of the first random number ‘r’.

4. The method of claim 3 , further comprising:
prior to performing the sequence of operations, correcting the first random number ‘r’ by adding a complement of a least significant bit of the underlying secret value to the initial cryptographic value.

5. The method of claim 4 , further comprising:
after performing the sequence of operations, correcting a result of a final operation of the sequence of operations by replacing a least significant bit of an output value of the final operation with a least significant bit of the initial cryptographic value.

6. The method of claim 1 , wherein the initial cryptographic value is obtained by arithmetically subtracting the first random number ‘r’ from the underlying secret value ‘x’.

7. The method of claim 6 , further comprising:
prior to performing the sequence of operations, selecting an even value for the underlying secret value ‘x’.

8. The method of claim 1 , wherein performing the Boolean operation comprises:
performing XOR operations independently on the first Boolean output share and the second Boolean output share to create the modified cryptographic value that is Boolean masked.

9. The method of claim 1 , wherein a number of operations in the sequence of operations is independent of the bit length of the first and the second arithmetic input shares.

10. The method of claim 1 , wherein the bit length of the first and the second arithmetic input shares is one or more words.

11. The method of claim 1 , wherein each of the intermediate values or any combination of intermediate values is statistically independent of the underlying secret value.

12. The method of claim 1 , wherein none of the operations in the sequence of operations requires any pre-computation.

13. The method of claim 1 , wherein each of the operations in the sequence of operations has a same bit length as other operations in the sequence of operations, irrespective of whether the operation is performed on arithmetic intermediate values or Boolean intermediate values.

14. A system comprising:
a memory; and
a computer processor operatively coupled with the memory, to:
receive an indication that an initial cryptographic value created using an arithmetic operation is to be converted into a modified cryptographic value that is compatible with Boolean operations, wherein the initial cryptographic value comprises an underlying secret value that is arithmetically masked using a first random number as a mask;
receive a first arithmetic input share, and a second arithmetic input share of the initial cryptographic value, wherein both the first and the second arithmetic input shares have a bit length equal to a bit length of the initial cryptographic value;
generate a second random number whose bit length is the same as the bit length of the first and the second arithmetic input shares;
perform a sequence of operations using the arithmetic input shares and the second random number to generate a first Boolean output share and a second Boolean output share at the end of the sequence of operations, wherein a current operation in the sequence of operations generates a corresponding intermediate value that is used in a subsequent operation in the sequence of operations; and
perform the Boolean operations on both the first Boolean output share and the second Boolean output share independently to create the modified cryptographic value that is Boolean masked.

15. The system of claim 14 , wherein the initial cryptographic value is obtained by arithmetically adding the first random number with the underlying secret value.

16. The system of claim 15 , wherein the underlying secret value is odd.

17. The system of claim 14 , wherein the initial cryptographic value is obtained by arithmetically subtracting the first random number from the underlying secret value.

18. The system of claim 17 , wherein the underlying secret value is even.

19. The system of claim 14 , wherein the Boolean operations the processing device performs are XOR operations performed independently on the first Boolean output share and the second Boolean output share to create the modified cryptographic value that is Boolean masked.

20. The system of claim 14 , wherein a number of operations in the sequence of operations is independent of the bit length of the first and the second arithmetic input shares.

Assignees

• Cryptography Res Inc

Inventors

• Hutter Michael
• Tunstall Michael

Classifications

• G06F21/72 Primary

  in cryptographic circuits · CPC title

• G06F21/755

  with measures against power attack · CPC title

• H04L9/003

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• H04L9/0662

  with particular pseudorandom sequence generator · CPC title