Apparatus and method for cryptography secure against side-channel attacks

1 . A method of encrypting an input, the encrypting including performing a plurality of operations, the plurality of operations including a plurality of first operations and at least one second operation dependent on the plurality of first operations, the method comprising:

randomly selecting a first operation from a first operation list, the first operation list including first operations, among the plurality of first operations, for which operands are prepared;

generating a first result by performing the randomly selected first operation based on the input;

updating the first operation list based on the randomly selected first operation; and

updating a second operation list based on the randomly selected first operation, the second operation list including the at least one second operation,

wherein the plurality of first operations and the at least one second operation are operations for the encrypting the input and generating an encrypted output.

2 . The method of claim 1 , wherein the randomly selecting the first operation comprises:

generating a random number; and

identifying the randomly selected first operation from the first operation list based on the random number.

3 . The method of claim 1 , wherein the generating the first result comprises:

generating at least one random number; and

generating and masking the first result by performing an operation having operands including the operands of the randomly selected first operation and the at least one random number such that the first result is independent from the at least one random number.

4 . The method of claim 1 ,

wherein the at least one second operation has an operand including a result of the randomly selected first operation.

5 . The method of claim 1 , wherein the updating the second operation list comprises:

identifying a second operation, among the at least one second operation, for which operands, including the result of the randomly selected first operation, are prepared;

removing the identified second operation from the second operation list; and

adding at least one third operation to the second operation list, the at least one third operation having an operand including a result of the identified second operation.

6 . The method of claim 5 , wherein the updating the first operation list comprises:

removing the randomly selected first operation from the first operation list; and adding the identified second operation to the first operation list.

7 . The method of claim 1 , wherein the plurality of operations are included in a number theoretic transform (NTT).

8 . The method of claim 7 , wherein the first operation list includes at least two first operations included in different stages of the NTT.

9 . The method of claim 1 , further comprising:

randomly selecting an additional first operation from the first operation list, the additional first operation being different from the first operation; and

generating a second result by performing the selected additional first operation, wherein the generating the first result and the generating the second result are performed in parallel.

10 . A device configured to perform a plurality of operations, the plurality of operations including a plurality of first operations and at least one second operation dependent on the plurality of first operations, the device comprising:

a non-transitory memory storing a first operation list including first operations, among the plurality of first operations, for which operands are prepared; and

processing circuitry configured to encrypt an input by

accessing the non-transitory memory,

randomly selecting a first operation, from the first operation list,

generate a first result by performing the randomly selected first operation based on the input,

updating the first operation list based on the randomly selected first operation, and

updating a second operation list based on the randomly selected first operation, the second operation list including the at least one second operation,

wherein the plurality of first operations and the at least one second operation are operations for the encrypting the input and generating an encrypted output.

11 . The device of claim 10 , wherein the processing circuitry is further configured to

generate a random number, and

identify the randomly selected first operation from the first operation list based on the random number.

12 . The device of claim 10 , wherein the processing circuitry is further configured to

generate at least one random number, and

generate the first result by performing an operation having operands including the operands of the randomly selected first operation and the at least one random number such that the first result is independent from the at least one random number.

13 . A device configured to perform a plurality of operations, the plurality of operations including a plurality of first operations and at least one second operation dependent on the plurality of first operations, the device comprising:

a non-transitory memory storing a first operation list including first operations, among the plurality of first operations, for which operands are prepared; and

processing circuitry configured to encrypt an input by

generating at least one first random number,

accessing the non-transitory memory,

selecting a first operation, from the first operation list, based on the at least one first random number,

updating the first operation list, based on the selected first operation,

producing a first result by performing the selected first operation, and

updating a second operation list based on the selected first operation, the second operation list including the at least one second operation,

wherein the plurality of first operations and the at least one second operation are operations for the encrypting the input and generating an encrypted output.

14 . The device of claim 13 , wherein the processing circuitry is further configured to

generate at least one second random number,

generate the first result by performing an operation having operands including the operands of the selected first operation and the at least one second random number such that the first result is independent from the at least one second random number.

15 . The device of claim 13 , wherein

the second operation list is stored in the non-transitory memory, and

the processing circuitry is configured to update the second operation list based on the selected first operation.

16 . The device of claim 15 , wherein the processing circuitry is further configured to

identify a second operation, among the at least one second operation, for which operands, including the result of the selected first operation, are prepared,

remove the identified second operation from the second operation list, and

add at least one third operation, to the second operation list, the at least one third operation having an operand including a result of the identified second operation.

17 . The device of claim 16 , wherein the processing circuitry is configured to update the first operation list by removing the selected first operation from the first operation list and adding the identified second operation to the first operation list.

18 . The device of claim 13 , wherein the plurality of operations are included in a number theoretic transform (NTT).

19 . The device of claim 18 , wherein the first operation list includes at least two first operations included in different stages of the NTT.

20 . The device of claim 13 , wherein the processing circuitry is configured to

select an additional first operation, different from the first operation, from the first operation list, based on the at least one first random number, and

generate a second result by performing the selected additional first operation such that the first result and the second result are generated in parallel.