Server-aided access control for cloud computing

WENG Jian， WENG Jia-si， LIU Jia-nan， HOU Lin

（College of Information Science and Technology， Jinan University， Guangzhou 510632， China）

stores

5）

Server-aided access control for cloud computing

WENG Jian， WENG Jia-si， LIU Jia-nan， HOU Lin

（College of Information Science and Technology， Jinan University， Guangzhou 510632， China）

With the massive diffusion of cloud computing， more and more sensitive data is being centralized into the cloud for sharing， which brings forth new challenges for the security and privacy of outsourced data. To address these challenges， the server-aided access control （SAAC） system was proposed. The SAAC system builds upon a variant of conditional proxy re-encryption （CPRE） named threshold conditional proxy re-encryption （TCPRE）. In TCPRE， t out of n proxies can re-encrypt ciphertexts （satisfying some specified conditions） for the delegator （while up to t-1 proxies cannot）， and the correctness of the re-encrypted ciphertexts can be publicly verified. Both features guarantee the trust and reliability on the proxies deployed in the SAAC system. The security models for TCPRE were formalized， several TCPRE constructions were proposed and that our final scheme was secure against chosen-ciphertext attacks was proved.

threshold conditional proxy re-encryption， server-aided access control， cloud computing， chosen-ciphertext attack

1 Introduction

Cloud computing is an emerging computing paradigm in which IT resources and capacities are provided as services over the Internet while hiding platform and implementation details. Nowadays，many users transparently rely on outsourced storage solutions based on the cloud model， e.g.， by using Dropbox and Google Docs. Unfortunately， in order to effectively protect the secrecy of their data， such users can only encrypt them locally and then upload the ciphertext to the cloud storage repository. However， if they use traditional public key encryption schemes， some shortcomings may heavily condition the sharing of such data with other authorized users. For example， suppose Alice wants to share her private data with Bob， then she has to first download the ciphertexts from the cloud， decrypt them locally with her own secret key， encrypt again the data by using Bob's public key， and finally upload the new ciphertext to the cloud. Then Bob can access the data with his secret key. However， such a solution is highly unsatisfactory， since it introduces heavy computational cost and communication overhead and does not scale well when data must be shared with a significant number of other users.

Fortunately， the cryptographic primitive of proxy re-encryption （PRE）［1］， which enables a proxy to transform a ciphertext under a delegator's public key into anothr ciphertext under the delegatee's public key， without learning anything about the content of the encrypted message， can be used to efficiently address this problem. Specifically， in the above storage outsourcing scenario， Alice uses a PRE scheme to encrypt her data and then upload the ciphertext to the cloud. When she wants to share the data with Bob， she can simply give a re-encryption key to a proxy in the cloud， and then the latter canefficiently transform these ciphertexts into the ciphertexts intended for Bob， who can then decrypt the ciphertext to obtain the plaintext data with his own secret key.

Nevertheless， there still exist some problems which are hard to be tackled with a traditional PRE scheme. Let us take the above cloud-based storage application as an example again. Suppose some of Alice's data are highly sensitive， and she wants to decrypt these ciphertexts only by herself. Unfortunately， in the above scenario， with the re-encryption key， the proxy can transform all of Alice's ciphertexts， including the highly sensitive ones， and thus also Bob can decrypt them by autonomously obtaining these particular contents. To address this problem， conditional proxy re-encryption （CPRE）was introduced in Refs.［2，3］. In a CPRE scheme，generated ciphertexts associated with a certain condition， and the proxy can translate only those ciphertexts satisfying the specified condition. In the above cloud- based scenario， by relying on CPRE，Alice becomes able to control the proxy to transform only non-highly-sensitive ciphertexts.

Although CPRE enables the delegator to implement fine-grained delegation of decryption rights for securing information sharing， it suffers from two limitations. The first is that CPRE cannot guarantee the correctness of the transformation done by the proxy. This is indeed a challenge for the applicability of the proxy re-encryption technology in cloud storage services. For example， in the typical pay-per-use model characterizing cloud computing services， the proxy charges the customer （e.g.， Alice）for the transformation efforts. Thus， for saving time and reducing the computational cost， the proxy might simply return ciphertexts which are not really generated by using the re-encryption algorithm. Unfortunately， existing CPRE solutions do not allow the users to check for such a malicious behavior of the proxy. The second is that common CPRE architectures only involve a single proxy. This inevitably faces with the single point of failure problem: if the proxy is out of service， the delegatees lose their ability to access the data. Thus， new solutions are needed to deal with these CPRE problems.

To address the above limitations， we propose a server-aided access control system， namely the SAAC system. The SAAC system is built upon a variant of CPRE primitive， named threshold conditional proxy re-encryption （TCPRE） primitive. The ciphertext in TCPRE is associated with a specified condition， and the proxies can only successfully transform those ciphertexts satisfying the specified condition. But unlike CPRE， TCPRE involves a number n of proxies and t out of n proxies can successfully transform ciphertexts， while up to t-1 proxies cannot. In addition， the correctness of the transformation done by each proxy can be publicly verified.

We formalize the TCPRE primitive and define the chosen-ciphertext security of TCPRE with respect to two types of ciphertexts （i.e.， original ciphertexts and transformed ciphertexts）. We present three constructions of TCPRE in a ''gradual'' way. The first one is a CPRE scheme， that allows the owner of some data stored in a specific file， to share it through （conditionally） delegating decryption capability. The second construction， based on the first one， adds the support of threshold-based proxy re-encryption to address the single-point-of-failure limitation. The third construction （that is the final one） additionally embeds the capability of verifying the correctness of the re-encryption done by the access control servers， and achieves CCA security. We only provide security and performance analysis of the final construction， that is the most complete one.

2 Preliminaries

We briefly review some preliminaries by first summarizing the notations used in this work， andthen introducing the bilinear map technique， which serves as the foundation of the proposed approach.

2.1 Notations

We denotepZ as the set｛0，1，2，， 1｝p-… and Zas Zp｛0｝. For a finite setS，x ∈ S （or x ∈RS） means choosing an element x from S （with a uniform distribution）. We define the Lagrange coefficientΔi，Sfor i∈ Zpand a set S of elements in Zp:. For a stringm，denotes its bit-length. For all stringsxand y， let ||x y denotes the concatenation ofxand y. A（ x1， x2，…） denotes that A is an algorithm with the input（ x1， x2，…） ， an y= A （x1， x2，…） denotes the running of A （x1， x2，…）with the output y. For AO1（·），O2（·），…（x， x，…） ， it 12 means that A is an algorithm with the input（x1， x2，…） and can access to the oracles O （·），O （·），…. By y= AO1（·），O2（·），…（x， x，…）， we 1212 denote the running of AO1（·），O2（·），…（x， x，…）with the 12 output y.

Besides， we briefly summarize the notations in Table 1 that will be used in the following.

Table 1 Notations used in proposed system

2.2 Bilinear Maps

A Bilinear Map is a common tool used for designing cryptographic primitives. In this subsection，we give the definition of the bilinear map， which will be used in this paper.

Definition 1 Bilinear Map

DenoteG，TGas cyclic groups of prime order p， writing the group action multiplicatively. g is a generator of G. Let e: G × G → GTbe a map with the following properties.

2） Non-degeneracy: There exists12，g g G∈ such thate （ g1， g2）≠ 1， in other words， the map does not send all pairs in G G× to the identity inTG.

3） Efficiency: There exists an efficient polynomial time algorithm to compute the bilinear map

3 System model

3.1 The architecture

As shown in Figure 1， we consider three types of entities in our access control system.

Figure 1 Access control system architecture

1） The Cloud， that is the entity providing outsourced storage facilities. It is in charge of controlling the accesses from outside users to the data，stored by using specific servers that provide the corresponding content delivery services. In this paper， we assume that the cloud storage service provider （S-CSP） is always online and has unlimited storage capacity.

2） The users of the storage services， whose data are structured into files. For each file， we consider two types of users. The former is the owner， who decided to outsource his data into the cloud servers for storing and making them accessible in a controlled way. The latter one is the generic file user that， according to the permissions granted by theowner， want to access some of the outsourced data files by relying on specific access control servers.

3） Multiple access control servers working as proxies and providing security services. More specifically， they transform the ''raw'' ciphertexts into ''selectively decryptable'' ones， so that only authorized users can decrypt them and then gain access to private contents.

It is worthwhile noting that， this type of architecture has several advantages. ① it does not involve any computational process， being deployed according to a thin cloud paradigm， just providing the LIST， PUT and GET interfaces［4］. It also brings the benefits of portability and easy provider switching. ② Compared with the previous work［5］， we introduce multiple access control servers， not only balancing the computational burden， but also removing the presence of single points of failure.

3.2 System overview

Next， we give an overview of the proposed access control system. There are three phases involving its activity.

1） System setup. In this phase， the system parameters are initialized. Users are assigned their secret keys， and the access control servers are given the global private parameters.

2） File outsourcing. When a file owner wants to outsource a file for storage， he/she encrypts and uploads the file to cloud.

3） File access. When a file user wants to access an outsourced file， he/she firstly downloads the cipher text， requests access permission from file owner， and decrypts the cipher text with the help of access control servers.

3.3 Threat model and security goal

Based on the architecture proposed above， we have three threat assumptions. 1） The channels（connecting users to cloud and access control servers） can be public， and the data transferred by using these channels might be eavesdropped by outside attackers. 2） The cloud and access control servers are ''honest-but-curious''. They follow the proposed protocol， but try to extract as much secret information as possible. 3） Some users might be compromised. We note that， this threat model is stronger than the one already proposed in［5，6］， which also considers the access control problem in cloud. More specifically， a fully trusted authority is assumed to exist in Refs.［6］， becoming a single-point-of-failure if it is compromised， while we do not need to ''put all the eggs in a single basket''. In addition， the private key channel is assumed to be private in Refs.［6］， but we do not need this assumption.

The security goal considered in this paper is providing semantic security under chosen ciphertext attacks （SS-CCA）. In other words， it requires that any useful information about the private data stored into files， cannot be extracted by attackers， even if they have chances to access one or more known ciphertexts/plaintexts into the system and obtain the resulting plaintexts. Thus， it differentiates from the previous works［5，6］which only achieve the same security goal for the （weaker） chosen plaintext attacks.

4 System framework

In order to realize the SAAC system， we introduce a new primitive， named threshold conditional proxy re-encryption （TCPRE）. In what follows， we will present the formal definition of TCPRE and show how it is used to construct the SAAC system in section 3.

4.1 Threshold conditional proxy re-encryption

Before formalizing the definition for TCPRE，we first give a brief overview for TCPRE in the literature of proxy re-encryption. As with conditional proxy re-encryption， a TCPRE-based system runs the global setup algorithm Setup to generate the global parameters param， and each user runs the key generation algorithm KeyGen to generate his/her public/secret key pair. The ciphertext is also generated with respect to a specified condition by using the encryption algorithm Encrypt. Unlike CPRE， the user in TCPRE can designate a numbernof proxies.The user can generate n re-encryption key shares and verification key shares with the ReKeyGen algorithm. Each re-encryption key share is kept secret by a proxy， and all the verification key shares are made public. By running the ReEncShare algorithm，the proxy can generate a re-encryption share， whose validity can be publicly verified by the ShareVerify algorithm. With the ShareCombine algorithm， at least t valid re-encryption shares can be used to generate a valid transformed ciphertext， which can then be decrypted by the delegatee.

Formally， a TCPRE scheme consists of the following algorithms.

1） Setup（k）: The global setup algorithm taking as input a security parameterk， and generating the global parameters param.

2） KeyGen（param）: The key generation algorithm taking as input the global parameters param，and generating user's public and secret key pair（pki， ski）.

3） ReKeyGen（ski， pkj，w， t， n）: The re-encryption key generation algorithm taking as input the delegator's secret keyisk， a delegatee's public keyjpk， a conditionw， a threshold t and a numbernof proxies. It generates nshares of the re-encryption keysand verification keys

4） Encrypt（pki， m， w）: The encryption algorithm taking as input user's public keyipk， a messagemand a conditionw. It returns an original ciphertextict.

Suppose a TCPRE scheme has been initialized asandThe correctness of TCPRE requires that， for any messagemand conditionw， the following equations hold

We explain these equations below. Equation （1）defines the consistency of the original ciphertext. It requires that the ciphertext encrypted with the i-th user's public key must be decrypted by using his/her secret key. Equation （2） defines the verifiability on encryption share: the correctness of each re-encryption share computed from a ciphertext can be verified only by using its corresponding verification key share. Equation （3） defines the consistency of transformed ciphertext: the ciphertext transformed from original ciphertext can be decrypted by using the delegatee's secret key.

4.2 Generic construction

Based on the definition of TCPRE， we give a generic construction of our SAAC system. Note that in the generic construction， all the algorithms involved in TCPRE are used as black boxes， the realization of which will be explained later.

1） System setup. In order to initialize the system， a security parameterkand the numbernof proxies are chosen. The global setup algorithmSetup（ k） of TCPRE is run to produce the parameters param. For each user in the system， the key generation algorithm KeyGen（ pa ram） of TCPRE is used to assign him/her a pair of public and private key（pki， ski）. The secret key skimust be kept secret and the public keyipkcan be published.

2） File outsourcing. Suppose that a file f is to be uploaded by the i-th user. This user randomly pick a symmetric keykto encrypt f. Then he/she runs the encryption algorithm Encrypt（ pki， k， w）to compute the TCPRE ciphertextictofkin respect towwhich describes the condition with respect to f. Finally， the file ciphertext， key ciphertext， file identifier and the user identity are sent to cloud for storage.

3） File access. Any user can use the LIST operation to list the names of files in the cloud. For each needed file owned by user i， the generic userjdownloads the key ciphertextictand file ciphertext. The user takes the identifier of this file to request access permission from the owner. The file owner （the i-th user） runs the re-encryption key generation algorithm ReKeyGen（ ski， pkj，w， t， n ）of TCPRE and responds with the set of re-encryption key sharesand verification key shares. Notice that the thresholdtshould be chosen flexibly by the file owner for reliability consideration.

5 TCPRE constructions

From Section 4， we have learn how to leverage TCPRE （as a black box） to build the SAAC system. In this section， we will get into the black box of TCPRE and present several constructions. For better understanding， we use an incremental approach by providing our constructions in a ''gradual'' way. Our first construction is just a Conditional Proxy Re-Encryption （CPRE） scheme. Our second construction， based on the first one， adds the support of threshold-based proxy re-encryption. Our third construction （the final， and more complete one） additionally embeds verifiability on the re-encryption shares， and achieves CCA security.

5.1 First construction

The first construction， related to CPRE facilities， is a special case of the more general definition of TCPRE presented in section 4.1. Specifically，here we fix the number of access control servers 1n= and the threshold value 1t= . Also， since we neither study verifiability nor allow multiple shares， the algorithms ShareVerify（·）and ShareCombine（·） are not considered.

We give our first construction as follows.

1） Setup（ k ）:Given a security parameterk， choose bilinear map groups（G， GT）of prime order 2kp＞ ， and pick the generatorRg G∈ . In addition， define the hash functions. The global parameters are set to

2） KeyGen（ pa ram） :To generate a public and secret key pair for useri， the key generation algorithm picks， and setsand

3） ReKeyGen（ ski， pkj，w） :Starting from the delegator's secret keyisk， the delegatee's publickeyjpk and a conditionw， the re-encryption key generation algorithm randomly picksRZ α ∈and returns the re-encryption key

① If the input is an original ciphertext

② If the input is a transformed ciphertext， compute

The correctness of this construction can be verified by computing.

5.2 Second construction

The second construction is based on the first one， but involves multiple access control servers for supporting threshold-based proxy re-encryption. The basic idea is to use Shamir's secret sharing［7］on the re-encryption key rkijto generate n re-encryption key shares. Each re-encryption key share is used by an access control server for proxy reencryption. At least t re-encryption shares are then collected and used for re-constructing the transformed ciphertext. We present the re-written ReKeyGen（·）， ReEncShare（·） and the newly introduced ShareCombine（·） algorithms as follows.

1） Re KeyGen（ ski， pkj，w， t， n） :Such algorithm takes the following steps.

①For each index v ∈ S'where S'= ｛1，2，…，t- 1｝， pick αv，βv∈RZand set the v-th re- encryption key share to be. This implicitly defines a polynomial

②For each remaining index ｛， 1，v t t∈ + t + 2，… ，n｝， pick a random variable βv∈RZand set the v-th re-encryption key share to be

③Finally return the set of re-encryption key shares

It finally returns the transformed ciphertext

The correctness of this construction could be easily verified through equation （4） and equation （5）. Thus it is omitted here.

5.3 Final construction

To achieve the goal of SS-CCA， we need to further embed the ''authentication code'' in ciphertext. This is because most （or maybe all） CCA attacks rely on the attackers' modifying the challenge ciphertext and then feeding it to the decryption oracle. The answer of the decryption oracle will enable the attacker to tell which message is encrypted. If an authentication code is put on top of the encryption，disallowing the attacker to fiddle with the ciphertext，then it essentially renders the decryption oracle useless. Following this intuition， we present the final construction for achieving CCA security （the KeyGen（·） is the same as in previous constructions， so it is omitted here）.

1） Setup（ k ）:The setup algorithm is identical to the same one presented in the first construction（see section 5.1） except that the hash functions in the global parameters param are initialized as:

2） ReKeyGen（ ski， pkj，w， t， n ）:Unlike the algorithm with the same name， presented in the first two constructions， the re-encryption key generation algorithm returns a set of re-encryption key sharesand verification key shares. In detail， it performs the following steps.

①For each index v ∈ S'where S'= ｛1，2，…，t- 1｝， pickαv，βv∈RZand set thev-th re-encryption key share to be. As in the previous construction， this way implicitly defines the polynomialMoreover， compute the verification key share

③ Finally output the set of re-encryption key sharesand verification key shares. Note that the validity of each re- encryption key sharecould be checked by verifying the equation

3） Encrypt（ pki， m， w） :The encryption algorithm takes input a plaintext， a public keyand a conditionw. It picksand computes. Finally returns， where

①Check the validity of the original ciphertextictby verifying the equations:. We note that ifictis a valid original ciphertext， the two equations above hold， since

③Finally output the v -th re-encryption share

①If the input is an original ciphertext: check whether the equationsand hold （as in the validity checking in ReEncShare（·）algorithm）. If both the conditions are positively verified computefollowing the same strategy of Decrypt（·）， in the second construction. Further， check whetherholds. Finally returnm.

②If the input is a transformed ciphertext: computein the same way of Decrypt（·） in the second construction. Then check whetherholds. Finally return m.

The consistency of original and transformed ciphertext could be easily checked in a similar way by using equation （4） and equation （5）.

6 Security analysis

In this section we analyze the security of the SAAC solution proposed in section 4.2. In what follows， we at first model the capabilities of attackers against the SAAC system. Then， we formalize two security definitions， original ciphertext security （IND-oCCA） and transformed ciphertext security （IND-tCCA）， associated to TCPRE. Finally we prove that the final TCPRE scheme presented in section 5.3 achieves both the security definitions.

6.1 Threat capabilities

We simplify the data flow of the proposed SAAC system as sketched in Figure 2. Notice that we omit the encrypted file content because it is protected by symmetric-key encryption， which is as-sumed to be secure if the symmetric encryption key is not leaked.

Figure 2 Data flow in server-aided access control system

Initially， the i -th user uploads the ciphertextictto cloud. Later， the j-th user downloads the ciphertextictand sends an access request to the owner （i.e.， the i -th user）. The file owner responds with a set of re-encryption keysthat would be forwarded along with the ciphertextictto the access control servers for re-encryption. After re-encryption by each access control server， the re-encryption shares are sent back to the j-th user for combination and decryption.

We point out that these data including the original ciphertextict， the re-encryption key shareand the re-encryption share， are transferred by using public channels and hence can be eavesdropped by attackers. For analyzing semantic security， we model these leakages （as threat capabilities against our system） in the following oracles. Notice that since the original ciphertextictcan be easily computed by using the user's public key， we omit modeling it as an oracle.

1） Re-encryption key share oracle. This oracle models the attackers' capabilities of eavesdropping the key shares on the channels from users to access control servers. Starting from the in-with 1 t n≤ ≤ and U⊆｛1，2，，｝n… this oracle runsand returnsand. Notice that the set Uhere models the set of channels from users to the access control servers eavesdropped by attackers.

2） Re-encryption share oracle. This oracle models the attackers' capabilities of eavesdropping the shares on the channels from access control servers to the users. Starting from the inputswith t n≤ and V⊆｛1，2，，｝n… ， this oracle runs. Also in this case， the set Vmodels the set of channels from access control servers to users eavesdropped by attackers.

We further strengthen threat capabilities by considering corrupted users and CCA model and defune three oracles below.

1） Uncorrupted key generation oracleThis oracle models the common users which can publish their public keys. With each useri， this oracle runs thealgorithm and obtains a public and secret key pair. Finally it returns the public keyipk.

2） Corrupted key generation oracle. This oracle models the corrupted users which have been intruded by attackers. For each useri， this oracle runs thealgorithm and obtains a public and secret key pair. Finally return the

6.2 Security definitions of TCPRE

Based on the threat capabilities formalized in the previous subsection， we define the semantic security of TCPRE， which captures the spirit of indistinguishability of both original and transformed ciphertext. Formally， we respectively formalize the security notions asIND-oCCA （for the security of original ciphertext） and IND-tCCA（for the security of transformed ciphertext）.

The above security definitions are verified by using specific experiments involving an adversary A. The adversary runs infindandguessstages. We give the experimentfor IND-oCCA as follows.

In theIND-oCCAexperiment， the （）Setup· algorithm is initially executed to generate the global parameters param. Next， A executes thefindstage. Specifically， it takes as its input the parameters param， accesses several oracles and returns the challenge messages01，m mas well asipkand*w. For these oracles， we have two requirements.

1） For a public keyjpk generated fromuO， one of them would be selected asfor generating output. Further， if A has issued the queriesand*，，w twith， then A cannot issue the querysuch that， where n is the number of proxies and t is the threshold.

2） For a public keyjpk generated fromcO， A cannot issue these queries， or，*，，w twith

We define A's advantage in theIND oCCA-experimentas

and formalize the IND oCCA- security as follows.

Definition 2 IND oCCA- Security

Similarly， we give the experimentfor IND tCCA- as follows.

We define A's advantage in the IND tCCA-experiment

and formalize the IND tCCA- security as follows.

Definition 3 IND tCCA- Security

A TCPRE scheme is said to be- secure， if for any t-time adversary A who asks at mostandqueries to oraclesandrespectively， we have

6.3 Security proof of TCPRE

We now turn to analyze the security of the final scheme presented in section 5.3 against Definition 2 and Definition 3. We firstly introduce a newcomputational problem， and show that it is equivalent to the weak Decisional Bilinear Diffie-Hellman Inversion （wDBDHI） problem investigated in［8］. Then， we prove that the final scheme is secure under the assumption that the newly introduced problem is intractable.

We describe both assumptions as follows.

Definition 4 q-wDBDHI Problem

Definition 5 New Problem

We present the following theorem to demonstrate the equivalence of the problem defined in Definition 5 and the q-wDBDHI problem.

Theorem 1 The problem defined in Definition 5 is equivalent to the wDBDHI problem.

Proof: Suppose there exists a q-wDBDHI problem solver S which can solve the q-wDBDHI problem in polynomial time. We then describe how to construct an algorithm leveraging S to solve the new problem introduced in Definition 5.

For the inverse implication， we suppose the existence of a solver S for the problem formalized in Definition 5. We then describe how to use S to solve the q-wDBDHI problem.

From Theorem 1， we can see that the introduced new problem is equivalent to the wDBDHI problem， for which the best known algorithm is to solve the standard Discrete Logarithm Problem（DLP）［9］. Thus we can present the following theorems （based on the intractability of the introduced problem） to demonstrate the IND-oCCA security of the final scheme in section 4.3.

Theorem 2 The proposed final scheme in section 5.3 is IND-oCCAsecure in the random oracle model， assuming our introduced problem is intractable in groups

Proof: Suppose that the algorithm B receives as input a challenge tuplewith unknownB's goal is to decide whether. For this purpose， algorithm B sets the parameters and plays the IND-oCCAexperiment with adversary A in the following way.

In the IND-oCCAexperiment， B gives the global parameterstoA. Hereare the random oracles controlled by B and can be adaptively asked by A at any time. B maintains 4 hash listsiL for， which are initially empty. B respondsto the random oracle queries from A as follows.

When operating in its find stage， A issues a series of queries as in the IND-oCCA experiment. B maintains listsand， which are initially empty.B answers these queries issued by A as follows.

Case

ReKeyGen（·）. Then it stores the tupleinandin. Finally it returnsandto A.

stores

① If there does not exist the tupleinorin， algorithm B first generates these re-encryption key shares and verification key shares.

② Search whether there exists a tuplesuch thatIf it does not， B generates a random bitand aborts.

5）

① ctiis an original ciphertextsearch the list3L to see whether there exists a tuple （，'）m r such thatandIf yes， return mtoA； otherwise B returns⊥.

②ictis a transformed ciphertext searchto see whether there exists a tuplein3L such that. If yes return mto A； otherwise return⊥.

When A decides that the initial stage is over，it emits a target public keyand two equal-length messages. AlgorithmB responds as follows. ① Recover tuplefrom theskL and tuplefrom1L， where*i corresponds to the index i of. If， generate a random bitand abort. Otherwise， it meansthat. ② Flip a random coinand pick. Define. ③ Issue a query ofto oracleto obtain the tuple. Defineand finally giveto A. Note that in the above construction， ifis indeed a valid ciphertext forunderandOn the other hand， if Z is uniform and independent inTG ， the challenge ciphertextis independent of δ in the adversary's view.

A continues to issue the rest of queries， with the restrictions described in theIND-oCCA experiment. Algorithm B responds to these queries as in the initial stage. Eventually， adversary A returns a guesstoB. If， B outputs 1b= to guess； otherwise， B outputs 0b= to guess that Z is a random element in groups

Theorem 3 The final scheme presented in Section 5.3 is IND-tCCA secure in the random oracle model， assuming the 1-wDBDHI problem is intractable in groups

Proof: Suppose B is given as input a 1 -wDBDHI challenge tuplewith unknown. Algorithm B's goal is to decide whether. Algorithm B acts as challenger and plays the IND-tCCA game with adversaryA in the following way.

In A's find stage， A issues a series of queries as in the IND-oCCA experiment. B maintains listsand， which are initially empty， and answer these queries for A as follows.

When A decides that the initial stage is over， it outputs two public keys pkiand pk， a condition w*and two equal-length messagesAlgorithm B responds as follows. ① Recover tuplefrom Lsk. ② Flip a random coinand pick. ③ Define. ④ Finally， giveto A.

Note that by the above construction， if，*ct is indeed a valid transformed ciphertext for mδunder pk. On the other hand， when Z is uniform and independent inTG ， the challenge ciphertext*ct is independent of δ in the adversary's view.

A continues to issue the rest of queries as in initial and find Stage， with the restrictions described in experimentIND tCCA- . Algorithm B responds to these queries as described above. Eventually， adversary A returns a guess δ'∈ ｛0，1｝ to B. If δ' = δ， B outputs 1 to guess； otherwise， B outputs 0 to guess that Z is a random element in groupTG.

7 Performance analysis

In this section， we at first analyze the computational complexity of the core scheme in SAAC， and then present an experimental simulation assesing its performance.

During the system setup phase， the basic operating parameters are initialized. The main computation overhead for Initialization is introduced by the s modular exponentiations in G， needed for generating each user's public key， where s is the number of users in the system.

The main computation overhead characterizing the filestorage operations， outsourced on the cloud，is the encryption of the file performed by using the symmetric-key encryption as well as the encryption of the symmetric encryption key involving TCPRE. The complexity of the former one depends on the size of the underlying file. The overhead for the latter consists of four modular exponentiations （in particular， three of them are in G while one is in GT）.

Regarding file access， most of the operations are carried out by the file owner， as well as by the requesting user and the involved access control servers. In particular， the file owner executes the ReKeyGen（·）algorithm to generate the re-encryption key share for each access control server， which represents 5n modular exponentiations inG ，where n is the number of access control servers involved； each access control server executes the ReEncrypt（·） algorithm to produce a re-encryption share， which costs 3 exponentiations inG， the requesting user combines at least t shares together to get the re-encrypted ciphertext for the involved file， and finally decrypts this ciphertext. The accessing user's computation overhead includes 2t bilinear pairings and t modular exponentiations in GTfor ShareCombine（·）， and one modular exponentiation in GTfor Decrypt（·）.

We summarize the main computational overhead of our proposed SAAC in Table 2， whereGE andTGE respectively denote the modular exponentiation in G andTG ， P denotes the bilinear pairing operation，1ξand2ξ respectively denote the computational complexity for encrypting and decrypting the file f， both of which depend on its size. Notice that in this analysis， we omit the additional computation needed for verifying the correctness of the original data stored in the file since it does not concern our specific access control framework.

Table 2 Computational overhead in SAAC

To be more clear on the overall efficiency of the proposed framework， we simulated its core scheme （in particular， the TCPRE scheme） according to the considerations reported in Table 2 The simulation， run on a Mac OS X laptop equipped with an 1.7 GHz Intel Core i7 processor and 8 GB 1 600 MHz DDR3 memory， uses the Pairing-Based Cryptography library［11］to implement both the users and access control servers activities. We did not consider time measurements for file encryption and decryption operations， since encrypting and decrypting files with symmetric-key encryption in anIND-CPA secure way was a well studied problem for which plenty of performance data was available. Furthermore， some clients may be equipped with highly specialized hardware for accelerating symmetric-key encryption operations.

Figure 3（a） shows the simulated efficiency in terms of system setup in the cases of 10，30，50，70，90 and 100 users in system. We can observe that the elapsed time is limited by 250 ms even for the maximum number （i.e.， 100in this case） of users. Regarding the outsourced file storage operations，we simulated the average cloud access time as 8.202 ms. Figure 3（b） describes the simulated efficiency for file access by varying the number n of access control servers and the threshold valuet. The total elapsed time is limited by 100 ms.

8 Related work

In 1997， Mambo and Okamoto［12］initially introduced the concept of delegation of decryption rights， as a better-performance alternative to the trivial approach of decrypting-then-encrypting of ciphertexts. In Eurocrypt'98， Blaze et al.［1］introduced the concept of proxy re-encryption， and presented the first bidirectional PRE scheme. Ateniese et al.［5］presented unidirectional PRE schemes that are secure against chosen-plaintext attacks （CPA）.

Figure 3 Time cost in simulation

The first chosen-ciphertext secure bidirectional PRE schemes and unidirectional PRE scheme were proposed by Canetti et al.［14］and Libert et al.［14，15］respectively， and both schemes rely on the bilinear pairings. Deng et al.［16，17］proposed a CCA-secure bidirectional PRE scheme without pairings. Shao et al.［18］tried to propose a unidirectional PRE scheme without pairings that was improved later by Chow et al.［19］Subsequently， several bidirectional and unidirectional PRE schemes have been proposed in Refs.［20～23］. Proxy re-encryption has also been studied in identity-based scenarios， such as the Refs.［24～26］.

Several variants of PRE have also been proposed in the past few years. Libert et al.［27］introduced the notion of traceable proxy re-encryption，in which a proxy who leaks its re-encryption key can be identified by the delegator. Ateniese et al.［28］also introduced the concept of key-private proxyre-encryption， in which the anonymity of the sender and receiver's identities can be protected. In TCC'12，Chandran et al.［29］introduced the notion of functional re-encryption， which can transform an encryption of a message m under an ''input public key'' pk into an encryption of the same message m under one of the n ''output public keys''，namely the public key index by function （）F m. Conditional proxy re-encryption （CPRE） was introduced in Ref.［2，3］. In a CPRE scheme， ciphertexts are generated associated with a certain condition，and the proxy can translate those ciphertexts satisfying the specified condition.

In this work， the core of the proposed SAAC system is the TCPRE scheme， which significantly improves the existing works［2，3］by quipping the capabilities of guaranteeing the correctness of transformations done by proxies.

9 Conclusion

Aiming at addressing the security and privacy issues in file outsourcing， we propose a server-aided access control system， namely SAAC. It is based on a new proxy re-encryption primitive， namely TCPRE. Compared with traditional CPRE， TCPRE enjoys two features: 1） TCPRE involves a number nof proxies where t out of n proxies can successfully re-encrypt ciphertexts， while up to t-1 proxies cannot； 2） The correctness of re-encryption done by each proxy can be publicly verified. We ''gradually'' provide three TCPRE constructions， and prove that the security of our final construction could be reduced to a new problem which is at least as strong as the wDBDHI problem. The performance of TCPRE construction has been analyzed as well， through simulation， by resulting in a limited overhead also in presence of a large number of users for each single outsourced file.

References:

［1］ BLAZE M， BLEUMER G， STRAUSS M. Divertible protocols and atomic proxy cryptography［C］//The International Conference on the Theory and Applications of Cryptographic Techniques. Berlin Heidelberg，1998:127-144.

［2］ WENG J， DENG R H， DING X， et al. Conditional proxy re-encryption secure against chosen-ciphertext attack［C］//The 4th International Symposium on Information， Computer， and Communications Security， ACM. 2009: 322-332.

［3］ TANG Q. Type-based proxy re-encryption and its construction［C］//The International Conference on Cryptology in India. 2008:130-144.

［4］ VRABLE M， SAVAGE S， VOELKER G M. Cumulus: filesystem backup to the cloud［J］. ACM Transactions on Storage （TOS）， 2009，5（4）: 14.

［5］ ATENIESE G， FU K， GREEN M， et al. Improved proxy re-encryption schemes with applications to secure distributed storage［J］. ACM Transactions on Information and System Security（TISSEC）， 2006， 9（1）: 1-30.

［6］ LI J， CHEN X， LI J， et al. Fine-grained access control system based on outsourced attribute-based encryption［C］//European Symposium on Research in Computer Security. 2013: 592-609.

［7］ SHAMIR A. How to share a secret［J］. Communications of the ACM， 1979， 22（11）: 612-613.

［8］ BONEH D， BOYEN X， GOH E J. Hierarchical identity based encryption with constant size ciphertext［C］//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2005: 440-456.

［9］ Final report on main computational assumptions in cryptography［EB/OL］. http://www.ecrypt.eu.org/documents/D.MAYA.6.pdf，2013.

［10］ CORON J S. On the exact security of full domain hash［C］//Annual International Cryptology Conference. 2000: 229-235.

［11］ Pairing-based cryptography library［EB/OL］. http://crypto. stanford. edu/pbc/.

［12］ MAMBO M， OKAMOTO E. Proxy cryptosystems: delegation of the power to decrypt ciphertexts［J］. IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences，1997， 80（1）: 54-63.

［13］ CANETTI R， HOHENBERGER S. Chosen-ciphertext secure proxy re-encryption［C］//The 14th ACM conference on Computer and Communications Security. 2007: 185-194.

［14］ LIBERT B， VERGNAUD D. Unidirectional chosen-ciphertext secure proxy re-encryption［J］. IEEE Transactions on Information Theory， 2011， 57（3）: 1786-1802.

［15］ LIBERT B， VERGNAUD D. Unidirectional chosen-ciphertext secure proxy re-encryption［C］//International Workshop on Public Key Cryptography. 2008: 360-379.

［16］ WENG J， DENG R H， LIU S， et al. Chosen-ciphertext secure bidirectional proxy re-encryption schemes without pairings［J］. Information Sciences， 2010， 180（24）: 5077-5089.

［17］ DENG R H， WENG J， LIU S， et al. Chosen-ciphertext secure proxy re-encryption without pairings［C］//International Conference on Cryptology and Network Security. 2008: 1-17.

［18］ SHAO J， CAO Z. CCA-secure proxy re-encryption without pairings［C］//International Workshop on Public Key Cryptography. 2009:357-376.

［19］ CHOW S S M， WENG J， YANG Y， et al. Efficient unidirectional proxy re-encryption［C］//International Conference on Cryptology in Africa. 2010: 316-332.

［20］ WENG J， ZHAO Y， HANAOKA G. On the security of a bidirectional proxy re-encryption scheme from PKC 2010［C］// International Workshop on Public Key Cryptography. 2011: 284-295.

［21］ HANAOKA G， KAWAI Y， KUNIHIRO N， et al. Generic construction of chosen ciphertext secure proxy re-encryption［C］// Cryptographers' Track at the RSA Conference. 2012: 349-364.

［22］ WENG J， CHEN M， YANG Y， et al. CCA-secure unidirectional proxy re-encryption in the adaptive corruption model without random oracles［J］. Science China Information Sciences， 2010， 53（3）: 593-606.

［23］ MATSUDA T， NISHIMAKI R， TANAKA K. CCA proxy re-encryption without bilinear maps in the standard model［C］// International Workshop on Public Key Cryptography. 2010: 261-278.［24］ GREEN M， ATENIESE G. Identity-based proxy re-encryption［C］// Applied Cryptography and Network Security. 2007: 288-306.

［25］ MATSUO T. Proxy re-encryption systems for identity-based encryption［C］//International Conference on Pairing-Based Cryptography. 2007: 247-267.

［26］ CHU C K， TZENG W G. Identity-based proxy re-encryption without random oracles［C］//International Conference on Information Security. 2007: 189-202.

［27］ LIBERT B， VERGNAUD D. Tracing malicious proxies in proxy re-encryption［C］//The International Conference on Pairing-Based Cryptography. 2008: 332-353.

［28］ ATENIESE G， BENSON K， HOHENBERGER S. Key-private proxy re-encryption［C］//Cryptographers' Track at the RSA Conference. 2009: 279-294.

［29］ CHANDRAN N， CHASE M， VAIKUNTANATHAN V. Functional re-encryption and collusion-resistant obfuscation［C］//Theory of Cryptography Conference. 2012: 404-421

About the authors:

WENG Jian（1976-）， born in Guangdong. In 2008， he received his Ph.D. degree in Computer Science and Engineering from Shanghai Jiaotong University. Currently， he is a professor and vice dean with the School of Information Technology， Jinan University. His research interests include cryptography and information security.

WENG Jiasi（1994-）， born in Guangdong. She is a master in Jinan University. Her research interests include cryptography and information security.

LIU Jianan（1992-）， born in Henan. He is a Ph.D student in Jinan University. His research interests include cryptography and information security.

HOU Lin （1991-）， born in Hubei. She is a Ph.D student in Jinnan University. Her research interests include cryptography and information security.

10.11959/j.issn.2096-109x.2016.00104

date: 2016-07-12， Revised date: 2016-08-23.

WENG Jian， cryptjweng@gmail.com

The National Natural Science Foundation of China （No.61272413， No.61472165）