Memory conflict resolution for dilithium cryptography

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

• storing, at a memory, polynomial coefficients;
• controlling, by a controller coupled to the memory, which of the polynomial coefficients are read from the memory and provided to 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 comprising:

• a memory including polynomial coefficients stored thereon;
• butterfly operator circuits configured 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;
• first, second, third, and fourth shift registers with different depths coupled between the butterfly operator circuits and the memory;
• a first multiplexer configured to provide, based on a select control of the first multiplexer, contents of the first, second, third, and fourth shift registers in consecutive, respective clock cycles;
• and
• a controller coupled to the memory, the controller configured to control which coefficients are provided to the butterfly operator circuits and which addresses of the memory store the outputs, including the transformed coefficients.