CN106921491A - A kind of safely and efficiently outsourcing calculates method and system - Google Patents

Abstract

The invention relates to a safe and efficient outsourcing computing realization method and system. The method includes: 1) the client uses a functional encryption scheme to generate two independent public-private key pairs; 2) the client sends the private key in the two public-private key pairs and the functions related to outsourcing calculation functions to two servers respectively; 3) The two servers respectively generate the decryption key corresponding to the function and send the result to the other party; 4) The client uses the public key of the two public-private key pairs to encrypt the message and the random number, and sends the ciphertext to the two 5) The two servers respectively use the decryption key to decrypt the ciphertext and return the calculation results to the client; 6) The client verifies the calculation results returned by the two servers, and if the verification passes, the value of the outsourced calculation function is obtained. Otherwise decline. The invention can improve the overall efficiency of the outsourcing calculation protocol, reduce the calculation amount of the client and the server at the same time, and can detect who is a malicious server.

Description

A Safe and Efficient Outsourcing Computing Realization Method and System

technical field

The invention belongs to the technical field of information security, and relates to a design scheme of an outsourcing computing protocol, specifically a method and system for implementing a secure outsourcing computing based on a functional encryption scheme, which can ensure the safety and overall efficiency of protocol execution.

Background technique

With the development of cloud computing, outsourced computing has been more and more widely used. Outsourced computing means that customers with weak computing capabilities hand over their computing tasks to an external server to help them complete the calculation, and the server returns the calculation result to the customer after completing the calculation. The design of an outsourced computing protocol needs to meet three main characteristics: correctness, security, and efficiency. Correctness refers to the result obtained by the server honestly executing the protocol, which must be verified after being returned to the client; security refers to that if the server returns an incorrect calculation result, the client will fail the verification and refuse to accept it; efficiency refers to the client The calculation amount of the end is much smaller than the calculation amount of the direct calculation function, otherwise the meaning of outsourcing calculation will be lost. In addition, the confidentiality of customer data also needs to be considered, because in some scenarios customers may not want the server to know their outsourced data.

In the outsourced computing scenario, because the server is not necessarily honest, the client needs to verify the correctness (or reliability) of the results returned by the server. Proof of interaction can be used to help the server prove the correctness of the calculation result to the client. The proposed proof system based on probabilistically verifiable proofs can be used to realize efficient outsourcing computing schemes. In his paper "CS proofs", Micali proposes a non-interactive outsourced computing scheme using a random oracle model. In the paper "Delegation of Computation withoutRejection Problem from Designated Verifier CS-Proofs" written by Goldwasser S, Lin H, and Rubinstein A, a non-interactive proof system was designed for any polynomial time computable function, and the outsourcing calculation scheme designed by it was Satisfy the high efficiency of client computing. However, the above works all focus on the reliability of the results returned by the server, without considering the confidentiality of the customer's outsourced data. In the follow-up, a lot of work has been carried out to study outsourced computing.

Outsourcing computing can be divided into outsourcing computing for specific functions and outsourcing computing for general functions. For specific functions, because the function structure features are clear, it is relatively easy to design an efficient and safe outsourcing computing protocol. There have been many excellent results in this regard. Designing confidentiality-satisfied outsourced computation protocols for general functions has been a difficult task. Until 2009, the proposal of the Gentry fully homomorphic encryption scheme theoretically solved the existence problem of a general function outsourcing computing protocol that satisfies confidentiality.

In the paper "Non-interactive verifiablecomputing: Outsourcing computation to untrusted workers" by Gennaro R, Gentry C and Parno B, the authors use the fully homomorphic encryption scheme and Yao's Garbled circuit to realize the outsourcing of general functions Computing protocol. Fully homomorphic encryption solves the problem that disordered circuits cannot be reused in outsourced computing. The protocol is divided into an offline stage and an online stage: in the offline stage, the client performs preprocessing calculations, and publicly transmits a part of the calculated information to the server; in the online stage, the client sends the code of the outsourced data to the server, and the server returns the operation result after performing the operation , and finally the client verifies and restores the result. In its solution, the client's outsourced data, functions and calculation results are kept secret from the server, and the client can use the labels in the disordered circuit to verify the reliability of the server's return results. By running the online stage multiple times, the customer's computing efficiency is efficient in the average sense. Subsequently, in the paper "Improved Delegation of Computation Using Fully Homomorphic Encryption" written by Chung K M, Kalai Y and Vadhan S, the authors used a fully homomorphic encryption scheme to design a new algorithm for general functions based on the indistinguishability of ciphertexts. Outsourced Computing Protocol. Compared with the work of Gennaro et al., the scheme of Chung et al. is also divided into offline phase and online phase, but in the offline phase, the client does not need to send any data to the server. Similarly, the client's calculations are only efficient in the average sense.

In view of the fact that the preprocessing of the above two schemes requires a large amount of calculation, and the current implementation efficiency of fully homomorphic encryption is not high, Ananth P and Chandran N et al. wrote in the paper "Achieving Privacy in Verifiable Computation with Multiple Servers–Without FHE and without Pre -processing" studies the outsourced computing protocol that does not require preprocessing and fully homomorphic encryption, and uses multiple servers (n>=2) to collaboratively complete the client's computing tasks. The basic idea is to assign the pre-processing operations (operations that generate disordered circuits) in the work of Gennaro et al. to the server, and the last server is responsible for completing the function calculation. Their approach offloads the client's calculations, but the server needs to regenerate the messy circuit each time the outsourced calculation is performed. This is because garbled circuits cannot be reused directly, which would destroy the reliability and confidentiality of the outsourcing agreement. Repetitively generating garbled circuits increases the computational cost on the server side, which in turn increases overhead costs on the client side.

Judging from the current research work, the main problem facing outsourcing computing for general functions is still the problem of efficiency.

Contents of the invention

Existing security outsourcing computing protocols for general functions, either the client computing amount is efficient in the average sense, or the server computing efficiency is not high (necessary to generate a disordered circuit every time the protocol is executed). In order to improve the overall efficiency of the outsourced calculation protocol, the present invention designs an outsourced calculation protocol based on a functional encryption scheme, which reduces the calculation amount of the server while reducing the calculation amount of the client.

To achieve the above object, the present invention takes the following technical solutions:

A safe and efficient method for implementing outsourced computing, the steps of which include:

1) The client uses the functional encryption scheme to generate two independent public-private key pairs;

2) The client sends the private key in the two public-private key pairs and the functions related to the outsourced calculation function to the two servers respectively;

3) The two servers respectively generate the decryption key corresponding to the function, and send the result to the other party;

4) The client uses the public key in the two public-private key pairs to encrypt the message and the random number, and sends the ciphertext to the two servers respectively;

5) The two servers respectively use the decryption key to decrypt the ciphertext, and return the calculation result to the client;

6) The client verifies the calculation results returned by the two servers. If the verification is passed, the value of the outsourced calculation function is obtained, otherwise it is rejected.

Specifically, in the outsourcing computing protocol of the present invention, there is a client (or client, represented by D) and two servers (S ₁ , S ₂ ), the outsourcing computing function is f, and the input is x. It is assumed that at least one server is semi-honest ("semi-honest" in the present invention means that the participants implement the agreement honestly, can record intermediate results and derive useful information, but cannot modify the intermediate results). The protocol execution process is as follows:

1) The customer uses the functional encryption scheme to generate two independent public-private key pairs (MPK ₁ , MSK ₁ ), (MPK ₂ , MSK ₂ ), and defines a function g related to the function f: the input of the function g is a triplet (x ,s ₁ ,s ₂ ), if f(x)=0, then function g outputs s ₁ , if f(x)=1, then outputs s ₂ , otherwise stop;

2) The client sends MSK ₁ and function g to the first server S ₁ ;

3) The client sends MSK ₂ and function g to the second server S ₂ ;

4) The server S ₁ uses the key generation algorithm of the functional encryption scheme to generate the decryption key SK _1g corresponding to the function g; send the SK _1g to the server S ₂ ;

5) The server S ₂ uses the key generation algorithm of the functional encryption scheme to generate the decryption key SK _2g corresponding to the function g, and sends the SK _2g to the server S ₁ ;

6) Customer input is x, select random numbers r ₁ , r ₂ , r ₃ , r ₄ ;

7) The client encrypts (x,r ₁ ,r ₂ ) with the public key MPK ₁ of the functional encryption scheme, obtains the ciphertext C ₁ , and sends it to the server S ₂ ;

8) The client encrypts (x, r ₃ , r ₄ ) with the public key MPK ₂ of the functional encryption scheme, obtains the ciphertext C ₂ , and sends it to the server S ₁ ;

9) The server S ₂ decrypts C ₁ with the private key SK _1g , obtains the result z ₁ , and returns z ₁ to the client;

10) The server S ₁ decrypts C ₂ with the private key SK _2g , obtains the result z ₂ , and returns z ₂ to the client;

11) The client verifies the values returned by the two servers. If the returned values of the two servers pass the random number verification and the corresponding function values are equal, the client accepts and obtains f(x), otherwise the client rejects.

A safe and efficient system for implementing outsourced computing, including a client and two servers; the client uses a functional encryption scheme to generate two independent public-private key pairs, and combines the sum of the private keys in the two public-private key pairs with the outsourced computing function Related functions are sent to the two servers respectively; the two servers respectively generate the decryption keys corresponding to the functions, and send the result to the other party; the client uses the public key pair message and the Encrypt the random number, and send the ciphertext to the two servers respectively; the two servers respectively use the decryption key to decrypt the ciphertext, and return the calculation result to the client; the client verifies the ciphertext returned by the two servers The calculation result, if the verification is passed, the value of the outsourced calculation function will be obtained, otherwise it will be rejected.

Compared with the prior art, the calculation of the present invention only includes master key generation, ciphertext generation and simple comparison and verification, and has nothing to do with the outsourced function f; the server generates the corresponding function g when executing the protocol for the first time For the decryption key, there is no need to regenerate the decryption key in the future, and only need to perform function operations (high efficiency). By using functional encryption, the client's data x is kept secret (confidentiality) from both servers (S ₁ , S ₂ ). When encrypting the input x, by introducing two confidential random numbers, the result returned by the server can be verified by the client (result reliability). Therefore, the present invention provides an overall efficient and safe outsourcing computing protocol design method.

Description of drawings

Fig. 1 is a schematic diagram of the initial preparation stage of the protocol of the present invention. In the initial stage of the protocol operation, the client sends the two generated master private keys and functions to two servers (assuming the channel is a secret channel), and the two servers respectively generate the decryption keys corresponding to the functions and send the results to the other server .

Fig. 2 is a schematic diagram of the execution phase of the outsourced computing protocol of the present invention. During the execution phase of the protocol calculation, the client encrypts the message and the random number with two different public keys, and sends them to the two servers respectively. After the server completes the calculation, it returns the calculation result to the client. The client verifies the result. If the verification is passed, the function value is obtained, otherwise it is rejected.

Figure 3 is a schematic diagram of the preliminary stages of the alternative protocol for outsourced computing of the present invention.

Fig. 4 is a schematic diagram of verification operation of an alternative protocol of the outsourced computing protocol of the present invention.

detailed description

In order to make the above objects, features and advantages of the present invention more obvious and understandable, the present invention will be further described below through specific embodiments and accompanying drawings.

The functional encryption scheme is a fine-grained encryption scheme. The decryptor can use the decryption key to obtain the function value corresponding to the plaintext, but does not know other information about the plaintext. This feature can be well applied in outsourced computing, because the client wants the server to complete the calculation, but does not want to leak the value of the outsourced data x.

Functional encryption means that the decryption party has the ciphertext C of the message x and the decryption key SK _f corresponding to the function f, and can only decrypt the function value f(x) of the message, but cannot know other information about x. The functional encryption algorithm is defined as follows:

Functional encryption algorithm FE＝{Setup,KeyGen,Enc,Dec}

Setup(1 ^k ): The algorithm inputs security parameter k and outputs a pair of public and private keys (MPK, MSK).

KeyGen(MSK,f): The algorithm inputs the master private key MSK and function f, and outputs the corresponding key SK _f .

Enc(MPK,x): The encryption algorithm inputs public key MPK and message x, and outputs ciphertext c.

Dec(SK _f ,c): The decryption algorithm inputs key SK _f and ciphertext c, and outputs f(x).

A direct idea is that the client uses the master private key to generate the private key SK _f corresponding to the function f, then sends the ciphertext of x and SK _f to the server, asks the server to do the decryption operation, and then returns f(x) to client. However, in this protocol, the amount of calculation required by the client to generate the private key SK _f is equivalent to the amount of calculation used to calculate the function f, so the efficiency of the client is not high.

In order to reduce the calculation amount of the client, we consider assigning the task of calculating SK _f to one server, and then let another server complete the outsourcing calculation task. We assume that at least one server is semi-honest, and in order to ensure the reliability of the calculation results, we let both servers participate in the calculation. The specific idea is to construct a new function g, the input is outsourcing data x and two random numbers s ₁ , s ₂ , if f(x)=0, then output s ₁ , if f(x)=1, then output s ₂ . This method is used to resist malicious behavior of the server.

In the protocol, the client is marked as D, the two servers are marked as (S ₁ , S ₂ ), the outsourced calculation function is f, and the outsourced data is x. The client needs to outsource the task of computing f(x) to two servers. Assume at least one server in the protocol is half-honest.

The preparatory stage of protocol execution is shown in Figure 1, and the protocol execution stage is shown in Figure 2. The specific process is as follows:

1) The client executes the Setup algorithm of the functional encryption scheme twice, and outputs two public-private key pairs (MPK ₁ , MSK ₁ ), (MPK ₂ , MSK ₂ ). Define the function g related to the function f: the input of the function g is triplet (x,r ₁ ,r ₂ ), if f(x)=0, the function g outputs r ₁ , if f(x)=1, the function g outputs r ₂ .

2) The client sends MSK ₁ and function g to the first server S ₁ . Here we assume that the channel is a secret channel. On the public channel, the client can use the public key of the server S ₁ to encrypt the message (MSK ₁ ,g) and send it to S ₁ .

3) The client sends MSK ₂ and function g to the second server S ₂ ;

4) The server S ₁ runs the key generation algorithm KeyGen of the functional encryption scheme, inputs (MSK ₁ ,g), and outputs the decryption key SK _1g corresponding to the function g. Server S ₁ sends SK _1g to server S ₂ ;

5) The server S ₂ runs the key generation algorithm KeyGen of the functional encryption scheme, inputs (MSK ₂ ,g), and outputs the decryption key SK _2g corresponding to the function g. Server S ₂ sends SK _2g to server S ₁ ;

6) The customer selects four random numbers r ₁ , r ₂ , r ₃ , r ₄ ;

7) The client encrypts (x, r ₁ , r ₂ ) with the public key MPK ₁ of the functional encryption scheme, obtains the ciphertext C ₁ , and sends C ₁ to the server S ₂ ;

8) The client encrypts (x, r ₃ , r ₄ ) with the public key MPK ₂ of the functional encryption scheme, obtains the ciphertext C ₂ , and sends C ₂ to the server S ₁ ;

9) The server S ₂ decrypts C ₁ with the private key SK _1g , obtains the result z ₁ , and returns z ₁ to the client;

10) The server S ₁ decrypts C ₂ with the private key SK _2g , obtains the result z ₂ , and returns z ₂ to the client;

11) The client verifies the values returned by the two servers: verify whether z ₁ is equal to r ₁ or r ₂ , whether z ₂ is equal to r ₃ or r ₄ , if z ₁ = r ₁ and z ₂ = r ₃ , then the client outputs f(x)=0, if z ₁ =r ₂ and z ₂ =r ₄ , the client outputs f(x)=1, otherwise the client rejects.

The present invention utilizes the functional encryption scheme and the outsourcing calculation model of two servers to realize the secrecy of the outsourcing data and greatly reduce the calculation amount of the client (the calculation amount of the client has nothing to do with the function f). Because the decryption key of the functional encryption algorithm can be reused, the server only needs to generate the decryption key of the function f once, and then only needs to perform decryption operations. In addition, in order to realize the correctness of the calculation result, the present invention introduces two confidential random numbers into the input part to realize the client's verification of the result returned by the server. Therefore, the outsourced computing protocol designed by the present invention satisfies confidentiality, security and overall high efficiency.

Table 1 below shows the calculation amount comparison between the present invention and the prior art. Compared with the prior art, the present invention reduces the calculation amount of the server on the premise of ensuring that the calculation amount of the client is low, and realizes an overall efficient and safe outsourcing calculation protocol.

Table 1. Comparison of calculation amount between the present invention and prior art

Work Client calculation server calculation Gennaro et al. [GGP10] It is related to f, and it is efficient in the average sense Calculation function f Chung et al. [CKV10] It is related to f, and it is efficient in the average sense Compute 2k functions f nothing to do with f Computationally messed up circuits and functions f this invention nothing to do with f In the average sense: the calculation function f

The invention provides a safe outsourcing calculation method, and the customer can verify whether the returned result is correct or not through a comparison operation. On this basis, if the client wants to know which server is malicious. Alternative protocols can be adopted as follows. The preparatory stage of the alternative protocol is shown in Figure 3, and the calculation process of the protocol execution is still shown in Figure 2, and further verification operations are added at the end, as shown in Figure 4. The specific process of the replacement agreement is as follows:

1) The client executes the Setup algorithm of the functional encryption scheme twice, and outputs two public-private key pairs (MPK ₁ , MSK ₁ ), (MPK ₂ , MSK ₂ ). Define the function g related to the function f: the input of the function g is triplet (x,r ₁ ,r ₂ ), if f(x)=0, the function g outputs r ₁ , if f(x)=1, the function g outputs r ₂ .

2) The client sends MSK ₁ and function g to the first server S ₁ . Here we assume that the channel is a secret channel. On the public channel, the client can use the public key of the server S ₁ to encrypt the message (MSK ₁ ,g) and send it to S ₁ .

3) The client sends MSK ₂ and function g to the second server S ₂ ;

4) The server S ₁ runs the key generation algorithm KeyGen of the functional encryption scheme, inputs (MSK ₁ ,g), and outputs the decryption key SK _1g corresponding to the function g. Server S ₁ sends SK _1g to server S ₂ ;

5) The server S ₂ runs the key generation algorithm KeyGen of the functional encryption scheme, inputs (MSK ₂ ,g), and outputs the decryption key SK _2g corresponding to the function g. Server S ₂ sends SK _2g to server S ₁ ;

6) Server S ₁ calculates hash functions H(SK _1g ), H(SK _2g ), and sends them to the client;

7) The server S ₂ calculates the hash functions H(SK _1g ), H(SK _2g ), and sends them to the client;

8) The client verifies whether the hash values returned by the two servers are correspondingly equal, if they are equal, continue, otherwise abort;

9) The customer selects four random numbers r ₁ , r ₂ , r ₃ , r ₄ ;

10) The client encrypts (x, r ₁ , r ₂ ) with the public key MPK ₁ of the functional encryption scheme, obtains the ciphertext C ₁ , and sends C ₁ to the server S ₂ ;

11) The client encrypts (x, r ₃ , r ₄ ) with the public key MPK ₂ of the functional encryption scheme, obtains the ciphertext C ₂ , and sends C ₂ to the server S ₁ ;

12) The server S ₂ decrypts C ₁ with the private key SK _1g , obtains the result z ₁ , and returns z ₁ to the client;

13) The server S ₁ decrypts C ₂ with the private key SK _2g , obtains the result z ₂ , and returns z ₂ to the client;

14) The client verifies the values returned by the two servers: verify whether z ₁ is equal to r ₁ or r ₂ , whether z ₂ is equal to r ₃ or r ₄ , if z ₁ = r ₁ and z ₂ = r ₃ , then the client outputs f(x)=0, if z ₁ =r ₂ and z ₂ =r ₄ , the client outputs f(x)=1, otherwise proceed to step 15);

15) The customer adopts the proof system (denoted as L) in the article "Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs" by Goldwasser et al., and runs the set-up algorithm of L to generate the function KeyGen(MSK ₁ , ) corresponding to public-private key (pp ₁ ,sp ₁ ) of the function KeyGen(MSK ₂ ,·) corresponding to the public-private key (pp ₂ ,sp ₂ ). Send pp ₁ to server S ₁ , and send pp ₂ to S ₂ ;

16) The server S ₁ executes the certifier algorithm in the certification system L, generates a certificate π ₁ , and sends (SK _1g ,π ₁ ) to the client, and the same server S ₂ generates a certificate π ₂ , and sends (SK _2g ,π ₂ ) to client.

17) The client calculates H(SK _1g ) and H(SK _2g ), and verifies whether it is equal to the hash value received in steps 6) and 7). If there is an inequity, then determine that the corresponding server is malicious and terminate. Otherwise continue. The client runs the verifier algorithm of the proof system L, uses the received message and the private key sp ₁ , sp ₂ to verify whether the proof π ₁ and π ₂ are valid, if the verification of π _i (i∈{1,2}) fails, then If the corresponding server S _i is malicious, terminate, otherwise continue. The client judges which server returns z _i (i∈{1,2}) and fails in step 14), that is, z _i does not have an equal relationship with the random number selected by the client, then the corresponding server is malicious and terminates.

Where π _i is the server S _i proves to the client that the returned SK _ig is honestly generated. Prove that the computational complexity of the verifier (here the client) in the system L is related to the logarithm of the computational complexity of the function KeyGen(MSK _i ,·). Because the computational complexity of the algorithm KeyGen(MSK _i ,·) in the functional encryption scheme is equivalent to that of the function f. Therefore, in this alternative scheme, the calculation amount of the client is related to the function f logarithm log(|f|). Compared with the works of Gennaro et al. and Chung et al., this scheme is still efficient. This alternative can help customers know who is a malicious server after authentication fails. In addition, we agree that after step 14), if any server refuses to execute step 16) and chooses to abort in advance, it is determined that the server is malicious.

An expanded implementation of the present invention: replace the functional encryption scheme with a multi-input functional encryption scheme, which is suitable for outsourcing computing scenarios with multiple clients. Multi-input functional encryption schemes are extensions of single-input functional encryption schemes. In the multi-input functional encryption scheme, the function f corresponding to the decryption key SK _f is an n-ary function, and the input of the key SK _f is n ciphertexts. Given the ciphertext of n messages (x ₁ , x ₂ ,…,x _n ), denoted as (c ₁ ,c ₂ ,…,c _n ), and the decryption key SK _f , the decryptor can decrypt to obtain f( x ₁ ,x ₂ ,…,x _n ). The multi-client outsourced computing means that n clients (n>=2) have their own input _xi and want to outsource the task of computing f(x ₁ ,x ₂ ,…,x _n ) to an external server. By replacing the functional encryption scheme in the present invention with multi-input functional encryption, an outsourcing calculation scheme in which multiple clients outsource calculation tasks to two servers can be designed more directly.

The above embodiments are only used to illustrate the technical solution of the present invention and not to limit it. Those of ordinary skill in the art can modify or equivalently replace the technical solution of the present invention without departing from the spirit and scope of the present invention. The scope of protection should be determined by the claims.

Claims (10)

1. safely and efficiently outsourcing calculates implementation method to one kind, it is characterised in that comprise the following steps：

1) client produces two independent public private key pairs using function encipherment scheme；

2) function that client calculates functional dependence by the private key in two public private key pairs and with outsourcing is sent respectively to two clothes Business device；

3) two servers produce the corresponding decruption key of function respectively, and send result to other side；

4) ciphertext and is sent to two by client respectively using the public key in two public private key pairs to message and random number encryption Server；

5) two servers are respectively adopted decruption key and ciphertext are decrypted, and return to result of calculation to client；

6) result of calculation that two servers of client validation are returned, is verified, and obtains the value that outsourcing calculates function, otherwise Refusal.

2. the method for claim 1, it is characterised in that it is S to set two servers₁And S₂, it is f that outsourcing calculates function, defeated It is x to enter；Assuming that at least one server is half honesty；Realize that the specific steps that outsourcing is calculated include：

1) client produces two independent public private key pair (MPK using function encipherment scheme₁,MSK₁),(MPK₂,MSK₂), definition And function f related function g：The input of function g is triple (x, s₁,s₂), if f (x)=0, function g outputs s₁If, f (x) =1, then export s₂, otherwise stop；

2) client is by MSK₁First server S is sent to function g₁；

3) client is by MSK₂Second server S is sent to function g₂；

4) server S₁The decruption key SK corresponding to function g is produced with the encryption key generating algorithms of function encipherment scheme_1g；By SK_1g It is sent to server S₂；

5) server S₂The decruption key SK corresponding to function g is produced with the encryption key generating algorithms of function encipherment scheme_2g, by SK_2g It is sent to server S₁；

6) client input is x, selection random number r₁,r₂,r₃,r₄；

7) the client public key MPK of function encipherment scheme₁Encryption (x, r₁,r₂), obtain ciphertext C₁, send it to server S₂；

8) the client public key MPK of function encipherment scheme₂Encryption (x, r₃,r₄), obtain ciphertext C₂, send it to server S₁；

9) server S₂Use private key SK_1gDecryption C₁, obtain result z₁, and by z₁Return to client；

10) server S₁Use private key SK_2gDecryption C₂, obtain result z₂, and by z₂Return to client；

11) values that two servers of client validation are returned, if two return values of server are all by random number verification and right The functional value answered is equal, then client receives, and obtains f (x), otherwise client refusal.

3. method as claimed in claim 2, it is characterised in that step 11) in, client validation z₁Whether with r₁Or r₂It is equal, z₂Whether with r₃Or r₄It is equal；If z₁=r₁And z₂=r₃, then client export f (x)=0；If z₁=r₂And z₂=r₄, then client Output f (x)=1；Otherwise client refuses.

4. method as claimed in claim 2, it is characterised in that use following methods to judge which server is malice：

A) in step 5) after, following steps are performed, then perform step 6)：

A1) server S₁Calculate hash function H (SK_1g), H (SK_2g), send them to client；

A2) server S₂Calculate hash function H (SK_1g), H (SK_2g), send them to client；

A3) cryptographic Hash that two servers of client validation are returned whether correspondent equal, if equal, continue, otherwise stop；

B) in step 11) in, if client validation fails, perform following steps：

B1) the set-up algorithms of client operation proof system L produce function KeyGen (MSK₁) corresponding to public and private key (pp₁,sp₁), produce function KeyGen (MSK₂) corresponding to public and private key (pp₂,sp₂)；By pp₁It is sent to server S₁, will pp₂It is sent to S₂；

B2) server S₁The certifier's algorithm in proof system L is performed, producing proves π₁, send (SK_1g,π₁) give client；Clothes Business device S₂Producing proves π₂, send (SK_2g,π₂) give client；

B3) client calculates H (SK_1g) and H (SK_2g), verify whether with the cryptographic Hash correspondent equal received in step a), if in the presence of , then judge that corresponding server is malice, terminate, otherwise continue；Verifier's algorithm of client's operation proof system L, uses The message and private key sp for receiving₁,sp₂Separately verify proof π₁And π₂Whether set up, if π_i(i ∈ { 1,2 }) authentication failed, then correspond to Server S_iIt is malice, terminates, otherwise continues；Client judges the z which server is returned_i(i ∈ { 1,2 }) are in step 14) in The failure, i.e. z such as sentence_iDo not exist relation of equality with the random number selected by client, then corresponding server is malice, is terminated.

5. method as claimed in claim 4, it is characterised in that in step 11) after, if there is server to refuse to perform step B2 select to stop) and in advance, then judge that this server is malice.

6. the method for claim 1, it is characterised in that the channel between client and server is hidden passageway；If Channel between client and server is overt channel, then client is using being then forwarded to clothes after the public key encryption message of server Business device.

7. the method as described in any claim in claim 1 to 6, it is characterised in that replace with function encipherment scheme The function encipherment scheme of multi input, it is adaptable to which the outsourcing of many clients calculates scene.

8. safely and efficiently system is realized in outsourcing calculating to one kind, it is characterised in that including client and two servers；The visitor Family end produces two independent public private key pairs using function encipherment scheme, is calculated by the private key in two public private key pairs and with outsourcing The function of functional dependence is sent respectively to described two servers；Described two servers produce the corresponding decryption of function close respectively Key, and send result to other side；The client utilizes the public key in two public private key pairs to message and random number encryption, and Ciphertext is sent to described two servers respectively；Described two servers are respectively adopted decruption key and ciphertext are decrypted, And result of calculation is returned to client；The result of calculation that two servers of the client validation are returned, is verified, and obtains outer Bag calculates the value of function, otherwise refuses.

9. system as claimed in claim 8, it is characterised in that the channel between client and server is hidden passageway.

10. system as claimed in claim 8, it is characterised in that the channel between client and server is overt channel, visitor Family end after the public key encryption message of server using being then forwarded to server.