Method and system for reducing FFT calculations in FHE bootstrapping

A system to perform bootstrapping in a Fully Homomorphic Encryption (FHE) computational operation on an input ciphertext, the system comprising:

• a processor performing the FHE computational operation on the input ciphertext to produce an output ciphertext;
• a first processing core configured to perform a fast Fourier transfer (FFT) on a vector of n ciphertext samples of the output ciphertext and a bootstrap key;
• an interconnection network coupled to the first processing core;
• a second processing core coupled to the interconnection network, the second processing core configured to determine a phase vector of n W(a) terms, without performing an FFT for each of the terms of the vector of the samples, wherein the W(a) terms are equivalents of FFT outputs of performing an FFT of each of the terms of the vector of the samples;
• a third processing core coupled to the interconnection network, the third processing core configured to perform a first set of pointwise multiplications of the FFT of the first vector of samples with each of the W(a) terms in the phase vector;
• and a second set of pointwise multiplications of the results of the first set of pointwise multiplications with the FFT of the bootstrap key;
• and
• a fourth processing core coupled to the interconnection network, the fourth processing core configured to perform an inverse FFT (IFFT) on an accumulated result of the second set of point-wise multiplications to obtain a bootstrapping result of the output ciphertext.

A non-transitory computer readable medium having stored thereon instructions that, when executed by a processor unit, cause the processor unit to:

• perform a Fully Homomorphic Encryption (FHE) computational operation on input ciphertext to produce an output ciphertext;
• separate the output ciphertext into a vector of n samples;
• perform a fast Fourier transfer (FFT) over a first vector of the samples;
• perform a FFT over a bootstrap key;
• determine a phase vector of n W(a) terms, without performing an FFT for each of the terms of the vector of the samples, wherein the W(a) terms are equivalents of FFT outputs of performing an FFT of each of the terms of the vector of the samples;
• perform a first set of pointwise multiplications of the FFT of the first vector of samples with each of the W(a) terms in the phase vector;
• perform a second set of pointwise multiplications of the results of the first set of pointwise multiplications with the FFT of the bootstrap key;
• and
• perform an inverse FFT (IFFT) on an accumulated result of the second set of point-wise multiplications to obtain a bootstrapping result of the output ciphertext.