Method of optimizing linear transformation

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.

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.