Method of optimizing linear transformation

1 . A method for optimizing compute runtime and memory footprint of a linear transformation process, comprising:

determining a set of optimal rotation parameters, wherein the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; wherein the linear transformation process is a linear transformation of a ciphertext by a matrix with nonzero diagonals; wherein the rotation parameters include: a number of baby steps (β), a number of giant steps (γ), a boosting factor (bf), and a ConAcc activation flag; wherein the ConAcc activation flag indicates whether a contiguous accumulation routine is utilized as part of the linear transformation process; and wherein the optimal tradeoff comprises selecting, among configurations that satisfy a hardware memory constraint, one with a shortest program runtime;

initializing the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, wherein the at least one iteration is based on the determined set of optimal rotation parameters and at least one key switching key (KSK), and wherein the boosting factor (bf) defines a number of key switching keys (KSKs) used in the at least one iteration; and

loading the initialized linear transformation process to an internal memory of a hardware accelerator.

2 . The method of claim 1 , further comprising: determining the optimal rotation parameters based on a size of the internal memory, hardware constraints of the hardware accelerator including a total memory limit for the hardware processing capabilities, a number of accelerators, multipliers, and CPU cores, and global parameters of a program including the linear transformation process.

3 . The method of claim 2 , wherein determining the optimal rotation parameters further comprises:

generating a plurality of configurations based on possible combinations of the global program parameters, including rotation parameters;

evaluating runtime compute resources and memory footprint required for each configuration of the plurality of configurations; and

selecting a configuration out of the plurality of configurations that satisfies the hardware memory constraint and has the shortest program runtime.

4 . The method of claim 3 , wherein the runtime compute resources are based in part on a number of digit decomposition operations, including number-theoretical transforms (NTTs) and multiplications.

5 . The method of claim 1 , further comprising:

initializing the boosting technique to perform a contiguous accumulation routine, when the ConAcc activation flag is set to true.

6 . The method of claim 5 , wherein performing the contiguous accumulation routine further comprises:

generating β ciphertext outputs one by one; and for each generated ciphertext output, accumulating the ciphertext output's contribution to each of γ accumulator ciphertexts corresponding to γ partial sums by computing the products of the ciphertext output by associated diagonals.

7 . The method of claim 6 , wherein the contiguous accumulation routine further comprises: reducing peak memory footprint in the process of multiplying diagonals by rotated ciphertext and summing products resulting from the multiplying during runtime.

8 . The method of claim 1 , wherein performing the at least one iteration further comprises:

computing one digit decomposition phase that generates temporary polynomials in a larger modulus QP from coefficients of an input polynomial;

computing a number of bf MultSum phases with bf KSKs, each MultSum phase computing two inner products between a decomposed array of polynomials and respective parts of a KSK; and

computing a number of bf permute phases of two ciphertext polynomials, wherein each MultSum phases outputs two ciphertext polynomials for the permute phases, and wherein each permute phase deterministically rearranges elements of a polynomial according to a parameter r to encode a rotation.

9 . The method of claim 8 , further comprising:

spanning a set of nonzero diagonal indices of a matrix representing the linear transformation using a set of baby step rotations (B) and a set of giant step rotations (G).

10 . The method of claim 1 , wherein the linear transformation process is executed as part of an fully homomorphic encryption (FHE) program, and wherein the hardware accelerator is an FHE fully homomorphic encryption (FHE) accelerator having an on-die memory as the internal memory.

11 . A non-transitory computer-readable medium storing a set of instructions for optimizing compute runtime and memory footprint of a linear transformation process, the set of instructions comprising:

one or more instructions that, when executed by one or more processors of a device, cause the device to:

determine a set of optimal rotation parameters, wherein the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; wherein the linear transformation process is a linear transformation of a ciphertext by a matrix with nonzero diagonals; wherein the rotation parameters include: a number of baby steps (β), a number of giant steps (γ), a boosting factor (bf), and a ConAcc activation flag; wherein the ConAcc activation flag indicates whether a contiguous accumulation routine is utilized as part of the linear transformation process; and wherein the optimal tradeoff comprises selecting, among configurations that satisfy a hardware memory constraint, one with the shortest program runtime;

initialize the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, wherein the at least one iteration is based on the determined of set optimal rotation parameters and at least one key switching key (KSK), and wherein the boosting factor (bf) defines a number of key switching keys (KSKs) used in the at least one iteration; and

load the initialized linear transformation process to an internal memory of a hardware accelerator.

12 . A system for optimizing compute runtime and memory footprint of a linear transformation process comprising:

one or more processors configured to:

determine a set of optimal rotation parameters, wherein the optimal rotation parameters provide an optimal tradeoff between runtime compute resources and a memory footprint for a runtime execution of the linear transformation process; wherein the linear transformation process is a linear transformation of a ciphertext by a matrix with nonzero diagonals; wherein the rotation parameters include: a number of baby steps (β), a number of giant steps (γ), a boosting factor (bf), and a ConAcc activation flag; wherein the ConAcc activation flag indicates whether a contiguous accumulation routine is utilized as part of the linear transformation process; and wherein the optimal tradeoff comprises selecting, among configurations that satisfy a hardware memory constraint, one with the shortest program runtime;

initialize the linear transformation process to run a boosting technique with the determined set of optimal rotation parameters, wherein the boosting technique, when executed at runtime as part of the linear transformation process, performs at least one iteration that yields rotated ciphertexts, wherein the at least one iteration is based on the determined set optimal rotation parameters and at least one key switching key (KSK), and wherein the boosting factor (bf) defines a number of key switching keys (KSKs) used in the at least one iteration; and

load the initialized linear transformation process to an internal memory of a hardware accelerator.

13 . The system of claim 12 , wherein the one or more processors are further configured to:

determine the optimal rotation parameters based on a size of the internal memory, hardware constraints of the hardware accelerator including a total memory limit for the hardware processing capabilities, a number of accelerators, multipliers, and CPU cores, and global parameters of a program, including the linear transformation process.

14 . The system of claim 13 , wherein the one or more processors, when determining the optimal rotation parameters, are configured to:

generate a plurality of configurations based on possible combinations of the global program parameters, including rotation parameters;

evaluate runtime compute resources and memory footprint required for each configuration of the plurality of configurations; and

select a configuration out of the plurality of configurations that satisfies the hardware memory constraint and has the shortest program runtime.

15 . The system of claim 14 , wherein the runtime compute resources are based in part on a number of digit decomposition operations, including number-theoretical transforms (NTTs) and multiplications.

16 . The system of claim 12 , wherein the one or more processors are further configured to:

initialize the boosting technique to perform a contiguous accumulation routine, when the ConAcc activation flag is set to true.

17 . The system of claim 16 , wherein the one or more processors, when performing the contiguous accumulation routine, are configured to:

generate β ciphertext outputs one by one; and for each generated ciphertext output, accumulate the ciphertext output's contribution to each of γ accumulator ciphertexts corresponding to γ partial sums by computing the products of the ciphertext output by associated diagonals.

18 . The system of claim 17 , wherein the one or more processors, when performing the contiguous accumulation routine, are further configured to:

reduce peak memory footprint in the process of multiplying diagonals by rotated ciphertext and summing products resulting from the multiplying during runtime.

19 . The system of claim 12 , wherein the one or more processors, when performing the at least one iteration, are configured to:

compute one digit decomposition phase that generates temporary polynomials in a larger modulus QP from coefficients of an input polynomial;

compute a number of bf MultSum phases with bf KSKs, each MultSum phase computing two inner products between a decomposed array of polynomials and respective parts of a KSK; and

compute a number of bf permute phases of two ciphertext polynomials, wherein each MultSum phases two ciphertext polynomials for the permute phases, and wherein each permute phase deterministically rearranges elements of a polynomial according to a parameter r to encode a rotation.

20 . The system of claim 19 , wherein the one or more processors are further configured to:

span a set of nonzero diagonal indices of a matrix representing the linear transformation using a set of baby step rotations (B) and a set of giant step rotations (G).

21 . The system of claim 12 , wherein the linear transformation process is executed as part of an fully homomorphic encryption (FHE) program, and the hardware accelerator is an fully homomorphic encryption (FHE) accelerator having an on-die memory as the internal memory.