Polynomial fully homomorphic encryption system based on coefficient mapping transform

Abstract

A polynomial complete homomorphic encryption method based on the coefficient mapping transformation. A plaintext is expressed as a polynomial consisting of a set of random values, two sets of random coefficient factors and a random constant of a specified mapping function, and in the polynomial: the expression and a set of random coefficient factors of the specified mapping function are taken as a key; another set of random coefficient factors, a set of random arguments and random constants of the mapping function are taken as the ciphertexts for homomorphic operations, so that the part of function key performs three different mappings and then undergoes numerical fitting to obtain the family of operational support functions consisting of three sub-functions respectively, which are used to perform the homomorphic operation of the ciphertext based on the family of operational support functions and return to the locality for decryption by the key.

Claims

1. A polynomial complete homomorphic encryption system comprising: a client; and a server; wherein the client consists of a circuit which is configured to generate a key K and an operation supporting function family G, and to encrypt a plaintext P or decrypt a ciphertext C; wherein the server consists of a memory which is configured to receive the ciphertext C and the operation supporting function family G, and a circuit which is to perform a homomorphic operation on the ciphertext according to the operation supporting function family G; wherein, for the plaintext PR of any real number, real-number vectors of A={a.sub.i|iI} and Y={y.sub.i|iI} are randomly chosen, satisfying that: $\{\begin{array}{c}\underset{iI}{.Math.}{a}_i.Math.f\left(x_i\right).Math.y_i+B=P\\ f\left(x_i\right)>0\end{array}$ wherein f(x) is differentiable, and real-number vectors are X={x.sub.i|iI} and BR, I is a subscript set of a polynomial key dimension, f(x.sub.i) is a function key part, the corresponding key generated is K={f ( ), Y}, and the ciphertext for P is C={A, X, B}; wherein the homomorphic result of the ciphertext is obtained by way of performing the homomorphic operation between the ciphertexts or between the plaintext and the ciphertext through the operation supporting function family G at different places; and wherein the homomorphic result of the plaintext is obtained via decryption by way of substituting the homomorphic result of the ciphertext into f and Y in the key of K.

2. The system as claimed in claim 1, characterized in that the server is provided with a database for storing ciphertexts.

3. The system as claimed in claim 1, characterized in that the server is provided with a ciphertext ID corresponding to the cached ciphertext.

4. The system as claimed in claim 1, characterized in that the client is provided with a key access control mechanism, which ensures that the visitor owns the authority to access the key by the way of authentication.

5. The system as claimed in claim 1, characterized in that the homomorphic operation of the ciphertext based on the family of operational support function family G and return to locality for decryption by the key K; wherein the plaintext P is expressed as a polynomial consisting of a set of random values, two sets of random coefficient factors and a random constant of a specified mapping function, and in the polynomial: the expression and a set of random coefficient factors of the specified mapping function are taken as a the key K; another set of random coefficient factors, a set of random arguments and random constants of the mapping function are taken as the ciphertexts for the homomorphic operations, so that the part of function key performs three different mappings and then undergoes numerical fitting to obtain the operational support function family G consisting of three sub-functions.

6. The system as claimed in claim 5, characterized in that the numerical fitting adopts the least square method.

7. The system as claimed in claim 5, characterized in that the homomorphic operations comprise addition, subtraction, multiplication and division, and any combination thereof.

8. The system as claimed in claim 5, characterized in that the operation supporting function G generated encrypts itself through the randomly generated function.

9. The system as claimed in claim 5, characterized in that; the operation supporting function family G used for the homomorphic operation of ciphertext comprises: $\{\begin{array}{c}{g}_1\left(,\right)\\ g_2\left(,\right)\\ g_3\left(,\right)\end{array},$ wherein: g.sub.1(,) is the numerical fitting of $\frac{f\left(\right)}{f\left(h_1\left(,\right)\right)}{g}_2\left(,\right)$ is the numerical fitting of $\frac{f\left(\right)}{f\left(h_1\left(,\right)\right)},$ g.sub.3 (,) is the numerical fitting of $\frac{f\left(\right).Math.f\left(\right)}{f\left(h_2\left(,\right)\right)},$ while X, h.sub.1(,) and h.sub.2(,) are any functions that satisfy h.sub.1 (,)h.sub.2 (,). the corresponding homomorphic operation comprises: i) addition and subtraction between ciphertext and ciphertext: C.sub.r=C.sub.2C.sub.1, C.sub.r={A.sub.r, X.sub.r, B.sub.r}, wherein:
A.sub.r={.sub.ri|iI},.sub.ri=.sub.2i.Math.g.sub.2(x.sub.1i,x.sub.2i).sub.1i.Math.g.sub.1(x.sub.1i,x.sub.2i),
X.sub.r={x.sub.ri|iI},x.sub.ri=h.sub.1(x.sub.2i,x.sub.1i),
B.sub.r=B.sub.2B.sub.1; ii) multiplication between ciphertext and ciphertext: C.sub.r=C.sub.3.Math.C.sub.4, C={A.sub.r,X.sub.r,B.sub.r}, wherein:
A.sub.r={a.sub.rij|iI,jI}{B.sub.4.Math.a.sub.3i|iI}{B.sub.3.Math.a.sub.4j|jI},a.sub.rij=a.sub.3i.Math.a.sub.4i.Math.g.sub.3(x.sub.3,x.sub.4),
X.sub.r={x.sub.rij|iI,jI}{x.sub.3i|iI}{x.sub.4j|jI},x.sub.rij=h.sub.2(x.sub.3i,x.sub.4i),
B.sub.r=B.sub.3.Math.B.sub.4; ii) division between ciphertext and ciphertext: C.sub.r=C.sub.a/C.sub.b, C.sub.r={A.sub.5,X.sub.5,B.sub.5,A.sub.6,X.sub.6,B.sub.6} wherein:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.3.Math.a.sub.1i|iI}{B.sub.1.Math.a.sub.3i|jI},a.sub.5ij=a.sub.1i.Math.a.sub.3j.Math.g.sub.3(x.sub.1,x.sub.3),
X.sub.5={x.sub.5ij|iI,jI}{x.sub.1i|iI}{x.sub.3j|jI},x.sub.5ij=h.sub.2(x.sub.1i,x.sub.3j),
B.sub.5=B.sub.1.Math.B.sub.3
A.sub.6={a.sub.6ij|iI,jI}{B.sub.4.Math.a.sub.2i|iI}{B.sub.2.Math.a.sub.4j|jI},a.sub.6ij=a.sub.2i.Math.a.sub.4j.Math.g.sub.3(x.sub.2,x.sub.4),
X.sub.6={x.sub.6ij|iI,jI}{x.sub.2i|iI}{x.sub.4j|jI},x.sub.6ij=h.sub.2(x.sub.2i,x.sub.4j),
B.sub.6=B.sub.2.Math.B.sub.4.

10. The system as claimed in claim 5, characterized in that the operation supporting function G comprises: $\{\begin{array}{c}{g}_1\left(,,\right)\\ g_2\left(,,\right)\end{array},$ wherein g.sub.1(,,) is the numerical fitting of $\frac{h_3\left(\right).Math.\left[f\left(\right)+.Math.f\left(\right)\right]}{f\left(h_1\left(,\right)\right)},$ g.sub.2(,) is the numerical fitting of $\frac{f\left(\right).Math.f\left(\right)}{f\left(h_2\left(,\right)\right)},$ X, h.sub.1(,), h.sub.2(,) and h.sub.3(,) are any functions that satisfy h.sub.1(,)h.sub.2(,)h.sub.3(,); the corresponding homomorphic operation comprises: i) addition and subtraction between ciphertext and ciphertext: C.sub.r=C.sub.2C.sub.1, C.sub.r={A.sub.r,X.sub.r,B.sub.r}, wherein: $A_r=\left\{a_{\mathrm{ri}}.Math.iI\right\},a_{\mathrm{ri}}=a_{2i}.Math.g_1\left(x_{2i},x_{1i},\frac{a_{1i}}{a_{2i}}\right)/h_3\left(\frac{a_{1i}}{a_{2i}}\right),X_r=\left\{x_{\mathrm{ri}}.Math.iI\right\},x_{\mathrm{ri}}=h_1\left(x_{2i},x_{1i}\right),B_r=B_2{B}_1;$ ii) multiplication between ciphertext and ciphertext: C.sub.r=C.sub.3.Math.C.sub.4, C={A.sub.rX.sub.r,B.sub.r}, wherein:
A.sub.r={a.sub.rij|iI,jI}{B.sub.4.Math.a.sub.3i|iI}{B.sub.3.Math.a.sub.4j|jI},a.sub.rij=a.sub.3i.Math.a.sub.4j.Math.g.sub.2(x.sub.3,x.sub.4),
X.sub.r={x.sub.rij|iI,jI}{x.sub.3i|iI}{x.sub.4j|jI},x.sub.rij=h.sub.2(x.sub.3i,x.sub.4i),
B.sub.r=B.sub.3.Math.B.sub.4; ii) division between ciphertext and ciphertext: C.sub.r=C.sub.a/C.sub.b, C.sub.r={A.sub.5, X.sub.5, B.sub.5, A.sub.6, X.sub.6, B.sub.6}, wherein:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.3.Math.a.sub.1i|iI}{B.sub.1.Math.a.sub.3j|jI},a.sub.5ij=a.sub.1i.Math.a.sub.3j.Math.g.sub.2(x.sub.1,x.sub.3)
X.sub.5={x.sub.5ij|iI,jI}{x.sub.1i|iI}{x.sub.3j|jI},x.sub.5ij=h.sub.2(x.sub.1i,x.sub.3j),
B.sub.5=B.sub.1.Math.B.sub.3,
A.sub.6={a.sub.6ij|iI,jI}{B.sub.4.Math.a.sub.2i|iI}{B.sub.2.Math.a.sub.4j|jI},a.sub.6ij=a.sub.2i.Math.a.sub.4j.Math.g.sub.2(x.sub.2,x.sub.4),
X.sub.6={x.sub.6ij|iI,jI}{x.sub.2i|iI}{x.sub.4j|jI},x.sub.6ij=h.sub.2(x.sub.2i,x.sub.4i),
B.sub.6=B.sub.2.Math.B.sub.4.

11. The system as claimed in claim 5, characterized in that the operation supporting function G comprises $\{\begin{array}{c}{g}_1\left(,\right)\\ g_2\left(,\right)\\ g_3\left(,\right)\\ g_4\left(,\right)\\ g_5\left(,\right)\\ g_6\left(,\right)\end{array},$ wherein: g.sub.1(,) is the numerical fitting of $\frac{f\left(\right).Math.f\left(h_3\left(,\right)\right)}{f_2\left(h_1\left(,\right)\right)},$ g.sub.2(,) is the numerical fitting of $\frac{f\left(\right).Math.f\left(h_3\left(,\right)\right)}{f_2\left(h_2\left(,\right)\right)},$ g.sub.3(,) is the numerical fitting of $\frac{f_2\left(\right)}{f\left(h_4\left(,\right)\right)},$ g.sub.4(,) is the numerical fitting of $\frac{f_2\left(\right)}{f\left(h_4\left(,\right)\right)}$ g.sub.5(,) is the numerical fitting of $\frac{f\left(\right).Math.f\left(\right)}{f\left(h_5\left(,\right)\right)},$ g.sub.6 (,) is the numerical fitting of $\frac{f\left(\right)}{f\left(\right).Math.f\left(h_6\left(,\right)\right)},$ X, h.sub.1(,), h.sub.2(,), h.sub.3(,) and h.sub.4(,) are any functions that satisfy h.sub.1(,)h.sub.2(,)h.sub.3(,)h.sub.4(,); .sub.2( ) is randomly generated function used for encrypting the operation supporting function, the corresponding homomorphic operation comprises: i) addition and subtraction between ciphertext and ciphertext: C.sub.r=C.sub.2C.sub.1, C.sub.r={A.sub.r,X.sub.r,B.sub.r}, wherein:
A.sub.r{a.sub.ri|iI},
a.sub.ri=g.sub.6.Math.[a.sub.2i.Math.g.sub.1(x.sub.2i,x.sub.1i).Math.g.sub.3(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i))a.sub.1i.Math.g.sub.2(x.sub.2i,x.sub.1i).Math.g.sub.4(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i))],
X.sub.r={x.sub.ri|iI},
x.sub.ri=h.sub.6(h.sub.4(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i)),h.sub.3(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i))),
B.sub.r=B.sub.2B.sub.1; ii) multiplication between ciphertext and ciphertext: C.sub.r=C.sub.3.Math.C.sub.4, C.sub.r={A.sub.r, X.sub.r, B.sub.r}, wherein
A.sub.r={a.sub.rij|iI,jI}{B.sub.4.Math.a.sub.3i|iI}{B.sub.3.Math.a.sub.4j|jI},a.sub.rij=a.sub.3i.Math.a.sub.4j.Math.g.sub.5(x.sub.3,x.sub.4),
X={x.sub.rij|iI,jI}{x.sub.3i|iI}{x.sub.4j|jI},x.sub.rij=h.sub.5(x.sub.3i,x.sub.4j),
B.sub.r=B.sub.3.Math.B.sub.4; ii) division between ciphertext and ciphertext: C.sub.r=C.sub.a/C.sub.b, C.sub.r={A.sub.5,X.sub.5,B.sub.5,A.sub.6,X.sub.6,B.sub.6} wherein:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.3.Math.a.sub.1i|iI}{B.sub.1.Math.a.sub.3j|jI},a.sub.5ij=.sub.1i.Math.a.sub.3j.Math.g.sub.5(x.sub.1,x.sub.3),
X.sub.5={x.sub.5|iI,jI}{x.sub.1i|iI}{x.sub.3j|jI},x.sub.5ij=h.sub.5(x.sub.1i,x.sub.3j),
B.sub.5=B.sub.1.Math.B.sub.3,
A.sub.6={a.sub.6ij|iI,jI}{B.sub.4.Math.a.sub.2i|iI}{B.sub.2.Math.a.sub.4j|j|I},a.sub.6ij=a.sub.2i.Math.a.sub.4j.Math.g.sub.5(x.sub.2,x.sub.4),
X.sub.6={x.sub.6ij|iI,jI}{x.sub.2i|iI}{x.sub.4j|jI},x.sub.6ij=h.sub.5(x.sub.2i,x.sub.4j),
B.sub.6=B.sub.2.Math.B.sub.4.

12. The system as claimed in claim 5, characterized in that the composite function ( ) is a periodic function.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

(1) FIG. 1 is a schematic diagram of the basic application of the invention;

(2) FIG. 2 is a schematic diagram of the process of key generation according to the invention;

(3) FIG. 3 is a schematic diagram of the embodiment of the process of data encryption;

(4) FIG. 4 is the first schematic diagram of the embodiment of the homomorphic operation of ciphertext;

(5) FIG. 5 is the second schematic diagram of the embodiment of the homomorphic operation of ciphertext;

(6) FIG. 6 is a schematic diagram of the embodiment of the process of data decryption.

DETAILED DESCRIPTION OF THE INVENTION

(7) The embodiments of the invention are described in detail below. The embodiments are implemented on the premise of the technical solutions in the invention, with the detailed implementation manners and specific operation procedures given. However, the protection scope of the invention is not limited to the following embodiments.

Embodiment 1

(8) The invention can be implemented in various ways corresponding to different requirement environments and application scenarios, such as USBKey, API, SDK, chip, expansion card, dedicated device. As shown in FIG. 1 and FIG. 2, any way of implementation comprises the client and the server, and the steps of a typical homomorphic encryption operation are as follows:

(9) 1) the client invokes a locally-stored key to encrypt sensitive plaintext data to obtain a ciphertext;

(10) 2) the client sends the ciphertext and the operation request to the server, with the key reserved on the client;

(11) 3) the server invokes the corresponding operation supporting function family and uses the homomorphic function to perform the required operation on the ciphertext uploaded by the client, and then returns the operation result of the ciphertext;

(12) 4) the client receives the resulted ciphertext, invokes the local key to decrypt, and outputs the resulted plaintext.

(13) In such a process, the key and plaintext data only appear on the client, and the data are always in the form of ciphertext throughout the transmission, operation and storage operations, so there is no possibility of data leakage.

(14) The following is a detailed description of the homomorphic encryption operation:

(15) Step 1: a key that consists of the function key part and the polynomial key part is generated on the client as follows:

(16) 1.1) a number of unitary or multivariate functions are randomly chosen, and for each unitary or multivariate function, the parameters are randomly generated for the linear combination or composite combination to form the function key part, that is, ( ).

(17) The unitary functions comprise but are not limited to various analytic functions, such as positive proportional function, inverse proportional function, sine function, cosine function, logarithmic function, exponential function and power function.

(18) For example, a linear combination of a unitary sine function sin(x) and a unitary power function x.sup.3 may form a function key (x)=10 sin(6x)+5x.sup.3, or a composite combination may generate a function key (x)=12 sin(8x.sup.3+6).

(19) When the strength of encryption needs to be increased, the binary or multivariate functions are chosen to constitute the function key part; taking a binary function as an example: (m.sub.i,n.sub.j),iI, jI, the corresponding ciphertext will have more than one dimension, that is C={A, M, N, B} and meanwhile, the operation supporting function family G will become more complex while the corresponding key strength will be increased, but the corresponding amount of operation is also larger.

(20) The function key part is a differentiable function, and its value in the definition domain should be greater than zero.

(21) In this embodiment, preferably, the function key part that changes relatively flatly is used.

(22) The change refers to

(23) $\left|\frac{f}{x}\right|K,xD,$
wherein: D is the definition domain of ( ), K is a positive real number, that is, a flat index.

(24) In this embodiment, preferably, the flat index is less than or equal to 10.

(25) In this embodiment, a basic list of functions satisfying the requirement is preset in a key generation algorithm implemented on the client, so that these basic functions may be randomly combined during generation to obtain the function form of the function key part.

(26) 1.2) The polynomial key part Y{y.sub.i|iI} is randomly generated, thus forming a complete key, that is, K={( ),Y}.

(27) In this embodiment, preferably, the polynomial key part y.sub.i is required to be a positive integer.

(28) The key can be stored in any encryption medium local to the client, such as an encrypted file, an encryption chip, a USB flash drive, or other similar types of memory.

(29) 1.3) The client or server generates the operation supporting function family G={g.sub.1, g.sub.2, g.sub.3} through function fitting which is saved by the server. Since each operation supporting function family G corresponds to a function key, the corresponding user, that is, the unique identifier of the ciphertext sender, needs to be recorded when the server receives the operation supporting function family G.

(30) The fitting generation can be directly performed on the client, and the result of the fitting, that is, the expression of the operation supporting function family G, is transmitted to the server; the client can also perform discrete sampling of the operation supporting function family G and output the sampling point data to the server, so that the operation supporting function family G can be calculated by the server according to the local fitting strategy or the dynamic local fitting strategy;

(31) During the process of computer operations, a problem of precision may occur in the floating-point operation, so the fitting described can be set to the required precision at initialization based on the specific hardware settings.

(32) The operation supporting function family G comprises the numerical fitting of

(33) $\begin{array}{cc}\{\begin{array}{c}{g}_1\left(,\right)\\ g_2\left(,\right)\\ g_3\left(,\right)\end{array}& \left(2\right)\end{array}$

(34) wherein: g.sub.1(,) is the numerical fitting of

(35) $\frac{f\left(\right)}{f\left(h_1\left(,\right)\right)}{g}_2\left(,\right)$
is the numerical fitting of

(36) $\frac{f\left(\right)}{f\left(h_1\left(,\right)\right)},$
g.sub.3(,) is the numerical fitting of

(37) $\frac{f\left(\right).Math.f\left(\right)}{f\left(h_2\left(,\right)\right)},$
while X, h.sub.1(,) and h.sub.2(,) are any functions that satisfy h.sub.1(,)h.sub.2(,).

(38) In this embodiment, h.sub.1=++1, h.sub.2=++2, >0 and >0 are chosen.

(39) Preferably, the operation supporting function family G does not appear in the form of an expression so as to improve the security of the invention; more preferably, it appears in the form of a numerical fitting to express the operation supporting function family G.

(40) In some cases, for example, if the function key part f itself is not complex enough, it can still be solved to a certain degree by some very huge number of operations, and the function key part f can be locally restored by the operation supporting function family G. So a variety of G deformations can be defined to improve the security, and there are many types of such deformations.

(41) The numerical fitting means that the values of G corresponding to each sampling point are recorded through wide and intensive discrete sampling of the definition domain of the operation supporting function family G, and then approximate expressions of G are made through the surface fitting technology; the embodiments are implemented using the surface fitting technology and the numerical calculation technology, such as using the least-square method to perform the surface fitting.

(42) When the surface of the operation supporting function family G is too complex, the numerical value fitting can be obtained by re-splicing upon the local fitting or the method of dynamic local fitting. That is to say, when getting a value by operation is required, the final value can be obtained by means of local surface fitting in the surface area in the vicinity of the value evaluation point.

(43) It is very difficult to restore the expression of without knowing the concrete form of the original function only by computing the fitting expression of the operation supporting function family G or the discrete value point information. This is also one of the security guarantees of the encryption method in the invention.

(44) Described here is the key generation process, that is, the client initialization process. This process is only initialized before a user uses the system for the first time, and the user only needs to directly access the generated key in future use.

(45) Step 2: as shown in FIG. 3, the sensitive data are encrypted by using the generated key as follows:

(46) The data to be encrypted in this embodiment are the production cost P.sub.1 of one product and the total sales contract offer P.sub.2 of the product, both of which are floating-point numerical data.

(47) 2.1) For the function key part ( ), an argument x.sub.i is randomly chosen in its definition domain to obtain the function value (x.sub.i) of the point, and then the function value is multiplied by the corresponding component of the polynomial key to obtain (x.sub.i).Math.y.sub.i, wherein iI and I is the subscript set of the polynomial key dimensions.

(48) Each element in the set of polynomial key dimensions is a positive integer, and the maximum value of 2 can meet the security requirement; the value can be increased according to the encryption strength requirement, and generally, the maximum value should not be greater than 10. If the maximum value is 4, I is equal to the set {1,2,3,4}.

(49) 2.2) a.sub.i is randomly chosen to obtain an item, .sub.i.Math.(x.sub.i).Math.y.sub.i, of the ciphertext polynomial.

(50) 2.3) Step 2.12.2 are repeated until iterating through the set of I, and

(51) $\underset{iI}{.Math.}{a}_i.Math.f\left(x_i\right).Math.y_i$
is finally obtained.

(52) 2.4) B is obtained by Formula 1), and so far, all components of the ciphertext, A={a.sub.i|iI} and X={x.sub.i|iI}, as well as B, have been obtained. The ciphertext C.sub.2 corresponding to the preceding plaintext P.sub.2 is obtained in this process.

(53) When the function key part is a binary function, the corresponding ciphertext is C={A, M, N, B} and the corresponding encryption strength is greatly improved.

(54) Step 3: as shown in FIG. 5, after the server obtains multiple ciphertexts, homomorphic operations on ciphertexts, including addition, subtraction, multiplication and division, are performed based on the operation supporting function family G stored on the server.

(55) i) The addition and subtraction in homomorphism are taken as an example. Supposing an enterprise needs to calculate the gross profit of the product sales contract, wherein the production cost of the product is sensitive data and its ciphertext is C.sub.1; the total offer of the contract is sensitive data and its ciphertext is C.sub.2; the quantity of product sales is the non-sensitive data of the open bidding without encryption and its value is 100, then the gross profit of the contract can be calculated as ciphertext C.sub.3, that is C.sub.3=C.sub.2100*C.sub.1, and the server can obtain the gross profit C.sub.3, that is C.sub.3={A.sub.3, X.sub.3, B.sub.3}, by sequentially calculating 100.Math.C.sub.1 and C.sub.2100.Math.C.sub.1, wherein:
A.sub.3={a.sub.3i|iI},a.sub.3i=a.sub.2i.Math.g.sub.2(x.sub.1i,x.sub.2i)100.Math.a.sub.1i.Math.g.sub.1(x.sub.1i,x.sub.2i)
X.sub.3={x.sub.3i|iI},x.sub.3i=h.sub.1(x.sub.2i,x.sub.1i)
B.sub.3=B.sub.2100.Math.B.sub.1

(56) The calculation result of the homomorphic encryption may be stored in a ciphertext manner in a database and used in other operations afterwards without needing to know the actual value of the ciphertext, and only when the form is displayed or the report is printed, the decryption algorithm is invoked on the client and the plaintext can be restored, for the authorized user who owns the key.

(57) ii) The multiplication in homomorphism is taken as an example. Supposing an enterprise signs the same product sales contract with several customers at the same time with the number of contracts being sensitive data and the ciphertext being C.sub.4, the total gross profit C.sub.5 is: C.sub.5=C.sub.3.Math.C.sub.4 and C.sub.5={A.sub.5, X.sub.5, B.sub.5}, wherein:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.4.Math.a.sub.3i|iI}{B.sub.3.Math.a.sub.4j|jI},a.sub.5ij=a.sub.3i.Math.a.sub.4j.Math.g.sub.3(x.sub.3,x.sub.4)
X.sub.5={x.sub.5ij|iI,jI}{x.sub.3i|iI}{x.sub.4j|jI},x.sub.5ij=h.sub.2(x.sub.3i,x.sub.4j)
B.sub.5=B.sub.3.Math.B.sub.4

(58) iii) The division of homomorphism is taken as an example. The polynomial division algorithm is used to introduce the fractional expression, and after the denominator polynomial is increased, the division is converted into the combination of addition and multiplication, so that the calculation result is obtained finally. Therefore, in the context of division, the expression of a more general plaintext should be in a fractional form, such as

(59) $P=\frac{P_1}{P_2}=\frac{\underset{iI}{.Math.}{a}_{1i}.Math.f\left(x_{1i}\right).Math.y_i+B_1}{\underset{iI}{.Math.}{a}_{2i}.Math.f\left(x_{2i}\right).Math.y_i+B_2}.$

(60) The ciphertext is specifically expressed as:

(61) $P_a=\frac{P_1}{P_2}=\frac{\underset{iI}{.Math.}{a}_{1i}.Math.f\left(x_{1i}\right).Math.y_i+B_1}{\underset{iI}{.Math.}{a}_{2i}.Math.f\left(x_{2i}\right).Math.y_i+B_2}$$C_a=\left\{A_1,X_1,B_1,A_2,X_2,B_2\right\}$$P_b=\frac{P_3}{P_4}=\frac{\underset{iI}{.Math.}{a}_{3i}.Math.f\left(x_{3i}\right).Math.y_i+B_3}{\underset{iI}{.Math.}{a}_{4i}.Math.f\left(x_{4i}\right).Math.y_i+B_4}$$C_b=\left\{A_3,X_3,B_3,A_4,X_4,B_4\right\}$

(62) then the result C.sub.r={A.sub.5, X.sub.5, B.sub.5, A.sub.6, X.sub.6, B.sub.6} of the division C.sub.r=C.sub.a/C.sub.h is:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.3.Math.a.sub.1i|iI}{B.sub.1.Math.a.sub.3j|jI},a.sub.5ij=a.sub.1i.Math.a.sub.3j.Math.g.sub.3(x.sub.1,x.sub.3)
X.sub.5={x.sub.5ij|iI,jI}{x.sub.1i|iI}{x.sub.3j|jI},x.sub.5ij=h.sub.2(x.sub.1i,x.sub.3j)B.sub.5=B.sub.1.Math.B.sub.3
A.sub.6={a.sub.6ij|iI,jI}{B.sub.4.Math.a.sub.2i|iI}{B.sub.2.Math.a.sub.4j|jI},a.sub.6ij=a.sub.2i.Math.a.sub.4jg.sub.3(x.sub.2,x.sub.4)
X.sub.6={x.sub.6ij|iI,jI}{x.sub.2i|iI}{x.sub.4j|jI},x.sub.6ij=h.sub.2(x.sub.2i,x.sub.4j)B.sub.6=B.sub.2.Math.B.sub.4

(63) In a fractional form, when the ciphertext homomorphism addition is performed, the fractions must be reduced to a common denominator, that is, the molecular part of a ciphertext is multiplied by the denominator part of another ciphertext as a new molecule, and then the new molecule is summed up with a new molecule part of another ciphertext upon the same operation to generate the numerator of the result. At the same time, the denominator parts of two ciphertexts are multiplied as the denominator of the result, and the final result is obtained after simplification.

(64) In a fractional form, when the homomorphic operation of multiplication of the ciphertext is performed, the numerator and denominator of the two ciphertexts are multiplied respectively as a new numerator and denominator, and the final result is obtained after simplification.

(65) In Step 3, when the homomorphic operation is performed on the server, the server may adopt the ciphertext-ID-based method to perform the homomorphic calculation upon retrieval to the cached ciphertext or through the acceptance of the ciphertext and operator sent by the client directly.

(66) The ciphertext ID is an ID number corresponding to the cached ciphertext, and preferably, the ID number is stored on the client.

(67) As shown in FIG. 4, in order to use the process of the ciphertext ID homomorphic operation, the specific steps comprise:

(68) 1) The client obtains the operation instruction, including the ciphertext ID that needs to be involved in the operation and the operation operators and other parameters that need to be performed.

(69) 2) The ciphertext ID, the homomorphic operator and the operation parameters are sent to the server to retrieve the corresponding ciphertext and wait for the operation; after receiving the instruction, the server first reads the corresponding the operation supporting function family and then performs the homomorphic operation on the ciphertext retrieved in the previous step according to the operation instruction.

(70) 3) The server returns the result of the homomorphic operation to the operation requester, and the operation result is still in the form of ciphertext.

(71) As shown in FIG. 5, in order to directly use the ciphertext instead of the homomorphic operation of the ciphertext ID, the specific steps comprise:

(72) i) the arithmetic instructions, including the ciphertext to be calculated, arithmetic operators and other parameters, are obtained;

(73) ii) the ciphertext, operator, operation parameters and other data are sent to the server;

(74) iii) after obtaining the operation instruction, the server reads the corresponding operation supporting function family and completes the operation requirement on the ciphertext to obtain the ciphertext of the operation result;

(75) iv) the server returns the operation result to the operation requester.

(76) In Step 4, as shown in FIG. 6, when the client obtains the resulted ciphertext upon the homomorphic operation from the server, the resulted ciphertext is substituted into the encryption formula (1) to obtain the corresponding plaintext result.

(77) In case the original plaintext data are numerical, the result of the decryption in the previous step is the final result; otherwise, the type conversion is needed to obtain the final decryption result.

Embodiment 2

(78) The difference between this embodiment and Embodiment 1 lies in that the operation supporting function G adopted comprises:

(79) 0$\{\begin{array}{c}{g}_1\left(,,\right)\\ g_2\left(,\right)\end{array},$
wherein g.sub.1(,,) is the numerical fitting of

(80) $\frac{h_3\left(\right).Math.\left[f\left(\right)+.Math.f\left(\right)\right]}{f\left(h_1\left(,\right)\right)},$
g.sub.2(,) is the numerical fitting of

(81) $\frac{f\left(\right).Math.f\left(\right)}{f\left(h_2\left(,\right)\right)},$
X, h.sub.1(,), h.sub.2(,) and h.sub.3(,) are any functions that satisfy h.sub.1(,)h.sub.2(,)h.sub.3(,);

(82) the corresponding homomorphic operation comprises:

(83) i) addition and subtraction between ciphertext and ciphertext: C.sub.r=C.sub.2C.sub.1, C.sub.r={A.sub.r, X.sub.r, B.sub.r} wherein:

(84) $A_r=\left\{a_{\mathrm{ri}}|iI\right\},a_{\mathrm{ri}}=a_{2i}.Math.g_1\left(x_{2i},x_{1i},\frac{a_{1i}}{a_{2i}}\right)\text{/}{h}_3\left(\frac{a_{1i}}{a_{2i}}\right),X_r=\left\{x_{\mathrm{ri}}|iI\right\},x_{\mathrm{ri}}=h_1\left(x_{2i},x_{1i}\right),B_r=B_2{B}_1;$

(85) ii) multiplication between ciphertext and ciphertext: C.sub.r=C.sub.3.Math.C.sub.4, C.sub.r={A.sub.r, X.sub.r, B.sub.r}, wherein:
A.sub.r={a.sub.rij|iI,jI}{B.sub.4.Math.a.sub.3i|iI}{B.sub.3.Math.a.sub.4i|jI},a.sub.rij=a.sub.3i.Math.a.sub.4i.Math.g.sub.2(x.sub.3,x.sub.4),
X.sub.r={x.sub.rij|iI,jI}{x.sub.3i|iI}{x.sub.4j|jI},x.sub.rij=h.sub.2(x.sub.3i,x.sub.4j),
B.sub.r=B.sub.3.Math.B.sub.4;

(86) ii) division between ciphertext and ciphertext: C.sub.r=C.sub.a/C.sub.b, C.sub.r={A.sub.5, X.sub.5, B.sub.5, A.sub.6, X.sub.6, B.sub.6}, wherein:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.3.Math.a.sub.1i|iI}{B.sub.1.Math.a.sub.3j|jI},a.sub.5ij=a.sub.1i.Math.a.sub.3j.Math.g.sub.2(x.sub.1,x.sub.3),
X.sub.5={x.sub.5ij|iI,jI}{x.sub.1i|iI}{x.sub.3j|jI},x.sub.5ij=h.sub.2(x.sub.1i,x.sub.3j),
B.sub.5=B.sub.1.Math.B.sub.3;
A.sub.6={a.sub.6ij|iI,jI}{B.sub.4.Math.a.sub.2i|iI}{B.sub.2.Math.a.sub.4j|jI},a.sub.6ij=a.sub.2i.Math.a.sub.4j.Math.g.sub.2(x.sub.2,x.sub.4),
X.sub.6={x.sub.6ij|iI,jI}{x.sub.2i|iI}{x.sub.4j|jI},x.sub.6ij=h.sub.2(x.sub.2i,x.sub.4j),
B.sub.5=B.sub.3.Math.B.sub.4.

(87) In this embodiment, g1 becomes a ternary function and the corresponding amount of fitting calculation will increase a lot, with the requirement for the flatness and complexity off also higher, but the corresponding security will be much higher than the binary function.

Embodiment 3

(88) In order to improve the security, in this embodiment, a function f2 is introduced when the operation support function G is generated, and it does not need to be added to the key and only affects the calculation and expression of the operation supporting function G. It can be understood that the operation supporting function G is encrypted. The specific expression is as follows:

(89) $\{\begin{array}{c}{g}_1\left(,\right)\\ g_2\left(,\right)\\ g_3\left(,\right)\\ g_4\left(,\right)\\ g_5\left(,\right)\\ g_6\left(,\right)\end{array},$
wherein: g.sub.1(,) is the numerical fitting of

(90) $\frac{f\left(\right).Math.f\left(h_3\left(,\right)\right)}{f_2\left(h_1\left(,\right)\right)},$
g.sub.2(,) is the numerical fitting of

(91) $\frac{f\left(\right).Math.f\left(h_3\left(,\right)\right)}{f_2\left(h_2\left(,\right)\right)},$
g.sub.3(,) is the numerical fitting of

(92) $\frac{f_2\left(\right)}{f\left(h_4\left(,\right)\right)},$
g.sub.4(,) is the numerical fitting of

(93) $\frac{f_2\left(\right)}{f\left(h_4\left(,\right)\right)},$
g.sub.5(,) is the numerical fitting of

(94) $\frac{f\left(\right).Math.f\left(\right)}{f\left(h_5\left(,\right)\right)},$
g.sub.6(,) is the numerical fitting of

(95) 0$\frac{f\left(\right)}{f\left(\right).Math.f\left(h_6\left(,\right)\right)},$
X, h.sub.1(,), h.sub.2(,), h.sub.3(,) and h.sub.4(,) are any functions that satisfy h.sub.1(,)h.sub.2(,)h.sub.3(,)h.sub.4(,); .sub.2( ) is a randomly generated function used for encrypting the operation supporting function,

(96) the corresponding homomorphic operation comprises:

(97) i) Addition and subtraction between ciphertext and ciphertext: C.sub.r=C.sub.2C.sub.1, C.sub.r={A.sub.r, X.sub.r, B.sub.r}, wherein:
A.sub.r={a.sub.ri|iI},
a.sub.ri=g.sub.6.Math.[a.sub.2i.Math.g.sub.1(x.sub.2i,x.sub.1i).Math.g.sub.3(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i))a.sub.1i.Math.g.sub.2(x.sub.2i,x.sub.1i).Math.g.sub.4(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i))],
X.sub.r={x.sub.ri|iI},
x.sub.ri=h.sub.6(h.sub.4(h.sub.1(x.sub.2i,x.sub.1i),h.sub.2(x.sub.2i,x.sub.1i)),h.sub.3(h.sub.1(x.sub.2i,x.sub.1i)),h.sub.2(x.sub.2i,x.sub.1i))),
B.sub.r=B.sub.2B.sub.1;

(98) ii) multiplication between ciphertext and ciphertext: C.sub.r=C.sub.3.Math.C.sub.4, C.sub.r={A.sub.r, X.sub.r, B.sub.r}, wherein:
A.sub.r={a.sub.rij|iI,jI}{B.sub.4.Math.a.sub.3i|iI}{B.sub.3.Math.a.sub.4j|jI},a.sub.rij=a.sub.3i.Math.a.sub.4j.Math.g.sub.5(x.sub.3,x.sub.4),
X.sub.r={x.sub.rij|iI,jI}{x.sub.3i|iI}{x.sub.4j|jI},x.sub.rij=h.sub.2(x.sub.3i,x.sub.4j),
B.sub.r=B.sub.3.Math.B.sub.4;

(99) ii) division between ciphertext and ciphertext: C.sub.r=C.sub.a/C.sub.b, C.sub.r={A.sub.5, X.sub.5, B.sub.5,A.sub.6, X.sub.6, B.sub.6}, wherein:
A.sub.5={a.sub.5ij|iI,jI}{B.sub.3.Math.a.sub.1i|iI}{B.sub.1.Math.a.sub.3j|jI},a.sub.5ij=a.sub.1i.Math.a.sub.3j.Math.g.sub.5(x.sub.1,x.sub.3),
X.sub.5={x.sub.5ij|iI,jI}{x.sub.1i|iI}{x.sub.3j|jI},x.sub.5ij=h.sub.5(x.sub.1i,x.sub.3j),
B.sub.5=B.sub.1.Math.B.sub.3,
A.sub.6={a.sub.6ij|iI,jI}{B.sub.4.Math.a.sub.2i|iI}{B.sub.2.Math.a.sub.4j|jI},a.sub.6ij=a.sub.2i.Math.a.sub.4j.Math.g.sub.5(x.sub.2,x.sub.4),
X.sub.6={x.sub.6ij|iI,jI}{x.sub.2i|iI}{x.sub.4j|jI},x.sub.6ij=h.sub.5(x.sub.2i,x.sub.4j),
B.sub.6=B.sub.2.Math.B.sub.4.

(100) Such an operation supporting function G can prevent a huge amount of operation for fitting a ternary function and also greatly improve the security, wherein, f2 is randomly generated only when G is calculated during initialization, and the form of f2 is required to be as simple as possible to prevent using too complicated expressions. At the same time, f2 expression neither needs to be stored on the client, nor needs to be saved on the server, so that it can be directly discarded after the process of initialization. This neither affects the client's encryption and decryption operations, nor affects the server's homomorphic operation, so in this case the security of G is very high, and it is more difficult to restore the function key f through G.