SECURED COMPUTING

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
131. 31. (canceled)
1 Assignment
0 Petitions
Accused Products
Abstract
According to an example aspect of the present invention, there is provided an apparatus comprising at least one processing core, at least one memory including computer program code, the at least one memory and the computer program code configured to cause the apparatus to receive an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when nm with the random data, obtain a homomorphic polynomial factorization of the function, comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials, and verify that the computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the decomposed representation, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of polynomials.
0 Citations
No References
No References
51 Claims
 131. 31. (canceled)
 32. An apparatus comprising at least one processor;
 and at least one memory including computer program code;
the at least one memory and the computer program code being configured to, with the at least one processor, cause the apparatus at least to;receive an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the encrypted random data; obtain a homomorphic polynomial factorization of the function, further comprising to obtain a decomposed representation of the function, the representation comprising a sum of polynomials, and verify that the encrypted computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the decomposed representation, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of the polynomials.  View Dependent Claims (33, 34, 35, 36, 37, 38, 39)
 and at least one memory including computer program code;
 40. An apparatus comprising at least one processor;
 and at least one memory including computer program code, the at least one memory and the computer program code being configured to, with the at least one processor, cause the apparatus at least to;
perform a homomorphic polynomial factorization of a function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials; obtain random data, and generate an output of the function, when run with the random data, and provide to a verifier node the random data in an encrypted form, the output in an encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein the apparatus is configured to offload computation of the function to the cloud computing server.  View Dependent Claims (41, 42, 43, 44)
 and at least one memory including computer program code, the at least one memory and the computer program code being configured to, with the at least one processor, cause the apparatus at least to;
 45. A method comprising:
receiving an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the encrypted random data; obtaining a homomorphic polynomial factorization of the function, further comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials, and verifying that the encrypted computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the decomposed representation, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of the polynomials.  View Dependent Claims (46, 47, 48)
 49. A method comprising:
performing a homomorphic polynomial factorization of a function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials; obtaining random data, and generating an output of the function, when run with the random data, and providing to a verifier node the random data in an encrypted form, the output in an encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein an apparatus performing the method is configured to offload computation of the function to the cloud computing server.  View Dependent Claims (50, 51)
1 Specification
The present invention relates to secured distributed computing, for example in the context of cloud computing.
Traditionally data processing has been performed using different frameworks. In the 1960s and 1970s data processing was centralized to a relatively small number of computers, which were accessed by users with terminals. Subsequently, a proliferation of increasingly capable computers led to a distributed model, where corporations, research groups and even individuals performed their data processing using proprietary local computing substrates, such as PCs and servers.
In the future, it is foreseen that large numbers of relatively light computing devices, such as sensors or internetofthings nodes, may generate large quantities of data, while these light devices may lack the processing resources to process. Consequently, cloud computing is one possible model where a return to the centralized framework is possible, such that light nodes provide their data to centralized, highly capable computing substrates for processing.
Cloud computing, however, faces challenges in situations where the cloud is not controlled by the same entity, such as a corporation, which generates the data. In detail, the data owner may not entirely trust a cloud operator to not be curious concerning the data, wherefore data may be encrypted for storage in a cloud.
In addition to storage, encryption provides the benefit of protecting data during transmission between the data owner and a computation substrate of a cloud data processing server.
When mere storage is not sufficient and the data owner desires to both store and process his data in a cloud such that the cloud operator is not enabled to discover the contents of the data, various cryptographic solutions may be considered.
Homomorphic encryption methods enable at least partial processing of encrypted data, such that the data that is the object of the processing is not revealed to the node performing the processing.
According to some aspects, there is provided the subjectmatter of the independent claims. Some embodiments are defined in the dependent claims.
According to a first aspect of the present invention, there is provided an apparatus comprising at least one processing core, at least one memory including computer program code, the at least one memory and the computer program code being configured to, with the at least one processing core, cause the apparatus at least to receive an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the random data, obtain a homomorphic polynomial factorization of the function, comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials, and verify that the computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the decomposed representation, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of polynomials.
Various embodiments of the first aspect may comprise at least one feature from the following bulleted list:
each polynomial in the sum of polynomials comprises a product of a first part and a second part, the first part comprising a difference between a first parameter and a second parameter and the second part comprising a polynomial expression involving the first parameter
the apparatus is configured to assign, in obtaining the value of the sum of polynomials, the encrypted random data as the first parameter and the encrypted input data as the second parameter
the apparatus is configured to receive the encrypted computation result from a result requesting party
the apparatus is configured to request the identifier of a function, the encrypted random data and the encrypted output of the function from a data provider node that originates the input data
the apparatus is further configured to request the encrypted input data from a cloud data processing node
the apparatus is further configured to indicate a result of the verification to a node from where the apparatus received the encrypted computation result
the apparatus is further configured to verify a second encrypted computation result using the same encrypted random data and encrypted output.
According to a second aspect of the present invention, there is provided an apparatus comprising at least one processing core, at least one memory including computer program code, the at least one memory and the computer program code being configured to, with the at least one processing core, cause the apparatus at least to perform a homomorphic polynomial factorization of a function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials, obtain random data, and generate an output of the function, when run with the random data, and provide to a verifier node the random data in an encrypted form, the output in an encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein the apparatus is configured to offload computation of the function to the cloud computing server.
Various embodiments of the second aspect may comprise at least one feature from the following bulleted list:
the apparatus is further configured to provide encrypted input data and an instruction to the cloud computing server to perform the function on the encrypted input data
the apparatus is configured to encrypt the output and the random data using a homomorphic encryption key received in the apparatus from a proxy node
the apparatus is configured to encrypt the input data using a homomorphic encryption key received in the apparatus from a proxy node
the apparatus comprises a sensor node configured to function as part of a packetbased communication network.
According to a third aspect of the present invention, there is provided a method comprising receiving an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the random data, obtaining a homomorphic polynomial factorization of the function, comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials, and verifying that the computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the decomposed representation, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of polynomials.
Various embodiments of the third aspect may comprise at least one feature corresponding to a feature from the preceding bulleted list laid out in connection with the first aspect.
According to a fourth aspect of the present invention, there is provided a method comprising performing a homomorphic polynomial factorization of a function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials, obtaining random data, and generating an output of the function, when run with the random data, and providing to a verifier node the random data in an encrypted form, the output in an encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein an apparatus performing the method is configured to offload computation of the function to the cloud computing server.
Various embodiments of the fourth aspect may comprise at least one feature corresponding to a feature from the preceding bulleted list laid out in connection with the second aspect.
According to a fifth aspect of the present invention, there is provided an apparatus comprising means for receiving an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the random data, means for obtaining a homomorphic polynomial factorization of the function, comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials, and means for verifying that the computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the sum of polynomials, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of polynomials.
According to a sixth aspect of the present invention, there is provided an apparatus comprising means for performing a homomorphic polynomial factorization of the function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials, means for obtaining random data, and generate an output of the function, when run with the random data, and means for providing to a verifier node the random data in an encrypted form, the output in an encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein the apparatus is configured to offload computation of the function to the cloud computing server.
According to a seventh aspect of the present invention, there is provided a nontransitory computer readable medium having stored thereon a set of computer readable instructions that, when executed by at least one processor, cause an apparatus to at least receive an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the random data, obtain a homomorphic polynomial factorization of the function, comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials, and verify that the computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the sum of polynomials, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of polynomials.
According to an eighth aspect of the present invention, there is provided a nontransitory computer readable medium having stored thereon a set of computer readable instructions that, when executed by at least one processor, cause an apparatus to at least perform a homomorphic polynomial factorization of the function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials, obtain random data, and generate an output of the function, when run with the random data, and provide to a verifier node the random data in an encrypted form, the output in encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein the apparatus is configured to offload computation of the function to the cloud computing server.
According to a ninth aspect of the present invention, there is provided a computer program configured to cause a method in accordance with at least one of the third and fourth aspects to be performed.
A method to verify results of computation outsourced to a computing party is herein described, wherein polynomial factorization of a function is employed to enable determination of correctness of a computation result, using random data with a decomposition of the function. This method may be used, for example, in an Internetofthings context where a data provider node provides data for processing in a server, and a requesting party may access the processed data such that the server doesn'"'"'t gain access to the data itself. The determination of correctness may relate to the processing in the server.
The system of
A proxy 140, which may be referred to as a trusted auditor proxy node, may be configured to provide homomorphic encryption keys to data provider 110. These keys may comprise a public key—secret key pair, for example. Proxy 140 may be configured to generate such keys, for example by using a random procedure, or proxy 140 may be configured to obtain such keys from a further node, and then provide them to data provider 110. A random procedure may comprise using thermal noise or radio noise, for example, to generate random numbers. A provision of such keys to data provider 110 is illustrated in
Server 120 may be comprised in a cloud computing cloud which comprises servers, for example. Server 120 has computational resources that are available for data provider 110 to offload computing tasks to. In general, server 120 may comprise or offer a computational substrate to other parties, such as, for example, data provider 110. Data provider 110 may provide a packet of its data, encrypted using the homomorphic encryption key, to server 120. This is illustrated in
Once a requesting party 130, or 135 expresses a desire to obtain the result of the processing, it may transmit a request to proxy 140. This is illustrated as message 134 in
Proxy 140 may reencrypt the obscured data for requesting party 130 and forward the reencrypted obscured data to requesting party 130, message 143. Requesting party 130 may then deobscure the data to obtain the processed data. In some embodiments, server 120 does not obscure the result using random data. The messaging need not proceed exactly as illustrated in
The system of
In
Verifier 150 may likewise request, phase 152, and receive, phase 125, an encrypted version of the unprocessed data from server 120. Verifier may then proceed to check if the processing was originally performed correctly in server 120. In detail, verifier 150 may use a homomorphic polynomial factorization of the function, as will be described in more detail herein below. Depending on the embodiment, verifier 150 may obtain the encrypted processed data from requesting party 135 or from server 120, for example.
In the verification, data provider 110 may be configured to make preparations for a future audit procedure by generating a verification algorithm according to a polynomial factorization algorithm. According to the verification algorithm, data provider 110 may choose random data as an input of the function and compute an output for this input, and then encrypts the random data and the output with the homomorphic encryption key pair for the purpose of verification. Verifier 150 who seeks to audit the correctness of the computation result at server 120 may request that data provider 110 provide the random data and the verification algorithm for performing auditing and verification. Concretely, verifier 150 may take these random data, the encrypted outsourced data and the computation result as inputs into the verification algorithm and further checks if the output of the verification algorithm is as expected in order to tell the correctness of the data processing result of server 120. Overall, verifier 150 may obtain the unprocessed data from data provider 110 or server 120, and the processed data from requesting party 135 or server 120, for example.
Verifiable computation is a technique of an outsourced computation service that helps clients to outsource their computations to server 120 with expected commitments. In a cloud computing scenario, clients and server 120 do not completely trust each other, thus, it is useful that server 120 may be requested to collaborate in proving that data computation processed by it is correct. Verifiable computation provides methods to audit data computation based on either computation complexity theorem, such as Probabilistically Checkable Proofs, PCPs, Noninteractive Proof, or cryptographic techniques such as Attributebased Encryption ABE, Fully Homomorphic Encryption FHE, or others.
Goldwasser et al. proposed interactive proofs based on PCPs in [1], in which a client can check and verify results of computation but in doing so has to store a large amount of data locally. Unfortunately, although these schemes offer an impressive theoretical performance, the clients still need to own powerful computation capabilities to deal with complicated computation, which seems impractical in the real world. Owing to these issues, much research has been directed to improve the efficiency of PCP in order to make it more practical.
Thaler proposed a scheme in [2] that builds on the PCPbased arguments designed by Goldwasser et al. (named GKR protocol) in [1]. In [2], Thaler proposed specific functions to deal with streaming settings in parallel, where not all data can be stored to compute over. Moreover, this scheme does not use cryptography and is secure against computationally unbounded adversaries.
Setty et al. proposed another PCPbased system called linear PCP [3], [4]. In contrast to the original PCP, linear PCP represents proof as a linear function. In existing schemes, workers can generate a commitment to its proof by a linearlyhomomorphic encryption scheme only based on some standard cryptographic assumptions. This method optimizes the traditional PCPbased schemes and makes it practical to utilize PCPbased schemes in the real world. Moreover, for applications that can tolerate large batch sizes, these schemes only cost a little in verification.
Noninteractive verifiable computation was first introduced by Gennaro et al. in [5]. It allows a computationally weak client to outsource its complex computation to a powerful server or operator, then the server or operator may return the result of the computation and generate a noninteractive proof for the result in order to help the client audit the correctness of the computation result. A number of constructions were proposed to increase the efficiency of performance, but most of them only permit limited functions such as polynomials [6], [7] and set operations [8].
Setty et al. [9] built a scheme based on the Quadratic Arithmetic Programs, QAPs, proposed by Gennaro et al. [8]. QAPs are similar to linear PCPs and can be similarly used in Ginger'"'"'s cryptographic framework [3], [4]. Vu et al. [11] proposed to improve GKR'"'"'s protocol [1] with a batching model and designed a compiler that chooses among three PCPbased back ends. However, in order to improve efficiency, these two schemes perform computations in batches. Thus, the client'"'"'s secret key is exposed to a third party to conduct the verification on the outsourced computation result, which causes security risks related to the usage of verifiable computation in practice.
Fully Homomorphic Encryption, FHE, was first introduced by Rivest et al. [12] in 1978. Homomorphic Encryption, HE, enables meaningful computations on encrypted data without decrypting them. However, due to some cryptographic problems, candidate FHE schemes were not proposed until 2009. In 2009, the first FHE scheme was proposed by Gentry [13] called Somewhat Homomorphic Encryption, SHE, and it enables clients to evaluate a limited depth circuit consisting of additions and multiplications directly on encrypted data. Although due to its limits on circuit depth, this scheme did not totally conform to the notion of FHE, which inspired many researchers to make efforts to improve SHE to be a real FHE, [14][20]. Moreover, some other FHE schemes [21][24] were proposed based on different assumptions from Gentry'"'"'s.
After the first FHE scheme, three main branches of homomorphic encryption have been developed: latticebased, integerbased, and learningwitherrors, LWE, or ringlearningwitherrors, RLWE, based homomorphic encryption, which aim to solve problems in different fields such as integer, field, polynomial, etc. Furthermore, FHE provides a new path to realize outsourced computation in a secure and general way. But how to verify the correctness of FHEbased data computation has been an open issue.
In order to realize public verification, Parno et al. in [9] first raised two key properties of public verification that were not achieved in earlier solutions based on ABE. One property is public delegatability. Briefly, public delegatability means that several parties should be able to delegate their computations to the cloud. Traditional schemes [26][28] require extensive preprocessing for any input x_{i }to compute F (x_{i}) at the cloud. Clients may generate a secret key SKF, which may be small and an evaluation key EKF, which may be large, at first. In this situation, for those clients who only want to perform a computation once, the initialization phase could be a waste of computation resources. A lightweight system setup or initiation would be preferred.
Goldwasser, Kalai and Rothblum [1] presented a publicly delegatable verifiable computation protocol for functions that can be computed by circuits of size poly(n) and depth poly(log(n)), where poly(n) denotes an unspecified function f(n)=o(n^{c}) for some constant c>0. This scheme improves the original one [5] as it does not need clients to perform prepossessing. Similarly, Canetti, Riva, and Rothblum in [30] investigated in another line of research and presented a protocol that relies on collisionresistant hashing and polylogarithmic Private Information Retrieval, PIR, for general circuits C, where the client runs in time poly(log(C), depth(C)). However, the above two studies do not satisfy the requirements of public verifiability very well.
Another property of public verifiable computation is public verifiability. Concretely speaking, several parties should be able to verify the work of the server or cloud with a specially designed “verification” key. In the same situation mentioned above, a client may generate a verification key VK_{x }for input x at the same time, for example, as it delegates the computation of function F to the cloud. This key enables the client to verify the correctness of the computation result without the involvement of the cloud. Moreover, even if the cloud knows the verification key VK_{x}, it is still impossible for the cloud to cheat on the result of the computation.
Papamanthou, Tamassia, and Triandopoulos [31] proposed a verifiable computation scheme for set operations that enables anyone to check the correctness of the set operation results. Parno et al. [23] designed a scheme for public verifiable computation called Pinocchio. This scheme achieves Public Verifiability of the operation result by combining QAPs and a highly efficient cryptographic protocol. In their scheme, proofs for operation results are constant no matter how many computations are executed. Thus, the computation result can be verified very efficiently. Papamanthou, Shi, and Tamassia [33] presented another protocol on public verifiable computation.
A system in accordance with at least some embodiments of the present invention will now be described.
The notion of fully homomorphic encryption was first introduced by Rivist in 1978. However, due to the technical limitations of that time, a promising scheme on fully homomorphic encryption had not been proposed until 2009 by Gentry. He first proposed a scheme called somewhat homomorphic encryption, SHE, using ideal lattices to realize a homomorphism that is able to compute a limited depth of circuits. Then he and his team improved this work and successfully constructed a fully homomorphic encryption scheme, FHE, based on ideal lattices. After Gentry first brought this theory in the real world, fully homomorphic encryption became an active topic in research. Among all of them, there are three main branches: fully homomophic encryption based on ideal lattices, fully homomorphic encryption based on integers, and fully homomorphic encryption based on Learning with Errors, LWE, or Ring Learning with Errors, RLWE. In at least some embodiments of this invention, a BGV [21] fully homomrophic encryption scheme is used, based on RLWE.
In this section, we briefly introduce the algorithms of fully homomrophic encryption that may be used in at least some embodiments of the invention. There are four algorithms in a fully homomrophic encryption scheme: Key Generation (Keygen), Encryption (Enc), Decryption (Dec), and Evaluate (Eval). The details are given below:
1) KeyGen(1^{λ})→(pk, sk): With the input a security parameter λ, the algorithm outputs a fully homomorphic public key pk, and a fully homomorphic secret key sk.
2) Enc(pk, m_{i})→φ_{i}: With the inputs: public key pk and plaintext m_{i}, the algorithm encrypts m and outputs a ciphertext φ_{i}, where m_{i }donates the ith plaintext provided by DP_{i }and φ_{i }donates the corresponding ciphertext of m_{i}.
3) Dec(pk, φ_{i})→m_{i}: With the inputs: secret key sk and the ciphertext φ_{i}, the algorithm decrypts φ_{i }and outputs plaintext m_{i}.
4) Eval(pk, C, Φ)→φ: With the inputs: public key pk, evaluated circuit C, and a tuple of ciphertext Φ(Φ=φ_{1}, . . . , φ_{t}), the algorithm computes and outputs result which donates a ciphertext computation result, where C(m_{i}, . . . , m_{t})=Dec(sk, φ).
The key algorithm of fully homomorphic encryption is Eval which computes the data in a ciphered form. Obviously, the encryption of data protects them from exposed to unauthorized users. Only the party who owns the secret key sk can get access to the plaintext result.
Next, polynomial factorization will be described. We now give the notation of multivariate polynomials. A key point is that we use a repeatable multiset which means an element can take place more than once to present a multivariate polynomial, e.g., {1,1,2,2,3,3} is a multiset. Formally, a function S→Z^{≥0 }donates a map between a multiset (S) and the multiplicity of each element in that multiset, i.e., S={1,1,2,3,3,3}, we have S(1)=2, S(2)=1, S(3)=3. S denotes the degree of a multiset, i.e. for a multiset {1,1,2,3,3,3}, S=6. Finally, S_{d,n }donates a set of multisets which have the size of at most d and different elements of at most n. Let f be an nvariable polynomials over Z_{p}, then f can be presented like this:
where c_{S }donates the coefficient of the corresponding monomial multivariate polynomials. For example, the multiset {1,1,2,5,5,5} is corresponding to the nvariable polynomials x_{1}^{2}x_{2}x_{5}^{3}.
Specially, as to a multivariate polynomial, we use the maximum degree of the monomial that contains in the polynomial to donate the degree of that polynomial, e.g. 4x_{1}x_{2}+3x_{1}^{3}x_{2}^{2}x_{1 }has the degree of 6.
Multivariate Polynomials factorization: Let f(x)=f(x_{1}, x_{2}, . . . , x_{n}) ∈Z_{p}^{n}[x] be a nvariable polynomial. For all a ∈Z_{p}^{n}, there exists q_{i}(x) ∈Z_{p}^{n}[x] where f(x)−f(a) can be presented as f(x)−f(a)=Σ_{i=1}^{n}(x_{1}−a_{1})q_{i}(x). Furthermore, there exists a polynomialtime algorithm to find these q_{i}(x).
Proof: The proof of this factorization algorithm is straightforward. Given a nvariable polynomial f(x)−f(a) over Z_{p}, we use x_{1}−a_{1 }to divide this polynomial to get
f(x)−f(a)=(x_{1}−a_{i})q_{i}(x_{1}, x_{2}, . . . , x_{n})+r_{1}(x_{2}, x_{3}, . . . , x_{n})
where r_{1}(x_{2}, x_{3}, . . . , x_{n}) is the remainder term which no longer contains the variable x_{1}. Continuously, divide the remainder with (x_{2}−a_{2}), then with (x_{3}−a_{3}), and so on. Finally, f(x)−f(a) can be presented as:
where r_{n}∈Z_{p}. Since f(x)−f(a)=0 when x=a, r_{n }should be 0 as well. So, we have
The following notations will be employed:
For system setup, each system entity x generates its own public and private key pairs PK_{x }and SK_{x }and broadcasts its public key inside the system. Proxy 140 generates and issues a fully homomorphic encryption key pair PK_{H }and SK_{H }to each data provider DP_{i}. (i=1, . . . , I). For different contexts, these keys can be set differently. Thus, in general, multiple homomorphic key pairs may exist in the system. For simplification, we use PK_{H }to refer to any of these homomorphic public keys and SK_{H }to refer to any of these homomorphic private keys.
Next, the data provision and computation phase will be described in more detail. DP_{i }provides data D_{i,j }with regard to function F_{j}. In order to hide the contents of the raw data and outsource its computation to server 120, DP_{i }encrypts D_{i,j }with PK_{H }provided by proxy 140 associated with the function F_{j }to generate a package P{D_{i,j}}={E(PK_{H}, D_{i,j})} and sign it with its secret key SK_{DP}_{i}. This signature makes sure that the package P{D_{i,j}} was generated by the corresponding DP_{i}. In various embodiments, cryptographic signatures may be omitted.
After server 120 receives the data package P{D_{i,j}} and its signature, it may first check whether that package is indeed sent by the corresponding DP_{i}. If it is true, server 120 unpacks the package P{D_{i,j}}, and computes the encrypted data E(PK_{H}, D_{i,j}) with regard to F_{j }in a fully homomorphic way and obtain E(PK_{H}, DM_{j})=F_{j}({E(PK_{H}, D_{i,j})})(i=1, . . . , I). Then server 120 may obscure E(PK_{H}, DM_{j}) by multiplying a random number ra to get E(PK_{H}, DM_{j}*ra) in order to hide the computation result from proxy 140.
If RP_{k }wants to request for the result of the data processing from server 120 with regard to function F_{j}, it first may deliver the request R_{k}={PK_{RP}_{k}, F_{j}} and signs R_{k }with its secret key SK_{RP}_{k }to server 120. After receiving this request, server 120 first sends them to proxy 140 to check the eligibility of that RP_{k}. If the check is positive, proxy 140 may request server 120 for the obscured result E(PK_{H}, DM_{j}*ra) and reencrypt it with the RP_{k}'"'"'s public key to get E′(PK_{RP}_{k}, DM_{j}*ra) associated with its signature on this data. Proxy 140, may then send the data back to server 120. After confirming that the data is sent from proxy 140, server 120 computes E′(PK_{RP}_{k}, ra), packs it with E′(PK_{RP}_{k}, DM_{j}*ra), F_{j }and signs them with its secret key (Sign_{CSP}=(SK_{CSP}, {E′(PK_{RP}_{k}, DM_{j}*ra), E′(PK_{RP}_{k}, ra)})), then it sends the package and signature to the requesting party RP_{k}. The RP_{k }can finally get the result by first decrypting E′(PK_{RP}_{k}, DM_{j}*ra) and E′(PK_{RP}_{k}, ra) with its own secret key SK_{RP}_{k }to get DM_{j}*ra and ra, then the result DM_{j}, for example.
Next, the data verification phase will be described in more detail. In preparation of the verification, according to the polynomial factorization formula (f(x)−f(a)=Σ_{i=1}^{n}(x_{i}−a_{i})q_{i}(x)), DP_{i }decomposes F_{j}′∈Z_{p}^{I}[x]=F_{j}(x)−F_{j}(D_{j}), where x ∈Z_{p}^{I}, to generate F_{j}″∈Z_{p}^{I}[x]=Σ_{i=1}^{I}(x_{i}−D_{i,j})q_{i}(x)(i=1, . . . , I), where q_{i}(x) are the polynomials generated by the multivariate polynomials factorization algorithm, which both correspond to F_{j}. Meanwhile, DP_{i }chooses random data RD_{i,j }and gets random data computation result RDM_{j}=F_{j}({RD_{i,j}}) with regard to function F_{j}.
For the first time when the verifier is required to audit the data processing result provided by server 120 with regard to function F_{j }from a RP_{k}, the verifier forwards the request to the corresponding DP_{i }associated with its signature, e.g., through server 120. When receiving this request, DP_{i }issues the data package P{RD_{i,j}}={E(PK_{H}, RD_{i,j}), E(PK_{H}, RDM_{j}), F_{j}} to the verifier for it to store attached to the function F_{j}. Then for the rest of the audit, the verifier may use this package to perform the auditing process all the time until that DP_{i }is requested to refresh the package by choosing a new random data RD_{i,j}.
Auditing process: The key task of the auditing process is to compute the polynomial factorization formula in a fully homomorphic manner. The verifier 150 first queries server 120 to get the corresponding package P{D_{i,j}}={E(PK_{H}, D_{i,j})} with regard to F_{j}. Then the verifier computes function F_{j}′ and F_{j}″ both in a fully homomorphic manner, and checks if these two results are equal:
E(PK_{H}, RDM_{j})−E(PK_{H}, DM_{j})Σ_{i=1}^{I}(E(PK_{H}, RD_{i,j})−E(PK_{H}, D_{i,j}))q_{i}({E(PK_{H}, RD_{i,j})})(i=1, . . . , I).
If the check is positive, then the result is correct, else it is wrong. Finally, the verifier issues the auditing result to the corresponding RP_{k}.
The correctness of the scheme above follows from the following: if the processing result provided by server 120 passes the auditing check, that is,
E(PK_{H}, RDM_{j})−E(PK_{H}, DM_{j})Σ_{i=1}^{I}(E(PK_{H}, RD_{i,j})−E(PK_{H}, D_{i,j}))q_{i}({E(PK_{H}, RD_{i,j})})(i=1, . . . , I).
which means that RDM_{j}−DM_{j}=Σ_{i=1}^{I}(RD_{i,j}−D_{i,j})q_{i}({RD_{i,j}})(i=1, . . . , I), according to the polynomial factorization formula (f(x)−f(a)=Σ_{i=1}^{n}(x_{i}−a_{i})q_{i}(x)), since RDM_{j}=F_{j}({RD_{i,j}})(i=1, . . . , I) (computed by DP_{i}), it exists that DM_{j}=F_{j}({D_{i,j}})(i=1, . . . , I), so that the computation processed at server 120 can be indicated correct, as expected. Otherwise, the computation processed at server 120 must be erroneous.
At least some embodiments provide benefits such as, for example, privacy preservation, wherein data mining/processing/computation privacy at server 120 is improved. Server 120 cannot gain access to the plain data sent by the DPs and the plain result DM_{j }either. Moreover, this invention further ensures that the verifier also cannot know the plain input and output of the computation in the whole verification procedure.
A further, or alternative, benefit may include authentication and nonrepudiation: the invention takes advantage of digital signature to ensure the authentication and nonrepudiation. It is impossible for an illegal entity to pretend to be one of the participants in the system.
A further, or alternative, benefit may include functionawareness: for each different function with which the data are computed, the invention may generate its specific verification algorithm according to the polynomial factorization formula. Thus, based on the function that the DPs want to compute on, the system can generate a proper computation and verification procedure to carry out computation verification.
A further, or alternative, benefit may include public verification: the invention enables the public to verify the computation result of the server 120 by requesting “verification input” and “verification function” to compute the verification result. The “verification input” includes encrypted raw data or encrypted processing result. Thus, these data do not expose any useful information about data providers to the public.
A further, or alternative, benefit may include generality: this invention enables data mining/processing/computation for different purposes at the cloud. This invention enables to audit data mining/processing/computation at distrusted or semitrusted server 120 in different situations and with different processing algorithms and functions.
Device 300 may comprise memory 320. Memory 320 may comprise randomaccess memory and/or permanent memory. Memory 320 may comprise at least one RAM chip. Memory 320 may comprise solidstate, magnetic, optical and/or holographic memory, for example. Memory 320 may be at least in part accessible to processor 310. Memory 320 may be at least in part comprised in processor 310. Memory 320 may be means for storing information. Memory 320 may comprise computer instructions that processor 310 is configured to execute. When computer instructions configured to cause processor 310 to perform certain actions are stored in memory 320, and device 300 overall is configured to run under the direction of processor 310 using computer instructions from memory 320, processor 310 and/or its at least one processing core may be considered to be configured to perform said certain actions. Memory 320 may be at least in part comprised in processor 310. Memory 320 may be at least in part external to device 300 but accessible to device 300.
Device 300 may comprise a transmitter 330. Device 300 may comprise a receiver 340. Transmitter 330 and receiver 340 may be configured to transmit and receive, respectively, information in accordance with at least one cellular or noncellular standard.
Transmitter 330 may comprise more than one transmitter. Receiver 340 may comprise more than one receiver. Transmitter 330 and/or receiver 340 may be configured to operate in accordance with global system for mobile communication, GSM, wideband code division multiple access, WCDMA, 5G, long term evolution, LTE, IS95, wireless local area network, WLAN, Ethernet and/or worldwide interoperability for microwave access, WiMAX, standards, for example.
Device 300 may comprise a nearfield communication, NFC, transceiver 350. NFC transceiver 350 may support at least one NFC technology, such as NFC, Bluetooth, Wibree or similar technologies.
Device 300 may comprise user interface, UI, 360. UI 360 may comprise at least one of a display, a keyboard, a touchscreen, a vibrator arranged to signal to a user by causing device 300 to vibrate, a speaker and a microphone. A user may be able to operate device 300 via UI 360, for example configure parameters relating to distributed computing.
Device 300 may comprise or be arranged to accept a user identity module 370. User identity module 370 may comprise, for example, a subscriber identity module, SIM, card installable in device 300. A user identity module 370 may comprise information identifying a subscription of a user of device 300. A user identity module 370 may comprise cryptographic information usable to verify the identity of a user of device 300 and/or to facilitate encryption of communicated information and billing of the user of device 300 for communication effected via device 300.
Processor 310 may be furnished with a transmitter arranged to output information from processor 310, via electrical leads internal to device 300, to other devices comprised in device 300. Such a transmitter may comprise a serial bus transmitter arranged to, for example, output information via at least one electrical lead to memory 320 for storage therein. Alternatively to a serial bus, the transmitter may comprise a parallel bus transmitter. Likewise processor 310 may comprise a receiver arranged to receive information in processor 310, via electrical leads internal to device 300, from other devices comprised in device 300. Such a receiver may comprise a serial bus receiver arranged to, for example, receive information via at least one electrical lead from receiver 340 for processing in processor 310. Alternatively to a serial bus, the receiver may comprise a parallel bus receiver.
Device 300 may comprise further devices not illustrated in
Processor 310, memory 320, transmitter 330, receiver 340, NFC transceiver 350, UI 360 and/or user identity module 370 may be interconnected by electrical leads internal to device 300 in a multitude of different ways. For example, each of the aforementioned devices may be separately connected to a master bus internal to device 300, to allow for the devices to exchange information. However, as the skilled person will appreciate, this is only one example and depending on the embodiment various ways of interconnecting at least two of the aforementioned devices may be selected without departing from the scope of the present invention.
In phase 410, data provider 110 receives its homomorphic encryption keys from proxy 140. In phase 420, data provider 110 provides its data, encrypted with a homomorphic encryption key, to server 120 for processing. This phase may comprise communication of a function or function identifier, to indicate the function for the requested processing. The data communicated in phase 420 may be signed by data provider 110 using a key of data provider 110.
In phase 430, server 120 performs the processing according to the request of phase 420, using homomorphic processing wherein server 120 does not gain access to an unencrypted copy of the data or result. Obscuring using random data may be performed in this phase as well. As a result of phase 430, server 130 has an encrypted copy of the processed data.
In phase 440, requesting party 130 requests to obtain the processed data by transmitting a request to server 120, or proxy 140. In
In the lower signalling process, verification is performed, as described herein above. In detail, in phase 480 requesting party 130 requests verification of the processing of phase 430 from verifier 150. The request may comprise the processed data in encrypted form. Responsively, verifier 150 requests a package of data from data provider 110, phase 490. Data provider 110 provides the requested package in phase 4100, this package comprising encrypted random data, encrypted function output such that the output is obtained with the random data as function input, and optionally the function identifier in case verifier 150 did not receive it in phase 480. In some embodiments, the package comprises also a decomposed representation of the function, obtained in data provider 110 using a homomorphic polynomial factorization of the function.
In phase 4110, verifier 150 requests data from server 120, and responsively in phase 4120 server 120 provides to verifier 150 an encrypted copy of the unprocessed data. In embodiments where the communication of phase 480 does not comprise the processed data, server 120 may provide a copy of the processed data to verifier 150 as well, in encrypted form, in phase 4120. The data provided in phase 4120 may be encrypted using a key of data provider 110, for example.
In phase 4130 verifier 150 may verify, whether the processing of phase 430 was correct, as described herein above. Phase 4140 comprises verifier 150 providing an indication to requesting party 130 concerning an outcome of the verification of phase 4130.
Phase 510 comprises receiving an identifier of a function, encrypted input data, an encrypted computation result, encrypted random data and an encrypted output of the function, when run with the random data. Phase 520 comprises obtaining a homomorphic polynomial factorization of the function, comprising obtaining a decomposed representation of the function, the representation comprising a sum of polynomials. Obtaining the decomposed representation may comprise performing the decomposition, or receiving the decomposed representation from another node, for example. Finally, phase 530 comprises verifying that the computation result is correct by checking, whether a difference between the encrypted output and the encrypted computation result equals a value of the decomposed representation, wherein the encrypted random data and the encrypted input data are used as parameter values in the sum of polynomials.
Phase 610 comprises performing a homomorphic polynomial factorization of the function to obtain a decomposed representation of the function, the representation comprising a sum of polynomials. Phase 620 comprises obtaining random data, and generating an output of the function, when run with the random data. Finally, phase 630 comprises providing to a verifier node the random data in encrypted form, the output in encrypted form, and an identifier of the function, the verifier node distinct from a cloud computing server, wherein an apparatus performing the method is configured to offload computation of the function to the cloud computing server.
It is to be understood that the embodiments of the invention disclosed are not limited to the particular structures, process steps, or materials disclosed herein, but are extended to equivalents thereof as would be recognized by those ordinarily skilled in the relevant arts. It should also be understood that terminology employed herein is used for the purpose of describing particular embodiments only and is not intended to be limiting.
Reference throughout this specification to one embodiment or an embodiment means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Where reference is made to a numerical value using a term such as, for example, about or substantially, the exact numerical value is also disclosed.
As used herein, a plurality of items, structural elements, compositional elements, and/or materials may be presented in a common list for convenience. However, these lists should be construed as though each member of the list is individually identified as a separate and unique member. Thus, no individual member of such list should be construed as a de facto equivalent of any other member of the same list solely based on their presentation in a common group without indications to the contrary. In addition, various embodiments and example of the present invention may be referred to herein along with alternatives for the various components thereof It is understood that such embodiments, examples, and alternatives are not to be construed as de facto equivalents of one another, but are to be considered as separate and autonomous representations of the present invention.
Furthermore, the described features, structures, or characteristics may be combined in any suitable manner in one or more embodiments. In the preceding description, numerous specific details are provided, such as examples of lengths, widths, shapes, etc., to provide a thorough understanding of embodiments of the invention. One skilled in the relevant art will recognize, however, that the invention can be practiced without one or more of the specific details, or with other methods, components, materials, etc. In other instances, wellknown structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention.
While the forgoing examples are illustrative of the principles of the present invention in one or more particular applications, it will be apparent to those of ordinary skill in the art that numerous modifications in form, usage and details of implementation can be made without the exercise of inventive faculty, and without departing from the principles and concepts of the invention. Accordingly, it is not intended that the invention be limited, except as by the claims set forth below.
The verbs “to comprise” and “to include” are used in this document as open limitations that neither exclude nor require the existence of also unrecited features. The features recited in depending claims are mutually freely combinable unless otherwise explicitly stated. Furthermore, it is to be understood that the use of “a” or “an”, that is, a singular form, throughout this document does not exclude a plurality.
At least some embodiments of the present invention find industrial application in secure distributed computing.
 ABE Attributebased Encryption
 FHE Fully Homomorphic Encryption
 HE Homomorphic Encryption
 LWE Learningwitherrors
 PCP Probabilistically Checkable Proofs
 QAP Quadratic Arithmetic Programs
 RLWE RingLearningwitherrors
 SHE Somewhat Homomorphic Encryption
[1] S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, “Delegating computation: Interactive proofs for muggles,” in Proc. ACM Symp. Theory Comput., pp. 113122, 2008.
[2] J. R. Thaler, “Practical verified computation with streaming interactive proofs,” Ph.D. dissertation, Harvard University, 2013.
[3] S. Setty, R. McPherson, A. J. Blumberg, and M. Walfish, “Making argument systems for outsourced computation practical (sometimes),” in Pceedings of the ISOC NDSS, 2012.
[4] S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish,“Taking proofbased verified computation a few steps closer to practicality,” in Proc. of USENIX Security, 2012.
[5] R. Gennaro, C. Gentry, and B. Parno, “Noninteractive verifiable computation: outsourcing computation to untrusted workers,” Proc. of the 30th annual conference on Advances in cryptology (CRYPTO'"'"'10), Springer Berlin Heidelberg, pp. 465482, 2010.
[6] D. Fiore and R. Gennaro, “Publicly verifiable delegation of large polynomials and matrix computations, with applications,” in ACM conference on Computer and communications security, ACM, pp. 501512, 2012.
[7] A. Kate, G. M. Zaverucha, and I. Goldberg, “Constantsize commitments to polynomials and their applications,” in Advances in CryptologyASIACRYPT 2010, Springer, pp. 177194, 2010.
[8] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs,” in EUROCRYPT, 2013. Originally published as Cryptology ePrint Archive, Report 2012/215.
[9] S. Setty, B. Braun, V. Vu, A. J. Blumberg, B. Parno, and M. Walfish, “Resolving the conflict between generality and plausibility in verified computation,” in Proc. of the ACM European Conference on Computer Systems (EuroSys), Apr. 2013.
[10] S. Benabbas, R. Gennaro, and Y. Vahlis, “Verifiable delegation of computation over large datasets,” in Proc. of the 31st annual conference on Advances in cryptology (CRYPTO'"'"'11), Springer Berlin Heidelberg, pp. 111131, 2011.
[12] R. L. Rivest, L. Adleman, and M. L. Dertouzos, “On data banks and privacy homomorphisms,” Foundations of Secure Computation, pp. 169180, 1978.
[13] C. Gentry, “A fully homomorphic encryption scheme,” Ph.D. dissertation, Stanford University, 2009.
[14] B. Parno, M. Raykova, and V. Vaikuntanathan, “How to delegate and verify in public: verifiable computation from attributebased encryption,” Proc. of the 9th international conference on Theory of Cryptography (TCC'"'"'12), Springer Berlin Heidelberg, pp. 422439, 2012.
[15] M. Dijk, D. Clarke, B. Gassend, G. Edward Suh, and S. Devadas, “Speeding up Exponentiation using an Untrusted Computational Resource,” Journal Designs, Codes and Cryptography, vol. 39, pp. 253273, May 2006.
[16] D. Catalano and D. Fiore, “Practical homomorphic macs for arithmetic circuits,” in Advances in Cryptology—EUROCRYPT. Springer, pp. 336352, 2013.
[17] R. Gennaro and D. Wichs, “Fully homomorphic message authenticators,” in Advances in CryptologyASIACRYPT, Springer, pp. 301320, 2013.
[18] M. Backes, D. Fiore, and R. M. Reischuk, “Verifiable delegation of computation on outsourced data,” in ACM conference on Computer and communications security. ACM, pp. 863874, 2013.
[19] D. Boneh and D. M. Freeman, “Homomorphic signatures for polynomial functions,” in Advances in Cryptology—EUROCRYPT. Springer, pp. 149168, 2011.
[20] K. M. Chung, Y. Kalai, and S. Vadhan, “Improved delegation of computation using fully homomorphic encryption,” in Advances in Cryptology—CRYPTO. Springer, pp. 483501, 2010.
[21] Z. Brakerski, C. Gentry, V. Vaikuntanathan, “(Leveled) Fully Homomorphic Encryption without Bootstrapping,” Acm Transactions on Computation Theory, vol. 6, no. 3, pp. 136, 2014.
[22] Z. Yan, X. X. Yu, W. X. Ding, “Contextaware verifiable cloud computing,” IEEE Access 5: 22112227, 2017.
[23] B. Parno, J. Howell, C. Gentry, and M. Raykova, “Pinocchio: Nearly practical verifiable computation,” in IEEE Symposium on Security and Privacy. IEEE, pp. 238252, 2013.
[24] S. Papadopoulos, G. Cormode, A. Deligiannakis, and M. Garofalakis, “Lightweight authentication of linear algebraic queries on data streams,” in International conference on Management of data. ACM, pp. 881892, 2013.
[25] C. Gentry, D. Wichs, “Separating succinct noninteractive arguments from all falsifiable assumptions,” In: Proceedings of the ACM Symposium on Theory of Computing, STOC, 2011.
[26] D. Catalano, A. Marcedone, 0. Puglisi, “ Linearly homomorphic structure preserving signatures: new methodologies and applications,” IACR Cryptology ePrint Archive 2013:801, 2013.
[27] M. J. Atallah, and K. B. Frikken, “Securely outsourcing linear algebra computations,” Proc. ACM Symposium on Information, Computer and Communications Security (ASIACCS 2010), ACM, pp. 4859, 2010.
[28] D. Benjamin, and M. J. Atallah, “Private and cheatingfree outsourcing of algebraic computations,” Proc. of the 6th Annual Conference on Privacy, Security and Trust (PST '"'"'08), IEEE Computer Society, pp. 240245, 2008.
[29] N. Attrapadung, B. Libert, T. Peters, “Computing on authenticated data: new privacy definitions and constructions,” In: ASIACRYPT 2012, LNCS, vol. 7658, pp 367385, Springer, Heidelberg, 2012.
[30] R. Canetti, B. Riva, and G. N. Rothblum, “Two 1round protocols for delegation of computation,” Cryptology ePrint Archive, Report 2011/518, 2011.
[32] C. Joo, A. Yun, “Homomorphic authenticated encryption secure against chosen ciphertext attack,” IACR Cryptology ePrint Archive 2013: 726, 2013.
[33] C. Papamanthou, E. Shi, and R. Tamassia, “Publicly verifiable delegation of computation,” Cryptology ePrint Archive, Report 2011/587, 2011.