Protection of transformations by intermediate randomization in cryptographic operations

A non-transitory computer-readable medium storing instruction thereon, wherein the instructions, when executed by a processing device performing a cryptographic operation that comprises a number theoretic transformation (NTT) of a first vector to a second vector, cause the processing device to:

• obtain components of the first vector;
• obtain one or more random numbers;
• perform a plurality of iterations, wherein in each of the plurality of iterations the processing device is to:
• determine a plurality of output values, wherein each of the plurality of output values is a linear combination of two or more input values;
• wherein (1) the input values into a first iteration of the plurality of iterations are the components of the first vector, (2) the input values into each subsequent iteration of the plurality of iterations are the output values of a previous iteration of the plurality of iterations, (3) the output values of the last of the plurality of iterations are representative of components of the second vector, and wherein one or more of the output values of a first randomized iteration of the plurality of iterations are randomized using a first randomization operation that comprises multiplying at least one input value into the first randomized iteration by a first random number of the one or more random numbers;
• and
• determine, based on the output values of the last of the plurality of iterations, the components of the second vector.

A system to perform a cryptographic operation that comprises a number theoretic transformation (NTT) of a first vector to a second vector, the system comprising:

• a memory device to store a first vector and a second vector;
• and
• a processing device coupled to the memory device, the processing device to:
• obtain components of the first vector;
• obtain one or more random numbers;
• perform a plurality of iterations, wherein in each of the plurality of iterations the processing device is to:
• determine a plurality of output values, wherein each of the plurality of output values is a linear combination of two or more input values;
• wherein (1) the input values into a first iteration of the plurality of iterations are the components of the first vector, (2) the input values into each subsequent iteration of the plurality of iterations are the output values of a previous iteration of the plurality of iterations, (3) the output values of the last of the plurality of iterations are representative of components of the second vector, and wherein one or more of the output values of a first randomized iteration of the plurality of iterations are randomized using a first randomization operation that comprises multiplying at least one input value into the first randomized iteration by a first random number of the one or more random numbers;
• and
• determine, based on the output values of the last of the plurality of iterations, the components of the second vector.