Method of operation for a configurable number theoretic transform (NTT) butterfly circuit for homomorphic encryption

1. A method of operation in a number theoretic transform (NTT) butterfly circuit, the circuit including a high input word path and a low input word path, the high input word path including a first adder/subtractor, and a first multiplier, the low input word path including a second adder/subtractor, and a second multiplier, wherein the method comprises:

selectively bypassing the second adder/subtractor and the second multiplier; and

reconfiguring the low and high input word paths into different logic processing units in response to different mode control signals.

2. The method according to claim 1 , wherein the reconfiguring comprises:

in response to receiving a first mode control signal, configuring the NTT butterfly circuit to carry out a ciphertext (C txt ) addition function; and

in response to receiving a second mode control signal, configuring the NTT butterfly circuit to carry out a C txt multiplication function.

3. The method according to claim 1 , further comprising:

employing a combinational modular adder for each of the first and second adder/subtractors.

4. The method according to claim 1 , further comprising:

employing a parallel integer multiplier for each of the first and second multipliers.

5. The method according to claim 1 , wherein each of the first and second multipliers includes a reduction unit, and wherein the method further comprises:

operating each reduction unit.

6. The method of claim 1 , further comprising:

operating the NTT butterfly circuit as a single-stage butterfly unit.

7. The method of claim 6 , further comprising:

operating the NTT butterfly circuit to perform an initial NTT step followed by log 2 (n)−1 stages of evaluation by the NTT butterfly circuit, where “n” represents a degree of a polynomial associated with coefficient values.

8. A method of operation for a number theoretic transform (NTT) butterfly circuit including a high input word path, a low input word path, and selection circuitry having a control signal input, the method comprising:

for a first mode of operation,

configuring the high input word path and the low input word path into a first logic processing unit in response to the selection circuitry receiving a first control signal; and

for a second mode of operation,

configuring the high input word path and the low input word path into a second logic processing unit different than the first logic processing unit, the configuring carried out by the selection circuitry in response to receiving a second control signal different than the first control signal.

9. The method of claim 8 , further comprising:

for the first mode of operation, carrying out a ciphertext (C txt ) addition function with the first logic processing unit; and

for the second mode of operation, carrying out a C txt multiplication function with the second logic processing unit.

10. The method of claim 8 , further comprising:

selectively cross-coupling the high and low input word paths.

11. The method of claim 8 , wherein the high input word path includes a first adder/subtractor, and a first multiplier, and wherein the low input word path includes a second adder/subtractor, and a second multiplier, the method further comprising:

for the first mode of operation, selectively bypassing the first adder/subtractor and the first multiplier; and

for the second mode of operation, selectively bypassing the second adder/subtractor and the second multiplier.

12. The method of claim 11 , wherein the first adder/subtractor and the second adder/subtractor each comprises a regular add/subtract unit having an output, and wherein the method further comprises:

feeding the output to a modular reduction unit.

13. The method of claim 12 , further comprising:

employing a parallel adder as the regular add/subtract unit.

14. The method of claim 12 , further comprising:

employing, as the modular reduction unit, one from the group including a Barrett modular reduction unit, a special prime modular reduction unit, and a Montgomery modular multiplication unit.

15. The method of claim 10 , further comprising:

employing a modular adder as each of the first multiplier and the second multiplier.

16. The method of claim 10 , further comprising:

operating each of the first multiplier and the second multiplier as an integer multiplier having an output; and

feeding the output to a modular reduction unit.

17. The method of claim 16 , further comprising:

operating the integer multiplier as a parallel integer multiplier.