# Identity-Based Unidirectional Collusion-Resistant Proxy Re-Encryption from U-LWE

Authors: Nan Yang; Youliang Tian
Journal: Security and Communication Networks
 (2023)

---

## Abstract

Identity-based proxy re-encryption (IB-PRE) converts the ciphertext encrypted under the delegator’s identity to the one encrypted under the delegatee’s identity through a semitrusted proxy without leaking delegator’s private key and the underlying plaintext. At present, the security of most IB-PRE schemes relies on the hardness of the discrete logarithm solution or large integer decomposition and cannot resist attacks of the quantum algorithms. The majority of the IB-PRE schemes over lattice are secure only in the random oracle model. Aiming at such problems, the paper constructs a secure IB-PRE scheme over lattice in the standard model. In the scheme, the underlying encryption scheme proposed by Gentry et al. in EUROCRYPT 2010 is adopted to reduce the storage space of ciphertext. The proposed scheme is unidirectional collusion-resistant multihop and anonymous, and it is semantically secure against selective identity and chosen plaintext attack based on Decisional Learning With Errors with uniformly distributed errors (D-U-LWE) hard problem in the standard model.


---

## Body

## 1. Introduction

Proxy re-encryption (PRE) scheme was introduced by Blaze et al. [1] in 1998. In the PRE scheme, the delegator sends ciphertext encrypted by delegator’s public key to the proxy with re-encryption key, and the proxy converts the original ciphertext into one under delegatee’s public key using the re-encryption key. In the process, neither plaintext nor delegator’s private key is leaked to delegatee or proxy. Identity-based proxy re-encryption scheme integrates the idea of identity-based encryption into PRE scheme, and in the IB-PRE scheme, the unique identity of user, such as telephone number and ID number, can be used for the public key of the user. Meanwhile, the Public Key Infrastructure (PKI) is not required without the generation, distribution, and management of the public key relative to the general PRE scheme. So the IB-PRE scheme is applied in a variety of scenarios [2–5].


### 1.1. Related Work

Since Blaze et al. first proposed and constructed the PRE scheme, the hardness of the PRE scheme is mainly based on the classical number theory hard problems or hard problems over lattice. The underlying classical number theory hard problems, such as large integer factorization hard problem and discrete logarithm hard problem, can be efficiently broken by the quantum algorithm [6] in the polynomial time. With the rapid progress of quantum algorithm technologies, constructing the lattice based PRE scheme to realize the quantum-resistant attack is very meaningful. The first lattice based PRE scheme was introduced by Xagawa [7] in his doctor of philosophy thesis, the scheme was bidirectional and not collusion-resistant attack. Aono et al. [8] proposed the key-private PRE scheme under LWE hard problem without leaking the identity of delegator and delegatee, whereas the scheme cannot resist the collusion attack of the proxy and delegatee, the scheme is CPA secure in the standard model and is CCA secure in the random oracle model. Singh et al. [9] constructed the first lattice based anonymous IB-PRE scheme; however, the scheme is bidirectional in which if the proxy and the delegatee are collusive, the private key of the delegator is leaked easily. Whereafter, Singh et al. [10] designed a new re-encryption key to resolve the problem of collusion in the literature [8] and constructed a lattice based unidirectional and multihop IB-PRE scheme. In the same year, Singh et al. [11] introduced another new lattice based unidirectional and multihop IB-PRE scheme using the strong trapdoor method [12], the scheme was shown unable to resist collusion attack in the literature [13]. [9–11] are IND-sID-CPA secure in the random oracle model.Jiang et al. [14] constructed the first lattice based multihop unidirectional PRE scheme using the underlying encryption scheme [15] with the IND-CPA security in the standard model, on the basis, a lattice based IB-PRE scheme was constructed with the IND-CPA security in the standard model, and also was multihop and unidirectional, whereas the detailed security proof was not given out. Wang et al. [16] indicated the re-encryption ciphertext had high decryption error rate in the literature [14], and subsequently presented a unidirectional collusion-resistant PRE scheme with the IND-CPA security in the standard model. Hou et al. [17] presented a multibit bidirectional IND-ID-CPA secure IB-PRE scheme. The hardness of the above lattice based schemes is based on the LWE hard problem or its variants. For the lack of unidirectionality or collusion-resistance, our focus is to present a unidirectional multihop and collusion-resistant IB-PRE scheme over lattice.


### 1.2. Contributions

The paper mainly constructs a novel IB-PRE scheme in the context of BGN-type cryptosystem [15] over lattice. To implement the scheme, some techniques are employed such as trapdoor generation algorithm [18] and Bonsai Trees algorithm [19]. In the setup phase, using trapdoor generation algorithm generates the public parameters pp and the master key TA0, i.e., a short basis of the random lattice ∧q⊥A0 as the relevant trapdoor. The private key of the user is created by the Bonsai Trees algorithm that utilizes relatively “small” A0,TA0 to obtain relatively “big” Fid,skid. The plaintext μ is encrypted by user (delegator) id’s public key Fid to gain the second-level ciphertext Cid=FidTs+2e1+μb1modq. In order to translate the second-level ciphertext Cidi to the first-level ciphertext Cidj=FidjTs2+2e2+μb2modq, we constructed the re-encryption key rkidi⟶idj=FidjTL1+R1skidiTmodq such that Cidj=rkidi⟶idjCidi+2t1modq, where rkidi⟶idj is similar to U-LWE hard problem form.


## 1.1. Related Work

Since Blaze et al. first proposed and constructed the PRE scheme, the hardness of the PRE scheme is mainly based on the classical number theory hard problems or hard problems over lattice. The underlying classical number theory hard problems, such as large integer factorization hard problem and discrete logarithm hard problem, can be efficiently broken by the quantum algorithm [6] in the polynomial time. With the rapid progress of quantum algorithm technologies, constructing the lattice based PRE scheme to realize the quantum-resistant attack is very meaningful. The first lattice based PRE scheme was introduced by Xagawa [7] in his doctor of philosophy thesis, the scheme was bidirectional and not collusion-resistant attack. Aono et al. [8] proposed the key-private PRE scheme under LWE hard problem without leaking the identity of delegator and delegatee, whereas the scheme cannot resist the collusion attack of the proxy and delegatee, the scheme is CPA secure in the standard model and is CCA secure in the random oracle model. Singh et al. [9] constructed the first lattice based anonymous IB-PRE scheme; however, the scheme is bidirectional in which if the proxy and the delegatee are collusive, the private key of the delegator is leaked easily. Whereafter, Singh et al. [10] designed a new re-encryption key to resolve the problem of collusion in the literature [8] and constructed a lattice based unidirectional and multihop IB-PRE scheme. In the same year, Singh et al. [11] introduced another new lattice based unidirectional and multihop IB-PRE scheme using the strong trapdoor method [12], the scheme was shown unable to resist collusion attack in the literature [13]. [9–11] are IND-sID-CPA secure in the random oracle model.Jiang et al. [14] constructed the first lattice based multihop unidirectional PRE scheme using the underlying encryption scheme [15] with the IND-CPA security in the standard model, on the basis, a lattice based IB-PRE scheme was constructed with the IND-CPA security in the standard model, and also was multihop and unidirectional, whereas the detailed security proof was not given out. Wang et al. [16] indicated the re-encryption ciphertext had high decryption error rate in the literature [14], and subsequently presented a unidirectional collusion-resistant PRE scheme with the IND-CPA security in the standard model. Hou et al. [17] presented a multibit bidirectional IND-ID-CPA secure IB-PRE scheme. The hardness of the above lattice based schemes is based on the LWE hard problem or its variants. For the lack of unidirectionality or collusion-resistance, our focus is to present a unidirectional multihop and collusion-resistant IB-PRE scheme over lattice.


## 1.2. Contributions

The paper mainly constructs a novel IB-PRE scheme in the context of BGN-type cryptosystem [15] over lattice. To implement the scheme, some techniques are employed such as trapdoor generation algorithm [18] and Bonsai Trees algorithm [19]. In the setup phase, using trapdoor generation algorithm generates the public parameters pp and the master key TA0, i.e., a short basis of the random lattice ∧q⊥A0 as the relevant trapdoor. The private key of the user is created by the Bonsai Trees algorithm that utilizes relatively “small” A0,TA0 to obtain relatively “big” Fid,skid. The plaintext μ is encrypted by user (delegator) id’s public key Fid to gain the second-level ciphertext Cid=FidTs+2e1+μb1modq. In order to translate the second-level ciphertext Cidi to the first-level ciphertext Cidj=FidjTs2+2e2+μb2modq, we constructed the re-encryption key rkidi⟶idj=FidjTL1+R1skidiTmodq such that Cidj=rkidi⟶idjCidi+2t1modq, where rkidi⟶idj is similar to U-LWE hard problem form.


## 2. Preliminaries

### 2.1. Notations

We exploitℤ and ℝ to denote the sets of integers and real numbers, respectively, and represent scalars by the lowercase letters, vectors by the lowercase bold letters, and matrixes by the uppercase bold letters. A vector can be represented in terms of column vector and a matrix can be denoted by the ordered column vectors, such as matrix A=a1,…,am. x denotes the l2-norm of the vector x. The norm A of the matrix A is the maxai. AT is used to denote the transpose of the matrix A, the symbol A|B indicates that matrixes are connected horizontally to construct a new matrix.The notationa˜ presents the Gram-Schmidt orthogonalization of the vector a and A˜ denotes the Gram-Schmidt orthogonalization of the matrix A. The poly⋅ expresses an unspecified polynomial function, the function ϵn presents a negligible function, i.e., ϵn=1/polyn, where n is an arbitrary positive integer.


### 2.2. Lattice

Definition 1.
a1,…,an∈ℝm are linearly independent. The lattice is the set of all integer coefficient linear combination of a1,…,an. The lattice LA=La1,…,an=∑i=1nziai|zi∈ℤ,ai∈ℝm, where a1,…,an is the basis, n is the rank, and m is the dimension for the lattice. Generally, when n=m, the lattice is called full rank lattice. In the paper, we use a kind of special integer lattices called “q−ray” random lattices.Definition 2.
Setq as a prime number, A∈ℤqn×m, the random lattices are defined as follows:(1)∧q⊥A=z∈ℤm|Az=0,A∈ℤqn×m,∧quA=z∈ℤm|Az=u,A∈ℤqn×m,u∈ℤqn,where ∧q⊥A and ∧quA are full rank integer lattices.
We introduce trapdoor generation algorithm. Using the algorithm, we can output a random matrix and a “short” basis of random lattice generated by the matrix. The matrix is used to construct a user’s public key and the basis is an input of the private key extraction algorithm, which we construct to generate the user’s private key in the scheme.Lemma 1.
Trapdoor generation algorithm [18]. For the parameters n, q=polyn and m≥6nlogq, there is a probabilistic polynomial time (PPT) algorithm Trap Genq,n,m, it generates pseudo-random matrix A∈ℤqn×m and a “short” trapdoor basis TA∈ℤm×m for the lattice ∧q⊥A, where the distribution of A is statistically close to uniform distribution over ℤqn×m and the length T˜A≤Onlogq.Lemma 2.
Bonsai Trees algorithm [19]. The Bonsai Trees algorithm has four basic procedures: undirected growth, controlled growth, extending control, and randomizing control.Undirected growth.A is an arbitrary matrix in ℤqn×m and A′=A|A¯∈ℤqn×m′ for some m′>m is an arbitrary extension of A.Controlled growth. It is actually trapdoor generation algorithm.Extending control.T∈ℤm×m is an arbitrary basis of ∧q⊥A, A¯∈ℤqn×m′ is an arbitrary matrix. There exists a deterministic polynomial time algorithm Ext BasisT,A|A¯, which outputs a basis T¯ of the ∧q⊥A|A¯, where T˜=T¯˜.Randomizing control. Set parameterss∈ℝ and A∈ℤqn×m, T is a basis of ∧q⊥A satisfying s≥T˜ωlogn, there exists a PPT algorithm Rand BasisT,s, which generates a basis T′ of ∧q⊥A with T′≤sm. Moreover, for two arbitrary basis T1 and T2, where s≥ max T1˜,T2˜ωlogn, the outputs of Rand BasisT1,s and Rand BasisT2,s are statistically indistinguishable.
Regarding Lemma2, in our scheme, the extending control procedure can extend a basis of the low-dimension lattice (i.e., ∧q⊥A0) to the one of the high-dimension lattice (i.e., ∧q⊥Aid) with loss in quality. Using randomizing control procedure, the private key of a user is generated.


### 2.3. A Variant of Learning with Errors (LWE)

The learning with errors was introduced by Regev [20]. Based on the LWE hard problem, cryptologists construct various cryptography schemes in the lattice cryptography, meanwhile, LWE hard problem generates a few variants, U-LWE is one of them.Definition 3.
([21]). Give parameters n, sufficiently small real constant number ϵ∈0,1, modular integer q=polyn, dimension integer m=polyn≥3n, real number r≥2n0.5+ϵm. If there is a PPT algorithm to successfully resolve LWE n,q,m,U−r,r with non-negligible probability in the polynomial time, then there exists an efficient quantum algorithm that can resolve the appropriate decisional the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) to within O˜n1+ϵmq/r in the worst case.
At the level of the parameters in the Definition3, the decisional version of the U-LWE (D-U-LWE) problem is hard [21]. In our secure proof, the D-U-LWE hard problem is used for proving Game 2 and Game 3 indistinguishable.


### 2.4. Encoding with Full-Rank Differences

In our IB-PRE scheme, we utilize an identity encoding function, i.e., encoding with full-rank differences (FRD) [22], to translate the identity of a user to the matrix in the ℤqn×2m.Definition 4.
Encoding with full-rank differences.
Let functionH:ℤqn⟶ℤqn×n satisfy the following conditions:(1)
For all distinctx1,x2∈ℤqn, Hx1−Hx2∈ℤqn×n is full rank(2)
For zero vector0∈ℤqn, H0=0∈ℤqn×n(3)
The functionH is efficiently and correctly computed in polynomial time
Note the functionH is injective.


### 2.5. IB-PRE Scheme Model

The IB-PRE scheme contains the following six algorithms [23].(1)
Setupn: Input secret parameter n and output the public parameters pp and the master secret key msk(2)
Extractpp,id,msk: Input the public parameters pp, the master secret key msk, and the user’s identity id, and output the private key skid for the user id(3)
Encpp,id,μ: Input the public parameters pp, the user’s identity id, and message μ, and output a second-level ciphertext Cid for the user id(4)
ReKeyGenpp,skidi,idj: Input the public parameters pp, the private key skidi for the user idi, and the user’s identity idj, and output the re-encryption key rkidi⟶idj from idi to idj(5)
ReEncpp,rkidi⟶idj,Cidi: Input the public parameters pp, the re-encryption key rkidi⟶idj, and the second-level ciphertext Cidi of the user idi, and output a first-level ciphertext Cidj of the user idj(6)
Decpp,skid,Cid: Input the public parameters pp, the private key skid, and the ciphertext Cid for the user id, and output the plaintext μCorrectness: If the scheme is correct, the following conditions must be metDecpp,skid,Encpp,id,μ=μDecpp,skidj,ReEncpp,ReKeyGenpp,skidi,idj,Encpp,idi,μ=μ


### 2.6. IB-PRE Security Model

The security of the IB-PRE scheme can be described with an interactive experiment (game)ExpIB−PRE,AIND−sID−CPAn between adversary A and challenger ℬ.


#### 2.6.1. Setup Phase

Challengerℬ executes the setup algorithm with the secure parameter n and obtains the public parameters pp and master secret key msk, then sends the public parameters pp to adversary A.


#### 2.6.2. Phase 1

In the phase 1, adversaryA wants to issue the following queries with no more than polynomial times, and challenger ℬ answers the queries.(1)
Private key extract query: AdversaryA inputs the identity id, and challenger ℬ returns the private key skid = Extract pp,id,msk, where id≠id∗ (id∗ is the target identity), otherwise outputs ⊥.(2)
Re-encryption key query: AdversaryA inputs the identity pair idi,idj, and challenger ℬ returns the re-encryption key rkidi⟶idj = ReKeyGen pp,skidi,idj, where idi≠id∗, otherwise outputs ⊥.


#### 2.6.3. Challenge Phase

AdversaryA transmits target identity id∗ and messages μ0≠μ1 to challenger ℬ, then challenger ℬ generates the challenge ciphertext Cid∗=Encpp,id∗,μi for any randomly chosen i∈0,1 and returns Cid∗ to adversary A.


#### 2.6.4. Phase 2

The phase 2 is same with phase 1.


#### 2.6.5. Guess Phase

ChallengerA outputs the guess result μi′. If μi′=μi, challenger A wins and outputs 1, otherwise, challenger A fails and outputs 0.Definition 5.
The advantage of adversaryA is defined as a function about the secure parameter n.(2)AdvIB−PRE,AIND−sID−CPAn=|PrExpIB−PRE,AIND−sID−CPAn=1−1/2|
For any polynomial time adversaryA, if there exists a negligible function ϵn making AdvIB−PRE,AIND−sID−CPAn≤ϵn true, the IB-PRE scheme is IND-sID-CPA secure.
The probability of an ordinary person, who does not interact with challengerℬ, breaking the scheme is 1/2. Adversary A may increase his knowledge by interacting with challenger ℬ and obtain the ability to break the scheme. Therefore, the winning probability of adversary A is the sum of advantage probability and 1/2. In Definition 5, when the absolute value of adversary A’s winning probability minus 1/2 is negligible, adversary A’s advantage probability is negligible, and it means that adversary A is incapable to break the scheme, so the scheme is safe.


## 2.1. Notations

We exploitℤ and ℝ to denote the sets of integers and real numbers, respectively, and represent scalars by the lowercase letters, vectors by the lowercase bold letters, and matrixes by the uppercase bold letters. A vector can be represented in terms of column vector and a matrix can be denoted by the ordered column vectors, such as matrix A=a1,…,am. x denotes the l2-norm of the vector x. The norm A of the matrix A is the maxai. AT is used to denote the transpose of the matrix A, the symbol A|B indicates that matrixes are connected horizontally to construct a new matrix.The notationa˜ presents the Gram-Schmidt orthogonalization of the vector a and A˜ denotes the Gram-Schmidt orthogonalization of the matrix A. The poly⋅ expresses an unspecified polynomial function, the function ϵn presents a negligible function, i.e., ϵn=1/polyn, where n is an arbitrary positive integer.


## 2.2. Lattice

Definition 1.
a1,…,an∈ℝm are linearly independent. The lattice is the set of all integer coefficient linear combination of a1,…,an. The lattice LA=La1,…,an=∑i=1nziai|zi∈ℤ,ai∈ℝm, where a1,…,an is the basis, n is the rank, and m is the dimension for the lattice. Generally, when n=m, the lattice is called full rank lattice. In the paper, we use a kind of special integer lattices called “q−ray” random lattices.Definition 2.
Setq as a prime number, A∈ℤqn×m, the random lattices are defined as follows:(1)∧q⊥A=z∈ℤm|Az=0,A∈ℤqn×m,∧quA=z∈ℤm|Az=u,A∈ℤqn×m,u∈ℤqn,where ∧q⊥A and ∧quA are full rank integer lattices.
We introduce trapdoor generation algorithm. Using the algorithm, we can output a random matrix and a “short” basis of random lattice generated by the matrix. The matrix is used to construct a user’s public key and the basis is an input of the private key extraction algorithm, which we construct to generate the user’s private key in the scheme.Lemma 1.
Trapdoor generation algorithm [18]. For the parameters n, q=polyn and m≥6nlogq, there is a probabilistic polynomial time (PPT) algorithm Trap Genq,n,m, it generates pseudo-random matrix A∈ℤqn×m and a “short” trapdoor basis TA∈ℤm×m for the lattice ∧q⊥A, where the distribution of A is statistically close to uniform distribution over ℤqn×m and the length T˜A≤Onlogq.Lemma 2.
Bonsai Trees algorithm [19]. The Bonsai Trees algorithm has four basic procedures: undirected growth, controlled growth, extending control, and randomizing control.Undirected growth.A is an arbitrary matrix in ℤqn×m and A′=A|A¯∈ℤqn×m′ for some m′>m is an arbitrary extension of A.Controlled growth. It is actually trapdoor generation algorithm.Extending control.T∈ℤm×m is an arbitrary basis of ∧q⊥A, A¯∈ℤqn×m′ is an arbitrary matrix. There exists a deterministic polynomial time algorithm Ext BasisT,A|A¯, which outputs a basis T¯ of the ∧q⊥A|A¯, where T˜=T¯˜.Randomizing control. Set parameterss∈ℝ and A∈ℤqn×m, T is a basis of ∧q⊥A satisfying s≥T˜ωlogn, there exists a PPT algorithm Rand BasisT,s, which generates a basis T′ of ∧q⊥A with T′≤sm. Moreover, for two arbitrary basis T1 and T2, where s≥ max T1˜,T2˜ωlogn, the outputs of Rand BasisT1,s and Rand BasisT2,s are statistically indistinguishable.
Regarding Lemma2, in our scheme, the extending control procedure can extend a basis of the low-dimension lattice (i.e., ∧q⊥A0) to the one of the high-dimension lattice (i.e., ∧q⊥Aid) with loss in quality. Using randomizing control procedure, the private key of a user is generated.


## 2.3. A Variant of Learning with Errors (LWE)

The learning with errors was introduced by Regev [20]. Based on the LWE hard problem, cryptologists construct various cryptography schemes in the lattice cryptography, meanwhile, LWE hard problem generates a few variants, U-LWE is one of them.Definition 3.
([21]). Give parameters n, sufficiently small real constant number ϵ∈0,1, modular integer q=polyn, dimension integer m=polyn≥3n, real number r≥2n0.5+ϵm. If there is a PPT algorithm to successfully resolve LWE n,q,m,U−r,r with non-negligible probability in the polynomial time, then there exists an efficient quantum algorithm that can resolve the appropriate decisional the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) to within O˜n1+ϵmq/r in the worst case.
At the level of the parameters in the Definition3, the decisional version of the U-LWE (D-U-LWE) problem is hard [21]. In our secure proof, the D-U-LWE hard problem is used for proving Game 2 and Game 3 indistinguishable.


## 2.4. Encoding with Full-Rank Differences

In our IB-PRE scheme, we utilize an identity encoding function, i.e., encoding with full-rank differences (FRD) [22], to translate the identity of a user to the matrix in the ℤqn×2m.Definition 4.
Encoding with full-rank differences.
Let functionH:ℤqn⟶ℤqn×n satisfy the following conditions:(1)
For all distinctx1,x2∈ℤqn, Hx1−Hx2∈ℤqn×n is full rank(2)
For zero vector0∈ℤqn, H0=0∈ℤqn×n(3)
The functionH is efficiently and correctly computed in polynomial time
Note the functionH is injective.


## 2.5. IB-PRE Scheme Model

The IB-PRE scheme contains the following six algorithms [23].(1)
Setupn: Input secret parameter n and output the public parameters pp and the master secret key msk(2)
Extractpp,id,msk: Input the public parameters pp, the master secret key msk, and the user’s identity id, and output the private key skid for the user id(3)
Encpp,id,μ: Input the public parameters pp, the user’s identity id, and message μ, and output a second-level ciphertext Cid for the user id(4)
ReKeyGenpp,skidi,idj: Input the public parameters pp, the private key skidi for the user idi, and the user’s identity idj, and output the re-encryption key rkidi⟶idj from idi to idj(5)
ReEncpp,rkidi⟶idj,Cidi: Input the public parameters pp, the re-encryption key rkidi⟶idj, and the second-level ciphertext Cidi of the user idi, and output a first-level ciphertext Cidj of the user idj(6)
Decpp,skid,Cid: Input the public parameters pp, the private key skid, and the ciphertext Cid for the user id, and output the plaintext μCorrectness: If the scheme is correct, the following conditions must be metDecpp,skid,Encpp,id,μ=μDecpp,skidj,ReEncpp,ReKeyGenpp,skidi,idj,Encpp,idi,μ=μ


## 2.6. IB-PRE Security Model

The security of the IB-PRE scheme can be described with an interactive experiment (game)ExpIB−PRE,AIND−sID−CPAn between adversary A and challenger ℬ.


### 2.6.1. Setup Phase

Challengerℬ executes the setup algorithm with the secure parameter n and obtains the public parameters pp and master secret key msk, then sends the public parameters pp to adversary A.


### 2.6.2. Phase 1

In the phase 1, adversaryA wants to issue the following queries with no more than polynomial times, and challenger ℬ answers the queries.(1)
Private key extract query: AdversaryA inputs the identity id, and challenger ℬ returns the private key skid = Extract pp,id,msk, where id≠id∗ (id∗ is the target identity), otherwise outputs ⊥.(2)
Re-encryption key query: AdversaryA inputs the identity pair idi,idj, and challenger ℬ returns the re-encryption key rkidi⟶idj = ReKeyGen pp,skidi,idj, where idi≠id∗, otherwise outputs ⊥.


### 2.6.3. Challenge Phase

AdversaryA transmits target identity id∗ and messages μ0≠μ1 to challenger ℬ, then challenger ℬ generates the challenge ciphertext Cid∗=Encpp,id∗,μi for any randomly chosen i∈0,1 and returns Cid∗ to adversary A.


### 2.6.4. Phase 2

The phase 2 is same with phase 1.


### 2.6.5. Guess Phase

ChallengerA outputs the guess result μi′. If μi′=μi, challenger A wins and outputs 1, otherwise, challenger A fails and outputs 0.Definition 5.
The advantage of adversaryA is defined as a function about the secure parameter n.(2)AdvIB−PRE,AIND−sID−CPAn=|PrExpIB−PRE,AIND−sID−CPAn=1−1/2|
For any polynomial time adversaryA, if there exists a negligible function ϵn making AdvIB−PRE,AIND−sID−CPAn≤ϵn true, the IB-PRE scheme is IND-sID-CPA secure.
The probability of an ordinary person, who does not interact with challengerℬ, breaking the scheme is 1/2. Adversary A may increase his knowledge by interacting with challenger ℬ and obtain the ability to break the scheme. Therefore, the winning probability of adversary A is the sum of advantage probability and 1/2. In Definition 5, when the absolute value of adversary A’s winning probability minus 1/2 is negligible, adversary A’s advantage probability is negligible, and it means that adversary A is incapable to break the scheme, so the scheme is safe.


## 2.6.1. Setup Phase

Challengerℬ executes the setup algorithm with the secure parameter n and obtains the public parameters pp and master secret key msk, then sends the public parameters pp to adversary A.


## 2.6.2. Phase 1

In the phase 1, adversaryA wants to issue the following queries with no more than polynomial times, and challenger ℬ answers the queries.(1)
Private key extract query: AdversaryA inputs the identity id, and challenger ℬ returns the private key skid = Extract pp,id,msk, where id≠id∗ (id∗ is the target identity), otherwise outputs ⊥.(2)
Re-encryption key query: AdversaryA inputs the identity pair idi,idj, and challenger ℬ returns the re-encryption key rkidi⟶idj = ReKeyGen pp,skidi,idj, where idi≠id∗, otherwise outputs ⊥.


## 2.6.3. Challenge Phase

AdversaryA transmits target identity id∗ and messages μ0≠μ1 to challenger ℬ, then challenger ℬ generates the challenge ciphertext Cid∗=Encpp,id∗,μi for any randomly chosen i∈0,1 and returns Cid∗ to adversary A.


## 2.6.4. Phase 2

The phase 2 is same with phase 1.


## 2.6.5. Guess Phase

ChallengerA outputs the guess result μi′. If μi′=μi, challenger A wins and outputs 1, otherwise, challenger A fails and outputs 0.Definition 5.
The advantage of adversaryA is defined as a function about the secure parameter n.(2)AdvIB−PRE,AIND−sID−CPAn=|PrExpIB−PRE,AIND−sID−CPAn=1−1/2|
For any polynomial time adversaryA, if there exists a negligible function ϵn making AdvIB−PRE,AIND−sID−CPAn≤ϵn true, the IB-PRE scheme is IND-sID-CPA secure.
The probability of an ordinary person, who does not interact with challengerℬ, breaking the scheme is 1/2. Adversary A may increase his knowledge by interacting with challenger ℬ and obtain the ability to break the scheme. Therefore, the winning probability of adversary A is the sum of advantage probability and 1/2. In Definition 5, when the absolute value of adversary A’s winning probability minus 1/2 is negligible, adversary A’s advantage probability is negligible, and it means that adversary A is incapable to break the scheme, so the scheme is safe.


## 3. Our Scheme

In the section, we employ Gentry et al.’s scheme [15] to design a unidirectional collusion-resistant and multihop IB-PRE scheme. The process of the construction is as follows:


### 3.1. Construction

SetupnInput secret parametern∈ℤ, q=polyn is an odd prime number, and m=Onlogq=Onlogn.(1)
Use trapdoor generation algorithm TrapGenq,n,m to generate random matrix A0∈ℤqn×m and a “short” trapdoor basis TA0∈ℤm×m, where the distribution of A0 is statistically close to the uniform distribution over ℤqn×m and the length T˜A0≤Onlogq.(2)
Select uniformly two matrixesA1,B∈ℤqn×m at random. Set real number σ≥T˜A0ωlogn.(3)
SetH as an identity encoding function.Output public parameterspp=A0,A1,B,H,σ and master secret key msk=TA0.Extractpp,id,mskInput public parameterspp, user’s identity id∈ℤqn, and master secret key msk=TA0.(1)
Encode the user’s identityid as Fid=A0|A1+HidB.(2)
Compute userid’s private key skid using Bonsai Trees algorithm. skid=Rand BasisExt BasisTA0,Fid,σ is a “short” basis of ∧q⊥Fid satisfying Fidskid=0, skid∈ℤ2m×2m, and skid≤σ2m.Output user’s private keyskid.Encpp,id,μInput public parameterspp, user’s identity id, and message μ∈0,1.(1)
Encode identityid as Fid=A0|A1+HidB.(2)
Choose a uniformly random vectore1∈−r,r2m and uniformly random nonzero vector s∈ℤqn, set b1=1,0,…,02m.(3)
SetCid=FidTs+2e1+μb1modq.Output the second-level ciphertextCid.ReKeyGenpp,skidi,idjInput public parameterspp, user idi’s private key skidi, and encode user idj to obtain the public key Fidj=A0|A1+HidjB.Choose a uniformly random nonzero matrixR1∈−1,12m×2m.Choose a uniformly random nonzero matrixL1∈ℤqn×2m.Output the re-encryption keyrkidi⟶idj=FidjTL1+R1skidiTmodq = R1skidiT+FidjTL1modq.ReEncpp,rkidi⟶idj,CidiInput public parameterspp, the re-encryption key rkidi⟶idj from idi to idj, and user idi’s ciphertext Cidi, and output user idj’s ciphertext Cidj.Cidj=rkidi⟶idjCidi+2t1modq, where t1∈−r,r2m is chosen uniformly at random.Decpp,skid,CidInput public parameterspp, user’s private key skid, and the ciphertext Cid.Output plaintextμ. Compute m=skidT−1skidTCidmodqmod2. If m=0,…,0, output μ=0, otherwise output μ=1.


### 3.2. Parameters and Correctness

To ensure the correctness of the IB-PRE scheme, the parameters should content the following requirements:(1)
According to the trapdoor generation algorithm, the conditions of D-U-LWE hard problem [21] and the left hash lemma [22] require m≥6nlogq(2)
In the private key extraction algorithm, in order to correctly generate the user’s private key, the algorithm uses the randomizing control procedure, satisfyingσ≥T˜A0ωlogn(3)
To make the D-U-LWE problem hard, the parametersr should satisfy r≥2n0.5+ϵm, where real number ϵ>0(4)
In the algorithm Dec⋅, we can achieve the decryption correctness of the second-level ciphertext by making sure the following inequalities are correct: skidTe1≤rσ2mm=2rσm<q/4. μskidTb1≤σ2m<q/2Therefore,2rσm<q/4, namely, q>42rσm.(5)
In the algorithm Dec⋅, we can achieve the decryption correctness of the first-level ciphertext by making sure the following inequalities are correct:R1≤124m=24m [22]skidjTR1skidiTe1≤482m2σ2r<q/4μskidjTR1skidiTb1≤48m3/2σ2<q/4skidjTt1<2mσr<q/8Therefore,482m2σ2r<q/4, namely, q>1922m2σ2r.According to the above five constraints in the IB-PRE scheme, we choose parameters as follows:m=6n⌈logq⌉, σ=Onlogqωlogn, q=Om2σ2r, and r=2n0.5+ϵm.For the second-level ciphertextCid, the correctness of the decryption is shown as follows:(3)skidTCidmodq=skidTFidTs+2e1+μb1modq=skidT2e1+μb1modq=2skidTe1+μskidTb1modq.According to aforementioned the forth constraint, we can obtainskidTCidmodq=2skidTe1+μskidTb1.(4)skidT−1skidTCidmodqmod2=skidT−12skidTe1+μskidTb1mod2=2e1+μb1mod2=μb1mod2=μb1.Ifμb1=0, then μ=0, otherwise μ=1.For the first-level ciphertextCidj, the correctness of the decryption is shown as follows:(5)Cidj=rkidi⟶idjCidi+2t1modq=R1skidiT+FidjTL1FidiTs+2e1+μb1+2t1modq=R1skidiT2e1+μb1+FidjTL1FidiTs+2e1+μb1+2t1modq=FidjTL1FidiTs+2rkidi⟶idje1+t1+μrkidi⟶idjb1modq.Lets2=L1FidiTs, e2=rkidi⟶idje1+t1, b2=rkidi⟶idjb1, then Cidj=FidjTs2+2e2+μb2.(6)skidjTCidjmodq=skidjTFidjTs2+2e2+μb2modq=skidjTR1skidiT2e1+μb1+2skidjTt1modq=2skidjTR1skidiTe1+μskidjTR1skidiTb1+2skidjTt1modq.According to aforementioned fifth constraint, we can obtain the following constraint:(7)skidjTCidjmodq=2skidjTR1skidiTe1+μskidjTR1skidiTb1+2skidjTt1.We compute,(8)m=skidjT−1skidjTCidjmodqmod2=μR1skidiTb1mod2.Ifm=μR1skidiTb1mod2=0, output 0, otherwise output 1.Because of the left hash lemma,R1skidiT is uniform and random, the probability of the R1skidiTb1mod2=0 is 1/4m. The error probability of the first-level decryption is 1/4m and is negligible.


### 3.3. Security Analysis

Theorem 1.
Letq, m, σ, and r be as in the aforementioned qualifications, then the IB-PRE scheme described above is IND-sID-CPA secure, assuming the D-U-LWE problem is hard.Proof.
In order to show the scheme is secure, we use a sequence of games to prove the advantage of adversaryA is negligible.
In the sequence of games,Game0 is identical with original IB-PRE scheme, and the advantage of adversary A is zero in Game3. Finally, we demonstrate that adversary A cannot distinguish four games and win in Game0 with negligible advantage, while the D-U-LWE hard problem is used for proving Game2 and Game3 indistinguishable.


#### 3.3.1. Game0

This is the original IB-PRE scheme. AdversaryA creates the challenge identity id∗ before the setup phase. Challenger ℬ gains the private key of user id≠id∗ and re-encryption keys from id to other users, with algorithms Extract ⋅ and ReKeyGen ⋅, separately.


#### 3.3.2. Game1

The difference betweenGame0 and Game1 is only the generation type of the public matrix A1. In Game1, challenger ℬ produces A1 by calculating A1=A0R∗−Hid∗B, where R∗∈−1,1m×m denotes a uniformly random matrix. The rest of the part of Game1 is same with Game0.InGame1, according to the left hash lemma, the distribution of A0R∗ is statistically close to the uniform distribution over ℤqn×m, hence, the distribution of A1 is statistically close to the uniform distribution over ℤqn×m. Therefore, in the view of adversary A, A1 in Game0 and Game1 are indistinguishable; furthermore, Game0 and Game1 are indistinguishable as well.


#### 3.3.3. Game2

InGame2, we change the way of the generation about public matrixes A0 and B, where A0 is uniformly and randomly sampled from ℤqn×m and B is generated by the trapdoor generation algorithm TrapGen ⋅ with a “short” trapdoor basis TB of Λq⊥B; hence, B is statistically close to uniformly random distribution over ℤn×m. A0 and B in Game1 and Game2 are indistinguishable severally. The choice of A1 is identical as in Game1.Challengerℬ responds to the private key query of the user id≠id∗ as follows:(1)
Encodeid as Fid=A0|A1+HidB=A0|A0R∗+Hid−Hid∗B.(2)
Generate a basisTFid of Λq⊥Fid using the algorithm SampleRight ⋅ [22] in which the syndrome is zero vector.(3)
Generateid’s private key skid using the randomizing control procedure in the Bonsai Trees algorithm, where skid=Rand BasisTFid,σ is a “short” basis of ∧q⊥Fid satisfying Fidskid=0. Hence, the distribution of skid is statistically indistinguishable with the one of skid in Game1.When adversaryA proposes the query for re-encryption key rkidi⟶idj, challenger ℬ replies A with rkidi⟶idj=R1skidT+FidjTL1. Therefore, in the view of adversary A, rkidi⟶idj in Game1 and Game2 are indistinguishable, Game1 and Game2 are indistinguishable as well.


#### 3.3.4. Game3

Challengerℬ uniformly chooses ciphertext Cid∗∈ℤq2m at random and returns Cid∗ to adversary A. Because of the randomness and uniformity of the ciphertext, the advantage of adversary A is zero in the game.Lemma 3.
Under the D-U-LWE hard problem,Game2 and Game3 are indistinguishable in the view of adversary A.Proof.
Assume that adversaryA can distinguish the Game2 and Game3 with non-negligible advantage ε, we can construct an algorithm (simulator) ℬ to solve the D-U-LWE hard problem.
Algorithmℬ receives a random instance F,Y∈ℤqn×2m×ℤq2m, where F,Y is either Fid∗,Fid∗Ts+e1modq or a uniformly random element over ℤqn×2m×ℤq2m.
Next, algorithmℬ receives messages μ0, μ1∈0,1, and challenge identity id∗. Algorithm ℬ randomly selects i∈0,1 and returns the challenge ciphertext 2Y+μib1modq to adversary A. If adversary A correctly guesses i, outputs 1, otherwise outputs 0.
On the one hand, ifY is uniformly chosen at random, regardless of the choice of i, the challenge ciphertext is uniformly random, therefore, algorithm ℬ outputs 1 with probability 1/2 at most.
On the other hand, ifY=Fid∗Ts+e1modq, the challenge ciphertext is 2Y+μib1=Fid∗Ts′+2e1+μib1modq, where s′=2smodq is uniformly random (because of q,2=1). At this time, adversary A correctly guesses the i with probability 1/2+ε.
The probability of the algorithmℬ receiving a random instance F,Y is 1/2. According to the assumption, adversary A correctly guesses i with the probability 1/21/2+1/2+ε=1+ε/2, this means that algorithm ℬ outputs 1 with the probability 1+ε/2, and therefore breaks the D-U-LWE hard problem with the advantage ε/2, and it is non-negligible.
Because D-U-LWE problem is the hard problem, the advantage of algorithmℬ in breaking the D-U-LWE hard problem is negligible. That is contradictory, so adversary A’s advantage in distinguishing Game2 with Game3 is negligible.
In conclusion, becauseGame0 and Game1 are indistinguishable for adversary A, Game1 and Game2, and Game2 and Game3 are also the same, meanwhile, adversary A’s advantage is zero in the Game3, so the advantage of the adversary A is negligible in the IB-PRE scheme described above and the IB-PRE scheme is IND-sID-CPA secure in the standard model.


## 3.1. Construction

SetupnInput secret parametern∈ℤ, q=polyn is an odd prime number, and m=Onlogq=Onlogn.(1)
Use trapdoor generation algorithm TrapGenq,n,m to generate random matrix A0∈ℤqn×m and a “short” trapdoor basis TA0∈ℤm×m, where the distribution of A0 is statistically close to the uniform distribution over ℤqn×m and the length T˜A0≤Onlogq.(2)
Select uniformly two matrixesA1,B∈ℤqn×m at random. Set real number σ≥T˜A0ωlogn.(3)
SetH as an identity encoding function.Output public parameterspp=A0,A1,B,H,σ and master secret key msk=TA0.Extractpp,id,mskInput public parameterspp, user’s identity id∈ℤqn, and master secret key msk=TA0.(1)
Encode the user’s identityid as Fid=A0|A1+HidB.(2)
Compute userid’s private key skid using Bonsai Trees algorithm. skid=Rand BasisExt BasisTA0,Fid,σ is a “short” basis of ∧q⊥Fid satisfying Fidskid=0, skid∈ℤ2m×2m, and skid≤σ2m.Output user’s private keyskid.Encpp,id,μInput public parameterspp, user’s identity id, and message μ∈0,1.(1)
Encode identityid as Fid=A0|A1+HidB.(2)
Choose a uniformly random vectore1∈−r,r2m and uniformly random nonzero vector s∈ℤqn, set b1=1,0,…,02m.(3)
SetCid=FidTs+2e1+μb1modq.Output the second-level ciphertextCid.ReKeyGenpp,skidi,idjInput public parameterspp, user idi’s private key skidi, and encode user idj to obtain the public key Fidj=A0|A1+HidjB.Choose a uniformly random nonzero matrixR1∈−1,12m×2m.Choose a uniformly random nonzero matrixL1∈ℤqn×2m.Output the re-encryption keyrkidi⟶idj=FidjTL1+R1skidiTmodq = R1skidiT+FidjTL1modq.ReEncpp,rkidi⟶idj,CidiInput public parameterspp, the re-encryption key rkidi⟶idj from idi to idj, and user idi’s ciphertext Cidi, and output user idj’s ciphertext Cidj.Cidj=rkidi⟶idjCidi+2t1modq, where t1∈−r,r2m is chosen uniformly at random.Decpp,skid,CidInput public parameterspp, user’s private key skid, and the ciphertext Cid.Output plaintextμ. Compute m=skidT−1skidTCidmodqmod2. If m=0,…,0, output μ=0, otherwise output μ=1.


## 3.2. Parameters and Correctness

To ensure the correctness of the IB-PRE scheme, the parameters should content the following requirements:(1)
According to the trapdoor generation algorithm, the conditions of D-U-LWE hard problem [21] and the left hash lemma [22] require m≥6nlogq(2)
In the private key extraction algorithm, in order to correctly generate the user’s private key, the algorithm uses the randomizing control procedure, satisfyingσ≥T˜A0ωlogn(3)
To make the D-U-LWE problem hard, the parametersr should satisfy r≥2n0.5+ϵm, where real number ϵ>0(4)
In the algorithm Dec⋅, we can achieve the decryption correctness of the second-level ciphertext by making sure the following inequalities are correct: skidTe1≤rσ2mm=2rσm<q/4. μskidTb1≤σ2m<q/2Therefore,2rσm<q/4, namely, q>42rσm.(5)
In the algorithm Dec⋅, we can achieve the decryption correctness of the first-level ciphertext by making sure the following inequalities are correct:R1≤124m=24m [22]skidjTR1skidiTe1≤482m2σ2r<q/4μskidjTR1skidiTb1≤48m3/2σ2<q/4skidjTt1<2mσr<q/8Therefore,482m2σ2r<q/4, namely, q>1922m2σ2r.According to the above five constraints in the IB-PRE scheme, we choose parameters as follows:m=6n⌈logq⌉, σ=Onlogqωlogn, q=Om2σ2r, and r=2n0.5+ϵm.For the second-level ciphertextCid, the correctness of the decryption is shown as follows:(3)skidTCidmodq=skidTFidTs+2e1+μb1modq=skidT2e1+μb1modq=2skidTe1+μskidTb1modq.According to aforementioned the forth constraint, we can obtainskidTCidmodq=2skidTe1+μskidTb1.(4)skidT−1skidTCidmodqmod2=skidT−12skidTe1+μskidTb1mod2=2e1+μb1mod2=μb1mod2=μb1.Ifμb1=0, then μ=0, otherwise μ=1.For the first-level ciphertextCidj, the correctness of the decryption is shown as follows:(5)Cidj=rkidi⟶idjCidi+2t1modq=R1skidiT+FidjTL1FidiTs+2e1+μb1+2t1modq=R1skidiT2e1+μb1+FidjTL1FidiTs+2e1+μb1+2t1modq=FidjTL1FidiTs+2rkidi⟶idje1+t1+μrkidi⟶idjb1modq.Lets2=L1FidiTs, e2=rkidi⟶idje1+t1, b2=rkidi⟶idjb1, then Cidj=FidjTs2+2e2+μb2.(6)skidjTCidjmodq=skidjTFidjTs2+2e2+μb2modq=skidjTR1skidiT2e1+μb1+2skidjTt1modq=2skidjTR1skidiTe1+μskidjTR1skidiTb1+2skidjTt1modq.According to aforementioned fifth constraint, we can obtain the following constraint:(7)skidjTCidjmodq=2skidjTR1skidiTe1+μskidjTR1skidiTb1+2skidjTt1.We compute,(8)m=skidjT−1skidjTCidjmodqmod2=μR1skidiTb1mod2.Ifm=μR1skidiTb1mod2=0, output 0, otherwise output 1.Because of the left hash lemma,R1skidiT is uniform and random, the probability of the R1skidiTb1mod2=0 is 1/4m. The error probability of the first-level decryption is 1/4m and is negligible.


## 3.3. Security Analysis

Theorem 1.
Letq, m, σ, and r be as in the aforementioned qualifications, then the IB-PRE scheme described above is IND-sID-CPA secure, assuming the D-U-LWE problem is hard.Proof.
In order to show the scheme is secure, we use a sequence of games to prove the advantage of adversaryA is negligible.
In the sequence of games,Game0 is identical with original IB-PRE scheme, and the advantage of adversary A is zero in Game3. Finally, we demonstrate that adversary A cannot distinguish four games and win in Game0 with negligible advantage, while the D-U-LWE hard problem is used for proving Game2 and Game3 indistinguishable.


### 3.3.1. Game0

This is the original IB-PRE scheme. AdversaryA creates the challenge identity id∗ before the setup phase. Challenger ℬ gains the private key of user id≠id∗ and re-encryption keys from id to other users, with algorithms Extract ⋅ and ReKeyGen ⋅, separately.


### 3.3.2. Game1

The difference betweenGame0 and Game1 is only the generation type of the public matrix A1. In Game1, challenger ℬ produces A1 by calculating A1=A0R∗−Hid∗B, where R∗∈−1,1m×m denotes a uniformly random matrix. The rest of the part of Game1 is same with Game0.InGame1, according to the left hash lemma, the distribution of A0R∗ is statistically close to the uniform distribution over ℤqn×m, hence, the distribution of A1 is statistically close to the uniform distribution over ℤqn×m. Therefore, in the view of adversary A, A1 in Game0 and Game1 are indistinguishable; furthermore, Game0 and Game1 are indistinguishable as well.


### 3.3.3. Game2

InGame2, we change the way of the generation about public matrixes A0 and B, where A0 is uniformly and randomly sampled from ℤqn×m and B is generated by the trapdoor generation algorithm TrapGen ⋅ with a “short” trapdoor basis TB of Λq⊥B; hence, B is statistically close to uniformly random distribution over ℤn×m. A0 and B in Game1 and Game2 are indistinguishable severally. The choice of A1 is identical as in Game1.Challengerℬ responds to the private key query of the user id≠id∗ as follows:(1)
Encodeid as Fid=A0|A1+HidB=A0|A0R∗+Hid−Hid∗B.(2)
Generate a basisTFid of Λq⊥Fid using the algorithm SampleRight ⋅ [22] in which the syndrome is zero vector.(3)
Generateid’s private key skid using the randomizing control procedure in the Bonsai Trees algorithm, where skid=Rand BasisTFid,σ is a “short” basis of ∧q⊥Fid satisfying Fidskid=0. Hence, the distribution of skid is statistically indistinguishable with the one of skid in Game1.When adversaryA proposes the query for re-encryption key rkidi⟶idj, challenger ℬ replies A with rkidi⟶idj=R1skidT+FidjTL1. Therefore, in the view of adversary A, rkidi⟶idj in Game1 and Game2 are indistinguishable, Game1 and Game2 are indistinguishable as well.


### 3.3.4. Game3

Challengerℬ uniformly chooses ciphertext Cid∗∈ℤq2m at random and returns Cid∗ to adversary A. Because of the randomness and uniformity of the ciphertext, the advantage of adversary A is zero in the game.Lemma 3.
Under the D-U-LWE hard problem,Game2 and Game3 are indistinguishable in the view of adversary A.Proof.
Assume that adversaryA can distinguish the Game2 and Game3 with non-negligible advantage ε, we can construct an algorithm (simulator) ℬ to solve the D-U-LWE hard problem.
Algorithmℬ receives a random instance F,Y∈ℤqn×2m×ℤq2m, where F,Y is either Fid∗,Fid∗Ts+e1modq or a uniformly random element over ℤqn×2m×ℤq2m.
Next, algorithmℬ receives messages μ0, μ1∈0,1, and challenge identity id∗. Algorithm ℬ randomly selects i∈0,1 and returns the challenge ciphertext 2Y+μib1modq to adversary A. If adversary A correctly guesses i, outputs 1, otherwise outputs 0.
On the one hand, ifY is uniformly chosen at random, regardless of the choice of i, the challenge ciphertext is uniformly random, therefore, algorithm ℬ outputs 1 with probability 1/2 at most.
On the other hand, ifY=Fid∗Ts+e1modq, the challenge ciphertext is 2Y+μib1=Fid∗Ts′+2e1+μib1modq, where s′=2smodq is uniformly random (because of q,2=1). At this time, adversary A correctly guesses the i with probability 1/2+ε.
The probability of the algorithmℬ receiving a random instance F,Y is 1/2. According to the assumption, adversary A correctly guesses i with the probability 1/21/2+1/2+ε=1+ε/2, this means that algorithm ℬ outputs 1 with the probability 1+ε/2, and therefore breaks the D-U-LWE hard problem with the advantage ε/2, and it is non-negligible.
Because D-U-LWE problem is the hard problem, the advantage of algorithmℬ in breaking the D-U-LWE hard problem is negligible. That is contradictory, so adversary A’s advantage in distinguishing Game2 with Game3 is negligible.
In conclusion, becauseGame0 and Game1 are indistinguishable for adversary A, Game1 and Game2, and Game2 and Game3 are also the same, meanwhile, adversary A’s advantage is zero in the Game3, so the advantage of the adversary A is negligible in the IB-PRE scheme described above and the IB-PRE scheme is IND-sID-CPA secure in the standard model.


## 3.3.1. Game0

This is the original IB-PRE scheme. AdversaryA creates the challenge identity id∗ before the setup phase. Challenger ℬ gains the private key of user id≠id∗ and re-encryption keys from id to other users, with algorithms Extract ⋅ and ReKeyGen ⋅, separately.


## 3.3.2. Game1

The difference betweenGame0 and Game1 is only the generation type of the public matrix A1. In Game1, challenger ℬ produces A1 by calculating A1=A0R∗−Hid∗B, where R∗∈−1,1m×m denotes a uniformly random matrix. The rest of the part of Game1 is same with Game0.InGame1, according to the left hash lemma, the distribution of A0R∗ is statistically close to the uniform distribution over ℤqn×m, hence, the distribution of A1 is statistically close to the uniform distribution over ℤqn×m. Therefore, in the view of adversary A, A1 in Game0 and Game1 are indistinguishable; furthermore, Game0 and Game1 are indistinguishable as well.


## 3.3.3. Game2

InGame2, we change the way of the generation about public matrixes A0 and B, where A0 is uniformly and randomly sampled from ℤqn×m and B is generated by the trapdoor generation algorithm TrapGen ⋅ with a “short” trapdoor basis TB of Λq⊥B; hence, B is statistically close to uniformly random distribution over ℤn×m. A0 and B in Game1 and Game2 are indistinguishable severally. The choice of A1 is identical as in Game1.Challengerℬ responds to the private key query of the user id≠id∗ as follows:(1)
Encodeid as Fid=A0|A1+HidB=A0|A0R∗+Hid−Hid∗B.(2)
Generate a basisTFid of Λq⊥Fid using the algorithm SampleRight ⋅ [22] in which the syndrome is zero vector.(3)
Generateid’s private key skid using the randomizing control procedure in the Bonsai Trees algorithm, where skid=Rand BasisTFid,σ is a “short” basis of ∧q⊥Fid satisfying Fidskid=0. Hence, the distribution of skid is statistically indistinguishable with the one of skid in Game1.When adversaryA proposes the query for re-encryption key rkidi⟶idj, challenger ℬ replies A with rkidi⟶idj=R1skidT+FidjTL1. Therefore, in the view of adversary A, rkidi⟶idj in Game1 and Game2 are indistinguishable, Game1 and Game2 are indistinguishable as well.


## 3.3.4. Game3

Challengerℬ uniformly chooses ciphertext Cid∗∈ℤq2m at random and returns Cid∗ to adversary A. Because of the randomness and uniformity of the ciphertext, the advantage of adversary A is zero in the game.Lemma 3.
Under the D-U-LWE hard problem,Game2 and Game3 are indistinguishable in the view of adversary A.Proof.
Assume that adversaryA can distinguish the Game2 and Game3 with non-negligible advantage ε, we can construct an algorithm (simulator) ℬ to solve the D-U-LWE hard problem.
Algorithmℬ receives a random instance F,Y∈ℤqn×2m×ℤq2m, where F,Y is either Fid∗,Fid∗Ts+e1modq or a uniformly random element over ℤqn×2m×ℤq2m.
Next, algorithmℬ receives messages μ0, μ1∈0,1, and challenge identity id∗. Algorithm ℬ randomly selects i∈0,1 and returns the challenge ciphertext 2Y+μib1modq to adversary A. If adversary A correctly guesses i, outputs 1, otherwise outputs 0.
On the one hand, ifY is uniformly chosen at random, regardless of the choice of i, the challenge ciphertext is uniformly random, therefore, algorithm ℬ outputs 1 with probability 1/2 at most.
On the other hand, ifY=Fid∗Ts+e1modq, the challenge ciphertext is 2Y+μib1=Fid∗Ts′+2e1+μib1modq, where s′=2smodq is uniformly random (because of q,2=1). At this time, adversary A correctly guesses the i with probability 1/2+ε.
The probability of the algorithmℬ receiving a random instance F,Y is 1/2. According to the assumption, adversary A correctly guesses i with the probability 1/21/2+1/2+ε=1+ε/2, this means that algorithm ℬ outputs 1 with the probability 1+ε/2, and therefore breaks the D-U-LWE hard problem with the advantage ε/2, and it is non-negligible.
Because D-U-LWE problem is the hard problem, the advantage of algorithmℬ in breaking the D-U-LWE hard problem is negligible. That is contradictory, so adversary A’s advantage in distinguishing Game2 with Game3 is negligible.
In conclusion, becauseGame0 and Game1 are indistinguishable for adversary A, Game1 and Game2, and Game2 and Game3 are also the same, meanwhile, adversary A’s advantage is zero in the Game3, so the advantage of the adversary A is negligible in the IB-PRE scheme described above and the IB-PRE scheme is IND-sID-CPA secure in the standard model.


## 4. Property

The IB-PRE scheme has desired properties as follows:


### 4.1. Multihop

An IB-PRE scheme is multihop if ciphertext is re-encrypted multiple times, on the contrary, it is single-hop. Multihop supports multiple encryption of ciphertext, that is, it allows delegating decryption right among multiple users. Single-hop only allows delegating decryption right between two users. In the multiuser scenario, multihop property is required generally.For simplicity, we present the identities of the users as1,2,…,vv>1, where the users participate in the process of re-encryption. According to the IB-PRE scheme, we can obtain the re-encryption procedure, which is performed from user 1 to user l1<l≤v as follows:(9)C1=F1Ts1+2e1+μb1modq,C2=rk1⟶2C1+2t2modq=F2TL1F1Ts1+2rk1⟶2e1+t2+μrk1⟶2b1modq,C3=rk2⟶3C2+2t3modq=F3TL2F2TL1F1Ts1+2rk1⟶2rk2⟶3e1+2rk2⟶3t2+2t3+μrk1⟶2rk2⟶3b1modq.⋮(10)Cl=rkl−1⟶lCl−1+2tlmodq=FlT∏i=1l−1LiFiTs1+2∑j=2l∏i=jlrki−1⟶itj−1+tl+μ∏i=2lrki−1⟶ib1modq=FlTsl+2el+μblmodq,where sl=∏i=1l−1LiFiTs1, e1=t1, el=∑j=2l∏i=jlrki−1⟶itj−l+tl, and bl=∏i=2lrki−1⟶ib1.According to the mathematical induction, the above equation is correct. If each entry of the2sklTel+μsklTbl is less than q, the error probability of the decryption is 1/4m and is negligible.


### 4.2. Unidirectionality

The property is related to the direction of delegation, and is portrayed by re-encryption key. Unidirectionality means the decryption rights are only authorized from delegator to delegatee, otherwise, the scheme is bidirectional. The bidirectional scheme requires delegator and delegatee are confident in each other, however, the situation is not common in most applications. Because re-encryption keyrkidi⟶idj=FidjTL1+R1skidiTmodq is U-LWE form, rkidi⟶idj is uniformly pseudo-random in the view of the proxy and the delegatee under the D-U-LWE assumption, and the proxy and the delegatee are not able to construct a re-encryption key from delegatee to delegator, and our scheme is unidirectional.


### 4.3. Collusion-Resistance

The property is that the plaintext or private key of delegator cannot be leaked against collusion attack made by the delegatee and the proxy, that is, the private key of the delegator cannot be obtained from the re-encryption key and the delegatee’s private key. Because re-encryption keyrkidi⟶idj is pseudo-random under the D-U-LWE assumption, the proxy and the delegatee cannot obtain the private key of delegator with collusion.


### 4.4. Noninteractivity

The property is that the delegator is capable of yielding a re-encryption key using the private key of delegator and the public key of delegatee without the participation of delegatee. In most cases, interactivity is not a desired property, because it can lead to communication overheads and may even be attacked by collusion of the proxy and delegatee. From the generation process ofrkidi⟶idj, we can find that re-encryption key can be implemented alone by the delegator without interaction with the delegatee or other trusted the third parties.


### 4.5. Anonymousness

Anonymousness is that the second-level ciphertext and the first-level ciphertext do not reveal identity messages about the delegator and delegatee. This property protects the privacy of users. The distributions of the second-level ciphertext and the first-level ciphertext meet U-LWE distribution, which is pseudo-random, in our scheme, so they do not leak any identity message about the delegator and delegatee.


## 4.1. Multihop

An IB-PRE scheme is multihop if ciphertext is re-encrypted multiple times, on the contrary, it is single-hop. Multihop supports multiple encryption of ciphertext, that is, it allows delegating decryption right among multiple users. Single-hop only allows delegating decryption right between two users. In the multiuser scenario, multihop property is required generally.For simplicity, we present the identities of the users as1,2,…,vv>1, where the users participate in the process of re-encryption. According to the IB-PRE scheme, we can obtain the re-encryption procedure, which is performed from user 1 to user l1<l≤v as follows:(9)C1=F1Ts1+2e1+μb1modq,C2=rk1⟶2C1+2t2modq=F2TL1F1Ts1+2rk1⟶2e1+t2+μrk1⟶2b1modq,C3=rk2⟶3C2+2t3modq=F3TL2F2TL1F1Ts1+2rk1⟶2rk2⟶3e1+2rk2⟶3t2+2t3+μrk1⟶2rk2⟶3b1modq.⋮(10)Cl=rkl−1⟶lCl−1+2tlmodq=FlT∏i=1l−1LiFiTs1+2∑j=2l∏i=jlrki−1⟶itj−1+tl+μ∏i=2lrki−1⟶ib1modq=FlTsl+2el+μblmodq,where sl=∏i=1l−1LiFiTs1, e1=t1, el=∑j=2l∏i=jlrki−1⟶itj−l+tl, and bl=∏i=2lrki−1⟶ib1.According to the mathematical induction, the above equation is correct. If each entry of the2sklTel+μsklTbl is less than q, the error probability of the decryption is 1/4m and is negligible.


## 4.2. Unidirectionality

The property is related to the direction of delegation, and is portrayed by re-encryption key. Unidirectionality means the decryption rights are only authorized from delegator to delegatee, otherwise, the scheme is bidirectional. The bidirectional scheme requires delegator and delegatee are confident in each other, however, the situation is not common in most applications. Because re-encryption keyrkidi⟶idj=FidjTL1+R1skidiTmodq is U-LWE form, rkidi⟶idj is uniformly pseudo-random in the view of the proxy and the delegatee under the D-U-LWE assumption, and the proxy and the delegatee are not able to construct a re-encryption key from delegatee to delegator, and our scheme is unidirectional.


## 4.3. Collusion-Resistance

The property is that the plaintext or private key of delegator cannot be leaked against collusion attack made by the delegatee and the proxy, that is, the private key of the delegator cannot be obtained from the re-encryption key and the delegatee’s private key. Because re-encryption keyrkidi⟶idj is pseudo-random under the D-U-LWE assumption, the proxy and the delegatee cannot obtain the private key of delegator with collusion.


## 4.4. Noninteractivity

The property is that the delegator is capable of yielding a re-encryption key using the private key of delegator and the public key of delegatee without the participation of delegatee. In most cases, interactivity is not a desired property, because it can lead to communication overheads and may even be attacked by collusion of the proxy and delegatee. From the generation process ofrkidi⟶idj, we can find that re-encryption key can be implemented alone by the delegator without interaction with the delegatee or other trusted the third parties.


## 4.5. Anonymousness

Anonymousness is that the second-level ciphertext and the first-level ciphertext do not reveal identity messages about the delegator and delegatee. This property protects the privacy of users. The distributions of the second-level ciphertext and the first-level ciphertext meet U-LWE distribution, which is pseudo-random, in our scheme, so they do not leak any identity message about the delegator and delegatee.


## 5. Comparison

We compare our IB-PRE scheme with the other relevant IB-PRE schemes over lattice in terms of private key size, unidirectionality, collusion-resistance, multihop, and security model. The result is shown in Table1, where s is the length of message and k=⌈logq⌉.Table 1
Comparison to the related works.
CryptosystemPrivate key sizeUnidirectionalityCollusion-resistanceMultihopSecurity model[9]OmslogqNoNoYesRandom oracle model[11]Oms1+klogqYesNoNoRandom oracle model[14]Om2logqYesYesYesStandard model[16]OmnlogqNoNoYesStandard modelOur schemeOmnlogqYesYesYesStandard model


## 6. Conclusion

In the paper, we constructed a unidirectional and multihop IB-PRE scheme with underlying BGN-type encryption system based on the hardness of the D-U-LWE problem. The scheme is collusion-resistant, noninteractive and anonymous. We also prove the scheme is IND-sID-CPA secure and resists quantum attack in the standard model. Because the related operations and storage only involve polynomials with small coefficients, the scheme based on the RLWE hard problem [24] can achieve faster operations and less storage overheads. Therefore, how to construct a new multibit IB-PRE scheme based on the RLWE hard problem is one direction for future research, meanwhile, extending single-bit encryption to multibit encryption is also the other direction for future research in our scheme.



---

*Source: 3765934-2023-01-03.xml*