Secure NTT and INTT

A method for number theoretic transform (NTT) or inverse NTT (INTT) comprising:

• storing, at a memory and in addresses thereof, polynomial coefficients;
• controlling, by a controller coupled to the memory, which of the polynomial coefficients are read from the memory;
• generating, by a random number generator, a random number;
• shuffling, by a shuffle circuit coupled between the memory and butterfly operator circuits and based on the random number, an order in which the polynomial coefficients are provided to the butterfly operator circuits including which address of polynomial coefficients is provided to the butterfly operator circuits;
• receiving, by butterfly operator circuits, the polynomial coefficients, a first subset of the butterfly operator circuits situated in series with each other and in parallel with a second subset of the butterfly operator circuits;
• generating, after iterations of operating on the polynomial coefficients by the butterfly operator circuits, transformed coefficients as outputs;
• and
• controlling, by the controller, which addresses of the memory are written to and store the outputs, including the transformed coefficients.

A system for number theoretic transform (NTT) or inverse NTT (INTT) comprising:

• a memory configured to store a plurality of polynomial coefficients in a plurality of addresses thereof;
• butterfly operator circuits coupled to receive the polynomial coefficients and generate, after iterations of operating on the polynomial coefficients, transformed coefficients as outputs, a first subset of the butterfly operator circuits situated in series with each other and in parallel with a second subset of the butterfly operator circuits;
• a random number generator configured to generate a random number;
• a shuffle circuit coupled between the memory and the butterfly operator circuits, the shuffle circuit configured to select, based on the random number, which address of polynomial coefficients is provided to the butterfly operator circuits and an order in which each polynomial coefficient of the polynomial coefficients is provided to the butterfly operator circuits;
• and
• a controller coupled to the memory, the controller configured to control which coefficients are provided to the shuffle circuit and which addresses of the memory store the outputs.