Protecting number theoretic transform operations

A method of performing a Number Theoretic Transform (NTT) on an input vector x to determine an output vector y, the method comprising:

• providing, to a processor of a computing device, the input vector x, a check vector ct, a detection vector dt and a matrix T representing the NTT to be performed on the input vector x, wherein the detection vector dt is equal to a product of the check vector ct and the matrix T;
• computing, by the processor, a first check value as a product of the detection vector dt with the input vector x;
• computing, by the processor, the output vector y as the NTT of the input vector x;
• computing, by the processor, a second check value as a product of the check vector ct with the output vector y;
• and
• determining, by the processor, the NTT of the input vector x is correct if the first and second check values are equal to each other.

An apparatus for performing a cryptographic operation comprising an NTT operation on an input vector x to determine an output vector y, the apparatus comprising a processor configured to:

• determine the input vector x, a check vector ct, a detection vector dt and a matrix T representing the NTT operation to be performed on the input vector x, wherein the detection vector dt is equal to a product of the check vector ct and the matrix T;
• compute a first check value as a product of the detection vector dt with the input vector x;
• compute the output vector y as an NTT of the input vector x;
• compute a second check value as a product of the check vector ct with the output vector y;
• and
• determine the NTT of the input vector x is correct when the first check value and the second check value are equal to each other.

A computer program comprising instructions that, when executed, cause a processor to perform a Number Theoretic Transform (NTT) method on an input vector x to determine an output vector y, the method comprising:

• determining the input vector x, a check vector ct, a detection vector dt and a matrix T representing the NTT to be performed on the input vector x, wherein the detection vector dt is equal to a product of the check vector ct and the matrix T;
• computing a first check value as a product of the detection vector dt with the input vector x;
• computing the output vector y as an NTT of the input vector x;
• computing a second check value as a product of the check vector ct with the output vector y;
• and
• determining the NTT of the input vector x is correct when the first check value and the second check value are equal to each other.