# Distributed Functional Signature with Function Privacy and Its Application

Authors: Muhua Liu; Lin Wang; Qingtao Wu; Jianqiang Song
Journal: Security and Communication Networks
 (2021)

---

## Abstract

We introduce a novel notion of distributed functional signature. In such a signature scheme, the signing key for functionf will be split into n shares skfi and distributed to different parties. Given a message m and a share skfi, one can compute locally and obtain a pair signature fim,σi. When given all of the signature pairs, everyone can recover the actual value fm and corresponding signature σ. When the number signature pairs are not enough, nobody can recover the signature fm,σ. We formalize the notion of function privacy in this new model which is not possible for the standard functional signature and give a construction from standard functional signature and function secret sharing based on one-way function and learning with error assumption. We then consider the problem of hosting services in multiple untrusted clouds, in which the verifiability and program privacy are considered. The verifiability requires that the returned results from the cloud can be checked. The program privacy requires that the evaluation procedure does not reveal the program for the untrusted cloud. We give a verifiable distributed secure cloud service scheme from distributed functional signature and prove the securities which include untrusted cloud security (program privacy and verifiability) and untrusted client security.


---

## Body

## 1. Introduction

Digital signature schemes were introduced by Diffie and Hellman [1]. In a digital signature scheme, it has a secret signing key and a corresponding verification key. Only the person who has the secret key can sign a message, and any person can verify the signature with the verifiable key. Goldwasser et al. [2] gave a standard secure definition. A signature scheme is unforgeable against chosen message attack if an adversary produces a valid signature of any message with at most negligible probability in probabilistic polynomial time. The adversary is allowed to query signatures for a polynomial number of messages of his choice. Subsequently, it appeared to have many other forms of signatures, such as blind signature [3], group signature [4], ring signature [5], identity-based signature [6], homomorphic signature [7, 8], and so on.Functional signatures (FSs) were proposed by Boyle et al. [9]. In a functional signature scheme, in addition to a master key which can sign any messages belonging to the message space, it also has a signing key skf for any function f, which are derived from the master key. Using the signing key skf, one can sign any message in the range of f. The security requires that the probability of producing a valid signature on message m does not exceed a negligible function for any probability polynomial adversary which can query the signing key for functions f1,f2,…,fℓ of his choice and signatures of messages m1,m2,…,mn of his choice. A valid signature on m means that m does not equal to one of the queried messages m1,m2,…,mn or m does not belong to range of one of the queried functions f1,f2,…,fℓ. For a functional signature scheme, a desirable property is function privacy which requires a signature should not reveal the function. A typical application is the signed photo-processing software [9]; the owner of photos want to remove red eyes or color scale, but does not allow more significant changes. At the same, the owner wishes the signed photos do not reveal the original image.Boyle et al. [9] firstly gave a construction based on the existence of one-way functions, which does not satisfy the property of function privacy. Then, they transformed it into a construction that satisfied the function privacy by the noninteractive zero-knowledge arguments of knowledge for NP languages which is based on nonfalsifiable assumptions. In their secure definition of function privacy, it requires that the distribution of signatures on a message m generated via different keys skf to be computationally indistinguishable. While this model restricted the application of the scheme, it is not clear how could this weakened notion be applied in the general setting. For example, a software company develops software and delegates the computation ability to a server. The company wishes it does not reveal the core function during the computational procedure and the returned results can be verified. In a functional signature scheme, standard function privacy cannot possibly satisfy this scenario. Since the attacker who has a signing key skf can generate the signature σ,fm for the message m on the fly, the attacker can obtain the evaluations of fm1,…,fmn for the messages m1,…,mn of its choices. It will reveal some functions of the software by the evaluation pairs mi,fmii=1n.Therefore, we try to find a realistic model that allows us to approach function privacy for functional signature based on some standard assumption, such as the existing one-way function and learning with error assumption.


### 1.1. Our Contributions

In this paper, we introduce the definition of distributed functional signature scheme. In such a model, the signing key for a functionf will be split into n shares skfi and distributed to different parties. Given a secret signing key skfi, anyone can compute locally and obtain a pair signature fim,σi. When given n signatures fim,σii=1n on the message m, everyone can reconstruct the function evaluation fm and the corresponding signature σ. While given less than n signatures fim,σii∈S satisfying S<n, anyone cannot reconstruct the evaluation fm and the corresponding signature σ. In our secure definition of function privacy, we require the attacker to not distinguish the distribution of signing key skfii∈S generated via different function f, where S<n. The attacker is allowed to query key generation oracle and evaluation oracle. This new definition of distributed functional signature generalizes the notion of threshold signature to the setting of functional signature, enables the participants to recover an evaluation of the function f on input m, and verifies the result by the corresponding signature together.In our new model, it provides a possibility of function privacy in the setting of functional signature. Specifically, when given less thann signing key skfi for function f, the adversary can only know fim corresponding to the share function fi which is not enough to determine fm. We give a construction for distributed functional signature by transforming any functional signature which does not support function privacy into a distributed version which satisfies both unforgeability and function privacy via function secret sharing [10]. Our scheme can be constructed based on the one-way function and learning with error assumption.We remark here that our notion of function privacy is different from the standard function privacy [9]. The latter mainly considers that single signature does not reveal the function, while we consider that the signature process does not reveal the function by splitting each function into secret key shares. In our scheme, the attacker only gets at most n−1 secret key shares and thus obtains at most n−1 signatures fim,σii∈S satisfying |S|<n. Anyone cannot reconstruct the value fm. Therefore, it satisfies the function privacy.Hosting services securely in multiple untrusted clouds. In recent years, cloud computing has become a very hot research area in cryptography. Boneh et al. [11] first studied hosting service in the cloud. They considered the security which includes protecting program information and client’s inputs against untrusted cloud and protecting program information and authorization procedure against untrusted clients. It has wide applications to protect program information against untrusted client and cloud, such as software protected. Fan and Tang [12] gave a construction from distributed functional encryption. However, it requires that the cloud is semihonest. Sometimes, the cloud may run a fast but incorrect computation due to a financial incentive. Therefore, we also consider another property of verifiability which requires that the returned results from the cloud can be checked in the untrusted cloud model.In addition, the construction of Fan and Tang [12] is based on the generic functional encryption. As far as we know, most works have approached the problem of constructing generic functional encryption by proposing a candidate under the existing of indistinguishability obfuscation [13]. Meanwhile, the construction of Boneh et al. [11] is also based on the existing indistinguishability obfuscation. However, indistinguishability obfuscation is not a particularly appealing assumption since the security of constructions relies on an exponential number of assumptions [14]. Recently, numerous attacks on multilinear maps [15] have reduced the community’s confidence in the security of existing construction of indistinguishability obfuscation. In this work, we provide a construction of secure cloud service scheme based on some more general assumptions, such as the existing one-way function and learning with error assumption.A secure cloud service scheme satisfying the verifiability can be constructed by a distributed functional signature scheme and a standard signature scheme. The standard signature scheme is used to authenticate the client. In order to achieve the verifiability, the service first generates some signing keyskP^i for the program P^=x|Px. When the client receives the returned results from clouds, it can get the evaluation y,σ by the reconstruction algorithm of distributed signature scheme. To prove that y=x|Px, the client verifies the signature σ of y, where the signature σ could only be obtained if y is in the range of P^.


### 1.2. Related Works

The concept of identity-based signature was proposed by Shamir in [16]. Bellare and Fuchsbauer [17] introduced policy-based signatures, where a signer can only sign messages satisfying some authority-specified policy. Backes et al. [18] introduced delegatable functional signatures which support the delegation of signing capabilities to another party with respect to a functionality. This new notion unifies several signature primitives, such as policy-based signature, functional signature, identity-based signature, and blind signature.Homomorphic signature was first proposed by Johnson et al. [19], which was initially designed to establish authentication in network coding. In addition, it can also be used to authenticate the stored data. In a homomorphic signature scheme, a holder which has the signature pairs m0,σ0 and m1,σ1 can construct a new signature σ on the value fm0,m1 for some function f without the signing key. Freeman [20] gave a linearly homomorphic signature scheme which allows authentication of linear functions on signed data. Catalano et al. [21] constructed a homomorphic signature scheme for polynomial functions.The concept of functional encryption comes from the work of Sahai and Waters [22]. The definition of simulation-based security was firstly proposed by Boneh et al. [23]. Garg et al. [13] firstly proposed a construction for functional encryption which supported all polynomial size circuits. Goldwasser et al. [24] constructed a succinct functional encryption scheme based on reusable garbled circuits and identity-based encryption for any polynomial-time function. Subsequently, Goldwasser et al. [25] introduced the notion of multi-input functional encryption, which supported the multi-input functions, and gave a construction based on indistinguishability obfuscation. In a multi-input functional encryption, the decryption key skf for a function f takes multiple ciphertexts as input and outputs a function evaluation. Besides, there are many other functional encryptions for inner-product functions [26–28].Boneh et al. [11] gave a construction of hosting service in the cloud. Their construction relied on indistinguishability obfuscation iO and restricted the number of colluded clients for the security. Fan and Tang [12] presented a new definition of distributed public key functional encryption. In their scheme, the decryption key for a function f is split into several sharing key skif. Given a ciphertext that encrypts a message m and a sharing key skif, it can evaluate a shared value yi which reveals nothing about the plaintext and the value of fm. One can recover the value of fm by adding all the shared values yi. With this approach, it can achieve function privacy which is not possible in the setting of regular public key functional encryption. Then, they considered the problem of hosting services in the untrusted cloud. Applying the function private distributed public key functional encryption to the setting of hosting service in multiple clouds, it can remove the restriction that the number of corrupted clients has to be bounded and known in the previous works.Boyle et al. [9] firstly proposed functional signatures, which allowed an authority to generate signing keys corresponding to various functions such that a user with a signing key skf can sign the image of function f on a message m. Okamoto and Takashima [29] firstly introduced the concept of a decentralised multiauthority functional signatures, which supports nonmonotone access structures combined with inner-product relations. Liang and Mitrokotsa [30] generalised the definition of decentralised multiauthority functional signature for more general policy functions. Datta et al. [31] introduced the concept of functional signcryption, which provided the functionalities of both functional encryption and functional signature. Pan et al. [32] introduced the notion of hierarchical functional signcryption which expanded the scope of functional signcryption in hierarchical access-control application. Li et al. [33] introduced the notion of private functional signatures, in which the signing key skf can be used to generate a signature σfx on the ciphertext cx, where cx is a ciphertext for message x.Blockchains originate from Bitcoin and are essentially a decentralised database that uses peer-to-peer network. It is a new application mode of computer technology such as distributed data storage, point-to-point transmission, and consensus mechanism. This makes blockchains potentially suitable for recording events, medical records, and other management activities. Although it can realize the function of software protection, it does not possess computing capabilities. In this work, our goal is to achieve software protection while ensuring software availability.Notation. In what follows, we will denote with λ∈N a security parameter. We say neglλ is negligible if neglλ<1/polyλ holds for all polynomials polyλ and all sufficiently large λ. Denote n as the set 1,2,…,n. We abbreviate probabilistic polynomial time as PPT. Denote S as the number of elements in the set S.


## 1.1. Our Contributions

In this paper, we introduce the definition of distributed functional signature scheme. In such a model, the signing key for a functionf will be split into n shares skfi and distributed to different parties. Given a secret signing key skfi, anyone can compute locally and obtain a pair signature fim,σi. When given n signatures fim,σii=1n on the message m, everyone can reconstruct the function evaluation fm and the corresponding signature σ. While given less than n signatures fim,σii∈S satisfying S<n, anyone cannot reconstruct the evaluation fm and the corresponding signature σ. In our secure definition of function privacy, we require the attacker to not distinguish the distribution of signing key skfii∈S generated via different function f, where S<n. The attacker is allowed to query key generation oracle and evaluation oracle. This new definition of distributed functional signature generalizes the notion of threshold signature to the setting of functional signature, enables the participants to recover an evaluation of the function f on input m, and verifies the result by the corresponding signature together.In our new model, it provides a possibility of function privacy in the setting of functional signature. Specifically, when given less thann signing key skfi for function f, the adversary can only know fim corresponding to the share function fi which is not enough to determine fm. We give a construction for distributed functional signature by transforming any functional signature which does not support function privacy into a distributed version which satisfies both unforgeability and function privacy via function secret sharing [10]. Our scheme can be constructed based on the one-way function and learning with error assumption.We remark here that our notion of function privacy is different from the standard function privacy [9]. The latter mainly considers that single signature does not reveal the function, while we consider that the signature process does not reveal the function by splitting each function into secret key shares. In our scheme, the attacker only gets at most n−1 secret key shares and thus obtains at most n−1 signatures fim,σii∈S satisfying |S|<n. Anyone cannot reconstruct the value fm. Therefore, it satisfies the function privacy.Hosting services securely in multiple untrusted clouds. In recent years, cloud computing has become a very hot research area in cryptography. Boneh et al. [11] first studied hosting service in the cloud. They considered the security which includes protecting program information and client’s inputs against untrusted cloud and protecting program information and authorization procedure against untrusted clients. It has wide applications to protect program information against untrusted client and cloud, such as software protected. Fan and Tang [12] gave a construction from distributed functional encryption. However, it requires that the cloud is semihonest. Sometimes, the cloud may run a fast but incorrect computation due to a financial incentive. Therefore, we also consider another property of verifiability which requires that the returned results from the cloud can be checked in the untrusted cloud model.In addition, the construction of Fan and Tang [12] is based on the generic functional encryption. As far as we know, most works have approached the problem of constructing generic functional encryption by proposing a candidate under the existing of indistinguishability obfuscation [13]. Meanwhile, the construction of Boneh et al. [11] is also based on the existing indistinguishability obfuscation. However, indistinguishability obfuscation is not a particularly appealing assumption since the security of constructions relies on an exponential number of assumptions [14]. Recently, numerous attacks on multilinear maps [15] have reduced the community’s confidence in the security of existing construction of indistinguishability obfuscation. In this work, we provide a construction of secure cloud service scheme based on some more general assumptions, such as the existing one-way function and learning with error assumption.A secure cloud service scheme satisfying the verifiability can be constructed by a distributed functional signature scheme and a standard signature scheme. The standard signature scheme is used to authenticate the client. In order to achieve the verifiability, the service first generates some signing keyskP^i for the program P^=x|Px. When the client receives the returned results from clouds, it can get the evaluation y,σ by the reconstruction algorithm of distributed signature scheme. To prove that y=x|Px, the client verifies the signature σ of y, where the signature σ could only be obtained if y is in the range of P^.


## 1.2. Related Works

The concept of identity-based signature was proposed by Shamir in [16]. Bellare and Fuchsbauer [17] introduced policy-based signatures, where a signer can only sign messages satisfying some authority-specified policy. Backes et al. [18] introduced delegatable functional signatures which support the delegation of signing capabilities to another party with respect to a functionality. This new notion unifies several signature primitives, such as policy-based signature, functional signature, identity-based signature, and blind signature.Homomorphic signature was first proposed by Johnson et al. [19], which was initially designed to establish authentication in network coding. In addition, it can also be used to authenticate the stored data. In a homomorphic signature scheme, a holder which has the signature pairs m0,σ0 and m1,σ1 can construct a new signature σ on the value fm0,m1 for some function f without the signing key. Freeman [20] gave a linearly homomorphic signature scheme which allows authentication of linear functions on signed data. Catalano et al. [21] constructed a homomorphic signature scheme for polynomial functions.The concept of functional encryption comes from the work of Sahai and Waters [22]. The definition of simulation-based security was firstly proposed by Boneh et al. [23]. Garg et al. [13] firstly proposed a construction for functional encryption which supported all polynomial size circuits. Goldwasser et al. [24] constructed a succinct functional encryption scheme based on reusable garbled circuits and identity-based encryption for any polynomial-time function. Subsequently, Goldwasser et al. [25] introduced the notion of multi-input functional encryption, which supported the multi-input functions, and gave a construction based on indistinguishability obfuscation. In a multi-input functional encryption, the decryption key skf for a function f takes multiple ciphertexts as input and outputs a function evaluation. Besides, there are many other functional encryptions for inner-product functions [26–28].Boneh et al. [11] gave a construction of hosting service in the cloud. Their construction relied on indistinguishability obfuscation iO and restricted the number of colluded clients for the security. Fan and Tang [12] presented a new definition of distributed public key functional encryption. In their scheme, the decryption key for a function f is split into several sharing key skif. Given a ciphertext that encrypts a message m and a sharing key skif, it can evaluate a shared value yi which reveals nothing about the plaintext and the value of fm. One can recover the value of fm by adding all the shared values yi. With this approach, it can achieve function privacy which is not possible in the setting of regular public key functional encryption. Then, they considered the problem of hosting services in the untrusted cloud. Applying the function private distributed public key functional encryption to the setting of hosting service in multiple clouds, it can remove the restriction that the number of corrupted clients has to be bounded and known in the previous works.Boyle et al. [9] firstly proposed functional signatures, which allowed an authority to generate signing keys corresponding to various functions such that a user with a signing key skf can sign the image of function f on a message m. Okamoto and Takashima [29] firstly introduced the concept of a decentralised multiauthority functional signatures, which supports nonmonotone access structures combined with inner-product relations. Liang and Mitrokotsa [30] generalised the definition of decentralised multiauthority functional signature for more general policy functions. Datta et al. [31] introduced the concept of functional signcryption, which provided the functionalities of both functional encryption and functional signature. Pan et al. [32] introduced the notion of hierarchical functional signcryption which expanded the scope of functional signcryption in hierarchical access-control application. Li et al. [33] introduced the notion of private functional signatures, in which the signing key skf can be used to generate a signature σfx on the ciphertext cx, where cx is a ciphertext for message x.Blockchains originate from Bitcoin and are essentially a decentralised database that uses peer-to-peer network. It is a new application mode of computer technology such as distributed data storage, point-to-point transmission, and consensus mechanism. This makes blockchains potentially suitable for recording events, medical records, and other management activities. Although it can realize the function of software protection, it does not possess computing capabilities. In this work, our goal is to achieve software protection while ensuring software availability.Notation. In what follows, we will denote with λ∈N a security parameter. We say neglλ is negligible if neglλ<1/polyλ holds for all polynomials polyλ and all sufficiently large λ. Denote n as the set 1,2,…,n. We abbreviate probabilistic polynomial time as PPT. Denote S as the number of elements in the set S.


## 2. Preliminaries

In this section, we present definition for various cryptographic primitives that we will use in our construction of distributed functional signature. We assume familiarity with standard signature satisfying unforgeability against adaptively chosen message attack. Below, we first recall the notions of function secret sharing and functional signature.


### 2.1. Function Secret Sharing

We give the formal definition following the syntax of [10]. An n,n−function secret sharing scheme for a function family ℱ is a tuple of algorithms (FSS.Setup, FSS.ShareGen,FSS.Recon) described as follows:(i)
FSS.Setup1λ,n,ℱ⟶FSS.pp: on inputting the security parameter λ, the number of sharers n, and the description of function family ℱ, this algorithm outputs the public parameters FSS.pp.(ii)
FSS.ShareGenFSS.pp,f⟶fii=1n: on inputting the parameters FSS.pp and a function f∈ℱ, this algorithm outputs n shares fii=1n for function f.(iii)
FSS.ReconFSS.pp,fixi=1n⟶fix: on inputting n values fixi=1n which evaluated each function share fi on x, this algorithm reconstructs all the share values fixi=1n and outputs fx.Definition 1.
Correctness: ann,n−function secret sharing scheme for the function family ℱ is correct, if for any function f∈ℱ,x∈Df,FSS.pp⟵FSS.Setup1λ,n,ℱ, and fii=1n⟵FSS.ShareGenFSS.pp,f, we have(1)Prfx=FSS.ReconFSS.pp,fixi=1n≥1−neglλ.Definition 2.
Security: we say ann,n−function secret sharing scheme is secure if for any PPT adversary A, the advantage in the following game is negligible:(i)
The challenger generatesFSS.PP⟵FSS.Setup1λ,n,ℱ and sends FSS.pp to the adversary A.(ii)
The adversary outputsS,f0,f1⟵AFSS.pp,λ, where f0,f1∈ℱ, Df0=Df1, and S∈n,S=n−1.(iii)
The challenger randomly chooses a bitb⟵0,1, computes fibi=1n⟵FSS.ShareGenFSS.pp,fb, and sends fibi∈S to the adversary A.(iv)
A outputs a guess b′⟵AFSS.pp,fibi∈S. The advantage of A is defined as Adv=Prb′=b−1/2.


### 2.2. Functional Signatures

We describe the definition of a functional signature scheme, which is proposed by Boyle et al. in [9]. A functional signature scheme for a message space ℳ and a function family ℱ=f:Df⟶ℳ consists of four algorithms (FS.Setup, FS.KeyGen,FS.Sign,FS.Very):(i)
FS.Setup1λ⟶FS.mvk,FS.msk: on inputting the security parameter, the setup algorithm outputs the master verification key FS.mvk and the master signing key FS.msk.(ii)
FS.KeyGenFS.msk,f⟶skf: on inputting the master signing key FS.msk and a function f∈ℱ, the key generation algorithm outputs a constrained signing key skf, which just signs the message fm for any m∈Df.(iii)
FS.Signf,skf,m⟶fm,σ: on inputting the function f, constrained signing key skf, and a message m∈Df, the signing algorithm outputs a pair signature fm,σ.(iv)
FS.VeryFS.mvk,m∗,σ⟶0,1: on inputting the verification algorithm FS.mvk, a message m∗, and a signature σ, the verifiable algorithm outputs “1” or “0,” where 1 indicates that the signature is valid.Definition 3.
Correctness: for anyf∈ℱ and m∈Df, FS.msk,FS.mvk⟵FS.Setup1λ, skf⟵FS.KeyGenFS.msk,f, m∗,σ⟵FS.Signf,skf,m, it holds that(2)FS.VeryFS.mvk,m∗,σ=1.Definition 4.
Unforgeability: the scheme is unforgeable if the successful probability of any PPT algorithmA in the following game is negligible:(i)
The challenger runsFS.mvk,FS.msk⟵FS.Setup1λ and sends FS.mvk to the adversary A.(ii)
The adversaryA can query a key generation oracle and a signing oracle. The challenger initializes a dictionary indexed by tuples f,j∈ℱ×N, which contains the signing keys: skf⟵FS.KeyGenFS.msk,f.(iii)
Key generation oracle: on inputtingf,j, the challenger runs as follows:(1)
If there is an entry forf,j in the dictionary, then output the corresponding key skfj.(2)
Otherwise, sample a fresh keyskfj⟵FS.KeyGenFS.msk,f, update the dictionary f,j⟶skfj, and output skfj.(iv)
Signing oracle: on inputtingf,j,m, the challenger runs as follows:(1)
If there is an entry for the keyf,j in the dictionary, then output the signature σ⟵FS.Signf,skfj,m.(2)
Otherwise, sample a fresh keyskfj⟵FS.KeyGenFS.msk,f, update the dictionary f,j⟶skfj, and output the signature σ⟵FS.Signf,skfj,m.(v)
The adversary succeeds if it outputs a signaturem∗,σ such that(1)
FS.VeryFS.mvk,m∗,σ=1.(2)
There does not existm such that m∗=fm for any f which was sent as a query to the key generation oracle.(3)
There does not exist af,m such that f,m was queried to the signing oracle and m∗=fm.Lemma 1.
(see [9]). A functional signature scheme can be constructed based on any one-way function that supports signing keys for any function f which is computed by a polynomial-sized circuit. This scheme satisfies the property of unforgeability, but not function privacy.


### 2.3. General Aggregate Signatures

A general aggregate signature scheme [34] consists of four algorithms (AS.KeyGen, AS.Sign, AS.Agg, AS.Very). The key generation algorithm and signing algorithm are the same as a standard digital signature. In the aggregate algorithm, it produce a new signature by σ⟵Aggpk1,m1,σ1,pkn,mn,σn. Given a sequence of public key, message, and signature triples, anyone can yield an aggregate signature σ. Through Verypk1,m1,…,pkn,mn,σ, anyone can verify the correctness of generation aggregate signature.In addition to satisfying unforgeability under chosen message attack of the standard signature, it needs to satisfy aggregate unforgeability. The security requires that it is computationally infeasible to produce an aggregate forgery for a PPT adversary which can corrupt at mostn−1 players. The detailed description of security is given as follows.Definition 5.
Aggregate security: a general aggregate signature scheme is aggregate unforgeable, if it holds that(3)PrVerypk1,m1,…,pkn,mn,σ=1<neglλ,where the probability is over the experiment pk,sk⟵AS.KeyGen1λ, pk1,m1,…,pkn,mn,σ⟵AAS.Signsk,⋅pk.Lemma 2.
(see [34]). A general aggregate signature scheme can be constructed based on the difficulty of coCDH problem.


## 2.1. Function Secret Sharing

We give the formal definition following the syntax of [10]. An n,n−function secret sharing scheme for a function family ℱ is a tuple of algorithms (FSS.Setup, FSS.ShareGen,FSS.Recon) described as follows:(i)
FSS.Setup1λ,n,ℱ⟶FSS.pp: on inputting the security parameter λ, the number of sharers n, and the description of function family ℱ, this algorithm outputs the public parameters FSS.pp.(ii)
FSS.ShareGenFSS.pp,f⟶fii=1n: on inputting the parameters FSS.pp and a function f∈ℱ, this algorithm outputs n shares fii=1n for function f.(iii)
FSS.ReconFSS.pp,fixi=1n⟶fix: on inputting n values fixi=1n which evaluated each function share fi on x, this algorithm reconstructs all the share values fixi=1n and outputs fx.Definition 1.
Correctness: ann,n−function secret sharing scheme for the function family ℱ is correct, if for any function f∈ℱ,x∈Df,FSS.pp⟵FSS.Setup1λ,n,ℱ, and fii=1n⟵FSS.ShareGenFSS.pp,f, we have(1)Prfx=FSS.ReconFSS.pp,fixi=1n≥1−neglλ.Definition 2.
Security: we say ann,n−function secret sharing scheme is secure if for any PPT adversary A, the advantage in the following game is negligible:(i)
The challenger generatesFSS.PP⟵FSS.Setup1λ,n,ℱ and sends FSS.pp to the adversary A.(ii)
The adversary outputsS,f0,f1⟵AFSS.pp,λ, where f0,f1∈ℱ, Df0=Df1, and S∈n,S=n−1.(iii)
The challenger randomly chooses a bitb⟵0,1, computes fibi=1n⟵FSS.ShareGenFSS.pp,fb, and sends fibi∈S to the adversary A.(iv)
A outputs a guess b′⟵AFSS.pp,fibi∈S. The advantage of A is defined as Adv=Prb′=b−1/2.


## 2.2. Functional Signatures

We describe the definition of a functional signature scheme, which is proposed by Boyle et al. in [9]. A functional signature scheme for a message space ℳ and a function family ℱ=f:Df⟶ℳ consists of four algorithms (FS.Setup, FS.KeyGen,FS.Sign,FS.Very):(i)
FS.Setup1λ⟶FS.mvk,FS.msk: on inputting the security parameter, the setup algorithm outputs the master verification key FS.mvk and the master signing key FS.msk.(ii)
FS.KeyGenFS.msk,f⟶skf: on inputting the master signing key FS.msk and a function f∈ℱ, the key generation algorithm outputs a constrained signing key skf, which just signs the message fm for any m∈Df.(iii)
FS.Signf,skf,m⟶fm,σ: on inputting the function f, constrained signing key skf, and a message m∈Df, the signing algorithm outputs a pair signature fm,σ.(iv)
FS.VeryFS.mvk,m∗,σ⟶0,1: on inputting the verification algorithm FS.mvk, a message m∗, and a signature σ, the verifiable algorithm outputs “1” or “0,” where 1 indicates that the signature is valid.Definition 3.
Correctness: for anyf∈ℱ and m∈Df, FS.msk,FS.mvk⟵FS.Setup1λ, skf⟵FS.KeyGenFS.msk,f, m∗,σ⟵FS.Signf,skf,m, it holds that(2)FS.VeryFS.mvk,m∗,σ=1.Definition 4.
Unforgeability: the scheme is unforgeable if the successful probability of any PPT algorithmA in the following game is negligible:(i)
The challenger runsFS.mvk,FS.msk⟵FS.Setup1λ and sends FS.mvk to the adversary A.(ii)
The adversaryA can query a key generation oracle and a signing oracle. The challenger initializes a dictionary indexed by tuples f,j∈ℱ×N, which contains the signing keys: skf⟵FS.KeyGenFS.msk,f.(iii)
Key generation oracle: on inputtingf,j, the challenger runs as follows:(1)
If there is an entry forf,j in the dictionary, then output the corresponding key skfj.(2)
Otherwise, sample a fresh keyskfj⟵FS.KeyGenFS.msk,f, update the dictionary f,j⟶skfj, and output skfj.(iv)
Signing oracle: on inputtingf,j,m, the challenger runs as follows:(1)
If there is an entry for the keyf,j in the dictionary, then output the signature σ⟵FS.Signf,skfj,m.(2)
Otherwise, sample a fresh keyskfj⟵FS.KeyGenFS.msk,f, update the dictionary f,j⟶skfj, and output the signature σ⟵FS.Signf,skfj,m.(v)
The adversary succeeds if it outputs a signaturem∗,σ such that(1)
FS.VeryFS.mvk,m∗,σ=1.(2)
There does not existm such that m∗=fm for any f which was sent as a query to the key generation oracle.(3)
There does not exist af,m such that f,m was queried to the signing oracle and m∗=fm.Lemma 1.
(see [9]). A functional signature scheme can be constructed based on any one-way function that supports signing keys for any function f which is computed by a polynomial-sized circuit. This scheme satisfies the property of unforgeability, but not function privacy.


## 2.3. General Aggregate Signatures

A general aggregate signature scheme [34] consists of four algorithms (AS.KeyGen, AS.Sign, AS.Agg, AS.Very). The key generation algorithm and signing algorithm are the same as a standard digital signature. In the aggregate algorithm, it produce a new signature by σ⟵Aggpk1,m1,σ1,pkn,mn,σn. Given a sequence of public key, message, and signature triples, anyone can yield an aggregate signature σ. Through Verypk1,m1,…,pkn,mn,σ, anyone can verify the correctness of generation aggregate signature.In addition to satisfying unforgeability under chosen message attack of the standard signature, it needs to satisfy aggregate unforgeability. The security requires that it is computationally infeasible to produce an aggregate forgery for a PPT adversary which can corrupt at mostn−1 players. The detailed description of security is given as follows.Definition 5.
Aggregate security: a general aggregate signature scheme is aggregate unforgeable, if it holds that(3)PrVerypk1,m1,…,pkn,mn,σ=1<neglλ,where the probability is over the experiment pk,sk⟵AS.KeyGen1λ, pk1,m1,…,pkn,mn,σ⟵AAS.Signsk,⋅pk.Lemma 2.
(see [34]). A general aggregate signature scheme can be constructed based on the difficulty of coCDH problem.


## 3. Distributed Functional Signature with Function Privacy

In this section, we give a detailed study of distributed functional signature (DFS), n-out-of-n threshold functional signature. In an n,n−DFS scheme, during the key generation algorithm, the secret key corresponding to the function is split into n secret key shares skfi,fii=1n. Then, we can obtain a pair shared signature fim,σi by running partial signature algorithm on the secret key share skfi corresponding to the shared function fi and a message m. There is also a reconstruction algorithm that outputs a pair signature fm,σ on n shared signatures fim,σii=1n.


### 3.1. Syntax and Security Definition

We present a formal definition of a distributed functional signature, specifying the properties of unforgeability and function privacy. A distributed functional signature scheme for a message spaceℳ and function family ℱ=f:Df⟶ℳ consists of algorithms DFS.Setup,DFS.KeyGen,DFS.Sign,DFS.Con,DFS.Very.(i)
DFS.Setup1λ,n⟶msk,mvk: on inputting the secure parameter λ and threshold parameter n, the setup algorithm outputs the master verifiable key mvk and the secret key msk.(ii)
DFS.KeyGenmsk,f⟶skfi,fii=1n: on inputting the master secret key msk and a function f∈ℱ, the key generation algorithm outputs n secret key shares skfi,fii=1n for the function f.(iii)
DFS.Signfi,skfi,m⟶fim,σi: on inputting the signing key skfi for a function fi and an input m∈Df, the signature algorithm outputs a value fim and a signature σi.(iv)
DFS.Conmvk,fim,σii=1n⟶fm,σ: on inputting the master verifiable key mvk and signing pairs fim,σii=1n for the same function f, the reconstruction algorithm outputs a signing pair fm,σ.(v)
DFS.Verymvk,m∗,σ⟶0,1: on inputting the master verifiable key mvk, a message m∗, and a signature σ, the verifiable algorithm outputs “1” or “0,” where 1 implies that the signature is valid.Definition 6.
Correctness: ann,n−DFS scheme is correct if for any DFS.Setup1λ,n⟶msk,mvk, any f∈ℱ, and any m∈Df, skfi,fii=1n⟵DFS.KeyGenmsk,f, it holds that(4)Prfm=f′m≥1−neglλ,PrDFS.Verymvk,f′m,σ=1≥1−neglλ,where fim,σi⟵DFS.Signfi,skfi,m, DFS.Conmvk,fim,σii=1n=f′m,σ, and the probability is taken over the coins in algorithms DFS.Setup1λ,n and DFS.KeyGenmsk,f.Definition 7.
Unforgeability: the scheme is unforgeable if the successful probability of any PPT adversaryA in the following game is negligible:(i)
The challenger generatesDFS.Setup1λ,n⟶msk,mvk and sends mvk to A.(ii)
The adversary is allowed to query a key generation oracle and a signing oracle. The challenger initializes a dictionary indexed by tuplesf,j∈ℱ×N, which contains signing keys skfi,fii=1n⟵DFS.KeyGenmsk,f.(iii)
Key generation oracle: on inputtingf,j, the challenger runs as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then output the corresponding value skfji,fiji=1n.(2)
Else, run the key generation algorithmskfji,fiji=1n⟵DFS.KeyGenmsk,fj, add an entry f,j⟶fij,skfjii=1n to the dictionary, and output fij,skfjii=1n.(iv)
Signing oracle: on inputtingf,j,m, the challenger runs as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then run DFS.Signfij,skfji,m⟶fijm,σiji=1n and DFS.Conmvk,fijm,σiji=1n⟶fjm,σj and output fjm,σj.(2)
Else, run the key generation algorithmskfji,fiji=1n⟵DFS.KeyGenmsk,fj, add an entry f,j⟶skfjii=1n,fij to the dictionary, and generate a signature σj on fjm by the following steps: DFS.Signfij,skfji,m⟶fijm,σiji=1n, DFS.Conmvk,fijm,σiji=1n⟶fjm,σj.(v)
The adversaryA succeeds if it can produce m∗,σ∗ such that(1)
DFS.Verymvk,m∗,σ∗=1.(2)
There does not existm such that fjm=m∗ and fijm=m∗ for any fij which was contained in the dictionary.(3)
There does not exist af,m pair such that f,m was queried to the signing oracle and m∗=fm.Definition 8.
Ind-based function privacy: intuitively, we require that the successful advantage of any PPT adversaryA in the following game is negligible:(i)
Setup: the challenger generates a key pairmsk,mvk⟵DFS.Setup1λ,n and sends the verifiable key mvk to the adversary A.(ii)
Key query: proceeding adaptively, the adversaryA submits fj∈ℱ to the challenger. The challenger computes skfji,fiji=1n⟵DFS.KeyGenmsk,fj and sends skfji,fiji=1n to the adversary A.(iii)
Challenge phase:A sends the challenge function pair f0,f1,S which is not queried in the key query phase. The challenger computes skfbi,fibi=1n⟵DFS.KeyGenmsk,fb and sends skfbi,fibi=1n to the adversary A, where b⟵0,1 and S is chosen randomly from n such that S=n−1.(iv)
Proceeding adaptively, the adversary can query the key generation oracle and evaluation oracle.(1)
Key query:A sends a function fj∈ℱ with a restriction that fj≠f0 and fj≠f1. The challenger answers the same as previous key query.(2)
Evaluation query:A sends an input xk with a restriction that f0xk=f1xk. For i∈n/S, challenger returns fixk,σi⟵DFS.Signfib,skfbi,xk.(v)
Guess: finally, the adversaryA outputs a bit b′. The successful advantage of A is defined as Adv=Prb′=b−1/2.


## 3.1. Syntax and Security Definition

We present a formal definition of a distributed functional signature, specifying the properties of unforgeability and function privacy. A distributed functional signature scheme for a message spaceℳ and function family ℱ=f:Df⟶ℳ consists of algorithms DFS.Setup,DFS.KeyGen,DFS.Sign,DFS.Con,DFS.Very.(i)
DFS.Setup1λ,n⟶msk,mvk: on inputting the secure parameter λ and threshold parameter n, the setup algorithm outputs the master verifiable key mvk and the secret key msk.(ii)
DFS.KeyGenmsk,f⟶skfi,fii=1n: on inputting the master secret key msk and a function f∈ℱ, the key generation algorithm outputs n secret key shares skfi,fii=1n for the function f.(iii)
DFS.Signfi,skfi,m⟶fim,σi: on inputting the signing key skfi for a function fi and an input m∈Df, the signature algorithm outputs a value fim and a signature σi.(iv)
DFS.Conmvk,fim,σii=1n⟶fm,σ: on inputting the master verifiable key mvk and signing pairs fim,σii=1n for the same function f, the reconstruction algorithm outputs a signing pair fm,σ.(v)
DFS.Verymvk,m∗,σ⟶0,1: on inputting the master verifiable key mvk, a message m∗, and a signature σ, the verifiable algorithm outputs “1” or “0,” where 1 implies that the signature is valid.Definition 6.
Correctness: ann,n−DFS scheme is correct if for any DFS.Setup1λ,n⟶msk,mvk, any f∈ℱ, and any m∈Df, skfi,fii=1n⟵DFS.KeyGenmsk,f, it holds that(4)Prfm=f′m≥1−neglλ,PrDFS.Verymvk,f′m,σ=1≥1−neglλ,where fim,σi⟵DFS.Signfi,skfi,m, DFS.Conmvk,fim,σii=1n=f′m,σ, and the probability is taken over the coins in algorithms DFS.Setup1λ,n and DFS.KeyGenmsk,f.Definition 7.
Unforgeability: the scheme is unforgeable if the successful probability of any PPT adversaryA in the following game is negligible:(i)
The challenger generatesDFS.Setup1λ,n⟶msk,mvk and sends mvk to A.(ii)
The adversary is allowed to query a key generation oracle and a signing oracle. The challenger initializes a dictionary indexed by tuplesf,j∈ℱ×N, which contains signing keys skfi,fii=1n⟵DFS.KeyGenmsk,f.(iii)
Key generation oracle: on inputtingf,j, the challenger runs as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then output the corresponding value skfji,fiji=1n.(2)
Else, run the key generation algorithmskfji,fiji=1n⟵DFS.KeyGenmsk,fj, add an entry f,j⟶fij,skfjii=1n to the dictionary, and output fij,skfjii=1n.(iv)
Signing oracle: on inputtingf,j,m, the challenger runs as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then run DFS.Signfij,skfji,m⟶fijm,σiji=1n and DFS.Conmvk,fijm,σiji=1n⟶fjm,σj and output fjm,σj.(2)
Else, run the key generation algorithmskfji,fiji=1n⟵DFS.KeyGenmsk,fj, add an entry f,j⟶skfjii=1n,fij to the dictionary, and generate a signature σj on fjm by the following steps: DFS.Signfij,skfji,m⟶fijm,σiji=1n, DFS.Conmvk,fijm,σiji=1n⟶fjm,σj.(v)
The adversaryA succeeds if it can produce m∗,σ∗ such that(1)
DFS.Verymvk,m∗,σ∗=1.(2)
There does not existm such that fjm=m∗ and fijm=m∗ for any fij which was contained in the dictionary.(3)
There does not exist af,m pair such that f,m was queried to the signing oracle and m∗=fm.Definition 8.
Ind-based function privacy: intuitively, we require that the successful advantage of any PPT adversaryA in the following game is negligible:(i)
Setup: the challenger generates a key pairmsk,mvk⟵DFS.Setup1λ,n and sends the verifiable key mvk to the adversary A.(ii)
Key query: proceeding adaptively, the adversaryA submits fj∈ℱ to the challenger. The challenger computes skfji,fiji=1n⟵DFS.KeyGenmsk,fj and sends skfji,fiji=1n to the adversary A.(iii)
Challenge phase:A sends the challenge function pair f0,f1,S which is not queried in the key query phase. The challenger computes skfbi,fibi=1n⟵DFS.KeyGenmsk,fb and sends skfbi,fibi=1n to the adversary A, where b⟵0,1 and S is chosen randomly from n such that S=n−1.(iv)
Proceeding adaptively, the adversary can query the key generation oracle and evaluation oracle.(1)
Key query:A sends a function fj∈ℱ with a restriction that fj≠f0 and fj≠f1. The challenger answers the same as previous key query.(2)
Evaluation query:A sends an input xk with a restriction that f0xk=f1xk. For i∈n/S, challenger returns fixk,σi⟵DFS.Signfib,skfbi,xk.(v)
Guess: finally, the adversaryA outputs a bit b′. The successful advantage of A is defined as Adv=Prb′=b−1/2.


## 4. The Construction of DFS

We are now ready to describe a construction of distributed functional signature scheme. Informally, our scheme works as follows. In the setup algorithm, the master verifiable key contains a public parameter of function secret sharing scheme and a verifiable key of functional signature. It sets the master signing key of functional signature scheme to the master secret key. The key generation algorithm consists of sharing function algorithm and key generation algorithm of functional signature, which generatesn constrained signature keys skfi corresponding to the shadow function fi. In the signing algorithm, it computes signing pairs fim,σi on inputting a message m. When enough signatures had been collected, anyone can reconstruct the function value and verify its correctness by the verifiable algorithm. We give a detailed description below. Let FSS=FSS.Setup,FSS.ShareGen,FSS.Recon be a function secret sharing scheme for function ensemble ℱ and FS.Setup,FS.KeyGen,FS.Sign,FS.Very be a functional signature scheme. The construction of DFS=DFS.Setup,DFS.KeyGen,DFS.Sign,DFS.Con,DFS.Very is given as follows.(i)
DFS.Setup1λ,n⟶msk,mvk:(1)
Run the setup algorithm ofFS and generate a key pair FS.mvk,FS.msk⟵FS.Setup1λ.(2)
Run the setup algorithm ofFSS and generate a public parameter FSS.pp⟵FS.Setup1λ,n,ℱ.(3)
Set the master verifiable key to bemvk=FS.mvk,FSS.pp and the master secret key to be msk=FS.msk.(ii)
DFS.KeyGenmsk,f⟶skfi,fii=1n:(1)
Run the function sharing algorithm ofFSS and get n sharing functions fii=1n⟵FSS.ShareGenFSS.pp,f.(2)
Run the key generation algorithm ofFS and generate n constrained signature keys skfi⟵FS.KeyGenFS.msk,fi for i=1,…,n.(3)
Output the signature pairsskfi,fii=1n.(iii)
DFS.Signfi,skfi,m⟶fim,σi: given the i−th secret key fi,skfi, it computes and outputs fim,σi=FS.Signfi,skfi,m.(iv)
DFS.Conmvk,fim,σii=1n⟶fm,σ: it computes fm=FSS.ReconFSS.pp,fimi=1n and σ=fim,σii=1n.(v)
DFS.Verymvk,m∗,σ⟶0,1:(1)
Ifσ=fim,σii=1n, then it runs FS.VeryFS.mvk,fim,σi for i=1,…,n. If all of the verifiable algorithms output “1” and m∗=FSS.ReconFSS.ppfimi=1n, it outputs “1”; else, it outputs “0.”(2)
If not, it runsFS.VeryFS.mvk,m∗,σ and outputs the corresponding result.Remark 1.
In our verifiable algorithm, it can verify two forms of signature. One is generated by the reconstruction algorithm. The another is generated by the signing algorithm.
Correctness. The correctness of our DFS construction follows from the correctness of FS and FSS. Firstly, the outputs fim of signature algorithm satisfy fm=FSS.ReconFSS.pp,fimi=1n by the reconstruction algorithm of FSS. Secondly, the verifiable algorithm will output “1” if the signature is generated correctly by the FS scheme.Theorem 1.
LetFS be an unforgeability functional signature scheme; then, our construction of DFS described above is secure (c.f. Definition 7).Proof.
We now prove that if there exists a PPT adversaryA that can break the unforgeable security of DFS with non-negligible probability, then another adversary ℬ can be constructed to break the unforgeable security of FS with the same probability.
LetC be the challenger for the FS scheme. We construct the adversary ℬ by A as follows:(i)
ℬ first honestly runs the secure experiment of FS and gets FS.mvk of functional signature. Then, it generates FSS.pp⟵FSS.Setup1λ,n. The adversary ℬ returns mvk=FS.mvk,FSS.pp to A.(ii)
ℬ initializes a dictionary indexed by tuples f,j∈ℱ×N, which contains signing keys skfji,fiji=1n.(iii)
Key generation oracle: on inputtingf,j, A operates as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then output the corresponding pair skfji,fiji=1n.(2)
Else, computefiji=1n⟵FSS.ShareGenFSS.pp,fj. For i=1,…,n, ℬ queries the key generation oracle of FS and gets n secret keys skfjii=1n. Add an entry f,j⟶skfji,fiji=1n to the dictionary and output skfji,fiji=1n.(iv)
Signing oracle: on inputtingf,j,m, A operates as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then run DFS.Signfij,skfji,m⟶fijm,σiji=1n and DFS.Conmvk,fijm,σiji=1n⟶fjm,σj and output fjm,σj.(2)
Else, computefiji=1n⟵FSS.ShareGenpp,fj. For i=1,…,n, ℬ queries the signing oracle fij,mi=1n of FS and gets n signature pairs fijm,σii=1n. Then, it computes DFS.Conmvk,fijm,σiji=1n⟶fjm,σj and returns fjm,σj to A.(v)
The adversaryA produces a forgeable signature m∗,σ∗. Then, B computes as follows:(1)
Ifσ∗ is the form of fijm,σii=1n, then ℬ returns f1jm,σ1j to the challenger.(2)
Else,ℬ returns m∗,σ∗ to the challenger.We observe thatℬ perfectly simulates the unforgeable experiment of DFS. If A successfully outputs a forgeable signature m∗,σ∗, it must satisfy the following:(1)
DFS.Verymvk,m∗,σ∗=1.(2)
There does not existm such that fjm=m∗ and fijm=m∗ for any fij which was contained in the dictionary.(3)
There does not exist af,m such that f,m was a query to the signing oracle and m∗=fm.
If the forgeable signaturem∗,σ∗ is the first form, then FS.VeryFS.mvk,fim,σi=1 for any i=1,…,n. Because fi is not contained in the dictionary and m∗,σ∗ is not queried to the signature oracle, f1jm,σ1j is a legally forgeable signature for the functional signature scheme. If the forgeable signature m∗,σ∗ is the second form, then m∗,σ∗ is a distributive signature and FS.VeryFS.mvk,m∗,σ∗=1. There does not exist m such that fim=m∗ which is contained in the dictionary; it is also a legally forgeable signature. Therefore, if A can break the unforgeability security of DFS with non-negligible probability, then we can construct another adversary ℬ which breaks the unforgeability security of FS with the same probability.Theorem 2.
AssumeFSS.Con is an invertible algorithm. FSS.Con is an invertible algorithm if for any n−1 inputs fixi=1n−1 and an output fx, it can compute the n−th input fnx, where the functions fixi=1n−1 share function of fx. For example, Fan and Tang [12] gave a function secret sharing in which the reconstruction algorithm is fx=∑i=1nfix, and fnx=fx−∑i=1n−1fix. Let FSS be a secure function secret sharing scheme (c.f. Definition 2); then, our construction of DFS described above satisfies function privacy (c.f. Definition 8).Proof.
We now prove that if there exists a PPT adversaryA that can break the function privacy of DFS with non-negligible probability, then another adversary ℬ can be constructed to break the security of FSS with the same probability.
LetC be the challenger for the FSS scheme. We construct the adversary ℬ by A as follows:(i)
ℬ first honestly runs the secure experiment of FSS and gets FSS.pp of function secret sharing scheme. Then, it generates FS.mvk,FS.msk⟵FS.Setup1λ. The adversary ℬ returns mvk=FSS.pp,FS.mvk to A.(ii)
ℬ initializes a dictionary indexed by tuples f,j∈ℱ×N, which contains signing keys skfji,fiji=1n.(iii)
Key query: on inputtingf,j, ℬ operates as follows:(1)
If there exists an entry for the keyf,j in the dictionary, then output skfji,fiji=1n.(2)
Else, computefiji=1n⟵FSS.ShareGenFSS.pp,fj. For i=1,…,n, ℬ computes skfji,fij⟵FS.KeyGenFS.msk,fij. Add an entry f,j⟶skfji,fiji=1n to the dictionary and output skfji,fiji=1n.(iv)
A sends the challenge function pair f0,f1,S to the adversary ℬ, where both f0 and f1 were not queried in the previous phase, and Df0=Df1,S=n−1. Then, ℬ queries the challenger of FS on f0,f1,S and gets fibi∈S. For i∈S, ℬ computes skfbi,fib⟵FS.KeyGenFS.msk,fib and returns skfbi,fibi∈S to the adversary A.(v)
Proceeding adaptively,A can query the key generation oracle and evaluation oracle.(1)
Key query:A sends a function fj∈ℱ with a restriction that fj≠f0 and fj≠f1. ℬ answers the same as previous key query.(2)
Evaluation query:A sends an input xk with a restriction that f0xk=f1xk. For i∈n/S, ℬ first computes fibxk,σii∈S and f0xk. Then, ℬ computes fi∈n/Sxk by the invertible property of FSS.Con and a corresponding signature σi∈n/S by the master secret key FS.msk of functional signature. For a functional signature scheme, it has a master signing key FS.msk, which can be used to sign any message. At the same time, it also has a constrained key skf for the function f, which only signs the message in the range of f. ℬ returns fi∈n/Sxk,σi∈n/S to A.(vi)
At last, the adversaryℬ outputs the guess b′ of the adversary A.
Although the generation way of the signatureσi∈n/S is changed, it does not influence the view of A because this signature can be verified by the verifiable algorithm of FS. Therefore, ℬ perfectly simulates function private experiment. If A can distinguish the function f0 and f1 with non-negligible advantage, then ℬ can break the security of FSS with the same advantage.
In the above construction, the size of combined signature depends on the threshold, which will reduce the verification efficiency. In order to improve the efficiency, it can use aggregate signature to compress the final signature size based on the construction of functional signature proposed by Boyle et al. [9]. In their key generation algorithm, it generates the secret key skf for the function f by a standard signature scheme. Therefore, we can change the standard signature into an aggregate signature. The generated signatures σ1,…,σn of functional signature scheme can be aggregated into a single signature σ. This change does not affect the security of the construction because the security of Boyle’s construction is reduced to the unforgeability of a standard signature. On the one hand, it does not use the aggregate property. On inputting an aggregate signature, the verifiable algorithm of functional signature will output one bit “0.” On the other hand, if the adversary can produce a forgeable signature for functional signature scheme by the aggregate signature, then it can be used to break the aggregate security. Based on the first construction, we modify the reconstruction algorithm and verifiable algorithm. The specific description is as follows.(i)
DFS.Setup1λ,n⟶msk,mvk: it runs the same as before.(ii)
DFS.KeyGenmsk,f⟶skfi,fii=1n: it runs the same as before.(iii)
DFS.Signfi,skfi,m⟶fim,σi: it runs the same as before.(iv)
DFS.Conmvk,fim,σii=1n⟶fm,σ: it computes fm=FSS.ReconFSS.ppfimi=1n and σ′=AS.Aggfim,σii=1n and returns fm,σ=σ′,fimi=1n.(v)
DFS.Verymvk,m∗,σ⟶0,1:(1)
Ifσ=σ′,fimi=1n, then it runs AS.Veryσ′,fimi=1n. If the verifiable algorithms output '1′ and m∗=FSS.ReconFSS.pp,fimi=1n, it outputs “1”; otherwise, it outputs “0.”(2)
If not, it runsFS.VeryFS.mvk,m∗,σ and outputs the corresponding result.
The secure proofs of the modified construction are similar to the Theorems1 and 2. In the proof of unforgeability, there are two forms of signature. The first one is m∗,σ=σ′,fim∗i=1n which satisfies AS.Veryσ′,fim∗i=1n=1. Because the reconstruction algorithm is run honestly, there exists an index i∈1,…,n such that FS.VeryFS.mvk,fim∗,σi∗=1. Meanwhile, it satisfies that fi is not contained in the dictionary, and m∗,σ∗ is not queried to the signature oracle. So, fim∗,σi∗ is a legally forgeable signature for the functional signature scheme. The second form of signature is the same as Theorem 1, which can also be reduced to the security of functional signature. The proof of function privacy is exactly the same as Theorem 2.


## 5. Hosting Services Securely in Multiple Untrusted Clouds

We consider the setting of hosting service in untrusted clouds which was first presented by Boneh [11]. In this model, it has three parties: service provider, who owns a program P, cloud server, who provides the computation capability, and arbitrary many clients. The service provider wants to host the program P on a cloud server and authenticate the clients who pay for the service provided by program P. Only the authenticated clients can access the program hosted on the cloud server and compute output on inputs of their choice. Meanwhile, the program P may contain proprietary information, and it needs to protect its privacy. Moreover, the scheme should satisfy some properties [11]:(i)
Weak client: the total cost of the client should only depend on the size of input and security parameter and should be independent of the running time of programP.(ii)
Delegation: the service provider only needs to run one-time setup of the whole system and authentication clients. The total cost should be bounded by a fixed polynomial in the program size in the setup phase and should only depend on the security parameter in the authentication phase.(iii)
Polynomial slowdown: the running time of the cloud is bounded by a fixed polynomial in the running time of the programP.In our verifiable distributed secure cloud service scheme, the service provider generates a set of encoded program shares for programP and then hosts each encoded program share on one cloud server. Any authenticated client can access the encoded program shares hosted in multiple cloud servers and compute output on inputs of his choice. Meanwhile, we require the client to verify the correctness of returned result from the cloud servers.


### 5.1. Syntax and Security Definitions

We recall the notion of secure cloud service scheme proposed by Boneh et al. [11] and make some changes based on [12]. The verifiable distributed secure cloud service scheme consists of five algorithms VDS=VDS.Prog,VDS.Auth,VDS.Inp,VDS.Eval,VDS.Very which is described as follows:(i)
VDS.Prog1λ,n,P⟶Pii=1n,sk: on inputting the security parameter λ, the threshold parameter n, and a program P, the program generation algorithm outputs encoded programs Pii=1n and a secret key sk which is used in the authentication algorithm.(ii)
VDS.Authsk,id⟶tokenid: on inputting an identity id of a client and the secret key sk, the authentication algorithm outputs a token tokenid for the client.(iii)
VDS.Inptokenid,x⟶x^,α: on inputting the token tokenid and an input x, this algorithm outputs an encoded input x^ and α which is used by client to verify the evaluated value.(iv)
VDS.EvalPi,x^⟶y^i: on inputting the encoded program Pi and input x^, the evaluation algorithm outputs a result y^i=Pix^.(v)
VDS.Veryα,y^i=1n⟶Pxor⊥: on inputting the verifiable information α and the evaluated value y^i, the verifiable algorithm outputs the value Pm or ⊥, which implies that the client rejects the evaluated result.The procedure runs as follows: the server provider first runs the algorithmVDS.Prog1λ,n,P and obtains the distributed encoded program Pii=1n and a secret key sk. Then, it sends Pi to the ith cloud server. If a client wants to access the program hosted on the cloud server, the service provider would authenticate the client by the secret key sk. An authenticated client with identity id can encode its inputs by the algorithm VDS.Inptokenid,x and send x^ to each cloud servers, respectively. Every cloud server will evaluate the sharing program Pi on encoded input x^ and return the evaluation Pix^. Finally, the client can reconstruct the value Px by the algorithm VDS.Veryα,y^i=1n and verify its correctness. In Figure 1, we give the algorithm flowchart for the verifiable distributed secure cloud service scheme.Figure 1
Algorithm flowchart forVDS.Two cases for security definition are considered in [11], untrusted cloud security and untrusted client security. We consider the case of untrusted cloud security into two subcases, program privacy and verifiability.Definition 9.
(untrusted cloud security: program privacy) (see [12], Definition 4.1). A VDS scheme is program privacy in untrusted cloud security if the successful advantage of any PPT adversary A in the following experiment is negligible:(i)
The adversaryA sends challenge program P0,P1,S to challenger such that S⊂n, and S=n−1. The challenger samples a random bit b⟵0,1, computes the encoded program Pibi=1n,sk⟵VDS.Prog1λ,n,Pb, and sends Pibi∈S to adversary A.(ii)
Proceeding adaptively, the adversaryA can make the authentication query and input query:(1)
Authentication query: the challenger initializes a dictionary indexed byid,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj⟵VDS.Authsk,id and updates the dictionary id,j⟶tokenidj.(2)
Input query:A sends id,j,x to the challenger. If there exists id,j⟶tokenidj in the dictionary, challenger returns x^,α⟵VDS.Inptokenidj,x. If not, challenger computes tokenidj⟵VDS.Authsk,idj, returns x^,α⟵VDS.Inptokenidj,x, and updates the dictionary id,j⟶tokenidj.(iii)
Finally, the adversaryA outputs his guess b′ for the bit b. The adversary A succeeds if b′=b. The advantage of A’s success is defined as Prb′=b−1/2.Definition 10.
(untrusted cloud security: verifiability). AVDS scheme is verifiable in untrusted cloud security if the successful probability of any PPT adversary A in the following experiment is negligible:(i)
The adversaryA sends challenge program P to challenger. The challenger samples the encoded program Pii=1n,sk⟵VDS.Prog1λ,n,P and sends Pii=1n to adversary A.(ii)
Proceeding adaptively, the adversaryA can make the authentication query. The challenger initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj⟵VDS.Authsk,id and updates the dictionary id,j⟶tokenidj.(iii)
Finally,A outputs x,α,y^i=1n. A succeeds if Px≠VDS.Veryα,y^i=1n.
For untrusted client security, we require that a collection of corrupt clients with the help of a subset of corrupt servers does not distinguish which program is encoded.Definition 11.
(untrusted client security) (see [12], Definition 4.4). The VDS scheme is untrusted client security if the successfully advantage of any PPT adversary A in the following experiment is negligible:(i)
The adversaryA sends challenge program P0,P1,S to challenger such that S⊂n,S=n−1. The challenger samples a random bit b⟵0,1, computes the encoded program Pibi=1n,sk⟵VDS.Prog1λ,n,Pb, and sends Pibi∈S to adversary A.(ii)
Proceeding adaptively, the adversaryA can make the authentication query and evaluation query:(1)
Authentication query: the challenger initializes a dictionary indexed byid,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj⟵VDS.Authsk,id and updates the dictionary id,j⟶tokenidj.(2)
Evaluation query:A sends an encoding x^k for the input xk to the challenger such that P0xk=P1xk. For i∈n/S, challenger returns y^i,k=Pibx^k.(iii)
Finally, the adversaryA outputs his guess b′ for the bit b. The adversary A succeeds if b′=b. The successful advantage of A is defined as Prb′=b−1/2.


### 5.2. Our VDS Construction

LetVDS=VDS.Prog,VDS.Auth,VDS.Inp,VDS.Eval,VDS.Very be a distributed functional signature scheme and Sig=Sig.Setup,Sig.Sign,Sig.Very be an existential unforgeable signature scheme. Now, we describe our construction as follows:(i)
VDS.Prog1λ,n,P⟶Pii=1n,sk:(1)
Runmsk,mvk⟵DFS.Setup1λ,n and Sig.sk,Sig.vk⟵Sig.Setup1λ.(2)
Construct a new programP^, which is given in Figure 2.(3)
ComputeskP^i,P^ii=1n⟵DFS.KeyGenmsk,P^.(4)
SetPi=skP^i,P^i and sk=Sig.sk,mvk.(ii)
VDS.Authsk,id⟶tokenid: parse sk=Sig.sk,mvk, compute the signature σid=Sig.SignSig.sk,id, and output tokenid=mvk,σid,id.(iii)
VDS.Inptokenid,x⟶x^,α: parse tokenid=mvk,σid,id and set x^=x,σid,id and α=x,mvk.(iv)
VDS.EvalPi,x^⟶y^i: parse Pi=skP^i,P^i and compute y^i=P^ix,σi⟵DFS.SignP^i,skP^i,x^.(v)
VDS.Veryα,y^ii=1n⟶Pxor⊥: parse α=x,mvk. Compute DFS.Conmvk,P^ix,σii=1n=P^x,σ. Parse P^x=x′|P′x. If DFS.Verymvk,P^x,σ=1 and x′=x, output P′x. Else, it rejects the returned results.Figure 2
ProgramP^.Correctness. The correctness of our VDS construction follows from the correctness of underlying distributed functional signature scheme DFS and the signature scheme Sig. We can observe that it outputs ⊥ for an invalid signature in the encoded program P^i. Otherwise, it outputs y^i=P^ix,σi. By the correctness of DFS, the output of VDS.Veryα,y^i=1n is Px.Efficiency. We do not consider the time cost of algorithm VDS.Prog because the cost of encoding the program can be amortized over many input computations. For each invocation of VDS.Auth, the service provider generates a signature for the client id. Therefore, it is efficient for the service provider. The work of the client in handling his inputs only depends polynomially on the size of inputs and a security parameter. For the verifiable algorithm, the client needs to reconstruct the function evaluation and verify a signature, which is independent of the complexity of the program. In the phase of reconstructing the function evaluation, the client just needs to compute a summation operation by using the function secret sharing proposed by Fan and Tang [12].Security. We show that our DFS construction satisfies untrusted cloud security (program privacy and verifiability) and untrusted client security defined as above.Theorem 3.
LetDFS be a distributed functional signature scheme against the security of function privacy (c.f. Definition 8); then, our construction of VDS described above has program privacy in untrusted cloud security (c.f. Definition 9).Proof.
We prove that if there exists a PPT adversaryA that can break the program privacy of VDS with non-negligible probability, then another adversary ℬ can be constructed to break the function privacy of DFS with the same probability.
LetC be the challenger for the DFS scheme. We construct the adversary ℬ by A as follows:(i)
The adversaryA sends challenge program P0,P1,S to ℬ such that S⊂n,S=n−1. A samples a signing key Sig.vk,Sig.sk⟵Sig.Setup1λ, constructs two new programs P^0,P^1 as defined in Figure 2, and sends P^0,P^1,S to the challenger of DFS. The challenger returns skP^bi,P^ibi∈S,mvk. ℬ returns skP^bi,P^ibi∈S to A and sets sk=Sig.sk,mvk.(ii)
Proceeding adaptively, the adversaryA can make the authentication query and input query:(1)
Authentication query:ℬ initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, ℬ returns tokenidj to A if there exists a id,j in the dictionary. If not, ℬ computes σidj⟵Sig.SignSig.sk,idj, then returns tokenidj=mvk,σidj,id, and updates the dictionary id,j⟶tokenidj.(2)
Input query:ℬ sends id,j,x to the challenger. If there exists id,j⟶tokenidj in the dictionary, A returns x^=x,σid,id,α=x,mvk to adversary. Else, A computes tokenidj⟵VDS.Authsk,id, returns x^,α⟵VDS.Inptokenidj,x, and updates the dictionary id,j⟶tokenidj.(iii)
Finally, the adversaryA outputs the guess b′ of ℬ.
We observe thatℬ perfectly simulates program private experiment of VDS. Therefore, if ℬ could distinguish the program P0 and P1 with non-negligible advantage in untrusted cloud security, then A can break the security of DFS with the same advantage.Theorem 4.
LetDFS be a distributed functional signature scheme against the security of unforgeability (c.f. Definition 7); then, our construction of VDS described above is verifiable in untrusted cloud security (c.f. Definition 10).Proof.
We prove that if there exists a PPT adversaryA that can break verifiability of VDS with non-negligible probability, then another adversary ℬ can be constructed to break unforgeability of DFS with the same probability.
LetC be the challenger for the DFS scheme. We construct the adversary ℬ by A as follows:(i)
ℬ honestly runs the unforgeable experiment of DFS and gets mvk of distributed functional signature. Then, ℬ samples a signing pair Sig.sk,Sig.vk⟵Sig.Sign1λ.(ii)
A sends challenge program P to ℬ. ℬ defines a new function P^ which is described in Figure 2 and sends P^ to the challenger C of DFS. The challenger returns P^i,skP^ii=1n, sets Pi=P^i,skP^i, and sends Pii=1n to adversary A.(iii)
Proceeding adaptively,A can make the authentication query. ℬ initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj=σidj,idj,mvk and updates the dictionary id,j⟶tokenidj, where σid=Sig.SignSig.sk,idj.(iv)
Finally,A outputs x,α,y^i=P^ix,σii=1n. Then, ℬ computes P^x,σ⟵VDS.Veryα,y^i=1n and outputs the forgeable signature x′|P′x,σ, where P^x=x′|P′x.
Assume thatA succeeded in the experiment of verifiability; then, it must satisfy that DFS.Verymvk,P^x,σ=1, x′=x, and P′x≠Px. For i=1,…,n, DFS.Verymvk,P^ix,σi=1; then, x|Pix must be contained in the range of program P^i. Because the adversary A can just sign the message belonging to the range of encoded programs P^i, the evaluation x|Pix must be computed correctly. In addition, x|P′x is not contained in the range of P^ because of P′x≠Px. x|P′x,σ is validly forgeable signature for the DFS scheme. So, if there exists an adversary that breaks the verifiability of VDS with non-negligible probability, then there exists another adversary that breaks the unforgeability of DFS with the same probability.Theorem 5.
LetDFS be a distributed functional signature scheme against the security of function privacy (c.f. Definition 8) and Sig be an unforgeable signature scheme; then, our construction of VDS described above is secure in untrusted client security (c.f. Definition 11).Proof.
We prove that if there exists a PPT adversaryA that can break security in untrusted client security with non-negligible probability, then another adversary ℬ can be constructed to break function privacy of DFS with the same probability.
LetC be the challenger for the DFS scheme. We construct the adversary ℬ by A as follows:(i)
ℬ runs the function private experiment of DFS and gets a master verifiable key mvk of DFS. Then, ℬ samples a signing pair Sig.sk,Sig.vk⟵Sig.Sign1λ.(ii)
The adversaryA sends challenge program P0,P1,S to ℬ such that S⊂n,S=n−1. ℬ defines two new functions P^0 and P^1 which are described in Figure 2 and sends P^0,P^1,S to the challenger C of DFS. The challenger returns P^ib,skP^bii∈S, sets Pi=P^ib,skP^bi, and sends Pii∈S to adversary A.(iii)
Proceeding adaptively, the adversaryA can make the authentication query and evaluation query:(1)
Authentication query:ℬ initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj=σidj,idj,mvk and updates the dictionary id,j⟶tokenidj, where σid=Sig.SignSig.sk,idj.(2)
Evaluation query:A sends an encoding x^k for the input xk to ℬ. ℬ first checks whether P0xk is equal to P1xk. If not, ℬ stops the experiment. Otherwise, ℬ queries the evaluation oracle of DFS and returns the output to A.(iv)
Finally, the adversaryℬ outputs the result b′ of the adversary A.
We observe thatℬ perfectly simulates the secure experiment in untrusted client model. Therefore, if A can distinguish the program P0 and P1 with non-negligible advantage, then ℬ can break the function private security of DFS with the same advantage.


## 5.1. Syntax and Security Definitions

We recall the notion of secure cloud service scheme proposed by Boneh et al. [11] and make some changes based on [12]. The verifiable distributed secure cloud service scheme consists of five algorithms VDS=VDS.Prog,VDS.Auth,VDS.Inp,VDS.Eval,VDS.Very which is described as follows:(i)
VDS.Prog1λ,n,P⟶Pii=1n,sk: on inputting the security parameter λ, the threshold parameter n, and a program P, the program generation algorithm outputs encoded programs Pii=1n and a secret key sk which is used in the authentication algorithm.(ii)
VDS.Authsk,id⟶tokenid: on inputting an identity id of a client and the secret key sk, the authentication algorithm outputs a token tokenid for the client.(iii)
VDS.Inptokenid,x⟶x^,α: on inputting the token tokenid and an input x, this algorithm outputs an encoded input x^ and α which is used by client to verify the evaluated value.(iv)
VDS.EvalPi,x^⟶y^i: on inputting the encoded program Pi and input x^, the evaluation algorithm outputs a result y^i=Pix^.(v)
VDS.Veryα,y^i=1n⟶Pxor⊥: on inputting the verifiable information α and the evaluated value y^i, the verifiable algorithm outputs the value Pm or ⊥, which implies that the client rejects the evaluated result.The procedure runs as follows: the server provider first runs the algorithmVDS.Prog1λ,n,P and obtains the distributed encoded program Pii=1n and a secret key sk. Then, it sends Pi to the ith cloud server. If a client wants to access the program hosted on the cloud server, the service provider would authenticate the client by the secret key sk. An authenticated client with identity id can encode its inputs by the algorithm VDS.Inptokenid,x and send x^ to each cloud servers, respectively. Every cloud server will evaluate the sharing program Pi on encoded input x^ and return the evaluation Pix^. Finally, the client can reconstruct the value Px by the algorithm VDS.Veryα,y^i=1n and verify its correctness. In Figure 1, we give the algorithm flowchart for the verifiable distributed secure cloud service scheme.Figure 1
Algorithm flowchart forVDS.Two cases for security definition are considered in [11], untrusted cloud security and untrusted client security. We consider the case of untrusted cloud security into two subcases, program privacy and verifiability.Definition 9.
(untrusted cloud security: program privacy) (see [12], Definition 4.1). A VDS scheme is program privacy in untrusted cloud security if the successful advantage of any PPT adversary A in the following experiment is negligible:(i)
The adversaryA sends challenge program P0,P1,S to challenger such that S⊂n, and S=n−1. The challenger samples a random bit b⟵0,1, computes the encoded program Pibi=1n,sk⟵VDS.Prog1λ,n,Pb, and sends Pibi∈S to adversary A.(ii)
Proceeding adaptively, the adversaryA can make the authentication query and input query:(1)
Authentication query: the challenger initializes a dictionary indexed byid,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj⟵VDS.Authsk,id and updates the dictionary id,j⟶tokenidj.(2)
Input query:A sends id,j,x to the challenger. If there exists id,j⟶tokenidj in the dictionary, challenger returns x^,α⟵VDS.Inptokenidj,x. If not, challenger computes tokenidj⟵VDS.Authsk,idj, returns x^,α⟵VDS.Inptokenidj,x, and updates the dictionary id,j⟶tokenidj.(iii)
Finally, the adversaryA outputs his guess b′ for the bit b. The adversary A succeeds if b′=b. The advantage of A’s success is defined as Prb′=b−1/2.Definition 10.
(untrusted cloud security: verifiability). AVDS scheme is verifiable in untrusted cloud security if the successful probability of any PPT adversary A in the following experiment is negligible:(i)
The adversaryA sends challenge program P to challenger. The challenger samples the encoded program Pii=1n,sk⟵VDS.Prog1λ,n,P and sends Pii=1n to adversary A.(ii)
Proceeding adaptively, the adversaryA can make the authentication query. The challenger initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj⟵VDS.Authsk,id and updates the dictionary id,j⟶tokenidj.(iii)
Finally,A outputs x,α,y^i=1n. A succeeds if Px≠VDS.Veryα,y^i=1n.
For untrusted client security, we require that a collection of corrupt clients with the help of a subset of corrupt servers does not distinguish which program is encoded.Definition 11.
(untrusted client security) (see [12], Definition 4.4). The VDS scheme is untrusted client security if the successfully advantage of any PPT adversary A in the following experiment is negligible:(i)
The adversaryA sends challenge program P0,P1,S to challenger such that S⊂n,S=n−1. The challenger samples a random bit b⟵0,1, computes the encoded program Pibi=1n,sk⟵VDS.Prog1λ,n,Pb, and sends Pibi∈S to adversary A.(ii)
Proceeding adaptively, the adversaryA can make the authentication query and evaluation query:(1)
Authentication query: the challenger initializes a dictionary indexed byid,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj⟵VDS.Authsk,id and updates the dictionary id,j⟶tokenidj.(2)
Evaluation query:A sends an encoding x^k for the input xk to the challenger such that P0xk=P1xk. For i∈n/S, challenger returns y^i,k=Pibx^k.(iii)
Finally, the adversaryA outputs his guess b′ for the bit b. The adversary A succeeds if b′=b. The successful advantage of A is defined as Prb′=b−1/2.


## 5.2. Our VDS Construction

LetVDS=VDS.Prog,VDS.Auth,VDS.Inp,VDS.Eval,VDS.Very be a distributed functional signature scheme and Sig=Sig.Setup,Sig.Sign,Sig.Very be an existential unforgeable signature scheme. Now, we describe our construction as follows:(i)
VDS.Prog1λ,n,P⟶Pii=1n,sk:(1)
Runmsk,mvk⟵DFS.Setup1λ,n and Sig.sk,Sig.vk⟵Sig.Setup1λ.(2)
Construct a new programP^, which is given in Figure 2.(3)
ComputeskP^i,P^ii=1n⟵DFS.KeyGenmsk,P^.(4)
SetPi=skP^i,P^i and sk=Sig.sk,mvk.(ii)
VDS.Authsk,id⟶tokenid: parse sk=Sig.sk,mvk, compute the signature σid=Sig.SignSig.sk,id, and output tokenid=mvk,σid,id.(iii)
VDS.Inptokenid,x⟶x^,α: parse tokenid=mvk,σid,id and set x^=x,σid,id and α=x,mvk.(iv)
VDS.EvalPi,x^⟶y^i: parse Pi=skP^i,P^i and compute y^i=P^ix,σi⟵DFS.SignP^i,skP^i,x^.(v)
VDS.Veryα,y^ii=1n⟶Pxor⊥: parse α=x,mvk. Compute DFS.Conmvk,P^ix,σii=1n=P^x,σ. Parse P^x=x′|P′x. If DFS.Verymvk,P^x,σ=1 and x′=x, output P′x. Else, it rejects the returned results.Figure 2
ProgramP^.Correctness. The correctness of our VDS construction follows from the correctness of underlying distributed functional signature scheme DFS and the signature scheme Sig. We can observe that it outputs ⊥ for an invalid signature in the encoded program P^i. Otherwise, it outputs y^i=P^ix,σi. By the correctness of DFS, the output of VDS.Veryα,y^i=1n is Px.Efficiency. We do not consider the time cost of algorithm VDS.Prog because the cost of encoding the program can be amortized over many input computations. For each invocation of VDS.Auth, the service provider generates a signature for the client id. Therefore, it is efficient for the service provider. The work of the client in handling his inputs only depends polynomially on the size of inputs and a security parameter. For the verifiable algorithm, the client needs to reconstruct the function evaluation and verify a signature, which is independent of the complexity of the program. In the phase of reconstructing the function evaluation, the client just needs to compute a summation operation by using the function secret sharing proposed by Fan and Tang [12].Security. We show that our DFS construction satisfies untrusted cloud security (program privacy and verifiability) and untrusted client security defined as above.Theorem 3.
LetDFS be a distributed functional signature scheme against the security of function privacy (c.f. Definition 8); then, our construction of VDS described above has program privacy in untrusted cloud security (c.f. Definition 9).Proof.
We prove that if there exists a PPT adversaryA that can break the program privacy of VDS with non-negligible probability, then another adversary ℬ can be constructed to break the function privacy of DFS with the same probability.
LetC be the challenger for the DFS scheme. We construct the adversary ℬ by A as follows:(i)
The adversaryA sends challenge program P0,P1,S to ℬ such that S⊂n,S=n−1. A samples a signing key Sig.vk,Sig.sk⟵Sig.Setup1λ, constructs two new programs P^0,P^1 as defined in Figure 2, and sends P^0,P^1,S to the challenger of DFS. The challenger returns skP^bi,P^ibi∈S,mvk. ℬ returns skP^bi,P^ibi∈S to A and sets sk=Sig.sk,mvk.(ii)
Proceeding adaptively, the adversaryA can make the authentication query and input query:(1)
Authentication query:ℬ initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, ℬ returns tokenidj to A if there exists a id,j in the dictionary. If not, ℬ computes σidj⟵Sig.SignSig.sk,idj, then returns tokenidj=mvk,σidj,id, and updates the dictionary id,j⟶tokenidj.(2)
Input query:ℬ sends id,j,x to the challenger. If there exists id,j⟶tokenidj in the dictionary, A returns x^=x,σid,id,α=x,mvk to adversary. Else, A computes tokenidj⟵VDS.Authsk,id, returns x^,α⟵VDS.Inptokenidj,x, and updates the dictionary id,j⟶tokenidj.(iii)
Finally, the adversaryA outputs the guess b′ of ℬ.
We observe thatℬ perfectly simulates program private experiment of VDS. Therefore, if ℬ could distinguish the program P0 and P1 with non-negligible advantage in untrusted cloud security, then A can break the security of DFS with the same advantage.Theorem 4.
LetDFS be a distributed functional signature scheme against the security of unforgeability (c.f. Definition 7); then, our construction of VDS described above is verifiable in untrusted cloud security (c.f. Definition 10).Proof.
We prove that if there exists a PPT adversaryA that can break verifiability of VDS with non-negligible probability, then another adversary ℬ can be constructed to break unforgeability of DFS with the same probability.
LetC be the challenger for the DFS scheme. We construct the adversary ℬ by A as follows:(i)
ℬ honestly runs the unforgeable experiment of DFS and gets mvk of distributed functional signature. Then, ℬ samples a signing pair Sig.sk,Sig.vk⟵Sig.Sign1λ.(ii)
A sends challenge program P to ℬ. ℬ defines a new function P^ which is described in Figure 2 and sends P^ to the challenger C of DFS. The challenger returns P^i,skP^ii=1n, sets Pi=P^i,skP^i, and sends Pii=1n to adversary A.(iii)
Proceeding adaptively,A can make the authentication query. ℬ initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj=σidj,idj,mvk and updates the dictionary id,j⟶tokenidj, where σid=Sig.SignSig.sk,idj.(iv)
Finally,A outputs x,α,y^i=P^ix,σii=1n. Then, ℬ computes P^x,σ⟵VDS.Veryα,y^i=1n and outputs the forgeable signature x′|P′x,σ, where P^x=x′|P′x.
Assume thatA succeeded in the experiment of verifiability; then, it must satisfy that DFS.Verymvk,P^x,σ=1, x′=x, and P′x≠Px. For i=1,…,n, DFS.Verymvk,P^ix,σi=1; then, x|Pix must be contained in the range of program P^i. Because the adversary A can just sign the message belonging to the range of encoded programs P^i, the evaluation x|Pix must be computed correctly. In addition, x|P′x is not contained in the range of P^ because of P′x≠Px. x|P′x,σ is validly forgeable signature for the DFS scheme. So, if there exists an adversary that breaks the verifiability of VDS with non-negligible probability, then there exists another adversary that breaks the unforgeability of DFS with the same probability.Theorem 5.
LetDFS be a distributed functional signature scheme against the security of function privacy (c.f. Definition 8) and Sig be an unforgeable signature scheme; then, our construction of VDS described above is secure in untrusted client security (c.f. Definition 11).Proof.
We prove that if there exists a PPT adversaryA that can break security in untrusted client security with non-negligible probability, then another adversary ℬ can be constructed to break function privacy of DFS with the same probability.
LetC be the challenger for the DFS scheme. We construct the adversary ℬ by A as follows:(i)
ℬ runs the function private experiment of DFS and gets a master verifiable key mvk of DFS. Then, ℬ samples a signing pair Sig.sk,Sig.vk⟵Sig.Sign1λ.(ii)
The adversaryA sends challenge program P0,P1,S to ℬ such that S⊂n,S=n−1. ℬ defines two new functions P^0 and P^1 which are described in Figure 2 and sends P^0,P^1,S to the challenger C of DFS. The challenger returns P^ib,skP^bii∈S, sets Pi=P^ib,skP^bi, and sends Pii∈S to adversary A.(iii)
Proceeding adaptively, the adversaryA can make the authentication query and evaluation query:(1)
Authentication query:ℬ initializes a dictionary indexed by id,j⟶tokenidj. When A queries an identity idj, the challenger returns tokenidj to adversary A if there exists a id,j in the dictionary. If not, the challenger returns tokenidj=σidj,idj,mvk and updates the dictionary id,j⟶tokenidj, where σid=Sig.SignSig.sk,idj.(2)
Evaluation query:A sends an encoding x^k for the input xk to ℬ. ℬ first checks whether P0xk is equal to P1xk. If not, ℬ stops the experiment. Otherwise, ℬ queries the evaluation oracle of DFS and returns the output to A.(iv)
Finally, the adversaryℬ outputs the result b′ of the adversary A.
We observe thatℬ perfectly simulates the secure experiment in untrusted client model. Therefore, if A can distinguish the program P0 and P1 with non-negligible advantage, then ℬ can break the function private security of DFS with the same advantage.


## 6. Conclusion

In this work, we introduce the notion of distributed functional signature. In such model, it provides a possibility of function privacy in the setting of functional signature. We give a construction from function secret sharing and functional signature. The function secret sharing can be constructed based on learning with error assumption, and the functional signature can be constructed based on the existence of one-way function. Therefore, our construction can be obtained from one-way function and learning with error assumption. In addition, we apply it to the host service in multiple untrusted clouds in which the clouds will be dishonest. We require that the returned result from the clouds can be verified.



---

*Source: 6699974-2021-03-12.xml*