Method and system for multi-authority controlled functional encryption

Abstract

In a system having a plurality of servers, a method is executed to perform an encryption scheme. The method includes a server of the plurality of servers receiving a request token to compute a function on a data point, the data point being encrypted as a ciphertext and the request token being based on the ciphertext and the function. The server grants the request to compute the function on the datapoint by sending a function evaluation key, and participates in a distributed decryption protocol for determining a result of computing the function on the data point by sending a master secret key.

Claims

1. A method for performing an encryption scheme in a system having a plurality of servers, the method comprising: receiving, by a first server of the plurality of servers, a request from a client to compute a function on a data point, the data point being encrypted as a ciphertext and the request including a request token generated by the client based on the ciphertext and the function; and granting, by the first server, the request to compute the function on the data point by sending a function evaluation key to the client, wherein the function evaluation key is generated by the first server based on the request token and a master secret key associated with the first server, wherein the master secret key is based on a share of a secret key under a linearly-homomorphic encryption scheme and another secret key under an adaptive chosen ciphertext attack encryption scheme, wherein the function evaluation key is one of a plurality of function evaluation keys, each function evaluation key in the plurality of function evaluation keys corresponding to one of the plurality of servers participating in a distributed decryption protocol, and the plurality of function evaluation keys enable the client to generate a result of computing the function on the data point.

2. The method according to claim 1, wherein the function is a non-linear function.

3. The method according to claim 1, wherein the ciphertext is an output of an encryption algorithm using both the linearly-homomorphic encryption scheme and the adaptive chosen ciphertext attack encryption scheme.

4. The method according to claim 3, wherein the ciphertext is of the form:
(x−r.sub.0,H.Enc(pk.sup.H,r.sub.0),{E.Enc(pk.sup.E.sub.i,ctr.sub.i)}.sub.i∈[n]), wherein H.Enc( ) is an encryption algorithm of the linearly-homomorphic encryption scheme, E.Enc( ) is an encryption algorithm of the adaptive chosen ciphertext attack encryption scheme, ctr.sub.i=r.sub.i−1−r.sub.i,H.Enc(pk.sup.H,r.sub.i), r.sub.i(i∈[0,n−1]) is random, r.sub.n=0, x is the data point, n is the number of servers in the system, pk.sup.H is a public key under the linearly-homomorphic encryption scheme, {pk.sup.E.sub.i}.sub.i∈[n] are public keys of the plurality of servers under the adaptive chosen ciphertext attack encryption scheme.

5. The method according to claim 1, wherein the function evaluation key is generated based upon the request token, the function, and the master secret key associated with the first server.

6. The method according to claim 5, wherein the function evaluation key is generated by decrypting the request token.

7. The method according to claim 1, wherein an authority generates the master secret key associated with the first server.

8. The method according to claim 1, wherein the ciphertext comprises a plurality of ciphertexts of a plurality of data points, including the data point.

9. The method of claim 1, wherein the first server does not learn the computed function on the data point.

10. A method for performing an encryption scheme in a system having a plurality of servers, at least one data provider, and a client, the method comprising: receiving, by the client from the at least one data provider, a ciphertext corresponding to an encrypted data point, sending, by the client to each of the servers, a respective request to compute a function on the data point, each respective request including a respective request token corresponding to a particular server and generated based on the ciphertext and the function, receiving, from each of the servers, a respective function evaluation key, and participating in a distributed decryption protocol for determining a result of computing the function on the data point by providing a private input, wherein the result is generated based on a plurality of function evaluation keys corresponding to the plurality of servers, wherein the private input comprises the respective function evaluation key received from each of the servers and a decryption token, the decryption token being based on an encryption algorithm of a linearly-homomorphic encryption scheme.

11. The method according to claim 10, wherein the method further comprises generating the respective request token for each of the servers according to:
ctx.sup.req=E.Enc(pk.sup.E.sub.i,(r.sub.i−1−r.sub.i,(r.sub.i−1−r.sub.i,H.Enc(pk.sup.H,r.sub.i))) wherein ctx.sup.req is the respective request token for an i-th server, E.Enc( ) is an encryption algorithm of an adaptive chosen ciphertext attack encryption scheme, H.Enc( ) is an encryption algorithm of a linearly-homomorphic encryption scheme, pk.sup.E.sub.i is a public key under the adaptive chosen ciphertext attack encryption scheme for the i-th server, pk.sup.H is a public key under the linearly-homomorphic encryption scheme, r.sub.i(i∈[0,n−1]) is random, r.sub.n=0, and n is the number of servers.

12. The method of claim 10, wherein the function is a non-linear function.

13. A server comprising a processor coupled to a non-transitory storage medium containing instructions, which, when executed by the processor, cause the server to: receive a request from a client to compute a function on a data point, the data point being encrypted as a ciphertext and the request including a request token generated by the client based on the ciphertext and the function, and grant the request to compute the function on the data point by sending a function evaluation key to the client, wherein the function evaluation key is generated based on the request token and a master secret key associated with the server, wherein the master secret key is based on a share of a secret key under a linearly-homomorphic encryption scheme and another secret key under an adaptive chosen ciphertext attack encryption scheme, wherein the function evaluation key is one of a plurality of function evaluation keys, each function evaluation key in the plurality of function evaluation keys corresponding to one of a plurality of servers participating in a distributed decryption protocol, and the plurality of function evaluation keys enable the client to generate a result of computing the function on the data point.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The present invention will be described in even greater detail below based on the exemplary figures. The invention is not limited to the exemplary embodiments. All features described and/or illustrated herein can be used alone or combined in different combinations in embodiments of the invention. The features and advantages of various embodiments of the present invention will become apparent by reading the following detailed description with reference to the attached drawings which illustrate the following:

(2) FIG. 1 illustrates a multi-authority controlled functional encryption system according the present invention;

(3) FIG. 2 illustrates the operation of the multi-authority controlled functional encryption system according to the present invention; and

(4) FIG. 3 is a block diagram of a processing system according to one embodiment.

DETAILED DESCRIPTION

(5) According to the present invention, systems and methods of Multi-Authority Controlled Functional Encryption (MCFE) are provided. As illustrated and described herein, multi-authority CFE of the present invention overcomes many drawbacks and limitations of the state of the art CFE.

(6) Embodiments of the present invention provide an encryption scheme that allows a client to evaluate non-linear (e.g., quadratic) functions over messages encrypted by third-party data producers, where evaluation is subject to approval from and collaboration of n third-party servers.

(7) According to an embodiment of the present invention, there is provided a method including the followings operations: (1) encrypting, by a data-producer, a data point to generate a ciphertext; (2) transmitting, by the data-producer to a client, the resulting ciphertext; (3) issuing, by the client to at least one server, a request to compute a function on the data point encrypted as the ciphertext; (4) granting, by the server to the client, its request to compute the function over data point encrypted as the ciphertext; and (5) decrypting, by the client and the at least one server, the ciphertext, where the output is the computation of the function evaluated at the data point encrypted as the ciphertext, the output only being available to the client. The function can be a non-linear function, such as a quadratic function. The encryption step can include using both a linearly-homomorphic encryption scheme and an adaptive chosen ciphertext attack encryption scheme.

(8) Embodiments of the present invention provide at least the following improvements over the state of the art CFE. First, embodiments of the present invention allow for computing a function over multiple ciphertexts (e.g., produced by several data producers), whereas the state of the art only considers functions over a single ciphertext. Second, embodiments of the present invention allow for computing quadratic functions (e.g., variance, hamming distance, etc.) over encrypted data (e.g., ciphertexts output by data producers) by using an ad-hoc cryptographic protocol, whereas the state of the art resorts to generic multi-party computation to compute non-linear functions. Third, embodiments of the present invention cater for multiple authorities, whereas the state of the art only allows for a single authority. For example, Embodiments of the present invention allow for application scenarios where multiple servers co-exist, which is not accounted for in the state of the art. When a data producer outputs a ciphertext c, the data producer can decide the set of servers S that should enforce access control on c. As a result, no client can compute any function over c, unless all servers in S agree.

(9) An encryption scheme H can be defined by a triplet of algorithm (KeyGen, Enc, Dec), where: 1. The algorithm KeyGen(1.sup.k) (“key generation”) takes as its input the security parameter k, and outputs a public key pk and a secret key sk (also called a private key); 2. The algorithm Enc(pk,x) (“encrypt”) takes as its input the public key pk and a message x, and outputs a ciphertext c; and 3. The algorithm Dec(sk, c) (“decrypt”) takes as its input the secret key sk and the ciphertext c, and outputs a message m.
Such a scheme is correct if, for any message m of the message-space, we have Pr(m←H.Dec(sk,Enc(pk,m)),(pk,sk)←H.KeyGen(1.sup.k))=1−negl(k), where negl(k) is function that is negligible in k (meaning that the function approaches zero faster than 1 over any polynomial in the security parameter k; the security parameter k is used to determine the size of relevant elements of the encryption scheme, e.g., private keys).

(10) Such a scheme is semantically secure if an adversary holding only the public key has a negligible advantage over guessing in the following game. The challenger runs (sk,pk)←KeyGen(1.sup.k) and gives the public key pk to the adversary. The adversary picks two messages m.sub.0,m.sub.1 and gives them to the challenger. The challenger picks a random bit b and returns to the adversary c*←Enc(pk,m.sub.b). The adversary must guess which out of messages m.sub.0,m.sub.1 was encrypted by the challenger. Similarly, such a scheme is CCA2 (Adaptive Chosen Ciphertext Attack) secure if the adversary has the same advantage over guessing in the same game with the addition of a decryption oracle. The adversary can ask the decryption oracle to decrypt any ciphertext but c*.

(11) Some encryption schemes are so-called “linearly-homomorphic.” Here, the scheme defines two operations: “⊕” and “.Math.”, such that given two ciphertexts, Enc(pk,m), Enc(pk,m′), then Enc(pk,m)⊕Enc(pk,m′)=Enc(pk,m+m′). Further, given a ciphertext Enc(pk,m) and a constant t, then t.Math.Enc(pk,m)=Enc(pk,tm). Linearly-homomorphic encryption schemes allow for computing linear functions over encrypted data.

(12) Further, some encryption schemes allow for distributed decryption. Here the secret key output by (sk,pk)←KeyGen(1.sup.k) is split in n random shares, say sk.sub.1, . . . , sk.sub.n and given a ciphertext c←Enc(pk,m), we have Σ.sub.i∈[n]Dec(sk.sub.i,c)=m.

(13) Catalano and Fiore, “Using Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data,” Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1518-1529 (2015) (“Catalano and Fiore”) (the entire contents of which is hereby incorporated by reference herein), discusses how to leverage a linearly-homomorphic encryption scheme H to evaluate degree-d functions over encrypted data. In particular, Catalano and Fiore defines an encryption scheme H′=(KeyGen, Enc, Eval, Dec) where: 1. The algorithm H′.KeyGen(1.sup.k) (“key generation”) takes as its input the security parameter k, runs (pk,sk)←H.KeyGen(1.sup.k), and sets the public pk and secret keys sk accordingly, here H. Key Gen( ) is the Key Gen( ) algorithm of the linearly-homomorphic encryption scheme; 2. The algorithm H′.Enc(pk, x) (“encrypt”) takes as its input the public key pk and a message x, outputs a ciphertext as a pair (a,b), where a=x−r and b=H.Enc(pk,r) for a random r, and H.Enc( ) is the algorithm Enc.( ) of the linearly-homomorphic encryption scheme; 3. The algorithm H′.Eval(f,(a,b)) (“evaluate”) takes as its input a degree-d function ƒ and a ciphertext (a,b), it uses the homomorphic properties of H to output a “second-level” ciphertext c, such that if a=x−r and b=H.Enc(pk,r)), then c=H.Enc(pk, ƒ(x)−ƒ(r)), where r is random, and H.Enc( ) is the Enc( ) algorithm of the linearly-homomorphic encryption scheme (see e.g., Catalano and Fiore explaining the homomorphic properties and a second-level ciphertext); 4. The algorithm H′.Dec(sk,c) (“decrypt”) takes as its input the secret key sk and a ciphertext c, if c is a second-level ciphertext (i.e., a ciphertext output by Eval( )), it outputs m=H.Dec(sk,c); otherwise if c=(a,b) is a “first-level ciphertext”, it outputs a+H.Dec(sk,b), where H.Dec( ) is the Dec( ) algorithm of the linearly-homomorphic encryption scheme.
The technique described in Naveed allows for computing arbitrary degree-d functions if d=2 and a limited set of functions if d>2. As the terms are used above, a level-one ciphertext has two elements, where one is in the message space and one is in the ciphertext space of a linearly homomorphic encryption scheme, and a level-two ciphertext has more than two elements.

(14) An embodiment of the present invention provides a method for performing an encryption scheme in a system having a plurality of servers. The method includes a server of the plurality of servers receiving a request token to compute a function on a data point, the data point being encrypted as a ciphertext and the request token being based on the ciphertext and the function. The server also grants the request to compute the function on the datapoint by sending a function evaluation key, and participates in a distributed decryption protocol for determining a result of computing the function on the data point by sending a master secret key.

(15) In an embodiment, the function is a non-linear function.

(16) The ciphertext can be an output of an encryption algorithm using both a linearly-homomorphic encryption scheme and an adaptive chosen ciphertext attack encryption scheme. In an embodiment, the ciphertext is of the form: (x−r.sub.0,H.Enc(pk.sup.H,r.sub.0), {E.Enc(pk.sup.E.sub.i,ctr.sub.i)}.sub.i∈[n]). Here, H.Enc( ) is an encryption algorithm of the linearly-homomorphic encryption scheme, E.Enc( ) is an encryption algorithm of the adaptive chosen ciphertext attack encryption scheme, ctr.sub.i=r.sub.i−1−r.sub.i,H.Enc(pk.sup.H,r.sub.i), r.sub.i (i∈[0,n−1]) is random, r.sub.n=0, x is the data point, n is the number of servers in the system, pk.sup.H is a public k under the linearly-homomorphic encryption scheme, {pk.sup.E.sub.i}.sub.i∈[n] are public keys of the servers under the adaptive chosen ciphertext attack encryption scheme.

(17) The function evaluation key can be generated based upon the request token, the function, and the server's master secret key. In an embodiment, the function evaluation key is generated by decrypting the request token.

(18) An authority can generate the master secret key. In an embodiment, the master secret key is based on the server's share of a secret key under a linearly-homomorphic encryption scheme and another secret key under an adaptive chosen ciphertext attack encryption scheme.

(19) In an embodiment, the ciphertext includes a plurality of ciphertexts of a plurality of data points, including the data point.

(20) In an embodiment, the server does not learn the computed function on the data point.

(21) Another embodiment of the present invention provides, a method for performing an encryption scheme in a system having a plurality of servers, at least one data provider and a client. In the method, the client receives from the at least one data provider, a ciphertext which is an encrypted data point. The client may send to each of the servers a respective request token to compute a function on the data point, the respective request token being based on the ciphertext and the function. Each of the servers receive a respective function evaluation key, and participate in a distributed decryption protocol for determining a result of computing the function on the data point by providing a private input.

(22) The private input may include the respective function evaluation key received from each of the servers and a decryption token, the decryption token being based on an encryption algorithm of a linearly-homomorphic encryption scheme.

(23) The method may further include generating the respective request token for each of the servers according to: ctx.sup.req=E.Enc(pk.sup.E.sub.i,(r.sub.i−1−r.sub.i, H.Enc(pk.sup.H,r.sub.i))). Here, ctx.sup.req is the respective request token for an i-th server, E.Enc( ) is an encryption algorithm of an adaptive chosen ciphertext attack encryption scheme, H.Enc( ) is an encryption algorithm of a linearly-homomorphic encryption scheme, pk.sup.E.sub.i is a public key under the adaptive chosen ciphertext attack encryption scheme for the i-th server, pk.sup.H is a public key under the linearly-homomorphic encryption scheme, r.sub.i(i∈[0,n−1]) is random, r.sub.n=0, and n is the number of servers. The function may be a non-linear function.

(24) According to another embodiment of the present invention, a server is provided that includes a processor coupled to a non-transitory storage medium containing instructions, which when executed by the processor, cause the server to: receive a request token to compute a function on a data point, the data point being encrypted as a ciphertext and the request token being based on the ciphertext and the function, granting the request to compute the function on the datapoint by sending a function evaluation key, and participate in a distributed decryption protocol for determining a result of computing the function on the data point by sending a master secret key.

(25) With the above in mind, the multi-authority Controlled Functional Encryption (MCFE) scheme according to embodiments of the present invention is described in detail below in connection with the figures.

(26) FIG. 1 illustrates a schematic model of a MCFE system 100 of the present invention. The MFCE system 100 of FIG. 1 has multiple data producers 110 and multiple servers 120. The multiple data producers 110 send encrypted data (solid arrows) 130 to a client 140. The client's goal is to compute a function ƒ over the data encrypted under the ciphertexts provided by the data producers 110. In order to do so, the client 140 sends a request (dashed arrows) 150 to each of the servers 120. Each server 120 decides whether to grant or deny the request from the client 140 (sending the grant/replay response 160). Finally, the client 140 computes ƒ over the data encrypted under the ciphertexts provided by the data producers 110, if all servers 120 grant the request.

(27) According to an embodiment, the above system can be instantiated for quadratic functions of the form ƒ(x)=ax.sup.2+bx, for a, x, b elements in Z.sub.p, where p is a prime (Z.sub.p thus is the set o integers coprime with p). Here, H=(Setup, Enc, Dec) is a linearly-homomorphic encryption scheme with distributed decryption, and E=(Setup, Enc, Dec) is a CCA2 (Adaptive Chose Ciphertext Attack) encryption scheme. The Eval( ) algorithm of Naveed as described above can also be employed in embodiments.

(28) According to an embedment, algorithms and protocols that instantiate the system of FIG. 1 include: 1. The algorithm Setup(1.sup.k) (“key setup”), which takes as its input the security parameter k, and outputs a master public key mpk and n master secret keys {msk.sub.i}.sub.i∈[n] (in an embodiment n is the number of servers); 2. The algorithm Enc(mpk,x) (“encrypt”), which takes as its input the master public key mpk and a value x, and outputs ciphertext ctx; 3. The algorithm KeyReq(ctx,ƒ) (“key request”), which takes as its input the ciphertext ctx and a function ƒ∈F, and outputs n request tokens {ctx.sup.reg.sub.i}.sub.i∈[n] and a decryption token ctx.sup.dec; 4. The algorithm KeyExtract(ctx.sup.reg.sub.iƒ,msk.sub.i) (“key extract”), which takes as its input a request token ctx.sup.req.sub.i, function ƒ, and the i-th master secret key msk.sub.i, and outputs the i-th function evaluation key skƒ.sub.i; and 5. The protocol Dec(ctx.sup.dec, {skƒ.sub.i}.sub.i∈[n]; msk.sub.1; . . . ; msk.sub.n) (“decrypt”), which is an interactive protocol between a client, with private input (ctx.sup.dec,{skƒ.sub.i}.sub.i∈[n]), and each of the servers, with its respective private input msk.sub.i. The private output for the client is y=ƒ(x), whereas each server outputs nothing.

(29) In an embodiment of the present invention, Setup( ) defines a CCA2 (Adaptive Chose Ciphertext Attack) secure encryption scheme E=(KeyGen, Enc, Dec), where the i-th server (i∈[n]) has its own public-private key pair (pkE.sub.i,skE.sub.i), and a linearly-homomorphic encryption scheme H=(Keygen, Enc, Dec), where the i-th server (i∈[n]) has a share of the decryption key skH.sub.i and the public key is pkH.

(30) Setup( ) can be either run by an authority that distributes keys to the server and then goes offline, or it can alternatively be run in a distributed fashion by all the servers. In the latter case, no authority is needed. In order to adhere to the above definition of MCFE, mpk=pkH, {pkE.sub.i}i∈[n] and, for i∈[n], msk.sub.i=(skH.sub.i,skE.sub.i).

(31) FIG. 2 illustrates an overview of the MCFE system 100 after Setup( ) has been run and all secret server keys are in place. The embodiment shown in FIG. 2 accounts for one data producer 110 and two servers 120, but the present invention can accommodate any number of data producers 110 and servers 120.

(32) The data producer 110 encrypts a data item x (S01) to produce a ciphertext ctx, and sends the ciphertext ctx to the client 140 (S02). In particular, the encryption routine on input x, outputs a ciphertext of the form:
ctx=(x−r.sub.0,H.Enc(pk.sup.H,r.sub.0),{E.Enc(pk.sup.E.sub.i,ctr.sub.i)}.sub.i∈[n])
where ctr.sub.i=r.sub.i−1−r.sub.i, H.Enc(pk.sup.H,r.sub.i), r.sub.i(i∈[0,n−1]) is random, and r.sub.n=0. The first two elements of a ciphertext (a=x−r.sub.0, b=H.Enc (pk.sup.H, r.sub.0)) are similar to a ciphertext as defined in Catalano and Fiore. Therefore, embodiments can use the Eval( ) algorithm of Catalano and Fiore to compute c′←Eval(a,b), where c′ is equivalent to H.Enc(pk.sup.H,ƒ(x)−ƒ(r)).

(33) Nevertheless, in Catalano and Fiore the secret key corresponding to the public key pk.sup.H is held by one party, whereas embodiments of the present invention distribute the secret key across then servers 120. Further, embodiments of the present invention randomly share r.sub.0 across all servers 120 (via ctr.sub.i), and use encryption scheme E to transfer securely each of those shares to each of the servers 120.

(34) Given ciphertext ctx and a function ƒ, the client 140 may be interested in computing ƒ(x). To do so, the client 140 should interact with all of the servers 120. The client 140 runs ({ctx.sup.reg.sub.i}.sub.i∈[n]ctx.sup.dec)←KeyReq(ctx,ƒ) (“key request”) to obtain n request tokens {ctx.sup.req.sub.i}.sub.i∈[n], one for each server 120, and one decryption token ctx.sup.dec(S03). In particular, the request token for the i-th authority is:
ctx.sup.req=E.Enc(pk.sup.E.sub.i,(r.sub.i−1−r.sub.i,H.Enc(pk.sup.H,r.sub.i)))
whereas the decryption token that the client 140 keeps is:
ctx.sup.dec=H.Enc(pk.sup.H,ƒ(x)−ƒ(r.sub.0)),
which the client 140 computes by applying the Eval( ) algorithm of Naveed to x-r.sub.0, H.Enc(pk.sup.H, r.sub.0).

(35) The client 140 issues to the i-th server 120 a request to compute the function ƒ(x), by sending the request token ctx.sup.req.sub.i to the i-th server 120 (S04). If the i-th server 120 decides to honor the client's request, it runs skf.sub.i←KeyExtract(ctx.sup.req.sub.iƒ,msk.sub.i) (“key extract”) (S05),and sends the function evaluation key skƒ.sub.i to the client (S06). In particular, the i-th server decrypts the request token ctx.sup.req.sub.i as:
a,b=E.Dec(sk.sup.E.sub.i,ctx.sup.req.sub.i)
where a=r.sub.i−1−r.sub.i, and b=H.Enc(pk.sup.H,r.sub.i), and then uses the Eval( ) algorithm of Naveed on input a, b to compute:
skƒ.sub.i=H.Enc(pk.sup.Hƒ(r.sub.i−1)−ƒ(r.sub.i)).

(36) The client 140 can issue another request to the next (i+1) server 120 in the system to compute the function ƒ(x), by sending the corresponding request token ctx.sup.req.sub.i+1 to the next server 120 (S07). If that server 120 decides to honor the client's request, it runs skƒ.sub.2←KeyExtract(ctx.sup.req.sub.i+1, ƒ,msk.sub.i+1) (“key extract”) (S08),and sends its secure key skƒ.sub.2 to the client (S09).

(37) Finally, if all n servers 120 have honored the client's requests, then the client 140 and the n servers 120 engage in a distributed decryption protocol where the client's private input is (ctx.sup.dec, {skƒ.sub.i}.sub.i∈[n]) (S10), the private input of the i-th server 120 is its master secret key msk.sub.i (S11), and the private input of the next server 120 is its master secret key msk.sub.i+1(S12). At the end of the protocol, the client's private output is y=ƒ(x) (i.e., the result of executing the function ƒ( ) on the data input x) (S13), whereas servers 120 output nothing. In particular, the client computes:
h=ctx.sup.dec⊕skƒ.sub.1⊕ . . . ⊕skƒ.sub.n
which is equivalent to H.Enc(pk.sup.H, ƒ(x)−ƒ(0)), and then asks each authority to partially decrypt h. That is, the client 140 sends h to the i-th server 120 that uses the share of its secret key of the linearly-homomorphic encryption scheme to compute y.sub.i←H.Dec(sk.sub.i,h), and sends it back to the client 140. Finally, the client 140 outputs y=Σ.sub.i∈[n]y.sub.i. The latter is equivalent to ƒ(x)−ƒ(0).

(38) Correctness of the scheme implies that if all algorithms are executed correctly, then the client 140 learns y=ƒ(x) (i.e., the result of the function executing on the data point). Security of the scheme implies that: (1) no information on the data point x is leaked unless the client 140 and all of the servers 120 collude, (2) the client 140 learns ƒ(x) and nothing else, if and only if all of the n servers 120 decided to honor the client's request, and (3) no server 120 learns any information on x nor do the servers learn any information on ƒ(x).

(39) According to embodiments, pseudocode of the algorithms discussed above can be represented as: 1. For the algorithm Setup(1.sup.k): On the input of the security parameter k, a. Run (pk.sup.H,sk.sup.H)←H.KeyGen(1.sup.k) and compute n random shares of sk.sup.H, namely {sk.sup.H.sub.i}.sub.i∈[n], such that sk.sup.H=Σ.sub.i∈[n]sk.sup.H.sub.i b. For i∈[n], run (pk.sup.E.sub.i,sk.sup.E.sub.i)←E.KeyGen(1.sup.k) c. Set mpk=pk.sup.H, {pk.sup.E.sub.i}.sub.i∈[n] d. For i∈[n], set msk.sub.i=sk.sup.H.sub.i,sk.sup.E.sub.i 2. For the algorithm Enc(mpk, x): On the input of the master public key mpk and a value x that belongs to Z.sub.p, a. Parse mpk as pk.sup.H, {pk.sup.E.sub.i}.sub.i∈[n] b. For I=[0, n−1], sample r.sub.i at random from Z.sub.p c. Set, r.sub.n=0 d. For i∈[n], set ctr.sub.i=(r.sub.i−1−r.sub.i, H.Enc(pk.sup.H,r.sub.i)) e. Output ctx=(x−r.sub.0, H.Enc(pk.sup.H,r.sub.0), {E.Enc(pk.sup.E.sub.i,ctr.sub.i)}.sub.i∈[n]) 3. For the algorithm KeyReq(ctx, ƒ): On the input of a ciphertext ctx and a function ƒ∈F , a. Parse ctx as (a,b, {e.sub.i}.sub.i∈[n]) b. For i∈[n], set ctx.sup.req.sub.i=e.sub.i c. Run ctx.sup.dec←Eval(ƒ,(a,b)); the latter is equivalent to H.Enc(pk.sup.H,ƒ(x)−ƒ(r.sub.0)), given that a=x−r.sub.0 and b=H.Enc(pk.sup.H, r.sub.0) d. Output {ctx.sup.reg.sub.i}.sub.i∈[n],ctx.sup.dec 4. For the algorithm KeyExtract(ctx.sup.req.sub.i, ƒ, msk.sub.i): On the input of a request token ctx.sup.req.sub.i, a function ƒ, and the master secret key of the i-th server msk.sub.i, a. Parse msk.sub.i=sk.sup.H.sub.i,sk.sup.E.sub.i b. Compute ctr.sub.i=E.Dec(sk.sup.E.sub.i, ctx.sup.req.sub.i) c. Parse ctr.sub.i as (a.sub.i,b.sub.i) and run skƒ.sub.i←Eval(ƒ(a.sub.i,b.sub.i)); the latter is equivalent to H.Enc(pk.sup.H,ƒ(r.sub.i−1)−ƒ(r.sub.i)), given that a.sub.i=r.sub.i−1−r.sub.i and b.sub.i=H.Enc(pk.sup.H,r.sub.i) 5. For the algorithm Dec(ctx.sup.dec, {skƒ.sub.i}i∈.sub.[n]; msk.sub.1; . . . ; msk.sub.n): On the input of the client's private input (ctx.sup.dec, {skƒ.sub.i}.sub.i∈[n]) and on the i-th server's private input msk.sub.i, a. Client computes h=ctx.sup.dec⊕skƒ.sub.1⊕ . . . ⊕skƒ.sub.n; the latter is equivalent to H.Enc(pk.sup.H, ƒ(x)−ƒ(0)), since ctx.sup.dec=,H.Enc(pk.sup.H, ƒ(x)−ƒ(r.sub.0)), for i∈[n] skf.sub.i=H.Enc(pk.sup.H,f(r.sub.i−1)−f(r.sub.i)), and f(r.sub.n)=f(0) b. For i∈[n], client sends to the i-th server h; c. For i∈[n], the i-th server uses msk.sub.i=sk.sup.H.sub.i,sk.sup.E.sub.i to compute y.sub.i=H.Dec(sk.sup.H.sub.i,h) and sends y.sub.i to the client d. The client outputs y=Σ.sub.i∈[n]y.sub.i+ƒ(0)

(40) The above scheme can be extended to accommodate multivariate functions where inputs are provided by different data producers. In particular, the scheme can be extended to compute functions of the form ƒ(x)=x.sup.TAx+b.sup.Tx, where A is an 1-by-1 symmetric matrix of elements in Z.sub.p, and b,x are vectors of 1 elements in Z.sub.p, and p is a prime.

(41) Algorithms Setup and Decrypt remain unchanged. The encryption algorithm does not change, but the notation is updated to reflect the fact that computation is performed over vectors of size 1. Here, x.sub.j denotes the j-th input to the function. 1. Enc(mpk,x.sub.j): On the input of the master public key mpk and a value x.sub.j that belongs to Z.sub.p, a. Parse mpk as pk.sup.H, {pk.sup.E.sub.i}.sub.i∈[n] b. For i=[0,n−1], sample r.sub.i,j at random from Z.sub.p c. Set, r.sub.n,j=0 d. For i∈[n], set ctr.sub.i,j=(r.sub.i−1,j−r.sub.i,j, H.Enc(pk.sup.H,r.sub.i,j)) e. Output ctx.sub.j=(x.sub.j−r.sub.0,j, H.Enc(pk.sup.H,r.sub.0,j), {E.Enc(pk.sup.E.sub.i,ct.sub.i,j)}.sub.i∈[n])

(42) In the scenario where ctx.sub.1, . . . , ctx.sub.1 are the ciphertexts of the 1 inputs x.sub.1, . . . , x.sub.1 to function ƒ. For simplicity, the notation ctx=[ctx.sub.1, . . . , ctx.sub.1], x=[x.sub.1, . . . , x.sub.j] is used, and for i∈[0,n]r.sub.i=[r.sub.i,1, . . . , r.sub.i,1]. Also, if ctx.sub.j=a.sub.j, b.sub.j, {e.sub.i,j}.sub.i∈[n], we also define α=[a.sub.1, . . . , a.sub.1] and β=[b.sub.1, . . . , b.sub.1], and, for i∈[n] ε.sub.i=[e.sub.i,1, . . . , e.sub.i,1]. Here, the key request and key extract algorithm can be expressed with the following pseudocode: 1. KeyReq(ctx,ƒ): On the input of a ciphertext ctx and a function ƒ∈F, a. Parse ctx as (α, β, {ε.sub.i}.sub.i∈[n]) b. For i∈[n], set ctx.sup.req.sub.i=ε.sub.i c. Run ctx.sup.dec←Eval(ƒ(α,β)); the latter is equivalent to H.Enc(pk.sup.H,ƒ(x)−ƒ(r.sub.0)), given that α=x−r.sub.0 and β=[H.Enc(pk.sup.H,r.sub.0,1) . . . H.Enc(pk.sup.H,r.sub.0,1)] d. Output {ctx.sup.reg.sub.i}.sub.i∈[n],ctx.sup.dec 2. KeyExtract(ctx.sup.req.sub.i,f,msk.sub.i): On the input of a request token ctx.sup.req.sub.i, a function ƒ, and the master secret key of the i-th server msk.sub.i, a. Parse as ctx.sup.req.sub.i as [ctx.sup.req.sub.i,1, . . . , ctx.sup.req.sub.i,1] and msk.sub.i=sk.sup.H.sub.i, sk.sup.E.sub.i b. For j∈[1], compute (a.sub.j,b.sub.j=E.Dec(sk.sup.E.sub.i,ctx.sup.req.sub.i,j) c. Set α=[a.sub.1, . . . a.sub.1] and β=[b.sub.1, . . . , b.sub.1] d. Run skƒ.sub.i←Eval(ƒ,(α,β)); the latter is equivalent to H.Enc(pk.sup.H,ƒ(r.sub.i−1)−ƒ(r.sub.i)), given that α=r.sub.i−1−r.sub.i and β=[H.Enc(pk.sup.H,r.sub.i−1) . . . H.Enc(pk.sup.H,r.sub.i,1)] e. Output skƒ.sub.i

(43) Compared to state of the art, embodiments of the present invention allow for computing multivariate functions and accommodate multiple servers. All servers should agree and cooperate with a client for the latter to compute a function over a ciphertext. Furthermore, embodiments of the present invention provide a faster solution to compute quadratic functions, whereas state of the resorts to generic multi-party computation.

(44) FIG. 3 is a block diagram of a processing system according to one embodiment. The processing system is a specialty computer configured and programed to embody and perform the multi-authority controlled functional encryption systems and methods of the present invention, for example, the processing system may be employed to embody a server, client, and/or data provider described above. The processing system includes a processor 704, such as a central processing unit (CPU) that executes computer executable instructions comprising embodiments of the system for performing the functions and methods described above. In embodiments, the computer executable instructions are locally stored and accessed from a non-transitory computer readable medium, such as storage 710, which may be a hard drive or flash drive. Read Only Memory (ROM) 706 includes processor executable instructions for initializing the processor 704, while the random-access memory (RAM) 708 is the main memory for loading and processing instructions executed by the processor 704. The network interface 712 may connect to a wired network or cellular network and to a local area network or wide area network, such as the Internet.

(45) While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. It will be understood that changes and modifications may be made by those of ordinary skill. In particular, the present invention covers further embodiments with any combination of features from different embodiments described above. Additionally, statements made herein characterizing the invention refer to an embodiment of the invention and not necessarily all embodiments.

(46) The terms used in the claims should be construed to have the broadest reasonable interpretation consistent with the foregoing description. For example, the use of the article “a” or “the” in introducing an element should not be interpreted as being exclusive of a plurality of elements. Likewise, the recitation of “or” should be interpreted as being inclusive, such that the recitation of “A or B” is not exclusive of “A and B,” unless it is clear from the context or the foregoing description that only one of A and B is intended. Further, the recitation of “at least one of A, B and C” should be interpreted as one or more of a group of elements consisting of A, B and C, and should not be interpreted as requiring at least one of each of the listed elements A, B and C, regardless of whether A, B and C are related as categories or otherwise. Moreover, the recitation of “A, B and/or C” or “at least one of A, B or C” should be interpreted as including any singular entity from the listed elements, e.g., A, any subset from the listed elements, e.g., A and B, or the entire list of elements A, B and C.