Optimizing encrypted computation parameters
Some embodiments are directed to a computer-implemented method of determining encrypted computation parameters for carrying out an encrypted computation on noisy ciphertexts. A computation graph is divided into multiple subgraphs, defined by a type and by instantiation parameters for the type. Respective sets of encrypted computation parameters are defined for the respective types. An optimization of the encrypted computation parameters is performed to minimize a computational cost of carrying out the encrypted computation according to the encrypted computation parameters. The encrypted computation parameters are constrained to satisfy a noise constraint on ciphertext noise while carrying out the encrypted computation. The noise constraint is based on respective noise constraints for respective subgraphs, defined by a noise constraint function for the type that takes at least the encrypted computation parameters for the type and the instantiation parameters of the subgraph as input.
1. A computer-implemented method ( 900 ) of determining encrypted computation parameters for carrying out an encrypted computation on noisy ciphertexts, comprising:
accessing ( 910 ) data representing a computation graph of the encrypted computation;
obtaining ( 920 ) a division of the computation graph into multiple subgraphs, wherein a subgraph represents a subcomputation resulting in an output ciphertext with an input-independent noise, and is defined by a type from a set of one or more types, and by zero or more instantiation parameters for the type;
defining ( 930 ) respective sets of encrypted computation parameters for the respective types;
performing ( 940 ) an optimization of the encrypted computation parameters, wherein:
the encrypted computation parameters are optimized to minimize a computational cost of carrying out the encrypted computation according to the encrypted computation parameters; and
the encrypted computation parameters are constrained to satisfy a noise constraint on ciphertext noise while carrying out the encrypted computation, wherein the noise constraint is based on respective noise constraints for respective subgraphs, wherein a noise constraint for a subgraph of a given type is defined by a noise constraint function for the given type that takes at least the encrypted computation parameters for the given type and the instantiation parameters of the subgraph as input,
determining, based on the instantiation parameters of a first and second subgraph, that the noise constraint for the first subgraph is at least as strict as the noise constraint for the second subgraph; and
eliminating the noise constraint for the second subgraph from the optimization.
2. The method ( 900 ) of claim 1 , wherein the first and second subgraph are parameterized by a noise bound and by a 2-norm of an applied linear map, and wherein noise bound of the first subgraph is at most the noise bound of the second subgraph and the 2-norm of the first subgraph is at least the 2-norm of the second subgraph.
3. The method ( 900 ) of claim 1 , wherein the computational cost is minimized based on a cost function, wherein the cost function is based on respective costs for respective subgraphs, wherein a cost for a subgraph of a given type is defined by a cost function for the given type that takes at least the encrypted computation parameters for the given type as input and is independent from the instantiation parameters.
4. The method ( 900 ) of claim 1 , wherein the encrypted computation parameters comprise one or more of: a decomposition base of a programmable bootstrapping, a decomposition level of a programmable bootstrapping, a decomposition base of a key switching, and a decomposition level of a key switching.
5. The method ( 900 ) of claim 1 , wherein a subgraph of the multiple subgraphs comprises a programmable bootstrapping resulting in an output ciphertext, and a noise rounding of the output ciphertext.
6. The method ( 900 ) of claim 1 , wherein the optimization of the encrypted computation parameters is performed by branch-and-bound.
7. The method ( 900 ) of claim 1 , wherein the encrypted computation parameters identify respective key switching and/or bootstrapping keys to be used for respective subgraphs, wherein, if the noise constraint for the first subgraph is at least as strict as the noise constraint for the second subgraph, the key switching and/or bootstrapping key for the first subgraph is constrained to add at most as much noise as the key switching and/or bootstrapping key for the second subgraph.
8. The method ( 900 ) of claim 1 , wherein the encrypted computation parameters indicate, for respective subgraphs in which respective linear maps are applied, a respective number of programmable bootstrappings to be performed during the application of the respective linear map.
9. The method ( 900 ) of claim 8 , further comprising splitting the respective linear map into a number of respective linear maps corresponding to the number of programmable bootstrappings by minimizing a maximal 2-norm of the respective linear maps.
10. The method ( 900 ) of claim 8 , wherein, if the noise constraint for the first subgraph is at least as strict as the noise constraint for the second subgraph, the number of programmable bootstrappings for the first subgraph is constrained to be greater than or equal to the number of programmable bootstrappings for the second subgraph.
11. The method ( 900 ) of claim 1 , further comprising:
transforming an unencrypted computation graph into the computation graph of the encrypted computation; and/or
compiling the computation graph of the encrypted computation into a set of instructions for an encrypted computation engine; and/or
carrying out the encrypted computation according to the determined encrypted computation parameters.
12. A transitory or non-transitory computer-readable storage medium ( 1000 ) comprising data ( 1020 ) representing instructions which, when executed by a processor system, cause the processor system to perform the method according to claim 1 ; and/or encrypted computation parameters and/or instructions for an encrypted computation engine determined.
13. A configuration device ( 110 ) for determining encrypted computation parameters for carrying out an encrypted computation on noisy ciphertexts, comprising:
a storage ( 130 ) for storing data representing a computation graph of the encrypted computation;
a processor subsystem ( 140 ) configured to:
obtain a division of the computation graph into multiple subgraphs, wherein a subgraph represents a subcomputation resulting in an output ciphertext with an input-independent noise, and is defined by a type from a set of one or more types, and by zero or more instantiation parameters for the type;
define respective sets of encrypted computation parameters for the respective types;
perform an optimization of the encrypted computation parameters, wherein: the encrypted computation parameters are optimized to minimize a computational cost of carrying out the encrypted computation according to the encrypted computation parameters; and the encrypted computation parameters are constrained to satisfy a noise constraint on ciphertext noise while carrying out the encrypted computation, wherein the noise constraint is based on respective noise constraints for respective subgraphs, wherein a noise constraint for a subgraph of a given type is defined by a noise constraint function for the given type that takes at least the encrypted computation parameters for the given type and the instantiation parameters of the subgraph as input,
determining, based on the instantiation parameters of a first and second subgraph, that the noise constraint for the first subgraph is at least as strict as the noise constraint for the second subgraph; and
eliminating the noise constraint for the second subgraph from the optimization.