Secure NTT and INTT
Devices, systems, and methods for secure number theoretic transform (NTT) and inverse NTT (INTT) operations are provided. A circuit includes a memory configured to store polynomial coefficients, 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, and a shuffle circuit coupled between the memory and the butterfly operator circuits, the shuffle circuit configured to change an order in which the polynomial coefficients are provided to the butterfly operator circuits.
1 . A circuit for number theoretic transform (NTT) or inverse NTT (INTT) comprising:
a memory configured to store polynomial coefficients in 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; and
a shuffle circuit coupled between the memory and the butterfly operator circuits, the shuffle circuit configured to change, 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.
2 . The circuit of claim 1 , further comprising a buffer situated to store the polynomial coefficients in shuffled order.
3 . The circuit of claim 2 , wherein the buffer includes a number of entries, the number of entries sufficient to store polynomial coefficients for multiple iterations of operating the butterfly operator circuits.
4 . The circuit of claim 1 , wherein the shuffle circuit is further configured to select, based on the random number, the order in which each polynomial coefficient of the polynomial coefficients is provided to the butterfly operator circuits.
5 . The circuit of claim 1 , wherein the shuffle circuit includes a delay component configured to delay the random number by a specified number of clock cycles.
6 . The circuit of claim 5 , wherein the specified number of clock cycles is greater than, or equal to, number of clock cycles used by the butterfly operator circuits in generating an output.
7 . The circuit of claim 1 further comprising 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.
8 . 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.
9 . The method of claim 8 , further comprising storing, at a buffer, the polynomial coefficients in shuffled order.
10 . The method of claim 9 , wherein the buffer includes a number of entries, the number of entries sufficient to store polynomial coefficients for multiple iterations of operating the butterfly operator circuits.
11 . The method of claim 8 , further comprising selecting, by the shuffle circuit and based on the random number, the order in which each polynomial coefficient of the polynomial coefficients is provided to the butterfly operator circuits.
12 . The method of claim 8 , further comprising delaying, by a delay component of the shuffle circuit, the random number by a specified number of clock cycles.
13 . The method of claim 12 , wherein the specified number of clock cycles is greater than, or equal to, number of clock cycles used by the butterfly operator circuits in generating an output.
14 . 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.
15 . The system of claim 14 , further comprising a buffer situated to store the polynomial coefficients in shuffled order.
16 . The system of claim 15 , wherein the buffer includes a number of entries, the number of entries sufficient to store polynomial coefficients for multiple iterations of operating the butterfly operator circuits.