CN120335815A - Method and device for generating fully homomorphic computing program - Google Patents

Abstract

The embodiment of the specification provides a method and a device for generating an isomorphic calculation program. The method comprises the steps of constructing a value flow graph according to homomorphic operations contained in a first homomorphic calculation program, enabling nodes to correspond to homomorphic operations, enabling directed edges to correspond to data transmission among the nodes, dividing the value flow graph into a plurality of partitions based on multiplication depths corresponding to the nodes respectively, traversing the partitions according to a topological sequence to execute the first operation, regarding a current partition as a source partition and a plurality of partition intervals of partitions which are target partitions respectively after the current partition, determining candidate positions for inserting target operations by adopting a minimum segmentation algorithm, determining target insertion positions for cutting off target operations of the target partitions according to the candidate positions, enabling the target operations to comprise a re-reduction operation and a bootstrap operation, and generating a second homomorphic calculation program according to the target insertion positions obtained through traversing.

Description

Method and device for generating isomorphic calculation program

Technical Field

One or more embodiments of the present specification relate to the field of computers, and more particularly, to methods and apparatus for generating isomorphic computing programs.

Background

Fully homomorphic encryption (fully homomorphic encryption, FHE) is a privacy computing technology, after encrypting plaintext data, homomorphic addition and homomorphic multiplication are carried out, decryption is carried out, and the result is the same as the result of directly carrying out addition and multiplication on the plaintext. Since the calculation process is performed in an encrypted state, the leakage of private data contained in the plaintext is avoided.

Full homomorphic encryption ensures encryption security by adding noise to the original plaintext data. Homomorphic multiplication can greatly increase noise levels, which can overwhelm the plaintext message after a certain depth of multiplication is performed, resulting in decryption failure. The noise increase speed is reduced by introducing a re-reduction (Rescale) operation, the supportable multiplication depth is increased, and a ciphertext containing higher noise is refreshed to a ciphertext containing lower noise by introducing a Bootstrapping (Bootstrapping) operation, so that multiplication operation of any depth can be performed.

In some scenarios, a plaintext calculation program is often determined first and then converted to a fully homomorphic calculation program, a process that may be referred to as compilation. At compile time, a re-reduction operation is inserted in the isomorphic calculation program to reduce the scale-up rate of the ciphertext, and a bootstrap operation is inserted to support more multiplication operations. At the same time, the insertion positions of the re-reduction operation and the bootstrap operation need to be optimized to optimize the execution efficiency of the encryption computation. In the prior art, a scheme which has short compiling time and high execution efficiency of the generated isomorphic computing program is lacking.

Disclosure of Invention

One or more embodiments of the present specification describe a method and apparatus for generating an isotactic computing program, which can shorten a compiling time and improve an execution efficiency of the isotactic computing program.

In a first aspect, there is provided a method of generating an isomorphic calculation program, the method comprising:

converting the plaintext calculation program into a first isomorphic calculation program;

Constructing a value flow graph according to each homomorphic operation contained in the first isomorphic computing program, wherein nodes in the value flow graph correspond to homomorphic operations, and directed edges in the value flow graph correspond to data transmission among the nodes;

Dividing the value flow graph into a plurality of partitions based on multiplication depths respectively corresponding to all nodes in the value flow graph;

traversing each partition according to a topological sequence to execute the first operation, wherein for a plurality of partition intervals taking a current partition as a source partition and a plurality of partitions after the current partition as target partitions, an increased value of the execution time of each homomorphic operation after the target operation is inserted is taken as an edge weight, a candidate position for inserting the target operation is determined by adopting a minimum cutting algorithm;

and generating a second isomorphic calculation program according to the target insertion position obtained through traversing.

In one possible embodiment, the constructing a value flow graph according to each homomorphic operation included in the first isomorphic calculation program includes:

For the loop of homomorphic multiplication operation contained in the first homomorphic calculation program, if the amplification factor of the output ciphertext of homomorphic multiplication operation in the loop is increased, expanding the loop;

Corresponding nodes are respectively constructed aiming at homomorphic operation in the loop and homomorphic operation outside the loop, and the execution times of the nodes are marked, wherein the execution times of the nodes in the loop are recorded as the circulation times, and the execution times of the nodes outside the loop are 1.

In a possible implementation manner, the dividing the value flow graph into a plurality of partitions based on multiplication depths corresponding to each node in the value flow graph includes:

Traversing each node forward according to the topological sequence of each node in the value flow graph, and calculating the initial multiplication depth of each node;

Traversing each node reversely according to the reverse topological sequence of each node in the value flow diagram, and updating the multiplication depth of each node to the maximum value allowed to obtain the optimized multiplication depth;

Nodes with the same optimized multiplication depth are divided into the same partition of the value flow graph.

Further, traversing each node in reverse according to the reverse topological order of each node in the value flow diagram, updating the multiplication depth of each node to the maximum value allowed to obtain the optimized multiplication depth, including:

traversing each node reversely according to the reverse topological sequence of each node in the value flow graph, and calculating the maximum multiplication depth allowed by the subsequent nodes of the current node under the topological sequence;

If the current node is a multiplication node and its multiplication depth is less than the maximum multiplication depth allowed by its successor nodes, the multiplication depth of the current node is updated, and the multiplication depths of all other nodes within the current multiplication depth that depend on the current node are updated.

In one possible implementation, the determining the candidate location for inserting the target operation using a cut-down algorithm includes:

Determining a first candidate location for inserting a bootstrap operation within the source partition based on a minimal cut algorithm;

For any partition, determining a first partition set needing to be inserted with a re-reduction operation from each partition between a source partition and a destination partition, and determining a second candidate position for inserting the re-reduction operation in each partition of the first partition set based on a minimum cut algorithm.

In a possible implementation manner, the determining, according to the candidate positions, a target insertion position for cutting off the target operation of each target partition includes:

and for any first partition interval with the first target partition, determining a first target position of the partition with the first target cut-off function based on the corresponding first candidate position and a previous insertion position determined by taking the previous partition as a source partition according to the execution time of the related homomorphic operation, and classifying the first target position into the target insertion position.

Further, the prior insertion locations include a first insertion location from a first partition to a previous partition of the current partition, and a second insertion location from the first partition to the first destination partition;

Determining a first target location of the partition that cuts off the first destination according to the execution time of the homomorphic operation involved, comprising:

Determining the section execution time for executing homomorphic operation in the first partition interval according to the first candidate position;

acquiring a first execution time corresponding to a first insertion position and a second execution time corresponding to a second insertion position;

And if the sum of the section execution time and the first execution time is smaller than the second execution time, determining a first insertion position and the first candidate position as a first target position, and if not, determining the second insertion position as the first target position.

Further, the section execution time is the sum of the execution time of each homomorphic operation in the first partition interval, and the execution time of any homomorphic operation is obtained by searching from the execution time of each hierarchy of the homomorphic operation obtained by the pre-test according to the hierarchy of the homomorphic operation.

In one possible implementation, the number of partitions corresponds to a maximum level of bootstrap operation.

Further, the determining, based on the minimal cut algorithm, a first candidate location for inserting a bootstrap operation within the source partition includes:

Taking the execution time of the bootstrap operation after the bootstrap operation is inserted and the added value of the execution time of each homomorphic operation as the weight of each side in the source partition;

The cut that minimizes edge weight in the source partition is selected as the first candidate location for inserting bootstrap operations within the source partition.

Further, the determining the first partition set needing to insert the re-reduction operation from each partition between the source partition and the destination partition includes:

and traversing each partition from the source partition to the destination partition in the forward direction, and sequentially selecting the partition which is inserted into the re-reduction operation and reduces the amplification factor of the destination partition to the greatest extent.

Further, the determining, based on the minimal cut algorithm, a second candidate location for inserting a re-reduction operation within each partition of the first set of partitions includes:

The execution time of the re-reduction operation after the re-reduction operation is inserted and the added value of the execution time of each homomorphic operation are used as the weight of each side in a single partition;

the cut that minimizes the edge weight in the single partition is selected as the second candidate location for the insert-in-re-reduction operation within the single partition.

Further, the minimum cut algorithm is calculated based on the weight of each edge and the set source node and sink node.

In a second aspect, there is provided an apparatus for generating an isomorphic calculation program, the apparatus comprising:

a conversion unit for converting the plaintext calculation program into a first isomorphic calculation program;

The system comprises a conversion unit, a construction unit and a value flow graph, wherein the conversion unit is used for converting a first isomorphic calculation program into a first isomorphic calculation program;

The dividing unit is used for dividing the value flow diagram into a plurality of partitions based on multiplication depths corresponding to all nodes in the value flow diagram obtained by the constructing unit;

The planning unit is used for traversing each partition obtained by the dividing unit according to a topological sequence to execute the first operation of determining a candidate position for inserting the target operation by adopting a minimum cutting algorithm for a plurality of partition intervals taking the current partition as a source partition and a plurality of partitions after the current partition as target partitions and taking an added value of execution time of each homomorphic operation after the target operation as an edge weight;

And the generation unit is used for generating a second isomorphic calculation program according to the target insertion position obtained by traversing the planning unit.

In a third aspect, there is provided a computer readable storage medium having stored thereon a computer program which, when executed in a computer, causes the computer to perform the method of the first aspect.

In a fourth aspect, there is provided a computing device comprising a memory having executable code stored therein and a processor which, when executing the executable code, implements the method of the first aspect.

The method and the device provided by the embodiment of the specification are used for firstly converting a plaintext calculation program into a first isohomomorphic calculation program, then constructing a value flow diagram according to each homomorphic operation contained in the first isohomomorphic calculation program, wherein nodes in the value flow diagram correspond to homomorphic operations, directed edges in the value flow diagram correspond to data transmission among the nodes, dividing the value flow diagram into a plurality of partitions based on multiplication depths respectively corresponding to the nodes in the value flow diagram, traversing each partition according to a topological sequence, performing a first operation of taking a current partition as a source partition, taking a plurality of partitions after the current partition as a plurality of partition intervals of a target partition respectively, determining candidate positions for inserting the target operation by adopting a minimum segmentation algorithm according to the increment of the execution time of each homomorphic operation after inserting the target operation, determining target insertion positions for cutting off each target partition according to the candidate positions, wherein the target operation comprises a curtailment operation and a bootstrap operation, and finally generating a second isomorphic calculation program according to the target insertion positions obtained by traversing. From the above, in the embodiment of the present disclosure, a divide-and-conquer strategy is adopted, and the insertion positions of the re-reduction operation and the bootstrap operation are analyzed based on the partition and the minimum cut algorithm, where each minimum cut algorithm only needs to be specific to a single partition, so that the compiling time is controllable, the insertion positions of the re-reduction operation and the bootstrap operation in the single partition are better, the partition interval is divided by combining the source partition and the destination partition, and the target insertion position of the target operation of each destination partition is determined according to the candidate position in the single partition, so that the overall execution efficiency is better, the compiling time can be shortened, and the execution efficiency of the isotactic computing program is improved.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the drawings required for the description of the embodiments will be briefly described below, it being obvious that the drawings in the following description are only some embodiments of the present invention, and that other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

FIG. 1 is a schematic illustration of an implementation scenario of an embodiment disclosed herein;

FIG. 2 is a schematic illustration of an implementation scenario of another embodiment disclosed herein;

FIG. 3 illustrates a flow chart of a method of generating an isomorphic calculation program in accordance with one embodiment;

FIG. 4 illustrates a schematic diagram of partitioning a value flow graph into a plurality of partitions, according to one embodiment;

FIG. 5 illustrates a schematic diagram of a programming process for a re-reduction operation and a bootstrapping operation, according to one embodiment;

FIG. 6 illustrates an application diagram of a min-cut algorithm according to one embodiment;

fig. 7 shows a schematic block diagram of a generation device of an isomorphic calculation program according to one embodiment.

Detailed Description

The following describes the scheme provided in the present specification with reference to the drawings.

Fig. 1 is a schematic diagram of an implementation scenario of an embodiment disclosed in the present specification. This implementation scenario involves the generation of an isomorphic calculation program. It will be appreciated that the above-mentioned process is specifically to convert the plaintext calculation program into a fully homomorphic calculation program, where the plaintext calculation program may include various types of calculations, for example, may include linear operations formed by addition or multiplication, or may include nonlinear operations such as convolution operations, activation functions, etc., and in the embodiment of the present disclosure, the operations and overall implementation functions included in the plaintext calculation program itself are not limited. Referring to fig. 1, taking a plaintext calculation program as an example of a machine learning model, for plaintext input, a plaintext result may be obtained by using the machine learning model, for example, the machine learning model is a classification model for predicting a risk class of a user, the plaintext input is feature data of the user, and the plaintext result is the risk class of the user. Because the characteristic data of the user usually belongs to the private data, in order to prevent the private data from being leaked, the characteristic data can be encrypted to obtain ciphertext input, a plaintext calculation program of a machine learning model is compiled into an isomorphic calculation program, the ciphertext input is utilized to obtain a ciphertext result by the isomorphic calculation program, the ciphertext result is decrypted to obtain a plaintext result, and in this way, the purpose of obtaining the plaintext result can be achieved, and the private data is prevented from being leaked.

The machine learning model can be obtained through two stages of pre-training and fine tuning, the pre-training model is obtained through pre-training, and then the pre-training model is fine tuned to obtain the machine learning model, which comprises a large amount of operations and can be used for carrying out reasoning prediction on a target object.

The pre-training model (PRE TRAINED model) is a machine learning (MACHINE LEARNING) model that has been trained on large datasets and can be fine-tuned for specific tasks. The pre-trained model contains model structure, tensors, weights and biases.

Reasoning inference the process of predicting new real world data using machine learning models that have been trained and deployed.

Some basic concepts related to homomorphic encryption are described below.

CKKS scheme CKKS is an isomorphic encryption scheme, namely an approximate calculation isomorphic encryption scheme supporting complex domain fixed point addition and multiplication operations, which is proposed by Cheon-Kim-Kim-Song four-bit author at ASIACRYPT' 17. The CKKS scheme does not pursue that the decryption result is exactly identical to the plaintext calculation, but only retains a part of the significant digits. Compared with other homomorphic encryption schemes, CKKS scheme details are greatly simplified, the calculation efficiency is greatly improved, and the method is suitable for application scenes such as machine learning reasoning and the like.

Magnification factor (scale) CKKS scheme at encoding, the encrypted initial variable m is multiplied by a magnification factor delta, e.g., mdelta, to ensure accuracy. When the multiplication of the two ciphertexts c ₁ and c ₂ is performed, the product corresponds to the plaintext m ₁m₂Δ², the ciphertext amplification factor is delta ², and the ciphertext amplification factor increases exponentially with the multiplication depth. If the ciphertext amplification factor exceeds a limit value, the encrypted data is corrupted and cannot be decrypted.

Further downscaling rescale to reduce the ciphertext amplification factor growth rate, the ciphertext may be divided by Δ after multiplication, such that the corresponding plaintext is changed from m ₁m₂Δ² to m ₁m₂ Δ.

The cipher text modulo (Q _L) CKKS format is implemented based on ring error learning (RING LEARNING WITH error, RLWE), the cipher text being represented as an integer coefficient polynomial, the polynomial coefficients taking values over a finite range, the range being the cipher text modulo. The ciphertext mode can only take values in a limited range, otherwise, the ciphertext security is destroyed. Each time a re-reduction (rescale) operation is performed, the ciphertext mode is reduced by Δ, thereby forming a set of progressively smaller modulus sequences, Q _L,Q_L-1,…,Q₀.

The level (level) is that the ciphertext modulus decreases after each re-reduction (rescale), but the ciphertext modulus must be greater than delta, otherwise the ciphertext cannot be decrypted. Thus, while re-reduction (rescale) may reduce the ciphertext amplification increase rate, each ciphertext may still only participate in a limited number of homomorphic multiplication operations. The hierarchy may be used to represent how many homomorphic multiplications the ciphertext may also take part in. After each re-reduction (rescale), the ciphertext amplification is reduced by Δ, with the level reduced by 1. Ciphertext calculation has a basic characteristic, and the lower the ciphertext level is, the higher the homomorphic calculation efficiency is.

Bootstrapping (bootstrapping), which is the process of multiplying a ciphertext by a finite number of times, beyond a defined value, the encrypted data is corrupted and cannot be decrypted. In the ciphertext state, the multiplication depth that the machine learning model needs to execute is generally greater than the multiplication depth that the ciphertext can support. Full homomorphic encryption (including CKKS format) uses bootstrapping (bootstrapping) techniques to implement multiplication operations of infinite depth. The bootstrap operation may restore the ciphertext modulo and hierarchy, adding it to the specified value, so that the ciphertext may continue to participate in the multiplication computation. The related homomorphic calculation efficiency is reduced due to the increase of ciphertext levels after bootstrapping.

Modulo switching (modswitch) the addition and multiplication operations in the CKKS scheme require the input ciphertext to be of the same level. If the levels are different, the input ciphertext level is flattened by reducing the input ciphertext level through a modulo switching operation. The addition also requires that the input ciphertext amplification be the same, and if different, the ciphertext amplification may be reduced by a re-reduction (rescale) operation to trim the input ciphertext. In CKKS format, the execution time of the die-cutting switch is negligible, and the die-cutting switch can be inserted as required without considering the execution time of the die-cutting switch.

The bilinear (relinearization) CKKS scheme supports ciphertext multiplication of plaintext (cipert-plaintext multiplication, mulCP) and ciphertext multiplication of ciphertext (cipert-ciphertext multiplication, mulCC). The CKKS scheme is implemented based on RLWE, where the plaintext is represented by one polynomial and the just-encrypted ciphertext is represented by two polynomials. The ciphertext comprising m polynomials is multiplied with the ciphertext or plaintext comprising n polynomials, the product being the ciphertext comprising (m+n-1) polynomials. The increase in the number of polynomials reduces the efficiency of subsequent homomorphic calculations, and the re-linearization operation is used to reduce the number of ciphertext polynomials back to 2.

The homomorphic encryption compiler (FHEcompiler) is a compiler that converts plaintext computations into homomorphic encryption computations. In generating the encryption computation, the compiler needs to insert a re-reduction (rescale) operation to reduce the ciphertext amplification increase rate, and insert a bootstrap (bootstrapping) operation to support more multiplication operations. Meanwhile, the compiler needs to optimize the insertion positions of the re-reduction operation and the bootstrap operation to optimize the encryption calculation execution efficiency.

In the embodiment of the present specification, encryption (encryption), decryption (decryption), addition, multiplication, rotation (rotation), re-linearization (relinearization), re-reduction (rescale), die-cut (modswitch), and bootstrap (bootstrapping) operations are denoted by Enc, dec, add, mul, rot, relin, rsc, ms and Bts, respectively, and homomorphic encryption computation can be expressed as the following two sets of equations:

Dec(Add(Enc(x),Enc(y)))==Add(x,y);

Dec(Mu l(Enc(x),Enc(y)))==Mu l(x,y)。

rsc, ms, and Bts only change the magnification factor and hierarchy of ciphertext, not change plaintext information:

Dec(Rsc(Enc(x)))==x;

Dec(Ms(Enc(x)))==x;

Dec(Bts(Enc(x)))==x。

Homomorphic encryption ensures encryption security by adding noise to the original plaintext data. Homomorphic multiplication can greatly increase noise levels, which can overwhelm the plaintext message after a certain depth of multiplication is performed, resulting in decryption failure. In CKKS format, introducing a re-reduction operation reduces the noise rise speed, increasing the multiplication depth that can be supported. Fully homomorphic encryption (including CKKS format) allows multiplication operations of arbitrary depth to be performed by introducing bootstrap operations to refresh a ciphertext containing higher noise to a ciphertext containing lower noise.

The full homomorphic encryption technology realizes the analysis and processing of the data on the premise of ensuring that the original data is not leaked by the data provider, ensures that the data is 'available and invisible' in the circulation and fusion process, and can be widely applied to various industries and scenes needing privacy protection.

Common isomorphic encryption schemes fall into two categories, one that is a scheme that supports high-throughput batch (batch) computation on integer or floating point number vectors, support vector addition, multiplication, and rotation operations of vector elements, such as BGV, BFV, and CKKS schemes, and another that is a computation scheme on boolean circuits that supports comparison operations and efficient bootstrap operations, but generally does not support batch processes, such as GSW, FHEW, and TFHE schemes. The common isomorphic encryption scheme is presented as follows:

CKKS scheme supporting complex number (real number), batch processing and bootstrap, basic operation includes homomorphic addition, multiplication, rotation and ciphertext bootstrap.

BGV/BFV scheme-scheme supporting integer, batch processing, basic operations including homomorphic addition, multiplication and rotation, bootstrap operation is very expensive.

TFHE scheme supporting Boolean circuit and quick bootstrap, basically operating as Boolean circuit gate, and constructing lookup table (LUT) to realize complex function by gate circuit.

CKKS/TFHE, namely realizing the interconversion of CKKS ciphertext and TFHE ciphertext through special bootstrap operation.

Let ct.s denote the magnification factor (sca le) of the ciphertext ct, ct.l denote the ciphertext level (level), and l _bts denote the ciphertext level after bootstrapping. The CKKS scheme supports batch processing, and the operation primitive of CKKS has different requirements and effects on ct.s and ct.l. CKKS the semantics of each primitive are as follows:

encryption, ct=enc (a ₀,a₁,…,a_n-1).

Decryption (c ₀,c₁,…,c_n-1)＝Dec(ct)≈(a₀,a₁,…,a_n-1).

Add, ct ₁＝Enc(a₀,a₁,…,a_n-1);

ct₂＝Enc(b₀,b₁,...,b_n-1);

ct₃＝Add(ct₁,ct₂);

(c₀,c₁,...,c_n-1)＝Dec(ct₃)

≈(a₀+b₀,a₁+b₁,...,a_n-1+b_n-1)。

Multiplication, ct ₁＝Enc(a₀,a₁,...,a_n-1);

ct₂＝Enc(b₀,b₁,...,b_n-1);

ct₃＝Mul(ct₁,ct₂);

(c₀,c₁,...,c_n-1)＝Dec(ct₃)

≈(a₀*b₀,a₁*b₁,...,a_n-1*b_n-1)。

re-linearization, ct ₁＝Enc(a₀,a₁,...,a_n-1);

ct₂＝Enc(b₀,b₁,...,b_n-1);

ct₃＝Relin(Mul(ct₁,ct₂));

(c₀,c₁,...,c_n-1)＝Dec(ct₃)

≈(a₀*b₀,a₁*b₁,...a_n-1*b_n-1)。

Rotation, ct ₁＝Enc(a₀,a₁,...,a_n-1);

ct₂＝Rot(ct₁,k);

(c₀,c₁,...,c_n-1)＝Dec(ct₂)

≈(a_k,a_k+1,...,a_n-1,a₀,a₁,...,a_k-1);

for each item, c _i≈a_(i+k)％n, i is more than or equal to 0 and less than or equal to (n-1).

Curtailment, ct ₁＝Enc(a₀,a₁,...,a_n-1);

(c₀,c₁,...,c_n-1)＝Dec(ct₂)≈(a₀,a₁,...,a_n-1)。

Bootstrap, ct ₁＝Enc(a₀,a₁,...,a_n-1);

ct₂＝Bts(ct₁)with ct₂·s＝Δand ct₂.l＝lb_ts;

(c₀,c₁,...,c_n-1)＝Dec(ct₂)≈(a₀,a₁,...,a_n-1)。

Mode switching, ct ₁＝Enc(a₀,a₁,...,a_n-1);

ct₂＝Ms(ct₁)with ct₂.s＝ct₁.s and ct₂.l＝ct₁.l-1;

(c₀,c₁,...,c_n-1)＝Dec(ct₂)≈(a₀,a₁,...,a_n-1)。

The constraint conditions of each element word on the ct.s and the ct.l of the input ciphertext and the ct.s and the ct.l of the output ciphertext are shown in the following table one: TABLE one constraint condition of CKKS primitive languages on ct.s and ct.l of input ciphertext and ct.s and ct.l of output ciphertext

Referring to table one, the ciphertext calculation program generated by direct conversion of plaintext calculation only contains Add, mul, rot, relin, and at this time, the constraint condition of Mul or Add on the input ciphertext is generally not satisfied. In order to meet the constraint condition of each homomorphic operation on the input ciphertext, a correct, efficient and executable homomorphic encryption program is generated, and the homomorphic encryption compiler needs to correctly insert operations such as re-reduction, modulo switching, bootstrapping and the like in the homomorphic calculation program, and optimize the insertion position of related operations so as to improve the efficiency of homomorphic calculation. The calculation efficiency of homomorphic operation has two basic rules, namely one rule is that the calculation efficiency of each operation increases along with the reduction of the input ciphertext level, and the other rule is that the calculation efficiency of different homomorphic operations is greatly different, and the time-consuming change rule is as follows:

Ms<<Add<Mul<Rsc<<Rot≈Relin<<Bts。

The bootstrap operation is the homomorphic calculation with the longest time consumption, and reducing the number of bootstrap operations can effectively improve the efficiency of the homomorphic calculation program. However, the preferred insertion location for solving bootstrap operations is typically a non-deterministic polynomial (nondeterministic polynomial, NP) problem, which is too time-complex to use in a compiler. The existing algorithm for solving the optimal management scheme of the amplification factor cannot be used when compiling a large machine learning model because of too high time complexity. For CKKS identical encryption schemes, the present embodiments propose a method to efficiently select and optimize bootstrap and re-shrink operation insertion locations. Compared with the common bootstrap operation and the management method of the amplification factors, the compiler execution time and the generated code execution efficiency are obviously improved.

Fig. 2 is a schematic diagram of an implementation scenario of another embodiment disclosed in the present specification. This implementation scenario demonstrates the generation of an isotactic computing program with the aim of generating an executable isotactic computing program with a short compiling time and high execution efficiency of the isotactic computing program. Referring to fig. 2, the above generation process includes converting a plaintext calculation program into an initial isotactic calculation program composed of homomorphic addition (Add), homomorphic multiplication (Mul), re-linearization (Relin), rotation (Rot), constructing a value flow graph (DFG) based on the initial isotactic calculation program, dividing the value flow graph into a plurality of partitions (regions) based on multiplication depths of respective nodes in the value flow graph, determining a plan scheme of insertion positions of a re-reduction operation and a bootstrap operation based on the respective partitions, and inserting the re-reduction operation and the bootstrap operation into the initial isotactic calculation program according to the plan scheme, to generate an executable isotactic calculation program, in step s, the step s, and the step s, the step s is performed.

The embodiment of the specification can be a management algorithm for ciphertext amplification factors and bootstrap operation of an isomorphic encryption scheme, and analysis and optimization of insertion positions of a re-reduction operation and the bootstrap operation can be completed simultaneously.

Among them, DFG is a graph for representing the flow of data in a system, and is widely used in compilers. Like other graphs, DFGs contain two key elements, nodes and edges. The nodes of the DFG are data operations, such as arithmetic operations, logical operations, or other data operations. Edges represent the transfer of data between nodes. Edges are typically directional, the start of a DFG edge being a node that manipulates input data, and the end of the edge being the corresponding data manipulation.

In the foregoing step 24, a divide-and-conquer strategy may be adopted, where the minimum cut algorithm is used to determine the insertion position of the re-reduction operation or the bootstrap operation in the single partition, and then the insertion positions of the re-reduction operation and the bootstrap operation in the whole procedure are determined comprehensively.

The minimum cut (Min-cut) algorithm is an algorithm in graph theory and is used for finding the cut (cut) which minimizes the sum of edge weights in the graph. In an undirected graph, a cut is the division of the set of vertices of the graph into two disjoint subsets, such that the set of edges from one subset to the other is referred to as a cut set. The goal of the min-cut algorithm is to find a cut such that the sum of the weights of the edges of the cut set is minimized. In the embodiment of the specification, the execution time increment value in a single partition caused by the insertion of the re-reduction operation or the bootstrap operation is used as the weight of the DFG edge, so that the minimum cut is the insertion position of the re-reduction operation or the bootstrap operation in the current partition, which leads the full homomorphic calculation to have better execution efficiency.

Fig. 3 shows a flow chart of a method of generating an isomorphic calculation program, which may be based on the implementation scenarios shown in fig. 1 and 2, according to one embodiment. As shown in FIG. 3, the method for generating the isomorphic calculation program in this embodiment includes the steps of converting a plaintext calculation program into a first isomorphic calculation program, constructing a value flow graph according to each isomorphic operation included in the first isomorphic calculation program, determining a candidate position for inserting the target operation by using a minimum segmentation algorithm for each partition section taking a current partition as a source partition and each isomorphic operation execution time increment after inserting the target operation, determining a target insertion position for cutting off each target partition according to the candidate position, dividing the value flow graph into a plurality of partitions based on multiplication depths corresponding to each node in the value flow graph, step 33, traversing each partition in topological order, performing the first operation including a re-reduction operation and a bootstrap operation, and step 34, performing the second isomorphic calculation according to the target insertion position, for each partition section taking the current partition as a source partition, taking each partition section after the current partition as a target partition, determining a target insertion position for inserting the target operation by using a minimum segmentation algorithm. Specific implementations of the above steps are described below.

First, in step 31, the plaintext calculation program is converted into a first isomorphic calculation program. It will be appreciated that the first isomorphic calculation procedure consists of a series of homomorphic operations that perform the same operational functions as the plaintext calculation procedure. The constraint condition of homomorphic addition and homomorphic multiplication on the input ciphertext may not be satisfied because the first isomorphic calculation program is not inserted with the re-reduction operation and the bootstrap operation, and thus cannot be executed correctly.

For example, the plaintext calculation program includes a convolution operation and an operation of an activation function, where the convolution operation may be converted into a plurality of terms Add, mul, rot, the operation of the activation function may be converted into a plurality of terms Add, mul, relin, and it may occur that the amplification factor of the ciphertext exceeds a limit value, and may not be decrypted, or that the amplification factors of the two ciphertexts are not matched, and may not satisfy the constraint condition of Add on the input data.

Then, at step 32, a value flow graph is constructed from the homomorphic operations contained in the first homomorphic calculation program, wherein nodes in the value flow graph correspond to homomorphic operations, and directed edges in the value flow graph correspond to data transfer between nodes. It will be appreciated that in constructing a direct flow graph, in order to reduce the size of the graph, loops in the program may be preserved under certain conditions, that is, the same operation performed multiple times in a loop may correspond to the same node in the value flow graph.

In one example, the constructing a value flow graph according to each homomorphic operation included in the first isomorphic calculation program includes:

For the loop of homomorphic multiplication operation contained in the first homomorphic calculation program, if the amplification factor of the output ciphertext of homomorphic multiplication operation in the loop is increased, expanding the loop;

Corresponding nodes are respectively constructed aiming at homomorphic operation in the loop and homomorphic operation outside the loop, and the execution times of the nodes are marked, wherein the execution times of the nodes in the loop are recorded as the circulation times, and the execution times of the nodes outside the loop are 1.

In this example, whether to reserve the loop is determined according to whether the amplification factor of the ciphertext output by the homomorphic multiplication operation in the loop is increased, so that the scale of the value flow graph can be effectively reduced, and the subsequent processing is not affected.

Next, in step 33, the value flow graph is divided into a plurality of partitions based on multiplication depths respectively corresponding to the nodes in the value flow graph. It will be appreciated that the multiplication depth, i.e. the number of homomorphic multiplication operations that the node undergoes, the amplification factor of the ciphertext increases exponentially with the multiplication depth.

In one example, the dividing the value flow graph into a plurality of partitions based on multiplication depths respectively corresponding to nodes in the value flow graph includes:

Traversing each node forward according to the topological sequence of each node in the value flow graph, and calculating the initial multiplication depth of each node;

Traversing each node reversely according to the reverse topological sequence of each node in the value flow diagram, and updating the multiplication depth of each node to the maximum value allowed to obtain the optimized multiplication depth;

Nodes with the same optimized multiplication depth are divided into the same partition of the value flow graph.

In this example, homomorphic operations which need to occur at the same multiplication depth are partitioned into the same partition, so that each homomorphic operation occurs at a required level, and the execution efficiency is better.

Further, traversing each node in reverse according to the reverse topological order of each node in the value flow diagram, updating the multiplication depth of each node to the maximum value allowed to obtain the optimized multiplication depth, including:

traversing each node reversely according to the reverse topological sequence of each node in the value flow graph, and calculating the maximum multiplication depth allowed by the subsequent nodes of the current node under the topological sequence;

If the current node is a multiplication node and its multiplication depth is less than the maximum multiplication depth allowed by its successor nodes, the multiplication depth of the current node is updated, and the multiplication depths of all other nodes within the current multiplication depth that depend on the current node are updated.

In this example, if there is a directed edge between node A and node B that is directed from node A to node B, then node B is the successor node of node A, and node A is the predecessor (predecessor) node of node B. This way of updating the multiplication depth facilitates to scribe a node as much as possible into the partition with the larger multiplication depth.

FIG. 4 illustrates a schematic diagram of partitioning a value flow graph into multiple partitions, according to one embodiment. Referring to FIG. 4, a first isomorphic calculation procedure is used to calculate a ₃x³+a₁ x, which can be broken down into homomorphic operations of calculating a ₁ x homomorphic multiplication, calculating a ₃ x homomorphic multiplication, calculating x ² homomorphic multiplication, calculating a ₃x³ homomorphic multiplication, calculating a ₃x³+a₁ x homomorphic addition, and two re-linearization operations. Accordingly, the value flow graph includes input nodes representing x and nodes corresponding to respective homomorphic operations. The multiplication depth is first calculated. In fig. 4 (a), starting from an input node, the DFG is traversed forward in topological order, the multiplication depth of each node is calculated, and the nodes contained in each multiplication depth are recorded. For example, the multiplication Depth of the input node x is 0, denoted Depth1, the homomorphic multiplication MulCP of the calculation a ₁ x, the homomorphic multiplication MulCP of the calculation a ₃ x, the homomorphic multiplication MulCC of the calculation x ², the first re-linearization operation Relin, the multiplication Depth of the node corresponding to these operations is 1, denoted Depth2, the homomorphic multiplication MulCC of the calculation a ₃x³, the second re-linearization operation Relin, the homomorphic addition AddCC of the calculation a ₃x³+a₁ x, the multiplication Depth of the node corresponding to these operations is 2, denoted Depth3.

The multiplication depth is then optimized. And traversing the DFG reversely from the program return value, traversing the DFG nodes sequentially from the maximum multiplication depth to the minimum multiplication depth, and updating the multiplication depth of each node to the maximum allowed value. The method comprises the steps of firstly traversing nodes with identical multiplication depths by reverse topological sequences, calculating the maximum multiplication depth allowed by the subsequent nodes of each node, and secondly updating the multiplication depth of the multiplication node and updating the multiplication depths of all other nodes depending on the multiplication node in the current multiplication depth if the multiplication depth of the multiplication node is smaller than the maximum multiplication depth allowed by the subsequent nodes. For example, for homomorphic multiplication MulCP of compute a ₁ x, the multiplication depth of this multiplication node is 1, the homomorphic addition AddCC of compute a ₃x³+a₁ x is followed by the addition node, which allows a maximum multiplication depth of 2, thus updating the multiplication depth of this multiplication node to 2.

And finally constructing a DFG partition. In fig. 4 (b), the DFG is partitioned into different subgraphs according to the optimized multiplication depth, and each subgraph is subsequently referred to as a partition (region). If the maximum multiplication depth of the homomorphic calculation program is max_depth, max_depth+1 partitions are constructed, and the multiplication depth difference between two adjacent partitions is 1. For example, max_depth is 2, and the dfg is divided into 3 partitions, a first partition, a second partition, and a third partition in order of topology. The first partition is denoted as Region1, which contains the input node x, the second partition is denoted as Region2, which contains homomorphic multiplication MulCP for computing a ₃ x, homomorphic multiplication MulCC for computing x ², first re-linearization operation Relin, and the third partition is denoted as Region3, which contains homomorphic multiplication MulCP for computing a ₁ x, homomorphic multiplication MulCC for computing a ₃x³, second re-linearization operation Relin, homomorphic addition AddCC for computing a ₃x³+a₁ x.

In the embodiment of the present specification, the partition process of the partition may be represented by a code. Wherein the input of the code is G, which represents DFG, the output of the code is R, which is the partition of G. The specific codes are as follows:

among the above codes, lines 4 to 11 are used to calculate the multiplication depth, and lines 13 to 28 are used to optimize the multiplication depth. The respective variables involved in the code are explained below.

Md represents multiplication depth, input.md represents multiplication depth of an input node, md2nodes represents a mapping of multiplication depth to nodes, e.g. note md2nodes = {0: [ input, x, y ],1: [ m, n ] }, representing that a node with multiplication depth 0 has input, x, y, and a node with multiplication depth 1 has m, n.

Md2nodes [ md ] represent all nodes corresponding to multiplication depth md, md2nodes [ node.md ]. Add (node) represents adding node to node.md corresponds to node, for example, let node.md=1, note that md2 nodes= {0: [ input, x, y ],1: [ m, n ] }, after performing md2nodes [ node.md ]. Add (node), md2 nodes= {0: [ input, x, y ],1: [ m, n, node ] }.

NodeLi st +.md 2nodes [ md ], nodeLi st represent all nodes corresponding to md. For example, assuming md=0, nodeLi st = [ input, x, y ].

Node.succmd, represents the multiplication depth of all successor nodes of the node.

Node. Successors, representing all successors of a node.

Uint_max represents a 32-bit unsigned integer maximum.

R refers to all partitions, R [ node.md ] refers to the partition corresponding to the multiplication depth node.md, and R [ node.md ]. Add (node) refers to adding node to the partition.

And in step 34, traversing each partition according to the topological sequence to execute the first operation of determining candidate positions for inserting the target operation by adopting a minimum cut algorithm for a plurality of partition intervals taking the current partition as a source partition and a plurality of partitions after the current partition as target partitions, taking an added value of the execution time of each homomorphic operation after the target operation is inserted as an edge weight, and determining target insertion positions for stopping the target operation of each target partition according to the candidate positions, wherein the target operation comprises a re-reduction operation and a bootstrap operation. It will be appreciated that this step determines both the insertion position of the re-reduction operation and the insertion position of the bootstrap operation.

In the embodiment of the present disclosure, in the foregoing step 33, a partition sequence consisting of max_depth+1 partitions is constructed, and the multiplication depth of the partitions increases by 1 from 0 to max_depth. In step 34, the insertion positions of the re-reduction operation and the bootstrap operation are analyzed using the divide-and-conquer strategy with the partitions as analysis objects. And traversing all the partitions in the forward direction, analyzing the position of bootstrap operation, sequentially taking the first partition as a source partition src, and sequentially taking the partition after the source partition as a target partition dst. The traversal strategy ensures that all schemes of the re-reduction operation and the bootstrap operation from the input node input to the source partition src have been analyzed when analyzing the source partition src to the destination partition dst. It is assumed that a bootstrap operation needs to be inserted in the source partition src and a preferred insertion location for the bootstrap operation within the source partition src is determined based on a minimal cut algorithm. Then analyzing the position of the re-reduction operation, analyzing the source partition src to the partition needing to be inserted into the destination partition dst, and determining the optimal insertion position of the re-reduction operation in the partition based on a minimum cut algorithm. Finally, performance analysis is carried out, a better scheme from the input node input to the destination partition dst is determined based on the insertion positions of the re-reduction operation and the bootstrap operation, and the scheme of the re-reduction operation and the bootstrap operation corresponding to the destination partition dst is updated according to the better scheme. When the division with the multiplication depth of max_depth is analyzed, all program nodes are analyzed, and a preferable scheme of the whole program re-reduction operation and the bootstrap operation is obtained.

In one example, the determining candidate locations for inserting the target operation using a cut-down algorithm includes:

Determining a first candidate location for inserting a bootstrap operation within the source partition based on a minimal cut algorithm;

For any partition, determining a first partition set needing to be inserted with a re-reduction operation from each partition between a source partition and a destination partition, and determining a second candidate position for inserting the re-reduction operation in each partition of the first partition set based on a minimum cut algorithm.

In this example, a divide-and-conquer strategy is employed to re-reduce the insertion locations of operations and bootstrap operations based on partition analysis to make homomorphic computing programs efficient and executable. Wherein, each time the minimum cut algorithm only aims at a single partition, the compiling time can be controlled, and candidate positions of the re-reduction operation and the bootstrap operation in the single partition are better.

In one example, the determining, according to the candidate positions, a target insertion position for cutting off the target operation of each target partition includes:

and for any first partition interval with the first target partition, determining a first target position of the partition with the first target cut-off function based on the corresponding first candidate position and a previous insertion position determined by taking the previous partition as a source partition according to the execution time of the related homomorphic operation, and classifying the first target position into the target insertion position.

In this example, by comparing execution times of homomorphic calculation programs at different insertion positions, insertion positions with shorter execution times can be selected, and thus the resulting homomorphic calculation program is more efficient.

Further, the prior insertion locations include a first insertion location from a first partition to a previous partition of the current partition, and a second insertion location from the first partition to the first destination partition;

Determining a first target location of the partition that cuts off the first destination according to the execution time of the homomorphic operation involved, comprising:

Determining the section execution time for executing homomorphic operation in the first partition interval according to the first candidate position;

acquiring a first execution time corresponding to a first insertion position and a second execution time corresponding to a second insertion position;

And if the sum of the section execution time and the first execution time is smaller than the second execution time, determining a first insertion position and the first candidate position as a first target position, and if not, determining the second insertion position as the first target position.

In this example, the segment execution time corresponding to the source partition src to the destination partition dst is calculated based on the candidate positions of the re-reduction operation and the bootstrap operation. Since all the re-reduction and bootstrap operating schemes from the input node input to the source partition src have been analyzed, the minimum execution time minL AT [ src ] from the input node input to the source partition src is also known. For the scheme of inserting bootstrap operation from input node input to destination partition dst and at source partition src, its new minimum execution time isIf the new minimum execution time newLAT is smaller than the known minimum execution time minLAT [ dst ], then this scheme is considered to be a preferred scheme for inputting the node input to the destination partition dst, and updating the scheme for the re-reduction operation and bootstrap operation corresponding to the destination partition dst accordingly. When the division of the multiplication depth which is the maximum multiplication depth max_depth is analyzed, all program nodes are analyzed, and therefore the optimal re-reduction operation and bootstrap operation scheme of the whole program are obtained.

Further, the section execution time is the sum of the execution time of each homomorphic operation in the first partition interval, and the execution time of any homomorphic operation is obtained by searching from the execution time of each hierarchy of the homomorphic operation obtained by the pre-test according to the hierarchy of the homomorphic operation.

In this example, the execution time of the program is approximated by the sum of the execution times of the homomorphic operations, where the execution time of each homomorphic operation is the execution time of each operation at a different level obtained by the pre-test, so that the execution time of the homomorphic calculation program can be estimated.

Wherein, each homomorphic operation comprises a to-be-inserted re-reduction operation and a bootstrap operation.

In one example, the number of partitions corresponds to a maximum level of bootstrap operation.

In this example, for a partition that is active with respect to the current partition, it is not necessary to use any partition that is subsequent to the current partition as the destination partition, but only the above-described maximum-level partitions that are subsequent to the current partition are used as the destination partitions, respectively.

Further, the determining, based on the minimal cut algorithm, a first candidate location for inserting a bootstrap operation within the source partition includes:

Taking the execution time of the bootstrap operation after the bootstrap operation is inserted and the added value of the execution time of each homomorphic operation as the weight of each side in the source partition;

The cut that minimizes edge weight in the source partition is selected as the first candidate location for inserting bootstrap operations within the source partition.

In this example, by the minimum cut algorithm, the insertion position of the bootstrap operation in the source partition, which makes the isomorphic calculation execution efficiency better, can be selected.

Further, the determining the first partition set needing to insert the re-reduction operation from each partition between the source partition and the destination partition includes:

and traversing each partition from the source partition to the destination partition in the forward direction, and sequentially selecting the partition which is inserted into the re-reduction operation and reduces the amplification factor of the destination partition to the greatest extent.

In this example, all partitions between the source partition and the destination partition that require the insertion of a re-reduction operation are selected.

Further, the determining, based on the minimal cut algorithm, a second candidate location for inserting a re-reduction operation within each partition of the first set of partitions includes:

The execution time of the re-reduction operation after the re-reduction operation is inserted and the added value of the execution time of each homomorphic operation are used as the weight of each side in a single partition;

the cut that minimizes the edge weight in the single partition is selected as the second candidate location for the insert-in-re-reduction operation within the single partition.

In this example, by the min-cut algorithm, the insertion position of the re-reduction operation that makes the isomorphic calculation more efficient within a single partition can be selected.

Further, the minimum cut algorithm is calculated based on the weight of each edge and the set source node and sink node.

Finally, in step 35, a second isomorphic calculation program is generated from the traversed target insertion position. It will be appreciated that at the target insertion location of the first isomorphic calculation procedure, a re-reduction operation and a bootstrap operation are inserted, thereby generating a second isomorphic calculation procedure.

In the embodiment of the present specification, the second isomorphic calculation procedure is not only executable but also efficient to execute.

In the embodiment of the present specification, the procedure of determining the target insertion position in step 34 may be represented by a code. The input of the code is R, which is a partition of the DFG, the output of the code is PLan, which is a scheme of the re-reduction operation and the bootstrap operation, and the scheme comprises a target insertion position of the re-reduction operation and a target insertion position of the bootstrap operation. The specific codes are as follows:

In the code, the 4 th line is used for sequentially taking the partitions after the source partition from the first partition as the destination partition, the 5 th line is used for sequentially taking the partitions after the source partition as the destination partition, the 6 th line is used for analyzing the partitions which need to be inserted with the re-reduction operation in the source partition to the destination partition, the 12 th line is used for determining the optimal insertion position of the re-reduction operation in the partition based on the minimum segmentation algorithm, the 10 th line to the 15 th line are used for calculating the execution time of all homomorphic calculation in the source partition to the destination partition, the 16 th line is used for calculating the minimum execution time under the current scheme, the 17 th line to the 19 th line are used for determining the optimal scheme from the input node to the destination partition, and Sca leMGR and SMOPLC, btsPLC are called subcodes. The respective variables involved in the code are explained below.

Fi rst, refers to the first partition in the DFG in topological order.

R.l ast refers to the last partition, i.e., the last partition in the DFG in topological order.

MinLAT, representing a mapping from partitions to minimum execution time (l atency).

MinLAT [ r ] represents the minimum execution time from the input node to partition r.

MinLAT [ R.fi rst ], represents the minimum execution time from the input node to the first partition.

DOBULE _MAX represents the double precision floating point number maximum.

And l _bts, which represents the level of ciphertext after bootstrapping.

And l _max, which represents the maximum ciphertext level allowed after bootstrapping.

RESCALINGPLAN, which represent a scheme of the insert-and-shrink operation.

BTSPlan, which represent a scheme of inserting bootstrap operations.

Plan, represents the mapping of partitions to minimum execution time schemes.

Plan [ dst ]: the scheme with the least execution time from the input node to the destination partition.

In the above code, "|" indicates the number of collection elements, "\" indicates the other than "..A" | RescalingRegions } { src } | "indicates the partition other than src that needs to be inserted with a re-reduction operation.

"RescalingRegions \ { dst }" represents all partitions except dst that require an insert re-reduce operation.

Indicating the execution time (latency) of all operations within [ src, dst) if bootstrap operations are inserted in src and dst, rescalingRegions to insert a re-reduction operation. Line 15 of the code is the execution time of each partition in turn, where r represents the partition being accumulated.

ScaleMGR is used for selecting all partitions from the source partition to the destination partition, which need to be inserted with a re-reduction operation, traversing all partitions from src to dst in the forward direction, and sequentially selecting the partition which reduces the amplification factor of the destination partition to the greatest extent after being inserted with the re-reduction operation. The code is input into the source partition, the source partition is represented by src and dst, the destination partition is represented by dst, bootstrap operation is inserted into the source partition and the bootstrap operation is inserted into the destination partition, and the code output is RescalingRegions, which is a partition set. The specific codes are as follows:

the respective variables involved in the code are explained below.

RescalingRegions, which represent all partitions that need to be inserted for a re-reduction operation.

Int_max, represents a 32-bit integer maximum.

Q represents an amplification factor used in encryption.

SMORegion, which represents the partition to be inserted with the re-reduction operation, on line 11, SMORegion is added to RescalingRegions, canRegion is a temporary variable in executing the loop, representing the partition that may need to be inserted with the re-reduction operation currently being analyzed.

SMOPLC are used to select the preferred insertion location for the re-reduction operation within a single partition based on a min-cut algorithm. The minimum cut algorithm is used for selecting the cut with the minimum weight in the weight graph. And taking the execution time of the insert-and-shrink operation and the added value of the execution time of each homomorphic operation after the insert-and-shrink operation as the weight of each side in the partition. The cut selected by the min-cut algorithm is the insertion position of the re-reduction operation that minimizes execution time. Where the input of the code is G _r＝(N_r,E_r),G_r representing a directed graph of partition r, N _r representing a node, E _r representing an edge, and the output of the code is minCut, which is the smallest cut in G _r. The specific codes are as follows:

the respective variables involved in the code are explained below.

Src/snk represent the source (source) node and sink (sink) node of the partition, respectively.

TopoSort, representing a sequence of nodes that are topologically ordered for all nodes within a partition, e.g., topoSort = [ MulCP, mulCC, relin ] in one partition and topoSort = [ MulCP, mulCC, relin, addCC ] in another partition.

Indicating that the re-reduction operation is performed on the node n and the execution time of the re-reduction operation.

Freq, which represents the number of executions of node n.

The total execution time of the execution node n is represented by the ciphertext of level l as input.

The execution time for executing the re-reduction operation is represented by taking the ciphertext of level l as an input.

Pred (n), represents all precursor nodes (predecessor) of node n.

And succc (n), representing all successor nodes (successor) of node n.

Indicating the execution time of the node n for the re-reduction operation and all the precursor nodes in the partition.

W _(n,m) represents the weight of the edge connecting nodes n and m.

BtsPLC are used to select a preferred insertion location for bootstrap operations within a single partition based on a minimal-cut algorithm. And taking the added value of the execution time of each homomorphic operation after the bootstrap operation is inserted as the weight of each side in the partition. The cut selected by the minimum cut algorithm is the insertion position of the bootstrap operation that minimizes the execution time. Where the code inputs are G _r＝(N_r,E_r) and l _bts,G_r represent a directed graph of partition r, N _r represents a node, E _r represents a side, l _bts represents the post-bootstrapping ciphertext level, and the code output is minCut, which is the smallest cut in G _r. The specific codes are as follows:

Wherein G _r contains only nodes with level 0, excluding the inserted re-reduction operation and its outgoing edges. The respective variables involved in the code are explained below. Both the BtsPLC code and SMOPLC code employ a minimum cut algorithm, the variables of which can be described with reference to the variables previously described for SMOPLC, and, in addition, The bootstrap operation is performed on the node n, and the execution time of the bootstrap operation is represented.

Fig. 5 shows a schematic diagram of a programming process of a re-reduction operation and a bootstrapping operation according to one embodiment. Referring to fig. 5, this embodiment illustrates a planning process by taking 6 partitions as an example, where these 6 partitions are sequentially denoted as Region1, region2, region3, region4, region5, and Region6, where x represents an input node, z represents an output node, conv1 represents a convolution operation, lu represents an operation of an activation function, conv2 represents another convolution operation, L0 represents a level of 0, L1 represents a level of 1, L2 represents a level of 2, L3 represents a level of 3, and finally the planning scheme is that bootstrap operation BTSs are inserted into regions 2 and Region5, and re-reduction operations RS are inserted into regions 2, region3, region4, and Region5, respectively. It is assumed that the bootstrap operation can only restore the ciphertext level to 3, i.e., the aforementioned l _bts is at most 3. The planning process is classical dynamic planning. If the preferred scheme of Region1- > Region4 determines that the scheme of Region4- > Region6 has no effect on the scheme of Region1- > Region4, i.e., the previous scheme is unchanged.

The complete traversal flow is as follows:

in the first round of traversal, region1 is used as a source partition, region2, region3 and Region4 are respectively used as destination partitions, and planning schemes corresponding to the destination partitions are respectively determined.

Plan 1 is first determined. src=region 1, dst=region 2. And inserting a re-reduction operation RS in the Region2, wherein src is the first partition, the self-contained level of the ciphertext is not consumed, and the bootstrap operation BTS is not required to be inserted. The first traversal to Region2, denoted as the preferred scheme for the current Region1- > Region2, denoted as plan [ Region2].

Plan 2 is then determined. src=region 1, dst=region 3. And inserting a re-reduction operation in Region2 and Region3, wherein the self-contained level of the ciphertext is insufficient, and bootstrap operation is required to be inserted in src to restore the ciphertext level to 2. The first traversal to Region3, denoted as the preferred scheme for the current Region1- > Region3, denoted as plan [ Region3].

Finally, plan 3 was determined. src=region 1, dst=region 4. Inserting a re-reduction operation at Region2, region3 and Region4, inserting a bootstrap operation at src, and restoring the ciphertext level to 3. The first traversal to Region4, denoted as the preferred scheme for the current Region1- > Region4, denoted as plan [ Region4].

In the second round of traversal, region2 is used as a source partition, region3, region4 and Region5 are respectively used as destination partitions, and planning schemes corresponding to the destination partitions are respectively determined.

Plan 4 is first determined. src=region 2, dst=region 3. Inserting a re-reduction operation in Region3, inserting a bootstrap operation in Region2, and restoring the ciphertext level to 1. Traversing 2 to Region3, compare Plan4+Plan [ Region2] with Plan [ Region3], update Plan [ Region3] if the current scheme is performed for a shorter time.

Plan 5 is then determined. src=region 2, dst=region 4. Inserting a re-reduction operation in Region3 and Region4, inserting a bootstrap operation in Region2, and restoring the ciphertext level to 2. Traversing 2 to Region4, compare PLAN5+PLANN [ Region2] with PLANN [ Region4], and update PLANN [ Region4] if the current scheme is performed for a shorter time.

Finally, plan 6 was determined. src=region 2, dst=region 5. Inserting a re-reduction operation at Region3, region4 and Region5, inserting a bootstrap operation at Region2, and restoring the ciphertext level to 3. The first traversal to Region5, denoted as the current Region1- > Region5 preferred solution, denoted as plan [ Region5].

In the third traversal, region3 is used as a source partition, regions 4, 5 and 6 are respectively used as destination partitions, and planning schemes corresponding to the destination partitions are respectively determined.

Plan 7 is first determined. src=region 3, dst=region 4. Inserting a re-reduction operation at Region4, inserting a bootstrap operation at Region3, and restoring the ciphertext level to 1. Traversing 3 rd to Region4, compare Plan7+Plan [ Region3] with Plan [ Region4], update Plan [ Region4] if the current scheme is performed for a shorter time.

Plan 8 is then determined. src=region 3, dst=region 5. Inserting a re-reduction operation in Region4 and Region5, inserting a bootstrap operation in Region3, and restoring the ciphertext level to 2. Traversing 2 to Region5, compare Plan8+Plan [ Region3] with Plan [ Region5], update Plan [ Region5] if the current scheme is performed for a shorter time.

Finally, plan 9 was determined. src=region 3, dst=region 6. Inserting a re-reduction operation at Region 4, region5 and Region6, inserting a bootstrap operation at Region3, and restoring the ciphertext level to 3. The 1 st traversal to Region6 is denoted as the current Region1- > Region6 preferred solution, denoted as plan [ Region6].

In the fourth traversal, region4 is used as a source partition, region5 and Region6 are respectively used as destination partitions, and planning schemes corresponding to the destination partitions are respectively determined.

Plan 10 is first determined. src=region 4, dst=region 5. Inserting a re-reduction operation at Region5, inserting a bootstrap operation at Region4, and restoring the ciphertext level to 1. Traversing 3 rd to Region5, compare Plan10+Plan [ Region4] with Plan [ Region5], update Plan [ Region5] if the current scheme is performed for a shorter time.

And then determines plan 11. src=region 4, dst=region 6. Inserting a re-reduction operation at Region5 and Region6, inserting a bootstrap operation at Region4, and restoring the ciphertext level to 2. Traversing 2 to Region6, compare PLAN11+PLANN [ Region4] with PLANN [ Region6], and update PLANN [ Region6] if the current scheme is performed for a shorter time.

In the fifth round of traversal, region5 is used as a source partition, region6 is used as a destination partition, and a planning scheme corresponding to the destination partition is determined.

Plan 12 was determined. src=region 5, dst=region 6. Inserting a re-reduction operation at Region6, inserting a bootstrap operation at Region5, and restoring the ciphertext level to 1. Traversing 3 rd to Region6, compare Plan12+PlanRegion 5 with PlanRegion 6, update PlanRegion 6 if the current plan execution time is shorter, which is the final plan.

Fig. 6 illustrates an application diagram of a min-cut algorithm according to one embodiment. Referring to FIG. 6, the present embodiment of the present description, a cut-down algorithm may be used to determine the insertion location of a bootstrap operation in a source partition, as well as to determine the insertion location of a re-curtailment operation in a single partition. First, based on the codes corresponding to SMOPLC, weights of 9 edges E1, E2, and E9 are calculated, and a min-cut algorithm is used to solve for the preferred insertion position of the re-reduction operation. In the minimum cut algorithm, the src node is { Mu lCP _1;Mu lCP_2;Mu lCP_3;Mu lCP_4}, and the snk node is { Mu lCC }. Let l=1, labeled L1, the input ciphertext level. The nodes within the partition are topologically ordered to obtain the sequence Mu lCP _1;Mu lCP_2;AddCC_1;Rot_1;Mu lCP_3;Mu lCP_4;AddCC_2;Rot_2;AddCC_3.

Traversing all nodes in turn according to the topological order, and calculating the weights of all edges, wherein the weights of all edges are as follows:

wherein, the Representing the execution time for executing one more downscaling operation at level 1; representing the execution time of the execution node AddCC _1 at level 1, Representing the execution time of execution node AddCC _1 at level 0 and, similarly,Representing the execution time of the execution node AddCC _2 at level 1,Representing the execution time of execution node AddCC _2 at level 0; represents the execution time of the node Rot _1 at the level 1, Representing the execution time of the execution node rot_1 at level 0; Represents the execution time of the node Rot _2 at the level 1, The execution time of the execution node rot_2 at level 0 is represented.

After the weights of 9 edges E1, E2, E9 are calculated, the preferred insertion position for the re-reduction operation can be obtained by invoking the existing min-cut algorithm.

Then, assume that a re-reduction operation is inserted after multiplication Mu lCP _1, mu lCP _2, mu lCP _3, mu lCP _4, and the bootstrapping operation outputs the ciphertext level as l _bts. Based on the codes corresponding to BTSPLC, weights of 9 edges E1, E2, and E9 are calculated, and a least squares algorithm is used to solve for the preferred insertion position of the bootstrap operation. In the minimum cut algorithm, the src node is { Mu lCP _1;Mu lCP_2;Mu lCP_3;Mu lCP_4}, and the snk node is { Mu lCC }. The nodes in the partition are subjected to reverse topological ordering to obtain a sequence of Mu lCC, addCC-3;Rot_1;AddCC_1;Mu lCP_1;Mu lCP_2;Rot_2;AddCC_2;Mu lCP_3;Mu lCP_4.

Traversing all nodes in turn according to the reverse topological order, and calculating the weights of all sides, wherein the weights of all sides are as follows:

wherein, the Representing the execution time of the bootstrap operation when the output ciphertext level is l _bts; Representing the execution time of the execution node AddCC _3 at the ciphertext level l _bts, The execution time of execution node AddCC _3 at ciphertext level 0 is represented. In a similar manner to that described above,Representing the execution time of the execution node AddCC _2 at the ciphertext level l _bts,Representing the execution time of execution node AddCC _2 at ciphertext level 0; Representing the execution time of the execution node Rot _1 at the ciphertext level l _bts, Representing the execution time of the execution node rot_1 at ciphertext level 0; Representing the execution time of the execution node Rot _2 at the ciphertext level l _bts, The execution time of the execution node rot_2 at the ciphertext level 0 is represented.

After the weights of the 9 edges E1, E2, E9 are calculated, the preferred insertion position of the bootstrap operation can be obtained by calling the existing minimum cut algorithm.

According to the embodiment of the specification, on one hand, an insertion scheme of a re-reduction operation and a bootstrap operation can be quickly constructed, and on the basis of test results of various machine learning models, the compiling time of each model is not more than 1 second. The isotactic state calculation program generated based on the scheme has higher execution efficiency compared with the isotactic state calculation program generated by the common scheme.

The method comprises the steps of firstly converting a plaintext calculation program into a first isohomomorphic calculation program, then constructing a value flow graph according to homomorphic operations contained in the first isohomomorphic calculation program, wherein nodes in the value flow graph correspond to homomorphic operations, directed edges in the value flow graph correspond to data transfer among the nodes, dividing the value flow graph into a plurality of subareas based on multiplication depths respectively corresponding to the nodes in the value flow graph, traversing each subarea according to a topological sequence to execute the first operation, regarding a current subarea as a source subarea, regarding a plurality of subareas of which a plurality of subareas are respectively destination subareas after the current subarea as edge weights, determining candidate positions for inserting the target operations by adopting a minimum segmentation algorithm, determining target insertion positions for cutting off the target operations of the destination subareas according to the candidate positions, performing the target operations including a curtailment operation and a bootstrap operation, and finally generating a second isohomomorphic calculation program according to the target insertion positions obtained by traversing. From the above, in the embodiment of the present disclosure, a divide-and-conquer strategy is adopted, and the insertion positions of the re-reduction operation and the bootstrap operation are analyzed based on the partition and the minimum cut algorithm, where each minimum cut algorithm only needs to be specific to a single partition, so that the compiling time is controllable, the insertion positions of the re-reduction operation and the bootstrap operation in the single partition are better, the partition interval is divided by combining the source partition and the destination partition, and the target insertion position of the target operation of each destination partition is determined according to the candidate position in the single partition, so that the overall execution efficiency is better, the compiling time can be shortened, and the execution efficiency of the isotactic computing program is improved.

According to an embodiment of another aspect, there is also provided a generation apparatus of an isomorphic calculation program for executing the method provided by the embodiments of the present specification. Fig. 7 shows a schematic block diagram of a generation device of an isomorphic calculation program according to one embodiment. As shown in fig. 7, the apparatus 700 includes:

a conversion unit 71 for converting the plaintext calculation program into a first isomorphic calculation program;

A construction unit 72, configured to construct a value flow graph according to each homomorphic operation included in the first homomorphic calculation program obtained by the conversion unit 71, where nodes in the value flow graph correspond to homomorphic operations, and directed edges in the value flow graph correspond to data transfer between the nodes;

A dividing unit 73, configured to divide the value flow graph into a plurality of partitions based on multiplication depths corresponding to each node in the value flow graph obtained by the constructing unit 72;

A planning unit 74, configured to traverse each partition obtained by the dividing unit 73 according to a topological order, and perform a first operation of determining, for a plurality of partition sections taking a current partition as a source partition and a plurality of partitions after the current partition as destination partitions, a candidate position for inserting the target operation by using a minimum cut algorithm with an added value of execution time of each homomorphic operation after inserting the target operation as an edge weight;

A generating unit 75 for generating a second isomorphic calculation program according to the target insertion position obtained by the traversal of the planning unit 74.

Alternatively, as an embodiment, the construction unit 72 includes:

A loop processing subunit, configured to, for a loop of homomorphic multiplication operations included in the first homomorphic calculation program, expand the loop if an amplification factor of a ciphertext output by the homomorphic multiplication operation in the loop increases;

the construction subunit is used for respectively constructing corresponding nodes according to homomorphic operation in the loop and homomorphic operation outside the loop, which are obtained by the loop processing subunit, and marking the execution times of the nodes, wherein the execution times of the nodes in the loop are marked as the loop times, and the execution times of the nodes outside the loop are marked as 1.

Alternatively, as an embodiment, the dividing unit 73 includes:

The calculating subunit is used for traversing each node forward according to the topological sequence of each node in the value flow diagram and calculating the initial multiplication depth of each node;

The updating subunit is used for traversing each node reversely according to the reverse topological sequence of each node in the value flow diagram, and updating the multiplication depth of each node obtained by the calculation subunit to the maximum value allowed to obtain the optimized multiplication depth;

and the dividing subunit is used for dividing the nodes with the same optimized multiplication depth obtained by the updating subunit into the same partition of the value flow graph.

Further, the updating subunit is specifically configured to:

traversing each node reversely according to the reverse topological sequence of each node in the value flow graph, and calculating the maximum multiplication depth allowed by the subsequent nodes of the current node under the topological sequence;

If the current node is a multiplication node and its multiplication depth is less than the maximum multiplication depth allowed by its successor nodes, the multiplication depth of the current node is updated, and the multiplication depths of all other nodes within the current multiplication depth that depend on the current node are updated.

Optionally, as an embodiment, the planning unit 74 includes:

a first planning subunit configured to determine a first candidate location for inserting a bootstrap operation within the source partition based on a minimal cut algorithm;

And the second planning subunit is used for determining a first partition set needing to be inserted with the re-reduction operation from each partition between the source partition and the destination partition for any partition interval, and determining a second candidate position for inserting the re-reduction operation in each partition of the first partition set based on a minimum segmentation algorithm.

Optionally, as an embodiment, the planning unit 74 is specifically configured to determine, for an arbitrary first partition section having the first destination partition, a first target position of the partition that is blocked by the first destination partition, based on the first candidate position corresponding to the first partition section and a previous insertion position determined by taking the previous partition as the source partition, and based on the execution time of the related homomorphic operation, and attribute the first target position to the target insertion position.

Further, the prior insertion locations include a first insertion location from a first partition to a previous partition of the current partition, and a second insertion location from the first partition to the first destination partition;

The planning unit 74 is specifically configured to:

Determining the section execution time for executing homomorphic operation in the first partition interval according to the first candidate position;

acquiring a first execution time corresponding to a first insertion position and a second execution time corresponding to a second insertion position;

And if the sum of the section execution time and the first execution time is smaller than the second execution time, determining a first insertion position and the first candidate position as a first target position, and if not, determining the second insertion position as the first target position.

Further, the section execution time is the sum of the execution time of each homomorphic operation in the first partition interval, and the execution time of any homomorphic operation is obtained by searching from the execution time of each hierarchy of the homomorphic operation obtained by the pre-test according to the hierarchy of the homomorphic operation.

Further, the number of partitions corresponds to a maximum level of bootstrap operation.

Further, the first planning subunit is specifically configured to:

Taking the execution time of the bootstrap operation after the bootstrap operation is inserted and the added value of the execution time of each homomorphic operation as the weight of each side in the source partition;

The cut that minimizes edge weight in the source partition is selected as the first candidate location for inserting bootstrap operations within the source partition.

Further, the second planning subunit is specifically configured to traverse each partition from the source partition to the destination partition in a forward direction, and sequentially select a partition that is inserted into the second planning subunit and reduces the amplification factor of the destination partition to the greatest extent after the second planning subunit is further reduced.

Further, the second planning subunit is specifically configured to:

The execution time of the re-reduction operation after the re-reduction operation is inserted and the added value of the execution time of each homomorphic operation are used as the weight of each side in a single partition;

the cut that minimizes the edge weight in the single partition is selected as the second candidate location for the insert-in-re-reduction operation within the single partition.

Further, the minimum cut algorithm is calculated based on the weight of each edge and the set source node and sink node.

The device provided by the embodiment of the specification comprises the steps of firstly converting a plaintext calculation program into a first isohomomorphic calculation program by a conversion unit 71, then constructing a value flow diagram by a construction unit 72 according to each homomorphic operation contained in the first isohomomorphic calculation program, wherein nodes in the value flow diagram correspond to homomorphic operations, directed edges in the value flow diagram correspond to data transmission among the nodes, dividing the value flow diagram into a plurality of subareas by a dividing unit 73 based on multiplication depths corresponding to the nodes in the value flow diagram, traversing each subarea by a planning unit 74 according to a topological sequence, performing the first operation of determining candidate positions for inserting the target operation by a minimum cutting algorithm by taking a plurality of subareas after the current subarea as a target subarea as edges according to a plurality of subareas respectively taking the target subareas after the current subarea as the subarea, determining target insertion positions for cutting off the target operation according to the candidate positions, determining target insertion positions of the target operation of each target subarea, performing the target operation by a planning unit 74 according to the target insertion positions, and finally generating a second isomorphic calculation program according to the target insertion positions. From the above, in the embodiment of the present disclosure, a divide-and-conquer strategy is adopted, and the insertion positions of the re-reduction operation and the bootstrap operation are analyzed based on the partition and the minimum cut algorithm, where each minimum cut algorithm only needs to be specific to a single partition, so that the compiling time is controllable, the insertion positions of the re-reduction operation and the bootstrap operation in the single partition are better, the partition interval is divided by combining the source partition and the destination partition, and the target insertion position of the target operation of each destination partition is determined according to the candidate position in the single partition, so that the overall execution efficiency is better, the compiling time can be shortened, and the execution efficiency of the isotactic computing program is improved.

According to an embodiment of another aspect, there is also provided a computer-readable storage medium having stored thereon a computer program which, when executed in a computer, causes the computer to perform the method described in connection with fig. 3.

According to an embodiment of yet another aspect, there is also provided a computing device including a memory having executable code stored therein and a processor that, when executing the executable code, implements the method described in connection with fig. 3.

Those skilled in the art will appreciate that in one or more of the examples described above, the functions described in the present invention may be implemented in hardware, software, firmware, or any combination thereof. When implemented in software, these functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium.

The foregoing embodiments have been provided for the purpose of illustrating the general principles of the present invention in further detail, and are not to be construed as limiting the scope of the invention, but are merely intended to cover any modifications, equivalents, improvements, etc. based on the teachings of the invention.

Claims (16)

1. A method for generating a fully homomorphic computing program, the method comprising: Converting the plaintext computing program into a first fully homomorphic computing program; According to each homomorphic operation included in the first fully homomorphic computing program, a value flow graph is constructed; the nodes in the value flow graph correspond to the homomorphic operations, and the directed edges in the value flow graph correspond to the transmission of data between the nodes; Dividing the value stream graph into a plurality of partitions based on the multiplication depths corresponding to the respective nodes in the value stream graph; Traverse each partition in topological order and perform the following first operation: for a current partition as a source partition, several partitions after the current partition are respectively several partition intervals of the target partition, and the increase in the execution time of each homomorphic operation after inserting the target operation is used as the edge weight, a minimum cut algorithm is used to determine a candidate position for inserting the target operation; based on the candidate position, a target insertion position of the target operation of each target partition is determined; the target operation includes a reduction operation and a bootstrap operation; A second fully homomorphic computing program is generated according to the target insertion position obtained through traversal. 2. The method of claim 1, wherein constructing a value flow graph according to each homomorphic operation included in the first fully homomorphic computing program comprises: For a loop of homomorphic multiplication operations included in the first fully homomorphic computing program, if the amplification factor of the ciphertext output by the homomorphic multiplication operation in the loop increases, then expand the loop; if the amplification factor of the ciphertext output by the homomorphic multiplication operation in the loop remains unchanged, then retain the loop; Corresponding nodes are constructed for homomorphic operations within the loop and homomorphic operations outside the loop, and the execution times of the nodes are marked; among them, for nodes within the loop, the execution times are recorded as the loop times; for nodes outside the loop, the execution times are 1. 3. The method of claim 1, wherein the dividing the value stream graph into a plurality of partitions based on the multiplication depths corresponding to the nodes in the value stream graph comprises: Forward traverse each node in the value flow graph according to the topological order of each node, and calculate the initial multiplication depth of each node; Traversing each node in the value flow graph in reverse order according to the inverse topological order of each node, and updating the multiplication depth of each node to the maximum allowed value to obtain an optimized multiplication depth; Nodes with the same optimized multiplication depth are divided into the same partition of the value stream graph. 4. The method of claim 3, wherein the step of traversing each node in the value stream graph in reverse order according to the inverse topological order of each node and updating the multiplication depth of each node to the maximum allowed value to obtain the optimized multiplication depth comprises: Traverse each node in reverse order according to the inverse topological order of each node in the value stream graph, and calculate the maximum multiplication depth allowed for the successor node of the current node in the topological order; If the current node is a multiplication node and its multiplication depth is less than the maximum multiplication depth allowed by its successor node, the multiplication depth of the current node is updated, and the multiplication depths of all other nodes within the current multiplication depth that depend on the current node are updated. 5. The method of claim 1, wherein the step of using a minimum cut algorithm to determine a candidate location for inserting the target operation comprises: Determine a first candidate location for inserting a bootstrap operation in the source partition based on a minimum cut algorithm; For any partition interval, a first partition set where a re-reduction operation needs to be inserted is determined from each partition between the source partition and the target partition, and a second candidate position for inserting the re-reduction operation in each partition of the first partition set is determined based on a minimum cut algorithm. 6. The method according to claim 1, wherein determining the target insertion position of the target operation ending at each target partition according to the candidate position comprises: For any first partition interval with a first destination partition, based on its corresponding first candidate position and the previous insertion position determined with the previous partition as the source partition, according to the execution time of the homomorphic operations involved, the first target position up to the first destination partition is determined and included in the target insertion position. 7. The method of claim 6, wherein the previous insertion position comprises a first insertion position from the first partition to a partition preceding the current partition, and a second insertion position from the first partition to the first destination partition; Determining a first target position of a first destination partition according to an execution time of the homomorphic operation involved includes: Determine, according to the first candidate position, a segment execution time for executing a homomorphic operation within the first partition interval; Obtain a first execution time corresponding to the first insertion position, and a second execution time corresponding to the second insertion position; If the sum of the segment execution time and the first execution time is less than the second execution time, the first insertion position and the first candidate position are determined as the first target position; otherwise, the second insertion position is determined as the first target position. 8. A method as claimed in claim 7, wherein the segment execution time is the sum of the execution times of each homomorphic operation within the first partition interval; the execution time of any homomorphic operation is obtained by searching the execution time of each level of the homomorphic operation obtained in advance according to its level. 9. The method of claim 1, wherein the number of partitions corresponds to a maximum level of a bootstrap operation. 10. The method of claim 5, wherein the determining the first candidate position for inserting the bootstrap operation in the source partition based on the minimum cut algorithm comprises: The execution time of the bootstrap operation after the bootstrap operation is inserted and the increase in the execution time of each homomorphic operation are used as the weight of each edge in the source partition; The cut that minimizes the edge weight in the source partition is selected as the first candidate location for inserting the bootstrap operation in the source partition. 11. The method of claim 5, wherein the step of determining the first set of partitions to be inserted into the re-reduction operation from the partitions between the source partition and the target partition comprises: Traverse the partitions from the source partition to the destination partition in a forward direction, and select the partitions that reduce the amplification factor of the destination partition the most after the insert and reduce operations. 12. The method of claim 5, wherein the determining the second candidate position for inserting the re-reduction operation in each partition of the first set of partitions based on the minimum cut algorithm comprises: The execution time of the re-reduce operation after the re-reduce operation is inserted, as well as the increase in the execution time of each homomorphic operation, are used as the weights of each edge in a single partition; The cut that minimizes the edge weight in a single partition is selected as the second candidate position for inserting the re-reduce operation in the single partition. 13. The method of claim 10, wherein the minimum cut algorithm performs calculations based on the weight of each edge and a set source node and sink node. 14. A device for generating a fully homomorphic computing program, the device comprising: A conversion unit, used to convert the plaintext computing program into a first fully homomorphic computing program; A construction unit, configured to construct a value flow graph according to each homomorphic operation included in the first fully homomorphic computing program obtained by the conversion unit; the nodes in the value flow graph correspond to the homomorphic operations, and the directed edges in the value flow graph correspond to the transfer of data between the nodes; A partitioning unit, configured to divide the value stream graph into a plurality of partitions based on the multiplication depths respectively corresponding to the nodes in the value stream graph obtained by the construction unit; The planning unit is used to traverse each partition obtained by the partitioning unit in a topological order and perform the following first operation: for a current partition as a source partition, several partitions after the current partition are respectively several partition intervals of the target partition, and the increase in the execution time of each homomorphic operation after the target operation is inserted is used as the edge weight, and a minimum cut algorithm is used to determine a candidate position for inserting the target operation; according to the candidate position, a target insertion position of the target operation of each target partition is determined; the target operation includes a reduction operation and a bootstrap operation; A generating unit is used to generate a second fully homomorphic computing program according to the target insertion position obtained by the traversal of the planning unit. 15. A computer-readable storage medium having a computer program stored thereon, which, when executed in a computer, causes the computer to execute the method according to any one of claims 1 to 13. 16. A computing device comprising a memory and a processor, wherein the memory stores executable codes, and when the processor executes the executable codes, the method according to any one of claims 1 to 13 is implemented.