Quantum-Resistant Multi-Feature Attribute-Based Proxy Re-Encryption Scheme for Cloud Services

1  Introduction

It is worth noting that sensitive data is being shared and held increasingly in the third party, such as AWS, AliCloud, iCloud, etc. In the current era of cloud computing and data protection, fine-grained access management of encrypted data is a crucial requirement. While sharing data in an open, complicated network environment, there is a chance that personal information will be compromised. For example, in telemedicine system, patients have to store the medical data to the cloud server of the hospital, so that medical service personnel can better analyze the health status of patients after downloading from the cloud. While sharing medical data brings about much convenience to patients and medical service personnel in the system, it also causes new privacy and security issues. Medical data usually contains patients’ sensitive information, thus, it is extremely important for patients. In addition, patients would only like the medical data to be obtained by authorized medical service personnel. In an ideal situation, people hope to encrypt data to a semi-trusted cloud service provider for privacy protection purposes. At the same time, the encrypted data can realize data access control and ciphertext selection calculation as well. In other words, a cryptographic mechanism is needed to make sure “who” can access the encrypted data, and that they can get “what” from the encrypted data.

Proxy re-encryption (PRE) [1] is regarded as a particular primitive in public key cryptography that can give flexible data access authorization for encrypted data in accordance with user needs. Additionally, due to the capability of PRE to securely convert ciphertext, this technology has undergone extensive research and has proven to be quite useful in the cloud context. Currently, PRE is widely employed in many areas of the cloud computing environment, including access control, distributed file systems, encrypted mail forwarding systems, spam filtering systems, etc. ABPRE provides a good solution for the above scenarios. A semi-trusted proxy in an ABPRE system having access to a re-encryption key (created by a delegator) can convert ciphertext that satisfies an access policy into another ciphertext for a delegatee that complies with a new access policy. This greatly reduces the overhead of the data encryption process, enhances non-interactive fine-grained access control, and significantly improves efficiency. Users can share or access data securely, and reliably through a semi-trusted cloud computing service provider. It should be noted that in this process, the proxy is unable to obtain anything about the plaintext. Users achieve the goal of sharing data file safely and efficiently in this way. Due to its characteristics, ABPRE is very suitable for cloud storage environment.

1.1 Related Works

In 2011, Boneh et al. [2] put forth the idea of functional encryption (FE), which broke the deadlock of the original “all or nothing” access mode. FE can not only accomplish the objective of fine-grained access control (only users who meet certain policies can decrypt), but also can select ciphertext. Compared with traditional public-key cryptography (PKC), FE has stronger expression ability. Later, the fuzzy identity-based encryption was constructed by Sahai et al. [3], which was also regarded as the original form of attribute-based encryption (ABE). Especially, ABE is a special FE. In an ABE system, the ciphertext and the secrect key correspond to the attribute set and access policy respectively. The user can decode and access the ciphertext via the secret key after the attribute set of the ciphertext fulfills the access policy.

Lattice cryptography is a kind of PKC, which is widely considered to not be threatened by quantum computing. What’s more, the security of lattice cryptography is based on the difficulty of solving lattice problems in the average case. Based on this superior feature, scholars began to focus on the design of the FE schemes on lattice. Boyen [4] realized FE for access structures based on the LWE hardness assumptions in 2013. More specifically, the key-policy attribute-based encryption (KP-ABE) scheme with monotonic access structure was the first ABE scheme on lattice that supported general Boolean expressions. In 2018, Dai et al. [5] first reported their implementation of a lattice-based KP-ABE scheme, which used short secret keys. What’s more, the homomorphism of the public key and the ciphertext was considered in their proposed scheme as well. In 2019, Tsabary [6] constructed a fully secure ciphertext-policy attribute-based encryption (CP-ABE) for t-CNF from LWE. Varri et al. [7] presented a CP-ABE scheme from the lattice. It is noteworthy that their scheme only allowed valid users of the access policy to conduct keyword searches on the encrypted index, but users who were not in the access policy could not obtain documents in the ciphertext. Recently, to realize attribute revocation, Zhao et al. [8] presented a revocable ABE scheme, which can expediently renew users’ attributes to revoke or grant their access rights. Besides, Fu et al. [9] put forward an offline/online CP-ABE, which had better computational performance for mobile device scenario. In the same year, Fu et al. [10] comprehensively summarized various kinds of ABE schemes from the lattice in terms of complexity assumptions, expressiveness, security, efficiency. In addition, they discussed ABE schemes on lattices which were deserving further research.

With the rapid development of cloud storage technology, the problems of data security and sharing have received extensive attention from industry and academia. PRE is an encryption method that can safely convert ciphertext. It allows that a non-completely trusted third party can directly convert the user Alice’s ciphertext into other users’ ciphertext without decryption, which guarantees the privacy and security of the data left with the third party.

The following desired characteristics should be met by a pretty PRE scheme:

•   Proxy transparency: In the transparent PRE scheme, neither the delegator nor the delegatee knows the existence of the proxy, meanings that the ciphertext sent to the delegatee after re-encryption is indistinguishable from the ciphertext originally sent to the delegatee;

•   Non-interactivity: The delegator does not require the assistance of the delegatee or any other third party for the generation of the proxy re-encryption key;

•   Unidirectionality: The non-reliable proxy can only change the ciphertext of the delegator into the ciphertext of the delegatee; Conversely, it cannot change the delegatee’s ciphertext;

•   Multi-use: The non-reliable proxy can also repeatedly re-encrypt the ciphertext that has already been re-encrypted in the unidirectional PRE, as shown in Fig. 1.

Figure 1: Schematic of multi-use PRE

The initial proposal for a lattice-based multi-bit encryption, unidirectional, and multi-use PRE scheme was made by Jiang et al. [11]. They improved the encryption efficiency. Besides, they proved that in the standard model under LWE, the scheme achieved CPA security. In 2016, PRE with multiple properties was put forward by Kim et al. [12]. What’s more, the scheme was key optimality, non-interactivity, unidirectional, invisibility, collusion-resistant and non-transferability. But unfortunately, only in the random oracle model was it demonstrated to be secure. In 2021, Dutta et al. [13] presented the concrete constructions identity-based PRE, which proved both selective and adaptive security. Furthermore, the scheme they came up with satisfied the nature of unidirectionality and anti-collusion. However, fine-grained access control was not supported by the proposed scheme. Therefore, the subsequent research work was aimed at designing a new cryptographic primitive combining ABE and PRE [14,15] in order to meet the requirements.

The ABPRE scheme combines ABE with PRE. This not only ensures that the new encryption scheme has the special conversion property of PRE, but also enables accessing the encrypted data of users who satisfy the access structure. This is achieved by setting up a corresponding access structure. The owner of the data has total authority over the data, while ensuring data confidentiality. Nowadays, ABPRE is widely used in distributed file systems, electronic medical systems, cloud storage services and other scenarios. Li et al. [16] constructed a key-policy attribute-based proxy re-encryption (KP-ABPRE) scheme based on the matrix access structure, but it was difficult to resist quantum attacks. Although lattice-based ABE and PRE schemes have been realized with the continuous development of lattice theory, the ABPRE schemes against quantum attacks have been realized only in the last few years. Therefore, there is less relevant literature about lattice-based ABPRE. Li et al. [17] designed the first ciphertext-policy ABPRE under the LWE assumption. Their scheme only supported the access structure of the AND gate, and the access policy’s expressiveness was relatively weak. To be able to control the proxy’s ability to re-encrypt the original ciphertext, Liang et al. [18] constructed the conditional ABPRE from lattice firstly, which met the requirements of more fine-grained data sharing. However, the schemes of [17] and [18] only satisfied the nature of single-use. This limited the practicality of the scheme. In addition, Susilo et al. [19] constructed an ABPRE that is honest and secure against re-encryption attacks, improving the security of ABPRE. To illustrate the potential of our research, we compare the existing (attribute-based) PRE schemes with our put forward scheme in Table 1.

From the Table 1, we can see that the existing PRE schemes generally have the following obvious problems:

•   The majority of the assumptions underlying current ABPRE scheme research come from traditional number theory. However, these traditional encryption schemes can not resist quantum attacks;

•   The feasibility of the existing PRE schemes is somewhat hampered by the fact that they only meet two or three characteristics. Besides, the proxy is regarded as a semi-trusted party, but there are few restrictive measures to check the legitimacy on the malicious proxy’s activities;

•   At present, most ABPRE schemes expression strategies are limited, which seriously hinders the feasibility of the ABPRE schemes in practical applications.

In summary, it is crucial to create a powerful ABPRE scheme to withstand quantum attacks in cryptography. Fortunately, the lattice-based cryptosystems can effectively resist quantum attacks. Consequently, constructing lattice-based ABPRE schemes with multiple properties has important theoretical significance and broad application prospects.

1.2 Our Contributions

Designing a post-quantum secure ABPRE scheme with a variety of properties under the standard model is a very meaningful research project. Therefore, we constructed an ABPRE scheme based on key-policy with re-encryption verifiability in the research (named KPAB-VPRE):

•   LSSS matrix is adopted to obtain a KP-ABPRE scheme that supports any monotonic policies. The delegator can formulate the corresponding attribute sets and encrypt the message on these attribute sets. Only when the attribute sets on the ciphertext meet the delegatee’s access policy can the ciphertext be decrypted. Our KP-ABPRE scheme uses the access structure constructed by the attribute sets to control the delegatee that can realize the flexible PRE. The delegatee can be one person, one organization or multiple organizations;

•   Taking the activities of corrupt proxy into consideration, the scheme is combined with homomorphic signature technology to realize the verifiability of re-encryption. In other words, during the re-encryption process, our KP-ABPRE with re-encryption verifiability (KPAB-VPRE) scheme can be verified whether the proxy performed an honest re-encryption operation. This property greatly enhances the security of the PRE;

•   In general, few ABPRE schemes can satisfy three or more properties. While, we design a multi-feature KPAB-VPRE scheme with proxy transparency, non-interactivity, unidirectionality multi-use and anti-quantum attack, which can greatly enhance the practicability of the program. What’s more, under the standard model, our KPAB-VPRE scheme is proven to be selectively IND-CPA secure.

1.3 Organization

In order to better obtain an understanding of this article, we introduce the relevant notations in the next Section 2, and briefly discuss some basic knowledge that we use. The definition and security model of the KPAB-VPRE scheme are described in the part of Section 3. Then, we construct a KPAB-VPRE scheme with various properties based on LWE. Besides, the security and properties of KPAB-VPRE are analyzed in Section 4. Furthermore, we also assess the effectiveness of the KPAB-VPRE in comparison to relevant literature in Subsection 4.5. Finally, Section 5 presents the conclusions.

2  Preliminaries

2.1 Notations

In this paper, we apply some initial symbols, as shown in the Table 2. Z and R represent the sets of integers and real numbers, respectively. For a matrix A∈Rn×m, we adopt AT to mark the transposed matrix. What’s more, we shorten algorithm names. For example, ReEncrypt is recorded as re-encryption algorithm.

2.2 Preliminaries

We give the following useful definitions and lemmas according to literature [4,24–27], consisting of lattice, some algorithms, decision LWE, LSSS and HS.

2.2.1 Lattice

Definition 2.1. Given a n×m matrix A=[a1,a2,…,am]∈Rn×m with linearly independent columns a1,a2,…,am∈Rn. The A forms a lattice Λ. Besides, Λ∗ is called dual lattice.

Λ(A)={u∈Rn,  s.t.  ∃s∈Zm,   u=As=∑i=1msiai}(1)

Λ∗={h∈Rm  s.t.  ∃u∈Λ,  hTu=⟨h,u⟩∈Z}.(2)

Lemma 2.1. Set the following parameters, q≥3,m=⌈6nlog⁡q⌉. Then, there exists a probability polynomial time (PPT) algorithm TrapGen(n,m,q,σ), which generates a random matrix A∈Zqn×m and a basis TA∈Zqm×m for Λq⊥(A) meeting the following equation:

‖TA~‖≤O(nlog⁡q),‖TA‖≤O(nlog⁡q).(3)

Here TA~ is the Schmidt orthogonalization matrix of TA, and ‖TA‖ is the Euclidean norm of matrix TA.

Lemma 2.2. We assume that given a prime number q>2, a matrix A∈Zqn×m, σ≥‖T~A‖⋅ω(log⁡m), where TA is the basis of Λq⊥(A). Next, we choose two vectors u∈Zqn and c∈Zm. Then,

•   Pr[x←DΛq⊥(A,σ):‖x‖>σm]≤negl(n), where negl(n) is a negligible function;

•   There exists a PPT algorithm SamplePre(A,TA,σ,u), which makes it output a vector x∈Λqu(A) with statistical properties similar to the discrete Gaussian distribution DΛqu(A),σ,c;

•   There is a PPT algorithm SampleBasisLeft(A,B,TA,σ), which makes it output a set of basis T(A|B) on the lattice Λq⊥(A|B) that is statistically close to the distribution Dσ,Λq⊥(A|B)m;

•   Given three matrices A,G∈Zn×m and S∈Zm×m, TG is a short basis for the lattice Λq⊥(G). Then, there is a PPT algorithm SampleBasisRight(A,G,S,TG,σ), which makes it output a basis T(A|AS+G) for the lattice Λq⊥(A|AS+G) distributed statistically close to the distribution Dσ,Λq⊥(A|AS+G)m.

Lemma 2.3. Given a positive integer n, a prime number q, a matrix A∈Zqn×m, and a vector e∈DZm,σ. We set m≥2nlog2⁡q, σ≥ω(log2⁡m). If so, the distribution of the vector u=Aemodq is statistically close to the uniform distribution on Zqn.

The above lemmas are used in the security proof of our scheme to show that the simulated system is indistinguishable from the real system.

2.2.2 Decision LWEq,Ψ

Definition 2.2. We assume that the positive integers n,m,q∈Z, and set Ψαm be an error distribution on Zqm. Let A and e be uniformly chosen at random from Zqn×m and Ψαm, respectively. Then, select secretly a vector s∈Zqn with uniform distribution. There is a LWE oracle with two algorithms:

•   Os: Outputs the samples (A,b)∈Zqn×m×Zqm according to LWE distribution, where b=ATs+e(modq);

•   O$: Outputs the samples (A,b) from the uniformly random distribution Zqn×m×Zqm.

The attacker 𝒜 could find a solution to the decision LWEq,Ψ problem, if and only if its advantages Adv(𝒜)=|Pr[𝒜Os=1]−Pr[𝒜O$=1]|>negl(n).

2.2.3 LSSS

Definition 2.3. If the following requirements are met by a secret sharing system Π over a group of participants P, we call it LSSS over ZP:

•   Each participant’s shares compose a vector over ZP;

•   The share generating matrix M for Π is a matrix of l rows and θ columns. Additionally, the function ρ is defined by the participant labeling row i as ρ(i) for all the i-th row of M(i=1,2,…,l). Besides, the column vector v=(s,r2,…,rn) is predetermined, where s∈ZP is a secret that is about to be shared, r2,…,rn∈ZP are selected at random. Moreover, M⋅v is the vector of l shares of s in the light of Π. Furthermore, the participant ρ(i) owns the share λi=(M⋅v)i.

In addition, a LSSS has linear reconstruction’s characteristics.

2.2.4 Homomorphic Signature-HS

Lemma 2.4. The HS scheme typically makes up the following four algorithms:

•   HS.KeyGen(λ,d,n): The algorithm returns a pair of keys (hssk,hsvk) by inputting the security parameter λ, the depth d of a circuit, and the message length n.

•   HS.Sign (hssk,m): The algorithm enters hssk and a message m, produces the original signature σ.

•   HS.SignEval(δ,(mi,σi)): The algorithm inputs an evaluation circuit δ:{0,1}N→{0,1}N with maximum depth d, and the pair (mi,σi), outputs an evaluation signature σm′.

•   HS.Verify(hsvk,δ,m′,σm′): The algorithm inputs hsvk, δ, an evaluation massage m′, and an evaluation signature σm′. If verification is successful, returns result 1, otherwise returns 0.

Correctness: The HS scheme is correct if the following equation holds for any λ,d,n,δ, m∈{0,1}n, HS.KeyGen(λ,d,n)→(hssk,hsvk), HS.Sign (hssk,mi)→σi, m′=δ(mi):

Pr[HS.Verify(hsvk,δ,m′,HS.SignEval(δ,(mi,σi)))=1]=1(4)

3  Defnition and the Security Model of KPAB-VPRE

3.1 System Model

Fig. 2 is an illustration of KPAB-VPRE. And in this encryption system, if user 1 and user 2 want to share encrypted data files, they need to execute the following series of algorithms (Setup, KeyGen, Encrypt, ReKeyGen, ReEncrypt, ReEncVer, Decrypt). Especially, an additional verification algorithm ReEncVer, executed by the verification server, is used to determine whether the ciphertext is an honest transformation. First, User 2 sends a sharing request to User 1, and uploads the access policy to the key generation center. Next, the key generation center issues public and private keys to User 1 and User 2, respectively. After receiving the request, user 1 encrypts the data to be shared with its own private key and calculates the re-encryption key. Then sends the original ciphertext and re-encrypted key to the proxy. The proxy re-encrypts the ciphertext with the re-encryption key and sends the re-encryption ciphertext to the verification server. The verification server sends the re-encrypted ciphertext to User 2 after judgment. Finally, User 2 decrypts the shared data of User 1 by its private key.

Figure 2: The system model of our proposed KPAB-VPRE

Definition 3.1. The following seven algorithms make up a KPAB-VPRE scheme:

•   Setup(1λ,𝒰): Inputs a security parameter 1λ and an attribute domain 𝒰, then the algorithm returns the public parameters pp and the master key msk.

•   KeyGen(pp,msk,P): Inputs the parameters pp generated by Setup and an access policy P on an attribute domain 𝒰 to return the secret key sk.

•   Encrypt(pp,m,Att): Enters pp, message m and an attribute set Att on the attribute domain 𝒰 to return the original ciphertext C1.

•   ReKeyGen(pp,sk1,Att′): Enters pp, sk1 and a new attribute set Att′ to return the re-encryption key rk1→2.

•   ReEncrypt(pp,rk1→2,C1): Enters pp, rk1→2 and the original ciphertext C1, if Att′⊨P, outputs the re-encrypted ciphertext C2; otherwise, outputs the symbol ⊥.

•   ReEncVer(pp,hsvk,C1,C2): Enters pp, hsvk, the ciphertext C1 and C2, if C2 is correctly converted from C1, outputs the result 1, which means the verification is passed; otherwise, outputs 0.

•   Decrypt(pp,sk,C): Enters pp, sk and Ci(i=1,2), then returns the message m. Note that

(i)   For the original ciphertext C1, enters the user 1’s secret key sk1. Finally, decryption successfully returns m; otherwise, the error mark ⊥ is output.

(ii)   For the converted ciphertext C2, inputs another user 2’s secret key sk2. After that, the decryption successfully outputs the underlying message m; otherwise, the error mark ⊥ is output.

Correctness: For parameters λ,m,Att∈𝒰, if the attribute sets satisfy the access policy, then a correct KPAB-VPRE scheme should meet the following Eqs. (5)–(7) requirements:

Decrypt(pp,sk1,Encrypt(pp,m,Att))=m(5)

Decrypt(pp,sk2,ReEncrypt(pp,rk1→2,C1))=m.(6)

Pr[ReEncVer(pp,hsvk,C1,C2)=1]=1.(7)

3.2 Security Model

In the part, we mainly describe the security model of KPAB-VPRE, which is based on the indistinguishability under chosen-plaintext attack in the selective security model (IND-sCPA). And we illustrate the model through the interactive games between the adversary 𝒜 and the challenger 𝒞. First, we input the security parameter λ, an attribute domain 𝒰={Att1,Att2,…,Attl}, where Atti={atti1,atti2,…,attit}, (t≤l). Then, the game is comprised of 𝒜’s operations and the following oracles (𝒪sk,𝒪rk,𝒪rv), which could be called more than once in any order. Besides, the following is the interaction process between them:

•   Target. The adversary 𝒜 initially chooses a set of target attributes Att∗ to challenge.

•   Instance. The adversary 𝒜 receives the system settings as a consequence of the challenger 𝒞’s execution of the Setup algorithm.

•   Phase 1. The adversary 𝒜 is allowed to perform the following inquiries multiple times:

(i)   Secret Key Query 𝒪sk: The attacker 𝒜 sends the access policy P to a challenger 𝒞 for secret key queries 𝒪sk. However, the target attribute Att∗ on P cannot be queried. Finally, the challenger 𝒞 calls the secret key generation algorithm KeyGen(pp,msk,P) to return the generated users’ secret key sk to 𝒜.

(ii)   Re-Encryption Key Query 𝒪rk: The adversary 𝒜 initiates 𝒪rk to the challenger 𝒞. When the challenger 𝒞 receives the query, first runs the private key generation algorithm KeyGen(pp,msk,P) to generate sk, and next carries out the ReKeyGen(pp,sk,Att′) algorithm to sends rk1→2 to 𝒜.

(iii)   Re-Encryption Verification Query 𝒪rv: After receiving the converted ciphertext C2, 𝒞 needs to access the oracle 𝒪rv and implement an algorithm ReEncVer(pp,hsvk,C1,C2) to check whether the C2 is legal.

•   Challenge. First, 𝒜 chooses two plaintext messages m0 and m1 of equal length. Next, sends them to 𝒞. After 𝒞 obtains two messages, a value b∈{0,1} is randomly selected. Besides, 𝒞 enforces the algorithm Encrypt(pp,m,Att), and finally exports the resulting ciphertext to 𝒜.

•   Phase 2: 𝒜 proceeds with Phase 1 queries during this process.

•   Guess. 𝒜 gives out his guess b′∈{0,1} to 𝒞. What’s more, when b′=b, means that 𝒜 wins the interactive game. In addition, the 𝒜’s advantage to victory is

ε=AdvIND−sCPA𝒪sk,𝒪rk,𝒪rv(1λ,𝒰)=|Pr[b′=b]−12|.(8)

For any PPT 𝒜, if 𝒜’s advantage AdvIND−sCPA𝒪sk,𝒪rk,𝒪rv(1λ,𝒰) against the KPAB-VPRE scheme is negligible, then the KPAB-VPRE scheme is IND-sCPA secure.

4  Scheme of our KPAB-VPRE

4.1 Construction

•   Setup(λ,n,q,m,𝒰): This algorithm takes security parameters λ, positive integer n>Ω(λ), prime number q>2, lattice dimension m>5nlog⁡q and an attribute domain 𝒰={Att1,Att2,…,Attl}, where Atti={att1,att2,…,attt}, (t≤l) as input. Then,

(i)   For each attribute atti∈𝒰, performs the algorithm TrapGen(n,m,q,σ) to produce two matrices, one is the uniform and random matrix Aatti∈Zqn×m, i∈[l]. The other is a small norm matrix TAatti∈Zqm×m, which is a trapdoor basis for Λq⊥(Aatti), where ‖TAatti~‖≤m⋅ωlog⁡m;

(ii)   Chooses a uniform random variable s∈Zq;

(iii)   Finally, returns the public parameters pp={Aatti,s}atti∈𝒰 and the master key msk=TAatti.

•   KeyGen(pp,msk,P): pp, msk and the access policy P are inputs into this algorithm. Next, the algorithm extracts the private key as follows:

(i)   Converts the user’s access policy P into a shared access policy (M,ρ) by the linear secret sharing theory. Here, M is a n×n share-generating matrix. Additionally, ρ(i):[n]→𝒰 is a function which maps the i-th row of the matrix M to the attribute domain 𝒰;

(ii)   Lets H=MG, G∈Zn×m is the gadget matrix. Generates an extended trapdoor T(Aatti|H)∈Zq2m×2m by running the SampleBasisLeft(Aatti,H,TAatti,σ) algorithm, and then sets F1=(Aatti|H)∈Zqn×2m;

(iii)   Finally, outputs sk=T(Aatti|H)=TF1.

•   Encrypt(pp,m,Atti): As input, the algorithm accepts pp, m∈{0,1} and an attribute set Atti={atti1,atti2,…,attit},(t≤l), then does:

(i)   Chooses uniformly at random a matrix S∈{±1}m×m, a vector u∈Zqn and two noises e1∈Ψα2m, e2∈Ψα;

(ii)   Sets

c1,0=F1Tu+e1∈Zq2m;(9)

(iii)   Computes

c1,1=[s,0,…,0]u+e2+m⌊q/2⌋∈Zq,i∈[n];(10)

(iv)   Outputs the ciphertext C1=(c1,0,c1,1).

•   ReKeyGen(pp,sk,Attj): This algorithm enters pp, sk and a new attribute set Attj={attj1,attj2,…,attjt}, (t≤l) to return the re-encryption key rk1→2 in the following way:

(i)   For each attribute attj∈𝒰, chooses a uniformly random matrix Aattj∈Zqn×m, j∈[l]. Then sets

F2=(Aattj|H)∈Zqn×2m;(11)

(ii)   Creates a low-norm matrix R1→2∈Zq2m×2m with the SamplePre(F1,TF1,F2,σ), with the goal of ensuring that

F1⋅R1→2=F2;(12)

Therefore, we set rk1→2=R1→2 as re-encryption key.

(iii)   Runs the algorithm HS.KeyGen(λ,d,n) to generate a key pair (hssk,hsvk), and parses each row of R1→2 to zx∈Zq2m,(1≤x≤2m), using the algorithm HS.Sign (hssk,zx) to each zx to get the sign σx,(1≤x≤2m), where hsvk is used to verify the signature;

(iv)   Finally, delivers rk1→2 and the associated signature σx over a secure channel to the proxy server.

•   ReEncrypt(pp,rk1→2,C1): This algorithm accepts as inputs pp, rk1→2 and C1. The proxy then produces the re-encrypted ciphertext in the manner described below:

(i)   Finds the vector g=(g1,g2,…,gn), ∀i∈[n]:(gi=0)∨(i∈[Atti]) so that

g⋅M=(1,0,…,0);(13)

(ii)   Sets two vectors

c2,0=rk1→2T⋅c1,0(modq);(14)

c2,1=c1,1;(15)

(iii)   Computes a signature σ1→2← HS.SignEval(δC1,σx) homomorphically where the evaluation circuit δC1(rk1→2) is defined by the original ciphertext as follows:

δC1(rk1→2)=ci,0;(16)

(iv)   Finally, outputs the re-encryption ciphertext C2=(c2,0,c2,1) and the signature σ1→2.

•   ReEncVer(pp,hsvk,C1,C2): pp, hsvk, C1 with σ∗→2 (if C1 is generated by encrypting a plaintext m, σ∗→2 is empty) and the transformed ciphertext C2 with σ1→2 are all inputted into this algorithm. Then, executes the algorithm HS.Verify(hsvk,δC1,C2,σ1→2). If it outputs 1, it means that the re-encryption ciphertext is legal, otherwise, outputs 0 indicates that the re-encryption ciphertext is illegal.

•   Decrypt(sk,C): The user inputs the secret key sk and a ciphertext C. If the attribute sets satisfy the access policy, then follow the steps below to decrypt.

(i)   Construct two new vectors

v=(s,v2,v3,…,vm)T∈Zqm;(17)

v′=(s,v2′,v3′,…,vk′)T∈Zqk;(18)

where v2,v3,…,vm,v2′,v3′,…,vk′∈Zq are chosen at random, and computes the matrix multiplication Mi⋅v, Mj′⋅v′, denotes the result by

λ1T=Mi⋅v∈Zq(19)

λ2T=Mj′⋅v′∈Zq(20)

where {Mi}i∈[n] is the i-th row of M∈Zqn×m and {Mj′}j∈[n] is the j-th row of M′∈Zqn×m;

(ii)   Lets μ1=(λ1T,0,…,0)T∈Zqn, μ2=(λ2T,0,…,0)T∈Zqn, μ1, μ2 respectively correspond to attribute ρ(i) and ρ(j) of the access policy (M,ρ) and (M′,ρ);

(iii)   Given a Gaussian parameter σ, and then runs the SamplePre algorithm to sample a vector kt∈Zq2m, t∈{1,2} such that F1⋅k1=μ1modq, F2⋅k2=μ2modq;

(iv)   Calculates

m′=ct,1−∑i∈𝒮giktTct,0,t∈{1,2},g=(g1,g2,…,gn),  ∀i∈[n]:(gi=0)∨(i∈[Atti]);(21)

(v)   Outputs the result:

m={0,|m′|≤⌊q4⌋1,|m′|≥⌊q4⌋.(22)

4.2 Correctness and Parameter

4.2.1 Proof of Correctness

(i)   The accuracy of unconverted ciphertext decoding. When t=1, if Atti⊨(M,ρ), the original ciphertext C1 is decrypted as follows:

m′=c1,1−∑i∈Sgik1Tc1,0(modq)=c1,1−∑i∈Sgik1T(F1Tu+e1)(modq)=[s,0,…,0]u+m⌊q/2⌋−∑i∈Sgiμ1Tu+noise1(modq)=[s,0,…,0]u+m⌊q/2⌋−[1,0,…,0][s,v2,v3,…,vk]u+noise1(modq)=m⌊q/2⌋+noise1(modq)(23)

(ii)   Decryption correctness of converted ciphertext. When t=2, for the re-encryption ciphertext C2, if Attj⊨(M,ρ), we need to compute

m′=c2,1−∑i∈Sgik2Tc2,0(modq)=c2,1−∑i∈Sgik2T(rk1→2T⋅c1,0)=c2,1−∑i∈Sgik2T(F2Tu+R1→2Te1)=[s,0,…,0]u+m⌊q/2⌋−∑i∈Sgiμ2Tu+noise2(modq)=[s,0,…,0]u+m⌊q/2⌋−∑i∈Sgi[Mj′⋅v′,0,…,0]u+noise2(modq)=m⌊q/2⌋+noise2(modq)(24)

(iii)   Correctness of re-encryption ciphertext verification. The effectiveness of the re-encryption ciphertext verification depends on the output of the verification algorithm HS.Verify. Besides, in the ReEncrypt(pp,rk1→2,C1), the the evaluation circuit is defined by δC1(rk1→2)=cj,0 with the original ciphertext ci,0 and rk1→2. From the correctness definition of HS, it can be seen that if the signature σ1→2 is the result of an honest calculation by the proxy, then the algorithm HS.Verify(hsvk,δC1,C2,σ1→2) will be accepted with overwhelming probability. In summary, the validity of the converted ciphertext has been verified.

Remark 4.1. If the parameter setting is reasonable and the noise item in Eqs. (23) and (24) is small enough, the plaintext message can be recovered correctly after decryption.

4.2.2 Parameter Settings

(i)   According to the assumption of the LWE problem, for the Gaussian noise distribution ei←Ψαm and the normalized variance α≥2m/q, the length of the vector satisfies O(αqm)≤2m in Regev’s proof [26];

(ii)   According to the algorithm TrapGen(n,m,q,σ), for the safety parameter n=Ω(λ), we require that the prime modulus q>2, the Gaussian parameter σ≥m⋅ω(log⁡n) and the dimension of the lattice base m≥5nlog⁡q. If the constraints of each parameter can be satisfied, the length of the lattice base generated by the trapdoor generation algorithm is at most m⋅ω(log⁡m);

(iii)   According to the algorithm SamplePre(F1,TF1,F2,σ), we set the discrete Gaussian distribution parameter σ≥‖T~‖⋅ω(log⁡m), the parameter q≥2 and m≥2nlog⁡q. If the above constraints are met, rk1→2=R1→2 is created with overwhelming probability advantage. Besides, the length of the rk1→2 satisfies ‖R1→2‖≤2σm;

(iv)   In order to make the error term |noise|<5/q, α must satisfy the conditions

α≤15[(ω(log⁡m)+1)(1+l)(m1.5ω(log⁡m))]−1;

Since qα≥m/2, q must meet

q≥52m[(ω(log⁡m)+1)(1+l(m1.5ω(log⁡m)))].

Thus, we decided on the following scheme parameters:

m=5n1+δ, δ>⌈log⁡q⌉, q=52m[(ω(log⁡m)+1)(1+l(m1.5ω(log⁡m)))],

α=15[(ω(log⁡m)+1)(1+l)(m1.5ω(log⁡m))]−1, σ=m⋅ω(log⁡n).

where l is the count of attributes on the access policy. If the parameters are set reasonably, it can be correctly recovered after the above decryption.

4.3 Security Analysis

Theorem 4.1. Assume that σ, m, n, α and q are the same as in the previous sentence. In the standard model, our KP-ABPRE scheme is IND-sCPA secure under the assumption that the decision LWEq,Ψ problem is difficult.

Proof. We utilize the assumption that there is a PPT adversary 𝒜 with a non-negligible advantage to attack our system under the selective security model via “game-hopping” in order to demonstrate the theorem. The basic idea is to construct three games. The first game is an actual IND-sCPA attack, however the last game is impossible for the attacker to win; Then, based on some difficult assumptions on lattice, it is proved that the first game and the last game are equivalent. We have to demonstrate that these three games are indistinguishable from each other for PPT adversary 𝒜 in the following ways.

Game sequence:

•   Game0: 𝒞 and 𝒜 are playing a typical IND-sCPA game. Besides, 𝒞 faithfully responds to different sk and rk1→2 queries in accordance with the real scheme’s algorithms.

•   Game1: This game changes the generation of Aatti and sk.

(i)   TrapGen(n,m,q,σ) algorithm produces a matrix Aatti in Game0, but in Game1, Aatti does not contain trapdoor, the matrix Aatti∈Zqn×m is a uniformly distributed matrix randomly selected by the challenger 𝒞;

(ii)   The challenger 𝒞 sets H=AattiS+G, and then runs the SampleBasisRight(Aatti,G,S, algorithm to get the private key sk=T(Aatti|H)=TF1;

(iii)   Finally, the attacker 𝒜 receives the sk back from the challenger 𝒞. And the settings of other parameters are the same as Game0.

•   Game2: The production of the challenge ciphertext C∗ distinguishes this game from Game1. In Game1, the Encrypt(pp,m,Atti) algorithm creates C∗. However, in Game2, the C∗ is a uniformly random and independent matrix from Zq2m×Zq. The rest of the settings are the same as Game1. In this case, the advantage of the attacker 𝒜 is zero.

If Game1 is indistinguishable from Game0, and Game2 is indistinguishable from Game1, our KPAB-VPRE scheme is IND-sCPA secure in the standard model.

Game transfer:

•   Game0 to Game1: We now prove that Game0 and Game1 are indistinguishable through the Lemma 4.1.

•   Lemma 4.1. If mn>(n+1)log2q+ω(lg⁡n), then Game1 and Game0 are indistinguishable, and the answer to the attacker 𝒜’s inquiries become indistinguishable from the true scheme.

Proof.

(i)   The matrix Aatti∈Zqn×m in Game0 is produced by the TrapGen(n,m,q,σ) algorithm. In addition, it is random. However, in Game1, the matrix Aatti is randomly selected from Zqn×m, so, for the attacker 𝒜 in polynomial time, the public parameter Aatti is taken from uniformly distributed Zqn×m;

(ii)   For the private key, sk is generated by the SampleBasisLeft algorithm in Game0, but in Game1, sk is generated by the SampleBasisRight algorithm. By definition of SampleBasisRight, we have that sk=T(Aatti|H) is distributed as required. Thus, the challenger 𝒞’s response to the secret key question is indistinguishable from that in Game1 for the 𝒜.

From the Lemma 4.1, we can see that the 𝒜’s advantage in Game1 is equal to that in Game0. Therefore, Game0 and Game1 are indistinguishable.

•   Game1 to Game2: Assuming that in the selective security model, an attacker 𝒜 can discriminate between Game1 and Game2 with a non-negligible advantage by chosen plaintext attack, the challenger 𝒞 will construct an algorithm ℬ to solve the decision LWE problem with a non-negligible probability. In the LWE problem, the decision algorithm has access to a sampling oracle 𝒪, which can be either a really random sampler 𝒪s or a pseudo-random sampler 𝒪$ with an embedded secret u∈Zqn. Following is the reduction’s progression:

–Target. The challenger 𝒞 receives a statement from the adversary 𝒜 announcing the target attribute set Atti∗ to attack.

•   –Instance. The challenger 𝒞 demands l+1 LWE samples from the oracle 𝒪, which we denote as:

[(w0,v0)]∈(Zqn×Zq)[(w11,v11),…,(w12m,v12m)]∈(Zqn×Zq)2m[(w21,v21),…,(w22m,v22m)]∈(Zqn×Zq)2m⋮[(wl1,vl1),…,(wl2m,vl2m)]∈(Zqn×Zq)2m(25)

–Setup. The challenger 𝒞 prepares the public parameters as follows once it has obtained the target attribute set Atti∗:

(i)   The central authority selects the appropriate system parameters n,m,q,σ;

(ii)   If the attribute atti is in the target attribute set Atti∗, then the challenger 𝒞 constructs a matrix F1∗=[wi1|…|wi2m] and a vector [s,0,…,0]T=w0, where wi(i∈[l]) comes from LWE sampling;

(iii)   The remaining parameters are the same as Game1 settings.

Remark 4.2. The above settings have the correct distribution.

–Phase 1. The attacker 𝒜 can ask the following questions:

Secret Key Query 𝒪sk:

(i)   The attacker 𝒜 sends the access policy P to a challenger 𝒞 for private key queries, However, the target attribute on (M,ρ) cannot be queried, that is, ρ(i)∉Atti∗, where ρ(i) is the attribute on the access policy (M,ρ). If ρ(i)∈Atti∗, a random bit is output and terminated;

(ii)   According to the parameters in Game1, the challenger 𝒞 generates sk as previously mentioned and gives it back to the attacker 𝒜.

Re-Encryption Key Query 𝒪rk:

(i)   The challenger 𝒞 first generates sk as in 𝒪sk. Then, the challenger 𝒞 replies with rk1→2 by running the algorithm ReKeyGen(pp,sk,Attj);

(ii)   rk1→2 is sent by the the challenger 𝒞 to the attacker 𝒜. The attacker 𝒜 can query multiple times.

Re-Encryption Verification Query 𝒪rv:

(i)   After 𝒜 gets the queries 𝒪rk from one access policy P to another access policy P′, 𝒜 can also make some queries 𝒪rv to 𝒞. Next, 𝒞 only executes the algorithm ReEncVer faithfully;

(ii)   Finally, 𝒞 sends the result to 𝒜 according to the verification algorithm.

Remark 4.3. Because of the unforgeability of HS, the algorithm ReEncVer cannot provide any additional capabilities for 𝒜 in the selectively IND-CPA security game. That is to say, 𝒜 cannot offer invalid ciphertext to pass the algorithm ReEncVer. This is very critical. What’s more, we are aware that the security features of the underlying algorithm HS.Verify determine if the algorithm ReEncVer is valid. Furthermore, 𝒜 must be able to counterfeit the signature σ1→2∗ and pass the algorithm HS.Verify in order to pass the game of re-encryption verification, as this is also a legal signature for HS. In other words, 𝒜 has the same benefits as violating the unforgeability of HS when it comes to our KPAB-VPRE scheme’s re-encryption verifiability.

–Challenge. In order to indicate that it is open to a challenge, 𝒜 selects two messages {m0,m1}←Zqm of equal-length. A message mφ(φ←{0,1}) is selected at random by 𝒞 for encryption. At last, 𝒞 replies with C∗ built as follows applying the LWE instance:

(i)   Constructing ciphertext C∗=(c0,1∗,c1,1∗) based on LWE samplings. Let

v∗=(vi1,vi2,…,vi2m)∈Zq1×2m(26)

c1,0∗=(v∗)T∈Zq2m(27)

c1,1∗=v0+mφ⌊q/2⌋∈Zq(28)

where vi is taken from the LWE instance;

(ii)   The challenger 𝒞 randomly selects a bit φ←{0,1}, if φ=0, C∗=(c1,0∗, c1,1∗) that will be returned to the attacker as challenge ciphertext. If φ=1, C∗ as a challenge ciphertext will be randomly chosen from Zq2m×Zq and returned to the attacker 𝒜.

Remark 4.4. The above challenge ciphertext C∗=(c1,0∗,c1,1∗) has the correct distribution. A simple analysis reveals that:

∗   If 𝒪=𝒪s in the instantiation process, it is a pseudo random sampling oracle embedded in the secret u∈Zqn. Well,

vi=wiTu+e,e∈Ψα.(29)

Due to the setting of public parameters, the ciphertext obtained is

c1,0∗=(v∗)T=[vi1,vi2,…,vi2m]T=[wi1,wi2,…,wi2m]Tu+e1=F1∗Tu+e1(30)

where e1∈Ψα2m.

c1,1∗=v0+mφ⌊q/2⌋=w0Tu+e2+mφ⌊q/2⌋=[s,0,…,0]u+e2+mφ⌊q/2⌋(31)

where e2∈Ψα.

The above C∗=(c1,0∗,c1,1∗) obeys uniform random distribution in statistics;

∗   C∗=(c1,0∗,c1,1∗) is chosen at random in Zq2m×Zq if 𝒪=𝒪$.

–Phase 2. The simulator ℬ operates in a similar manner to Phase 1, the attacker 𝒜 is able to query secret keys multiple times, and the set of attributes Atti∗ that have done so have not yet met the access structure (M,ρ).

–Guess. After enough questioning, the attacker outputs his guess of φ as φ′. If φ′=φ, the challenger outputs 𝒪′=𝒪$, otherwise 𝒪′=𝒪s.

In the attacker 𝒜’s view, the challenger 𝒞’s behavior is close to that of a real, adaptive security experiment. In this game, the attacker 𝒜 has the advantage since ε=|Pr[φ′=φ]−12|. Therefore, the advantages of the LWE predictor are as follows:

(i)   In a pseudo-random sampler, an attacker 𝒜 has the advantageous value ε. In this case, 𝒪=𝒪$, Pr[φ′=φ∣𝒪=𝒪$]=12+ε and the challenger’s advantage is

Pr[𝒪′=𝒪∣𝒪=𝒪$]=12+ε;(32)

(ii)   In a true random predictor, an attacker 𝒜 has an advantage of 0. In this case, 𝒪=𝒪s, Pr[φ′=φ∣𝒪=𝒪s]=12+ε, the challenger’s advantage is