Increasing the speed of homomorphic encryption encoding
Mechanisms are provided for increasing the speed of an encoding process. The mechanisms classify operations in the encoding process based on learned associations between patterns of input data and corresponding encoding result types generated from encoding the patterns of input data. The mechanisms identify operations in the encoding process that can be pruned based on the classifications, to thereby generate a set of prune operations. In addition, the mechanisms replace operations in the set of prune operations with replacement operations that retrieve a corresponding previously generated result. Moreover, the mechanisms emit optimized encoding code comprising the replacement operations in replacement of the set of prune operations that are pruned, for execution of the encoding process using the optimized encoding code.
1 . A computer-implemented method, in a data processing system, for increasing a speed of an encoding process, the method comprising:
classifying non-optimized operations in the encoding process into classifications based on learned associations between patterns of input data and corresponding encoding result types generated from encoding the patterns of input data;
identifying non-optimized operations in the encoding process that can be replaced based on the classifications, to thereby generate a set of prune operations;
replacing identified non-optimized operations in the set of prune operations with replacement optimized operations that retrieve a corresponding previously generated result; and
emitting optimized encoding code comprising the replacement optimized operations in replacement of the set of prune operations that are replaced, such that a speed of an execution of the encoding process using the optimized encoding code is increased relative to the speed of the execution of the encoding process using non-optimized code.
2 . The computer-implemented method of claim 1 , wherein the replacement optimized operations comprise a copy operation, a copy-conjugate operation, or an assignment operation for assigning a result value to a predetermined value.
3 . The computer-implemented method of claim 1 , wherein the encoding process corresponds to original encoding code provided by an orchestrator computing system, and wherein the optimized encoding code is output to a client computing device for execution on the client computing device as part of an encoder that encodes an input workload for homomorphic encryption operations.
4 . The computer-implemented method of claim 3 , wherein the encoder operates to compare first metadata of the input workload to second metadata associated with the optimized encoding code, and in response to the first metadata matching the second metadata, the optimized encoding code is executed on the input workload to encode the input workload.
5 . The computer-implemented method of claim 1 , wherein the learned associations between the patterns of input data and corresponding encoding result types comprises patterns of metadata specifying a structure of the input data that correspond to encoding operations whose results are duplicative of other encoding operations or whose results are a zero value.
6 . The computer-implemented method of claim 5 , wherein the duplicative operations comprise duplicate conjugate operations.
7 . The computer-implemented method of claim 1 , wherein the optimized encoding code comprises at least one of an optimized Discrete Fourier Transform (DFT) algorithm, an optimized scale-and-round algorithm, an optimized Number Theoretic Transform (NTT) algorithm, or a mask for an optimized hardware implementation of one or more of the DFT, scale-and-round, or NTT algorithms.
8 . The computer-implemented method of claim 1 , wherein the encoding process is a homomorphic encryption (HE) encoding process executed by a HE circuit.
9 . The computer-implemented method of claim 1 , wherein the classifying, identifying, and replacing operations are performed for a client specified encoding process comprising a discrete Fourier transform (DFT) operation, a scale-and-round operation, and a Number Theoretic Transform (NTT) operation, and wherein the classifying, identifying, and replacing operations are repeated for each of the DFT operation, the scale-and-round operation, and the NTT operation.
10 . The computer-implemented method of claim 9 , where the DFT or the NTT operation operate over mathematical structures defined by a homomorphic encryption scheme.
11 . A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed in a data processing system, causes the data processing system to:
classify non-optimized operations in the encoding process into classifications based on learned associations between patterns of input data and corresponding encoding result types generated from encoding the patterns of input data;
identify non-optimized operations in the encoding process that can be pruned based on the classifications, to thereby generate a set of prune operations;
replace identified non-optimized operations in the set of prune operations with replacement optimized operations that retrieve a corresponding previously generated result; and
emit optimized encoding code comprising the replacement optimized operations in replacement of the set of prune operations that are replaced, such that a speed of an execution of the encoding process using the optimized encoding code is increased relative to the speed of the execution of the encoding process using non-optimized code.
12 . The computer program product of claim 11 , wherein the replacement optimized operations comprise a copy operation, a copy-conjugate operation, or an assignment operation for assigning a result value to a predetermined value.
13 . The computer program product of claim 11 , wherein the encoding process corresponds to original encoding code provided by an orchestrator computing device, and wherein the optimized encoding code is output to a client computing device for execution on the client computing device as part of an encoder that encodes an input workload for homomorphic encryption operations.
14 . The computer program product of claim 13 , wherein the encoder operates to compare first metadata of the input workload to second metadata associated with the optimized encoding code, and in response to the first metadata matching the second metadata, the optimized encoding code is executed on the input workload to encode the input workload.
15 . The computer program product of claim 11 , wherein the learned associations between the patterns of input data and corresponding encoding result types comprises patterns of metadata specifying a structure of the input data that correspond to encoding operations whose results are duplicative of other encoding operations or whose results are a zero value.
16 . The computer program product of claim 15 , wherein the duplicative operations comprise duplicate conjugate operations.
17 . The computer program product of claim 11 , wherein the optimized encoding code comprises at least one of an optimized Discrete Fourier Transform (DFT) algorithm, an optimized scale-and-round algorithm, an optimized Number Theoretic Transform (NTT) algorithm, or a mask for an optimized hardware implementation of one or more of the DFT, scale-and-round, or NTT algorithms.
18 . The computer program product of claim 11 , wherein the encoding process is a homomorphic encryption (HE) encoding process executed by a HE circuit.
19 . The computer program product of claim 11 , wherein the classifying, identifying, and replacing operations are performed for a client specified encoding process comprising a discrete Fourier transform (DFT) operation, a scale-and-round operation, and a Number Theoretic Transform (NTT) operation, and wherein the classifying, identifying, and replacing operations are repeated for each of the DFT operation, the scale-and-round operation, and the NTT operation.
20 . An apparatus comprising:
at least one processor; and
at least one memory coupled to the at least one processor, wherein the at least one memory comprises instructions which, when executed by the at least one processor, cause the at least one processor to:
classify non-optimized operations in the encoding process into classifications based on learned associations between patterns of input data and corresponding encoding result types generated from encoding the patterns of input data;
identify non-optimized operations in the encoding process that can be pruned based on the classifications, to thereby generate a set of prune operations;
replace identified non-optimized operations in the set of prune operations with replacement optimized operations that retrieve a corresponding previously generated result; and
emit optimized encoding code comprising the replacement optimized operations in replacement of the set of prune operations that are replaced, such that a speed of an execution of the encoding process using the optimized encoding code is increased relative to the speed of the execution of the encoding process using non-optimized code.