Achieving Fuzzy Matching Data Sharing for Secure Cloud-Edge Communication

Chuan Zhang，Mingyang Zhao，Yuhua Xu，Tong Wu，3，*，Yanwei Li ，Liehuang Zhu，Haotian Wang

1 School of Cyberspace Science and Technology，Beijing Institute of Technology，Beijing 100081，China

2 School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China

3 Yangtze Delta Region Academy of Beijing Institute of Technology，Jiaxing 314019，China

4 National Computer Network Emergency Response Technical Team/Coordination Center of China，Beijing 100029，China

5 College of Arts and Science，University of Pennsylvania，Philadelphia 19104，USA

Abstract:In this paper，we propose a novel fuzzy matching data sharing scheme named FADS for cloudedge communications.FADS allows users to specify their access policies，and enables receivers to obtain the data transmitted by the senders if and only if the two sides meet their defined certain policies simultaneously.Specifically，we first formalize the definition and security models of fuzzy matching data sharing in cloud-edge environments.Then，we construct a concrete instantiation by pairing-based cryptosystem and the privacy-preserving set intersection on attribute sets from both sides to construct a concurrent matching over the policies.If the matching succeeds，the data can be decrypted.Otherwise，nothing will be revealed.In addition，F(xiàn)ADS allows users to dynamically specify the policy for each time，which is an urgent demand in practice.A thorough security analysis demonstrates that FADS is of provable security under indistinguishable chosen ciphertext attack(IND-CCA)in random oracle model against probabilistic polynomial-time(PPT)adversary，and the desirable security properties of privacy and authenticity are achieved.Extensive experiments provide evidence that FADS is with acceptable efficiency.

Keywords:fuzzy-matching; privacy-preserving set intersection;cloud-edge communication;data sharing

I.INTRODUCTION

Cloud computing has been widely applied in various domains to help users，especially the resourceconstraint end devices，to enjoy convenient and lowcost computing and storage services.However，with the explosive growth of end devices，it is quite difficult for the end devices to connect with the cloud servers with low response time.To deal with this issue，cloud-edge computing[1]，as an emerging paradigm that exploits the computing，storage，and communication capacities of edge devices，has drawn significant attention[2].The system architecture of cloudedge computing is shown in Figure 1.By integrating the resources of both edge devices and cloud servers，cloud-edge computing offers a set of advantages such as providing a fast response for end devices，reducing bandwidth constraints，and relieving network congestion[3，4].Based on the report released by Grand View Research，the market of cloud-edge computing is expected to reach USD 61.14 billion by 2028[5].As an intermediate layer，the edge nodes handle the large scale of data transmission between the user and cloud，which however may raise severe privacy concerns.Firstly，although edge computing stores and proceeds data more close to the end devices compared with the cloud，the edge devices cannot be trusted.As the rising of cyber attacks，the edge devices are vulnerable to the attacks，such as eavesdropping，unauthorized modification，and unauthorized access to the system，etc.，which causes that the users are deterred from sharing their data for concerns on the leakage of sensitive information.Secondly，the behavior of data transmission between two users may cause information leakage by launching inference attacks.The accurate sharing will expose the relationship among the users，helping the observers to clarify the social relationship among the users.For the aforementioned security and privacy concerns，we summarize the security requirements of cloud-edge computing as follows:1)Data confidentiality:the data can be recovered if and only if the decryption succeeds; 2)User privacy:the adversary cannot determine the exact sender or receiver even if it observes the data transmission occurs;3)Collusion resistance:when the cloud colludes with some edge devices，the cloud cannot decrypt the ciphertext correctly.

Figure 2.System architecture of FADS for cloud-edge computing environment.

To construct a secure data sharing scheme in the cloud-edge computing environment，we may consider attribute-based encryption(ABE)，access control，and access control encryption(ACE)[6，7].However，in these conventional cryptographic primitives，the access policies are specified by only one side，which is a one-to-many communication mode.Additionally，in ACE，a fully trusted third party needs to be always online to participate in data sharing and prevent attacks from malicious senders and receivers.To realize that both sender and receiver can specify access policy for the other，a solution is matchmaking encryption(ME)[8]，which provides an accurate matching between attribute and access policy.More specifically，the matching is measured both by the sender’s policy，sender’s attributes，receiver’s policy，and receiver’s attributes.From the sender side，the sender’s policy indicates the specific attributes of the receiver who can decrypt the ciphertext.From the receiver side，the receiver’s policy indicates the specific attributes of the sender whose ciphertext can be decrypted.In addition，ME guarantees that if and only if the matching succeeds，the message will be recovered.Otherwise，nothing will be revealed.However，accurate matching may not satisfy the requirements of real-world applications，which require a many-to-many communication mode.Specifically，the many-to-many communication mode indicates that one sender can specify access policies for multiple receivers and vice versa.For example，in the healthcare system[9，10]，suppose that the hospital cooperates with other organizations to develop a novel treatment for some diseases(i.e.，COVID-19).The hospital may only allow the organizations that meet its access policy to access the corresponding case data and the organization may only access the case data sent by hospitals that meet its access policy.With ME，the hospital needs to specify the corresponding access policy and generate the corresponding ciphertext for each organization，which causes a huge waste on computation and communication resources.Additionally，the aforementioned cryptographic primitives cannot support the receivers to dynamically specify the access policy for the senders during data sharing.Specifically，dynamic policies indicate that the receiver could specify the scope of the received message by changing the threshold value for the number of senders’attributes in the access policy.

To support the dynamic policies and many-to-many communication mode，we apply the ME with fuzzy matching.Specifically，compared with the aforementioned cryptographic primitives，ME with fuzzy matching has some advantages as follows:

·The message will be recovered if and only if the matching succeeds.Otherwise，nothing will be revealed except that the matching occurs.

·The policy is not specified by one side only，but both sides can make access policies for the opposite sides.Additionally，ME with fuzzy matching supports the receivers to dynamically specify the access policy for the senders during data sharing.

·The fuzzy matching allows a certain distance of error between the access policy and individual’s attributes to realize the many-to-many communication mode in cloud-edge computing，to hide the accurate users involved in the sharing procedure.

In this paper，we introduce a novel fuzzy matchingbased data sharing scheme，named FADS，for cloudedge computing，derived from ME.Different from the conventional underlying cryptographic primitives，the decryption of fuzzy type ME is decided by both senders and receivers with error tolerance，forming a potential of many-to-many communication.Considering the aforementioned security requirements，F(xiàn)ADS should be with the following characteristics:1)Both sender and receiver can specify the access policies for establishing communication，and the receivers can dynamically specify the access policy for the senders during data sharing;2)The matching should allow error tolerance，measured by the attributes and access policies;3)The messages，attributes，and access policies of participants(senders and receivers)should stay secure even if the cloud colludes with some edge devices.4)Some heavy computation will be taken by the edge devices to release the end devices from the burden of computation so that secure data sharing can be conducted among end devices efficiently by introducing cloud-edge computing.

1.1 Contribution

We formally define the notion of FADS in the cloudedge computing environment，implemented by the pairing-based cryptosystem.We provide the security analysis and performance evaluation to FADS.Specifically，our contributions are listed as the following points:

1.We apply ME to present a pairing-based solution for constructing a fuzzy matching data sharing scheme named FADS.FADS is the first MEbased scheme supporting fuzzy matching by allowing the matching with error-tolerance between attributes and policies.If the decryption fails，nothing will be revealed，including the accurate attributes of users or why the matching fails.

2.We construct the encryption key for senders in the system with their own attributes.And we generate the decryption key for receivers with their own attributes.The key generation algorithm adopts Shamir’s secret sharing[11]to accomplish error-tolerance in key components.Suppose that the subsets of the key components from opposite sides satisfying the access policies are in a designed offset.The message can be recovered from the ciphertext.Additionally，the receivers can dynamically specify the access policy for the senders during data sharing.

3.We prove the security of FADS to be with semantic security against any probabilistic polynomialtime adversary.Further，we prove two essential properties in FADS for cloud-edge computing，as privacy and authenticity.

4.We also evaluate FADS by conducting comparison experiments with some existing works to demonstrate that FADS is practical in real-world applications.

1.2 Literature Review

In this section，we compare ourFADS with the existing works，shown as Table 1，in the perspective of security，privacy，authenticity，access control，and fuzzy matching.

Table 1.Theoretical comparison with the existed data sharing schemes.

Data Sharing for Cloud-edge Computing.Edge computing is a novel computing model that provides computation，storage，and networking services between end devices[25].For supporting various datadriven services，a large scale of data is transmitted among the cloud and users in the network，including personal privacy and collaborated data.For instance，the static data and transmission process can be eavesdropped from the work logs by the malicious attacks in the whole procedure[26].In cloud-edge computing，collaborated and personal data are treated as sensitive information，stored and processed near to users.In a cloud-edge computing system，the edge devices act as the proxy for end devices，which cannot protect the security and privacy of sensitive information for its constrained resource.In terms of our research on the stateof-the-art of cloud-edge computing，there are some existing works on resolving the security and privacy issues in cloud-edge computing.In[27]，the authors figure out that secure edge devices usage is one of the crucial challenges in the cloud-edge computing environment.Hui et al.[28]suggested a secure data transmission scheme for edge computing，which relies on the synchronization of chaotic systems with differentorders.The security of their proposed data transmission is based on the size of the keyspace.Their system is a one-to-one communication method.In[29]，Xu et al.introduced a secure data transmission by using the physical layer with beamforming and artificial noise.With this method，the physical channel plays an essential role in ensuring system safety.From 2012，Gaurav[30]proposed the secure file transmission scheme，implemented by encryption.A sequence of encryptionbased data sharing schemes has emerged for the distribution system[18，12，19，13，14，20，21].In[12]，Pan et al.suggested the ciphertext-policy attribute-based encryption(CP-ABE)to ensure the confidentiality of the information and share data among different domains，which organized by edge computing vehicles.In their scheme，the privacy of individuals is protected by using pseudo identities during the communication process.Liu et al.[13]constructed a secure data sharing scheme for mobile edge computing by applying the additional zero-knowledge proof(ZKP)，secure multiparty computation，and succinct，transparent arguments of knowledge(STAK)to ensure the security and privacy of data，which is also a one-to-one communication model.Yang et al.[14]introduced a data sharing scheme by outsourcing the complex computation workloads of end-user devices to the edge nodes in a consortium blockchain system.The access control is realized by adopting the linear secret sharing scheme(LSSS).However，the data is encrypted with symmetric encryption，where the key management and distribution is a crucial issue to be solved.

To conclude the existing works，the data sharing schemes for edge computing are commonly in the form of one-to-one communication.To support the one-to-many communication，CP-ABE is considered to be an adequate methodology in practice.However，the access policy of CP-ABE is designed only by one side，so it cannot realize the many-to-many communication.

Matchmaking Encryption.The matchmaking encryption allows the sender and receiver to specify the access policy，simultaneously，firstly introduced by Ateniese et al.at CRYPTO’19[8].The subsequent works[15，16，22]make attempts to apply ME to fog computing to realize the fine-grained bilateral access control over outsourced data.Specifically，Chen et al.[16]avoids forging an identity in a conventional way and introduces certificateless matchmaking encryption(CL-ME)for the Internet of Things scenario.Danilo et al.[22]proposed an identity-based matchmaking encryption(IB-ME)scheme based on standard assumptions over bilinear groups.Our challenge in this work is to build fuzzy matching type ME，remaining privacy，authenticity，and security of the typical ME，to serve as a qualified building block of fuzzy matching data sharing scheme for cloud-edge computing.We take the privacy-preserving set intersection[31]into consideration to securely and privately compute the result of the access policies and attributes[32].

Linear Secret Sharing.In 1979，Shamir et al.[11]and Blakley et al.[33]introduced the linear secret sharing scheme.The process of the linear secret sharing scheme is as follows:1)The sender splits the secret into multiple shares in an appropriate way;2)The sender distributes each share to different participants;3)Participants cooperate to recover the secret.As one of the important tools of modern cryptography，the linear secret sharing scheme has been used in many practical applications[34–38].Generally，the linear secret sharing scheme has two types，threshold secret sharing scheme and non-threshold secret sharing scheme.In non-threshold secret sharing scheme，a sequence of works[23，24，39]make attempts to apply the coding theory，linear universal hash functions，etc.，to reach secret sharing.Specifically，Appala et al.[23]proposed a secret sharing scheme for compartmented access structure with lower bounds based on the Maximum Distance Separable(MDS)codes.Ronald et al.[24]constructed a linear secret sharing scheme based on linear code and linear universal hash functions in a black-box way.The non-threshold secret sharing scheme requires all receivers to participate in secret recovery，while the threshold secret sharing scheme only requires some members to participate in this procedure.Particularly，in fuzzy matching，the receiver only needs to meet some requirements specified by senders，which is similar to the requirement to recover the secret in the threshold secret sharing scheme.Therefore，we regard the threshold secret sharing scheme as a building block of our proposed scheme.The Lagrange interpolation polynomial method is typical to achieve the threshold secret sharing scheme.Specifically，the Lagrangian interpolation polynomial has the property that if the data is in the original data set used to generate the interpolation function，the corresponding Lagrangian coefficient equals 1.Otherwise，the Lagrangian coefficient equals 0.Based on this property，the Lagrangian interpolation polynomial method can be used to achieve secret recovery in threshold secret sharing.Thus far，a sequence of works[17，40，32，41，42]have been proposed to achieve the threshold secret sharing scheme.Specifically，Song et al.[40]proposed a secure fuzzy matching scheme based on symmetric-key threshold predicate encryption(STPE)and proxy re-encryption for vehicular crowdsourcing system.Their scheme achieves privacy-preserving threshold-based task matching and data transmission between worker and requester.Amit et al.[17]proposed a fuzzy identity-based encryption(IBE)scheme based on the Lagrange interpolation polynomial method.Their scheme is both errortolerant and secure against collusion attacks.However，in these methods，the access policy is specified only by one side.To achieve that both sender and receiver can specify policy for the other，Giuseppe et al.[32]proposed a fuzzy secret handshake scheme based on the Lagrange interpolation polynomial method，and their scheme allows the handshakes to be based on bilateral matching.However，the aforementioned methods cannot support non-interactive bilateral matching in data sharing.

Thus，in this paper，we exploit the possibility of the Lagrange interpolation polynomial method for constructing efficient non-interactive bilateral fuzzy matching data sharing in the cloud-edge environment.

1.3 Organization

We organize our article as follows:in Section II，we introduce the mathematical preliminaries and cryptographic primitives used in our work.In SectionIII，we define the system model and architecture of FADS.In Section IV，we introduce the workflow of FADS and give a concrete construction.We formally analyze the security，privacy，and authenticity of our proposed scheme in Section V.In Section VI，we provide the theoretical comparison and experimental evaluation with the existing relevant works.In Section VII，we conclude our work and discuss our future works.

II.PRELIMINARY

In this section，we introduce some mathematical preliminaries and cryptographic primitives used in FADS.

2.1 Bilinear Group

2.2 Lagrange Interpolation Polynomial

2.3 Privacy-Preserving Set Intersection(PSI)

III.DEFINITION

We introduce the system architecture of FADS for cloud-edge computing and formally define security models as INDCCA security，privacy，and authenticity.

Privacy-preserving Set Intersection:· Input:Private set X1，···，Xn and a public encrypted vector E(C)=(E(c1)，···，E(cm)).· Output:E(B)=(E(b1)，···，E(bm)).If uj ∈T， bj is an even number; otherwise， bj is an odd number.Step 1.P1 construct a vector in terms of two cases:S1 =A1.uj ∈A1，E(d1j)=E(cj)uj /∈A1，E(d1j)=E(r1j)S1 = ˉA1.uj ∈A1，E(d1j)=E(r1j)uj /∈A1，E(d1j)=E(cj)Note that rij is a randomly chosen odd number.P1 sends E(D1)=(E(d11)，···，E(d1m))to P2.Step 2.For 2 ≤i ≤n-1，Pi computes Enc(Di):Si =Ai.uj ∈Ai，E(dij)=E(di-1j)uj /∈Ai，E(dij)=E(rij)Si = ˉAi.uj ∈Ai，E(dij)=E(rij)uj /∈Ai，E(dij)=E(di-1j)Pi sends E(Di)=(E(di1)，···，E(dim))to Pi+1.Step 3.As Step 2，Pn computes E(Dn)=(E(dn1)，···，E(dnm))，and sets E(B)=E(Dn).

3.1 System Architecture

We first define the system architecture of FADS for the cloud-edge computing environment.There are three layers in the system，the service layer，the intermediate layer，and the device layer.The responsibility of each layer is described as follows:1)The service layer contains the cloud to store the data from users and the key generation center(KGC).As for KGC，it generates the key for users before joining the system.The sender’s encryption key is computed with his/her own attributes.The receiver’s decryption key is computed with its own attributes; 2)The edge devices compose the intermediate layer，responsible for the computation and storage between end devices and cloud;3)The device layer consists of end devices for generating data.The sender specifies the access policy for the target receivers then encrypts the data by the encryption key and the sender’s policy.The receiver also can specify the access policy to indicate who can send data to it.Then，decrypt the ciphertext by the decryption key and policy of the receiver.If the decryption successes，the receiver can recover the data from the ciphertext.Otherwise，it will not reveal anything，except the matching does not occur.

The system architecture is shown in Figure 2，and the notations used in this paper are listed in Table 2.At a high level，the process of FADS is described as follows:1)Senders and receivers register to the KGC and obtain the corresponding secret key;2)The KGC distributes system parameters to senders，receivers，and the edge devices; 3)Senders generate a series of ciphertexts and then send them to the edge devices; 4)The edge devices retain the ciphertexts used in the match phase and then upload the rest to the cloud; 5)Receivers send the ciphertexts of attributes and the ciphertexts of access policies used in PSI to the edge devices;6)The edge devices execute matching and send the data request to the cloud;7)The cloud returns the corresponding data to the edge devices;8)the edge devices return the data to receivers，and receivers execute the decryption phase to recover the message.

Table 2.Notations used in FADS.

More specifically，F(xiàn)ADS consists of polynomialtime algorithms:Setup，SKGen，RKGen，Enc，Matching，and Dec.

·Setup.The system server takes the security parameterλas the input.It outputs the master public key mpk and the master secret key msk.

·SKGen.The system server takes the master secret key msk and attributesσ ∈{0，1}*.It outputs an encryption key ekσfor the sender.

·RKGen.The system server takes the master secret key msk and attributesρ ∈{0，1}*.It outputs a decryption key dkρfor the receiver.

·Enc.The sender takes the encryption key ekσ，policy of sender:R :{0，1}* →{0，1}，and a messagem ∈M.It outputs a ciphertextC.

·Matching.The edge device takes the encrypted attributes of sender/receiver and the encrypted access policy of sender/receiver.It outputsacceptedif the matching succeeds.Otherwise，rejected.

·Dec.The receiver takes the secret decryption key dkρ，policy of receiver:S:{0，1}* →{0，1}，and a ciphertextC.It outputs a messagemor⊥.

Informally，when a ciphertext onmis generated honestly under the sender’s encryption key and access policy of sender R，the output of the decryption algorithm is conducted under the receiver’s decryption key and access policy of receiver S.mcan be recovered from the ciphertext，if and only ifρmatches R，andσmatches S，simultaneously.

Definition 4(Correctness).A fuzzy matching data sharing scheme with massage space M is correct if the security parameter λ ∈N，?m ∈ M to be encrypted，the sender’s attributes and receiver’s attributes σ，ρ ∈{0，1}*，the access policy of sender and receiver ?R，S :{0，1}* →{0，1}，and ?(mpk，msk)generated bySetup(λ):

if and only if Dist(S，σ)≥d ∧Dist(R，ρ)≥d，and otherwise，

whereekσ←SKGen(msk，σ)，dkρ←RKGen(msk，ρ).

Distindicates the distance between the attributes and policies of the sender/receiver.

3.2 Threat Model

In our scheme，the KGC is a fully trusted third party，and all communications with the KGC are secure.Except for the KGC，each entity in our scheme can be an adversary.It is noted that we assume that the cloud can collude with the edge devices.Based on the capabilities of an adversary，we summarize the adversary into five types，i.e.，malicious participant，cloud-only adversary，edge-only adversary，cloud-edge collusion adversary，and external adversary.Specifically，we describe the threat model of FADS as follows:

·Malicious participant.The participant(sender and receiver)possesses his/her own attributes and access policies and can access the ciphertexts generated by others.The malicious participant launches chosen ciphertext attack to obtain messages，attributes，and access policies of others.

·Cloud-only adversary.The cloud is responsible for storing the ciphertexts generated by senders.It is honest to perform the execution，but it launches ciphertext-only attack to obtain messages，attributes，and access policies of participants.

·Edge-only adversary.The edge device is responsible for executing the matching by PSI.The edge device can access the ciphertexts stored on the cloud，the ciphertexts of attributes，and the ciphertexts of access policies used in PSI，stored on the edge devices.The edge device launches ciphertext-only attack to obtain messages，attributes，and access policies of participants.

·Cloud-edge collusion adversary.The adversary can access the ciphertexts stored on the cloud，the ciphertexts of attributes，and the ciphertexts of access policies used in PSI，stored on the edge devices.Then，the adversary launches ciphertextonly attack to obtain messages，attributes，and access policies of participants.

·External adversary.External adversary can access the ciphertexts by eavesdropping on the communication channel between participants and the edge devices.The adversary launches ciphertextonly attack to obtain messages，attributes，and access policies of participants.

3.3 Security on FADS

The security characteristics of our proposed data sharing are formally defined in this part in terms of security，privacy，and authenticity.Informally，the security is on top of the computational indistinguishability between Enc(ekσ0，R0，m0)and Enc(ekσ1，R1，m1)with querying SKGen and RKGen.More specifically，we define our proposed data sharing is IND-CCA secure.The oraclesOS，ORare represented to SKGen and RKGen.

·Setup.The challenger runs Setup algorithm and publishes the public parameters.

·Phase 1.The challenger will allow the adversary to request the encryption keys and decryption keys fromOS，OR，respectively.The adversary givesσtoOSfor gettingekσ.And it providesρtoORfor gettingdkρ.

·Challenge.The adversary chooses the sender’s encryption key，the target receiver and two messagesm0，m1，where|m0|=|m1|.The challenger encryptsmb，b ∈{0，1}，by flipping a random coin.The challenger will send the ciphertext to the adversary.Note that the target receiver’s decryption key cannot be requested in Phase 1.

·Phase 2.It is similar toPhase 1，except that the adversary cannot request the target receiver’s decryption key.

·Guess.At the end of the game，the adversary outputs a guessb′onb.

We say the adversary wins the game ifb′given by the adversary in theGuessphase is equal tobchosen by the challenger.Therefore，F(xiàn)ADS is secure that

where?is negligible.From[8]，the security of ME implies privacy and authenticity.Thus，the security of FADS implies privacy and authenticity，as well.

3.4 Privacy on FADS

To protect the privacy of attribute，F(xiàn)ADS should first guarantee that the adversary cannot recover the attributes from the ciphertext，encrypted byσ0orσ1.Secondly，F(xiàn)ADS should guarantee that if the matching fails，the adversary cannot know whose attributes cannot meet the other’s policy.

To protect the privacy of access policy，F(xiàn)ADS should first guarantee that the adversary cannot recover the access policy from the ciphertext，encrypted by R0or R1.Secondly，F(xiàn)ADS should guarantee that if the matching fails，the adversary cannot know whose access policy is not met.

In summary，we say the adversary breaks the privacy ifb′=bthat the adversary gives the guess onbcorrectly.Therefore，F(xiàn)ADS holds the privacy that

where?is negligible.

3.5 Authenticity on FADS

Authenticity demands that if a sender attempts to create a valid ciphertext with attributesσ，the sender must obtain the encryption keyekσfrom the KGC and useekσto generate the ciphertext.Otherwise，the ciphertext will be invalid.The authenticity ensures that if a ciphertext can be decrypted correctly，it must be produced by an authenticated sender.More specifically，the sender encryptsm*under a forged secret keyek*to generateC*.Then，the receiver attempts to recover the message fromC*.However，the probability that the message can be recovered fromC*is negligible.Thus，F(xiàn)ADS holds the authenticity that

wherem* ∈M，ek*was not queried before，and?is negligible.

IV.FUZZY MATCHING DATA SHARING FOR CLOUD-EDGE COMPUTING

In this section，we introduce the workflow of FADS and the concrete construction of FADS for cloud-edge computing in terms of the aforementioned system architecture.

4.1 Workflow

The workflow of our proposed data sharing is shown as Figure 3.The working entities in the system are divided into KGC，End Devices，Edge Devices，and Cloud.Our system has four phases:System Initialization，Registration，Data Synchronization，andData Sharing.

Figure 3.Workflow of fuzzy matching data sharing scheme.

Figure 4.Encryption performance in FADS.

·System Initialization:Given a security parameter，KGC outputs the master secret key and the public parameters.Then，KGC distributes the public parameters to all legal end devices and edge devices.

·Registration:An end device can access the system after registering in KGC.This process can be divided into two cases:sender key generation and receiver key generation.

1.Sender Key Generation:When an end device，as the sender，sends the attributes，KGC takes the master secret key and attributes to generate the encryption key.KGC sends the encryption key to the end device for encryption during data sharing.

2.Receiver Key Generation:When an end device，as the receiver，sends the attributes，KGC takes the master secret key and attributes to generate the decryption key.KGC sends the decryption key to the end device for decryption during data sharing.

·Data Synchronization:In our system，the edge devices establish a ciphertext pool，an attribute pool，and an access policy pool and store the data in the corresponding pool.In addition，the edge devices will upload ciphertexts that have not been accessed for a long time to the cloud，and delete the data locally，thereby improving the resource utilization of edge devices.

·Data Sharing:In our system，the end devices，edge devices，and cloud collaborate the data sharing.The data sharing stage can be divided into three procedures:data encryption，matching，and data decryption.

1.Data Encryption:An end device as the sender is aiming to send the data to a group of receivers whose attributes satisfy the access policy designed by the sender itself with a certain distance of error.The encrypted data is computed with the access policy and the encryption key.Then，it sends the ciphertext to the edge device.

2.Matching:The edge devices conduct the matching procedure by applying the PSI over the attributes of end devices and their access policies.The edge device will return accepted if the matching occurs;otherwise，it returns rejected.If the matching occurs，the edge device obtains the corresponding ciphertext and forwards it to the corresponding end device.

3.Data Decryption:An end device as the receiver once received the data from the edge device，which means the matching occurs.The end device will conduct the decryption algorithm to recover the message from the ciphertext.

4.2 Concrete Construction

In the following part，we introduce the concrete construction of FADS，which is divided into six algorithms，including Setup，SKGen，RKGen，Enc，Matching，and Dec.

4.3 Correctness

In this section，we give a detailed proof for the correctness of FADS.

Theorem 1.If the matching succeeds，where the attributes of the receiver meet the access policy of the sender and the attributes of the sender meet the access policy of the receiver as well，the receiver can correctly recover the message from the ciphertext.

Proof.The correctness of our construction is oblivious，which depends on the computation ofK1andK2.We reviewK1，K2in Enc as the following:

V.SECURITY ANALYSIS

According to our construction，we have an intuition of the security that the message is semantically secure from the view of a receiver who cannot decrypt the ciphertext.Moreover，sinceH(·)is close to random distribution，the core idea of the decryption algorithm is to compute symmetric keysgT，1andgT，2，motivated by the Fujisaki-Okamoto transformation[45].

Here，the sender’s encryption key and receiver’s decryption key are linearly independent and indistinguishable to that in Game 1 from the view ofA.IfAcan tell the difference，it will terminate the game and return failed.

VI.PERFORMANCE EVALUATION

In this section，we evaluate the performance of our data sharing scheme with relevant works AFNV19[8]and CFDS20[15]by a sequence of experiments.AFNV19 and CFDS20 are typical matchmaking encryption and ME-based data sharing scheme in fog computing，allowing bilateral access control.Therefore，we choose AFNV19 and CFDS20 to conduct the performance comparison.

6.1 Environment Configuration

Our scheme is implemented in Java using JPBC[47].We choose Type A curve，as symmetric pairings(Type-I)，with 80-bit security.The execution environment is conducted with a laptop，which is of an 8th generation Intel Core i7-8550U @ 1.80GHz with 16 GB of RAM.

We executed the experiments 20 times to obtain the average time for each algorithm.We make each end device in the system contain at most 30 attributes(n ≤30)，includingID，name，gender，age，occupation，faculty，organization，suburban，city，country，etc.To realize fuzzy matching，we set the threshold valuedfor the number of attributes to be half the size of the policies.Additionally，we leverage the number of attributes to represent the size of policies in our experiments.We evaluate the encryption performance，decryption performance，storage overhead，and communication overhead.

6.2 Performance Evaluation

Encryption Performance.As shown in Figure 4，we compare our scheme with AFNV19 and CFDS20 in terms of the encryption running time and the size of policies.In Figure 4，the horizontal axis represents the number of attributes，and the vertical axis represents the average encryption running time overhead.In the encryption process，our scheme，CFDS20，and AFNV19 all generate the ciphertexts based on the bilinear group.Specifically，in the encryption process，the computational cost of our scheme is(O(1)×Tpairing+O(|S|)×Tmultiplication+O(|R|+|S|)×Texponent)，whereTpairingrepresents the time to perform a pairing operation，Tmultiplicationrepresents the time to perform a multiplication operation，Texponentrepresents the time to perform an exponent operation，|R|represents the size of the sender’s policy R，and|S|represents the size of the receiver’s policy S.Compared with CFDS20，our scheme leads to a relatively higher computation cost to support fuzzy matching over the access policies and user’s attributes by precomputing some elements，i.e.，W.Thus，the running time of encryption in our scheme is slightly higher than that of CFDS20.Since AFNV19 extends directly from an identity-based setting to an attributebased setting in the encryption process，which incurs a large computation overhead，the running time of the encryption process in AFNV19 is much higher than that of our scheme.

Figure 5.Decryption performance in FADS.

Decryption Performance.As shown in Figure 5，we compare our scheme with AFNV19 and CFDS20 in terms of the decryption running time and the size of policies.In Figure 5，the horizontal axis represents the number of attributes，and the vertical axis represents the average decryption running time overhead.In AFNV19，the whole process of decryption is executed on the receiver side，which brings a large computation overhead on the receiver side.CFDS20 attempts to reduce the computation overhead on the receiver side by outsourcing the workload of sender verification to edge devices.To further reduce the computation overhead on the receiver side，our scheme outsources the workload of matching between sender and receiver to edge devices.Specifically，in the decryption process，the computational cost of our scheme is(O(|R|)×Tpairing+O(|R|+|S|)×Tmultiplication+O(|R|)×Texponent)，whereTpairingrepresents the time to perform a pairing operation，Tmultiplicationrepresents the time to perform a multiplication operation，Texponentrepresents the time to perform an exponent operation，|R|represents the size of the sender’s policy R，and|S|represents the size of the receiver’s policy S.

Storage Overhead.As shown in Figure 6，we compare our scheme with AFNV19 and CFDS20 in terms of the storage overhead and the size of policies on the cloud side.In Figure 6，the horizontal axis represents the number of attributes，and the vertical axis represents the average storage overhead.Our scheme has the same performance as the accurate matching type data sharing CFDS20.However，the storage overhead of FADS is much lower than that in AFNV19 because the ciphertext in AFNV19 is the multiply of senders’attributes and receivers’attributes.

Figure 6.Storage overhead in FADS.

Figure 7.Communication overhead of FADS.

Communication Overhead.We evaluate the communication overhead on the receiver side by varying the size of policies in the presence and absence of edge devices.The comparison results are shown in Figure 7，where we set the number of senders as 10 and vary the number of attributes from 5 to 30.Obviously，F(xiàn)ADS greatly reduces communication overhead on the receiver side because of the assistance of edge devices.

VII.CONCLUSION

In this paper，we introduce a novel notion of data sharing for the cloud-edge computing environment and provide a concrete construction of FADS with a pairing-based cryptosystem.To the best of our knowledge，F(xiàn)ADS is the first data sharing scheme based on fuzzy matchmaking encryption.Our proposed data sharing enables the matching holds with a certain distance of error and allows the policies from both sides to be checked simultaneously without revealing any additional information except the matching holds or not.We give the formal security proof to show the security，privacy，and authenticity.The experiments are conducted to evaluate the performance of our proposed data sharing.By comparing with the existing works，the results indicate that our proposed data sharing is practical.

Our work inspires a few interesting open problems.The first is how to construct a cross-domain fuzzy matching data sharing scheme where the users come from multiple authorities.In real-world applications，it is a common case that users are registered from different authorities.The second problem is to build fuzzy matching data sharing schemes for arbitrary policy to provide fine-grained access control.The third problem is to create more efficient fuzzy matching data sharing schemes with standard assumptions.Furthermore，we should consider including the addressing key escrow[48]，key management infrastructure，and revocation[49]efficiently.In addition，applying FADS into other application domains，such as truth discovery[50]，task recommendation[51]，federated learning[52]is also an interesting and important research direction.

ACKNOWLEDGEMENT

This work is supported by the China Postdoctoral Science Foundation(Grant Nos.2021TQ0042，2021M700435，2021TQ0041)，the National Natural Science Foundation of China(Grant No.62102027)，and the Shandong Provincial Key Research and Development Program(2021CXGC010106).