# Identity Based Proxy Re-encryption Scheme under LWE.

1. IntroductionIn 1998, Blaze, Bleumer and Strauss presented a new primitive called proxy re-encryption [4], of which the unique feature is the intermediation of delegation via proxy re-encryption key. In detail, the new primitive allows an intermediate agent to convert Alice's(delegator) ciphertext to Bob's(recipient) ciphertext by using proxy re-encryption key [rk.sub.Alice[right arrow]Bob] so that the latter can decrypt it. Naturally, the agent is required that cannot obtain information of Alice or Bob about the plaintext and the secret keys. For example, Alice can entrust her proxy to re-encrypt her ciphertext to B when she is out traveling. A natural idea is that Alice can decrypt the ciphertext with her private key, then uses Bob's public key to encrypt it. However, this method requires Alice to be always online. In order to solve this problem, Alice and Bob together set up proxy re-encryption key [rk.sub.Alice[right arrow]Bob], this situation is called interactive, as opposed to it, there is non-interactive that [rk.sub.Alice[right arrow]Bob] can be generated by Alice alone. The [rk.sub.Alice[right arrow]Bob] is stored in a semi-trusted server, and allows proxy to delegate Alice's ciphertext, and the server cannot decrypt it.

Green and Ateniese first proposed the identity based proxy re-encryption schemes(IB-PRE). It allows proxy to convert a ciphertext for Alice under Alice's identity to one encrypted ciphertext under Bob's identity[10][6][8]. The proxy employs a re-encryption key to complete the transformation, in the process, it could not obtain any information about the message and the private keys of Alice and Bob from the proxy re-encryption key.

Lattice based cryptography has been developed rapidly in recent years[3][2][1][13][14][15], due to the following advantages: (1)Number theoretic hard problem, large integer factoring problem and the discrete logarithm problem can be solved by quantum algorithms, so cryptographic protocols based on those problems in quantum computing system environment are no longer safe. However, so far, there have been no effective quantum algorithms to solve lattice hard problems. (2)Traditional cryptosystem is based on the hard problems in the average case. However, lattice-based cryptography is based on the hard problems in the worst case, which is stronger security.

2. Related Work

Blaze et.al proposed the first proxy re-encryption scheme in 1998[4]. Their scheme is based on the ElGamal encryption construction and it is CPA secure under the Decisional Diffie-Hellman assumption. Their re-encryption key from user A to B is [rk.sub.A[right arrow]B] = b / a, in which a and b are the private keys of A and B . Through these useful information, the proxy can easily generate the re-encryption key b/a to convert ciphertext of A to B, then it also allows to convert the ciphertext of B from the opposite direction to A. So PRE schemes like that are called bidirectional, but more desirable schemes in practical application are unidrectional for any bidirectional scheme could always be acquired by calling a unidirectional one in both directions, where the proxy only works in one direction by the re-encryption key. The possibility of using lattice as a tool for PRE scheme was shown in [16] by Xagawa, but the scheme lacks a complete formalization security analysis.

Aono et.al first proposed a CPA-secure PRE scheme based on the hardness of the standard Learning-With-Errors(LWE) problem in the standard model[9]. A unidirectional single-hop PRE based on the hardness of lattice based problem was proposed by Kirshanova[7], which is the first lattice based construction that achieves collusion resilience and non-interactivity. Green and Ateniese presented first proxy re-encryption scheme in the identity based setting[10], which is based on Decisional Diffie-Hellman assumption. Singh et.al proposed a lattice based identity based PRE scheme in the random oracle model for the single bit plaintext as well as for the multi bit plaintext [6], which is anonymous, bidirectional and multi-hop, but it does not meet the security requirement in the standard model, however, there is a potential threat in their construction, if the proxy and one of the parties collude, they can recover the secret key of another party easily, another issue is that a proxy obtained [mathematical expression not reproducible] through calculating [mathematical expression not reproducible].

Our Contribution

According to our knowledge, there does not exist any lattice based identity based PRE scheme in the standard model. In this paper, we first put forward a lattice based identity based proxy re-encryption scheme in the standard model. Our scheme satisfies the following properties [7][6]:

* Unidirectional: Unidirectional scheme allows proxy to convert a ciphertext of A to B in only one direction, but not vice versa.

* Non-interactivity: Re-encryption key [rk.sub.A[right arrow]B] can be generated by A alone using public key of B, the process does not require the participation of B and the proxy.

* Proxy transparency: Either A or B are not aware of the presence of the proxy. That is, recipients can not distinguish whether received ciphertext is the encryption by public key of recipient directly or re-encrypted by the proxy.

* Collusion resilience: The coalition of the proxy and recipient can not compute to obtain delegator's private key.

* Non-transitivity: It is hard for the proxy to re-delegate the decryption right, namely, to obtain [rk.sub.A[right arrow]C] from [rk.sub.A[right arrow]B] and [rk.sub.B[right arrow]C] by any method.

* Anonymous: Ciphertext does not reveal any information about the identity of the recipient.

* Multi-hop: A multi-hop scheme allows the proxy to perform multiple re-encryptions for a ciphertext, i.e. re-encrypt a ciphertext from A to B, then re-encrypt the result from B to C.

In our scheme, for the sake of CPA security we use the sample algorithms, include SampleRight and SampleLeft technologies in [3], to guarantee that master secret key could produce every identities' private key in the real system and simulator to answer private key query in the proof. In order to achieve the function of re-encryption, we use the G -trapdoor for lattice technology in [2] which solved LWE problem efficiently for its special structure, but it is not a simple combination of the two technologies that could achieve our desired results. Specifically, the user [id.sub.i] 's private key is separated into two components-([e.sub.i], [R.sub.i]), the generation of [e.sub.i] by using sample function SampleLeft is for correct decryption, the other one [R.sub.i] is built to achieve the effect of re-encryption. When we designed our scheme, there was an obstacle: in the process of security proof, the adversary interacts with the challenger who simulate scheme so that the adversary cannot distinguish it with real scheme, the adversary obtains the user's private key by asking the challenger private key query for he cannot get the private key on his own. The original purpose of using G -trapdoor is to generate the re-encryption key, but the adversary can obtain the user's private key through the algorithm e[left arrow]SampleRight(A|-AR+HG) since G is public parameters(We employ the gadget matrix G = I[cross product][g.sup.T] with [g.sup.T] =(1,2,...2[k.sup.-1]) in the interest of sampling vectors according to the discrete Gaussian distribution, so the basis of [mathematical expression not reproducible] is easy to get.)if we apply this G -trapdoor to IBE of [3] directly.

To solve this dilemma and avoid affecting normal private key query with challenger in proof, we introduce a random uniform matrix parameters T which constitutes a binding form of TG . With this approach, the information of G is hidded. In this case the adversary will not be able to obtain user's private keys except e [left arrow] SampleLeft(A | -AR+HTG) by a basis [T.sub.A] for [mathematical expression not reproducible]. And the challenger still answers private key query via algorithm e[left arrow]SampleRight(A|-AR+HTG) with a basis [T.sub.G] for [mathematical expression not reproducible].

Paper Outline

The rest of our paper is organized as follows. In section 2 we give some basic definitions, hard problems, some conclusions in lattice, and IB-PRE security model. In section 3 we show strong trapdoors in [2] and sample algorithms in [3]. In section 4 we present a CPA-secure IB-PRE scheme in the standard model, and prove the security of our scheme in section 5. In section 6 we conclude this paper.

3. Preliminaries

3.1 Identity-Based Unidirectional Proxy Re-encryption Scheme (IB-uPRE)

An Identity-Based unidirectional proxy re-encryption scheme is a tuple of algorithms-(Setup, Extract, Encrypt, ReKeyGen, ReEnc, Decrypt) [6]:

* Setup([lambda]): On input a security [lambda], output the public parameters PP and master secret key MK.

* Extract(PP, MK, id): On input public parameters PP, master secret key MK, and an identity id, output the private key S[K.sub.id] corresponding to the identity id .

* Encrypt(PP, id, M): On input public parameters PP, an identity id, and a message M, this algorithm outputs ciphertext [C.sub.id].

* ReKeyGen(PP, [sk.sub.id], [id.sub.i], [id.sub.j]): On input a secret key [sk.sub.id], the algorithm output a re-encryption key [rk.sub.i,j].

* ReEnc(PP, [C.sub.idi], [rk.sub.i,j]): On input a ciphertext [mathematical expression not reproducible] of identity [id.sub.i] and re-encryption key [rk.sub.i,j], the algorithm outputs a re-encrypted ciphertext [C.sub.id], for an identity [id.sub.j].

* Decrypt(PP, [sk.sub.id], [C.sub.id]): On input public parameters PP, a private key [sk.sub.id] of identity id and a ciphertext [C.sub.id], this algorithm outputs message M.

Correctness Identity-Based Unidrectional Proxy Re-encryption Scheme is correct if:

* For all PP, [sk.sub.id] outputted by Extract and for all M in plaintext space, it holds that Decrypt([sk.sub.id], Encrypt(id, M))=M.

* For re-encryption key [rk.sub.i,j] outputted by ReKeyGen and for any [mathematical expression not reproducible] outputted by Encrypt (PP, [id.sub.i], M), and for all M in plaintext space, it holds that Decrypt [sk.sub.id], ReEnc([rk.sub.i,j], [mathematical expression not reproducible])=M.

Definition 1. A proxy re-encryption system is called multi-hop if a proxy can re-encrypted the encrypted ciphertext repeatedly. By comparison in a signle-hop system, a ciphertext can be re-encrypted only once.

Whether our system is single-hop or multi-hop, the requirements of correctness for decryption are the same. That is to say, we can obtain the plaintext message by using decryption algorithm from the resulting ciphertext. No matter what the ciphertext is, it just needs produced or re-encrypted.

Security Game[8,10] We define IB-uPRE selective-ID security using a series of games that are played between the challenger and the adversary. This security includes semantic security and recipient anonymity. The game plays as follows.

Before introducing the game model, we first divide all users into two categories: honest user and corrupted user. HU represents honest user that the adversary only knows their public key, and CU represents corrupted user that the adversary not only knows their public key, but also knows their private key. We let M denote the message space and let C denote the ciphertext space.

Init The adversary publishes the target identity id*, which he wants to attack.

Setup The challenger runs Setup([1.sup.n]) and gives the public parameters PP to adversary and keeps the master key MK to itself. HU and CU are defined as above.

Phase 1 The adversary can make the following queries:

* The adversary can ask a private key query on identity id except identity id*, the challenger responds by running Extract algorithm to generate a private key [sk.sub.id] for identity id and sents it to the adversary. The adversary can repeat issue query for different identities polynomial times.

* The adversary can ask a re-encryption key query [rk.sub.i,j] from identity [id.sub.i] to identity [id.sub.j], the challenger responds by running ReKeyGen algorithm to generate a re-encryption key [rk.sub.i] j from identity [id.sub.i] to identity [id.sub.j] and sents it to the adversary, all queries where i = j or i [member of] HU, j [member of] CU are ignored. The adversary can repeat polynomial times for different couple of identities.

* The adversary can ask re-encryption query [mathematical expression not reproducible] from ([id.sub.i], [id.sub.j], [mathematical expression not reproducible]), the challenger responds by running ReKeyGen algorithm to generate a re-encryption key [rk.sub.i,j] from identity [id.sub.i] to identity [id.sub.j] and then the challenger generates ciphertext [C.sub.j] by running ReEnc algorithm, and returns [C.sub.j] to the adversary. All queries where i = j or i [member of] HU, j [member of] CU are ignored. The adversary can repeat polynomial times for different couples of identities.

Challenge Once adversary considers that Phase 1 could be over then it outputs a plaintext M [member of]M which he wishes to challenge on, and submits identity id* and M to challenger, id* should be in HU. The challenger picks a random bit r [member of] {0,1} and a random ciphertext C. If r = 0, it sets the challenge ciphertext to [C.sub.id]* = Encrypt(PP,id*,m). If r = 1, it sets the challenge ciphertext to [C.sub.id]* = C . Afterwards it sends [C.sub.id]* as a challenge ciphertext to the adversary.

Phase 2 The adversary could ask extra queries that for private key query, re-encryption key query and re-encryption query on the identity id [NOT EQUAL TO] id*, the challenger responds are the same as in Phase 1.

Guess Finally, the adversary outputs a guess r' [member of] {0,1} and wins if r = r'.

We refer to the adversary A in above game as an IND-sID-CPA adversary. We define the advantage of the adversary A in attacking an IB-uPRE scheme [epsilon] as

Ad[v.sub.[epsilon], [LAMBDA]] =| Pr[ r = r ]-[1-2]

Definition 2. We say that an IB-uPRE scheme is IND-sID-CPA if for all probabilistic polynomial time algorithm A and negligible function [epsilon], we always have that Ad[v.sub.[epsilon],A] is a negligible function, that is, Ad[v.sub.[epsilon], [LAMBDA]][less than or equal to][epsilon].

3.2 Lattice Definition

Definition 3 (Integer Lattice[13,15]). Let B = [[b.sub.1]|...|[b.sub.m]][member of][R.sup.mxm] be a mxm matrix whose columns are linearly independent vectors [b.sub.1],...,[b.sub.m] [member of] [R.sup.m] . The m-dimensional full-rank lattice [LAMBDA] generated by B is the set,

[mathematical expression not reproducible]

Here, we are interested in integer lattices, i.e., when L is contained in [Z.sup.m]. We let det([LAMBDA]) denote the determinant of [LAMBDA].

Definition 4 (q-ary lattice). For prime q, [mathematical expression not reproducible] and [mathematical expression not reproducible], define:

[mathematical expression not reproducible]

We can observe that if [mathematical expression not reproducible] then [mathematical expression not reproducible] and hence [mathematical expression not reproducible] is a shift of [mathematical expression not reproducible]

3.3 The Gram-Schmidt Norm

Definition 5 (Gram-Schmidt norm[13]). Let S be a set of vectors S = {[s.sub.1],...,[s.sub.k]} in [R.sup.m]. We use the following standard notations:

* ||S|| denotes the [L.sub.2] length of the longest in S, i.e., [max.sub.1[less than or equal to]i[less than or equal to]k ]||[s.sub.i]||.

* S = {[s.sub.1],...,[s.sub.k]}[subset] [R.sup.m] denotes the Gram-Schmidt orthogonalization of the vectors [s.sub.1],...,[s.sub.k] taken in that order.

We refer to ||S|| as the Gram-Schmidt norm of S.

Lemma 1 ([17], Lemma 7.1). There is a deterministic poly-time algorithm ToBasis(S,B) that, given a full rank set S of lattice vectors in [LAMBDA] = L(B), outputs a basis T of [LAMBDA] such tha ||[t.sub.i]|| [less than or equal to] [s.sub.i] for all i.

In 1996, Ajtai[18] showed how to sample an essentially uniform matrix [mathematical expression not reproducible] with an associated basis [S.sub.A] of [mathematical expression not reproducible] with low Gram-Schmidt norm. Here we use an improved algorithm from [1]. The following heorems 3.2 are derived from [1] taking [sigma] := [1/3].

Theorem 1. Let q [greater than or equal to] 3 be odd and m:=[6nlog q]. There is a probabilistic polynomial-time algorithm TrapGen(q,n) that outputs a pair ([mathematical expression not reproducible]) such that A is statistically close to a uniform matrix in [mathematical expression not reproducible] and S is a basis for [mathematical expression not reproducible] satisfying

||S|| [less than or equal to] O([square root of (nlogq)]) and ||S||[less than or equal to]O(nlogq)

with all but negligible probability in n.

3.4 The LWE Problems

Construction of this paper reduces to the Learning with Errors problem, which may be seen as average case problem related to the family of lattices described above.

Definition 6 (Learning with Errors[19]). For a prime q, a positive integer n, and a distribution X over [Z.sub.q], the LW[E.sub.q,x] problem is to distinguish, given oracle access to any desired m = poly(n) samples, between the distribution [A.sub.s,x] (for uniformly random and secret [mathematical expression not reproducible])and the uniform distribution over [mathematical expression not reproducible].

We give an outline of Gaussian distributions over lattice. For any s > 0 and dimension m [greater than or equal to] 1, the Gaussian function [[rho].sub.s]:[R.sup.m] [right arrow] (0,1] is defined as [[rho].sub.s](x) = exp(-[pi] [|| x ||.sup.2]/[s.sup.2]). For any coset [mathematical expression not reproducible], and probability zero elsewhere. We summarize several facts from the literature about discrete Gaussian over lattices, again specialized to our family of interest.

Lemma 2 ([21], Lemma 4.4). For any n-dimensional lattice [LAMBDA], vector c [member of] [R.sup.n], and reals 0 < [epsilon] < 1, s [greater than or equal to] [[eta].sub.[epsilon]]([LAMBDA]), we have

[mathematical expression not reproducible]

Lemma 3 ([13]). There are two PPT algorithms SampeGaussia(A,[T.sub.A], [sigma],c) and a PPT algorithm SampePre(A,[T.sub.A], [sigma],u), the former returns [mathematical expression not reproducible] drawn from a distribution statistically close to [D.sub.[LAMBDA],s,c], and the latter returns [mathematical expression not reproducible] sampled from a distribution statistically close to [mathematical expression not reproducible] is not empty, where [T.sub.A] be a basis for [mathematical expression not reproducible] and [sigma][greater than or equal to]||[T.sub.A]| [omega] ([square root of (logm)]), for c [member os] [R.sup.m] and [mathematical expression not reproducible].

3.5 Encoding Identities as Matrices

Our construction needs a function [mathematical expression not reproducible] which could map identities(in [mathematical expression not reproducible]) to matrices(in [mathematical expression not reproducible]), and the proof of our scheme's security requires the function to satisfy a strong injectivity, i.e., for two distinct identities [id.sub.1], [id.sub.2], det(H([id.sub.1])-H([id.sub.2])) [NOT EQUAL TO] 0.

Definition 7. For a prime q and a positive integer n. We say that a function H :[mathematical expression not reproducible] is an encoding with full rank differences (FRD) if:

1. For all distinct [mathematical expression not reproducible], the matrix [mathematical expression not reproducible] is full rank

2. H is computable in polynomial time.

We use an injective FRD encoding function that is described in [20]. A short instruction is as follows: For the finite field [Z.sub.q], a polynomial g [member of] F[X] of degree less than n, coeffs(g) [member of] [F.sup.n] be defined as n-vector which the element is coefficients of g . Let f be some polynomial of degree n in F[X] that is irreducible. For input u = ([u.sub.0], [u.sub.1],...,[u.sub.n-1]), define the polynomial [mathematical expression not reproducible].

Define H(u) as

[mathematical expression not reproducible] (1)

Theorem 2 ([20]). Let F be a field and f a polynomial in F[X] . If f is irreducible in F(X), then the function H defined in (1) is an encoding with full rank differences.

4. G-trapdoor and Sample Algorithms

In this section, we briefly describe the main results in [2] and [3], which be used in our construction: the definition of a so called G-trapdoor and the sampling algorithms include SampleLeft and SampleRight .

4.1 G-trapdoor Generation

In brief, a G-trapdoor is a key matrix that can transform a public matrix A to a special matrix G. This trapdoor(represented by a matrix R) has special properties, and includes algorithms for sampling SIS preimages and inverting LWE problems, which be admitted very efficient and high quality, and these problems are considered to be hard if for a uniform A . There is an example of G-trapdoor in [2] make [mathematical expression not reproducible]

[mathematical expression not reproducible]

where

[mathematical expression not reproducible]

There are efficient algorithms for inverting [g.sub.G](s,e):= [s.sup.t]G + [e.sup.t]modq and preimage Gaussian sampling for [f.sub.G](x) = Gx mod q.

Definition 8. ([2], Definition5.2). Let [mathematical expression not reproducible] and [mathematical expression not reproducible] be matrices with m[greater than or equal to]w[greater than or equal to]n. A G -trapdoor for A is a matrix R[member of][Z.sup.(m-w)xw] such that [mathematical expression not reproducible] for some invertible matrix [mathematical expression not reproducible]. We refer to H as the tag or label of the trapdoor. The quality of the trapdoor is measured by its largest singular value [s.sub.1](R).

We construct A = [[A.sub.0]| -[A.sub.0]R + G], where [A.sub.0] is a uniform matrix, and R is a transformation in order to make A with this structured matrix. By the Leftover Hash Lemma, let appropriate parameters, (A,A R) is negl(n)-far from uniform. This R can be transformed as follows:

[mathematical expression not reproducible]

In order to construct a CPA-secure encryption scheme, there is an invertible matrix H can be used like this

[mathematical expression not reproducible]

In this situation, to complete the transformation and answer adversary's queries must know both R and H. Once the matrix H is zero matrix, then the challenger cannot answer adversary's queries, because of [mathematical expression not reproducible], and solving LWE or SIS problems cannot be reduced to solve the same problem about G. Therefore, in this case, the challenger can make a challenge ciphertext.

LWE Inversion. We give an effective algorithm which denoted by [Invert.sup.o] (R,A,b) for inverting the function [g.sub.A](s,e) = [s.sup.t]A + [e.sup.t] for any [mathematical expression not reproducible] and suitably small vector e [member of] [Z.sup.m], [mathematical expression not reproducible] is a parity-check matrix, G -trapdoor R for A with invertible tag H . There is an oracle O for inverting the function [g.sub.G](s,e) where e [member of] [Z.sup.w] is small. Then we compute [mathematical expression not reproducible], get (s,e) [left arrow] O(b), return s = [H.sup.-t]s, e = b - [A.sup.t]s and output vectors (s,e).

Gaussian Sampling. We show how to sample a discrete Gaussian over [mathematical expression not reproducible], and this efficient algorithm is denoted as Sampl[e.sup.O] (R,A,H,u,s). There is an oracle O for sampling over a desired coset [mathematical expression not reproducible] with fixed parameter r[square root of ([[SIGMA].sub.G ][greater than or equal to] [[eta].sub.e]([[LAMBDA].sub.[perpendicular to]](G)))], for some [[SIGMA].sub.G ][greater than or equal to] 2 and [??][less than or equal to][1/2]. We define matrix A = [A | HG - AR] with invertible tag [mathematical expression not reproducible], a parity-check matrix [mathematical expression not reproducible], G -trapdoor matrix [mathematical expression not reproducible], positive definite [mathematical expression not reproducible] and syndrome [mathematical expression not reproducible]. In order to obtain a vector x drawn from a distribution within O([??]) statistical distance of [mathematical expression not reproducible], first choose a fresh perturbation [mathematical expression not reproducible], let [mathematical expression not reproducible] for [p.sub.1 ][member of] [Z.sup.m], [p.sub.2 ][member of] [Z.sup.w], compute w = A([p.sub.1]-R[p.sub.2]) and w = G[p.sub.2], let v[left arrow][H.sup.-1](u-w)-w = [H.sup.-1](u-AP), choose [mathematical expression not reproducible] by calling O(v), and return [mathematical expression not reproducible].

4.2 SampleLeft and SampleRight

In short, lattices in this system are built with two parts called "Left" and "Right" lattices. In the real system, a trapdoor for left lattices is used as master secret to generate every user's private key. While in the simulation system, a trapdoor for right lattice is used to generate private keys for all identities except for one, which is selected by the adversary[3].

Let [mathematical expression not reproducible] and R [member of] [{-1,1}.sup.mxm]. Our framework is constructed by form F = (A | AR+B), and we use different methods(Precisely, it is from a different direction) to sample short vectors from [mathematical expression not reproducible] for some [mathematical expression not reproducible]. These two specific algorithms are in the following :

* Algorithm SampleLeft

SampleLeft takes a basis for [mathematical expression not reproducible] (i.e., the left side of F) and outputs a short vector [mathematical expression not reproducible]. Specifically, in algorithm SampleLeft(A,[M.sub.1], [T.sub.A],u, [sigma]), [mathematical expression not reproducible] is a rank n matrix, a matrix [mathematical expression not reproducible], a short basis [T.sub.A] of [mathematical expression not reproducible] and a vector [mathematical expression not reproducible] as input, gaussian parameter [mathematical expression not reproducible]. Then it samples a random vector [mathematical expression not reproducible] distributed statistically close to [mathematical expression not reproducible], and runs [e.sub.1][left arrow]SamplePre(A,[T.sub.A],y,[sigma]) where [mathematical expression not reproducible], outputs e [left arrow]([e.sub.1], [e.sub.2]).

* Algorithm SampleRight

SampleRight takes a basis for [mathematical expression not reproducible] (i.e., the right side of F) and outputs a short vector [mathematical expression not reproducible]. Specifically, Algorithm SampleRight(A,B,R,[T.sub.B],u,[sigma]) where [mathematical expression not reproducible], [mathematical expression not reproducible] where B is rank n, and a matrix R [MEMBER OF] [Z.sup.k,m], where [s.sub.R]:= ||R||, with a basis [T.sub.B] of [mathematical expression not reproducible] and a vector [mathematical expression not reproducible] as input. Then it constructs a set [mathematical expression not reproducible] of (m + k) linearly independent vectors in [mathematical expression not reproducible], uses Lemma 3 to convert [mathematical expression not reproducible] into a basis [mathematical expression not reproducible], of [mathematical expression not reproducible] with same Gram-Schmidt norm, invokes SamplePre([mathematical expression not reproducible]) to generate a vector [mathematical expression not reproducible] as output.

5. The Basic Construction

In our construction, we need to publish identity identifier for each user, that is [[A.sub.0] | -[A.sub.0] [R.sub.i]], in which the function of [R.sub.i] is used to implement re-encryption, for i = 1,...,n, n is the number of users.

Setup([lambda]): On input a security parameter [lambda], set the parameters q,n,m,[sigma], [alpha] as specified before. then do as follows:

* Use algorithm TrapGen(q,n) to select a uniformly random nxm-matrix [mathematical expression not reproducible] with a basis [mathematical expression not reproducible] such that [mathematical expression not reproducible].

* Select [mathematical expression not reproducible] with special structure, and select a uniformly random nxm-matrix [mathematical expression not reproducible].

* Select [R.sub.1], [R.sub.2],...,[R.sub.n] [member of] D in which n is the number of users([R.sub.i] is sampled from the Gaussian [mathematical expression not reproducible], and [id.sub.i] will be assigned by [R.sub.i] for i = 1,...,n.

* Select a uniformly random n-vector [mathematical expression not reproducible].

* An encoding function [mathematical expression not reproducible].

[mathematical expression not reproducible]

Extract(PP,MK,[id.sub.i]) : On input public parameters PP, master key MK, and an identity [mathematical expression not reproducible], do:

* Sample [e.sub.i] [left arrow] SampleLeft([mathematical expression not reproducible])

* Assigned to [id.sub.i] [R.sub.i].

* Output [mathematical expression not reproducible]

Let [mathematical expression not reproducible], then [mathematical expression not reproducible], and [e.sub.t] is distributed as [mathematical expression not reproducible].

Encrypt(PP,[id.sub.i],b): On input public parameters PP, an identity [id.sub.i], and a message b [member of] {0,1}, do:

* Set [mathematical expression not reproducible].

* Choose a uniformly random [mathematical expression not reproducible]

* Choose a uniformly random mxm matrix [mathematical expression not reproducible].

* Choose noise vector [mathematical expression not reproducible] and [mathematical expression not reproducible], and set [mathematical expression not reproducible].

* Set [mathematical expression not reproducible] and [mathematical expression not reproducible].

* Output the ciphertext [mathematical expression not reproducible]. ReKeyGen(PP,[id.sub.i], [id.sub.j],S[K.sub.id]): On input [mathematical expression not reproducible] and [mathematical expression not reproducible] ([A.sub.0]|-[A.sub.0][R.sub.j]+H([id.sub.j]) TG). do:

* Use the second part of a secret key - the Gaussian matrix [R.sub.i] and the invertible [mathematical expression not reproducible], execute Sampl[e.sup.O] to sample from the cosets of the [-[A.sub.0][R.sub.j]+H([id.sub.j]) TG]. Specifically, we sample column-wise so that for each column of the [-[A.sub.0][R.sub.j] +H([id.sub.j])TG], we obtain a 2m- dimensional column of the re-encryption key. After sampling m times we can receive an 2m x m matrix and parse it as two matrices [mathematical expression not reproducible] and [X.sub.4] [mathematical expression not reproducible]

[mathematical expression not reproducible]

* To set up the equation, continue sampling for the cosets obtained from the columns of the matrix [[A.sub.0]]

[mathematical expression not reproducible]

* The re-encryption key is a matrix with Gaussian entries:

[mathematical expression not reproducible]

ReEnc([mathematical expression not reproducible]): Compute the component [c.sub.1] in the ciphertext as follows :

* Compute

[mathematical expression not reproducible]

* Output ciphertext for [id.sub.2]:

[mathematical expression not reproducible]

Decrypt([mathematical expression not reproducible]) : On input public parameters PP, a private key S[K.sub.id]:=[e.sub.id], and a ciphertext CT = ([c.sub.0], [c.sub.1]'), do:

* Compute w = [c.sub.0]-[c.sub.1]'[e.sub.id [member of]] [Z.sub.q].

* Compare w and [mathematical expression not reproducible] treating them as integers in Z . If they are close, i.e., if [mathematical expression not reproducible], output 1, otherwise output 0.

Intuition on non-interactivity The generation process of re-encryption key [mathematical expression not reproducible] depends upon public key of user [mathematical expression not reproducible] without resorting to [id.sub.j] secret [mathematical expression not reproducible], which means the process does not require the participation of [id.sub.j], which is non-interactivity. Error term in re-encryption ciphertext stems from raw ciphertext which is random and unrelated to Bob, which is the recipient anonymous property.

Unidirectionality Essentially, this property is mainly to ensure that user [id.sub.i] and the proxy cannot decrypt user [id.sub.j]'s ciphertexts through collusion. Intuitively, [id.sub.j] is not involved in the whole process of re-encryption, so privacy information's disclosure is unlikely to occur. Actually, neither [mathematical expression not reproducible] is impossible to reverse, nor get [mathematical expression not reproducible] through the calculation method expect making use of [d.sub.j]'s secret information. Therefore, the information would not contribute to the directionality.

5.1 Parameters and Correctness

When the cryptosystem is operated as specified, we have during decryption(here we focus on the re-encryption ciphertext):

[mathematical expression not reproducible]

Lemma 4. The norm of error term is bounded by [mathematical expression not reproducible] w.h.p.

Proof. Letting [mathematical expression not reproducible] with [e.sub.1], [e.sub.2][member of][Z.sup.m], the error term is

x-[[y.sup.T]|[z'.sup.T]][e.sub.id]=x-([y.sup.T][e.sub.1]+[z'.sup.T][e.sub.2]) = x- [([y.sup.T][X.sub.1] + [z.sup.T][X.sub.2]) [e.sub.1] + ([y.sup.T][X.sub.3] + [z.sup.T][X.sub.4]) [e.sub.2]] = x-[y.sup.T][([X.sub.1] +R[X.sub.2]) [e.sub.1] +([X.sub.3] +R[X.sub.4])[e.sub.2]]

By Lemma 8 we have ||[e.sub.id]|| [less than or equal to] [sigma] [square root of (2m)] w.h.p.

By Lemma 15 we have [mathematical expression not reproducible]. Then, by Lemma 12 the error term is bounded by

[mathematical expression not reproducible]

which proves the lemma.

In order to make the system work correctly, we need to ensure that:

* the error term is less than, [q/5],

* TrapGen can operate, i.e., m >6nlogq,

* [sigma] is sufficiently large for SampleLeft and SampleLeft, i.e.,[sigma]>m[omega]([square root of (logm)])

* Regev's reduction can apply, i.e., q > 2[square root of (n / [alpha])]

To satisfy these requirements we set the parameters (q,m,[sigma], [alpha]) as follows, taking n to be the security parameter:

m = [6n.sup.1+[delta]], q = [m.sup.4] [greater than or equal to] [omega] (log[n.sup.2]), [sigma] = m [greater than or equal to] [omega][([square root of (logn)]), [alpha] = [[m.sup.3][square root of (n[omega] (log[n.sup.2]))]].sup.-1] and round up m to the nearest larger integer and q to the nearest larger prime. Here we assume that [delta] meets [n.sup.[delta]] > [logn] = O(logn).

Since the matrices [A.sub.0], [R.sub.i] (i = 1,...,n) are random in [Z.sup.n.sup.x.sup.m] and m>nlogq, both matrices will have rank n with overwhelming probability. Hence, calling SampleLeft in algorithm Extract succeeds w.h.p.

6. Security Reduction

Under a selective identity attack, our construction is indistinguishable from random one, which means the challenge ciphertext is indistinguishable from a random element in the ciphertext space. This property implies both semantic security and recipient anonymity.

Theorem 3. Under the parameters (m,q,[sigma], [alpha],n), The PRE scheme is IND-sID-CPA secure provided that the ([Z.sub.q],n,[[PSI].sub.[alpha]])-LWE assumption holds.

Proof. Our proof process is a group of games where the first game is identical to the IND-sID-CPA secure game from Definition 2. In the last game, the adversary's advantage is zero. We can prove that the order of the two games are indistinguishable for the adversary, so the adversary's advantage in the final game is zero, the advantage of the original IND-sID-CPA game is also zero.

Game 0 This is the original IND-sID-CPA game from Definition 2 between the adversary A against our scheme and an IND-sID-CPA challenger.

Game 1 In Game 1, we slightly change the way the challenger generates -[A.sub.0][R.sub.i] in the public parameters. Let id* be the identity that A wants to attack. The challenger in Game 1 chooses -H(id*)TG at the setup phase and makes -[A.sub.0][R.sub.i] as

-[A.sub.0][R.sub.i] [left arrow]-[A.sub.0][R.sub.i] -H(id*)TG

The remainder of the game is unchanged. We show that Game 0, Game 1 is statistically indistinguishable. Because from the adversary's views, the -[A.sub.0][R.sub.i] is statistically close to uniform, and the result of alternative -[A.sub.0][R.sub.i] -H(id*)TG by minus a portion -H(id*)TG is also close to uniform. Hence, Game 0 and Game 1 are indistinguishable for the attacker.

Game 2 In Game 2, we change the generation mode of [A.sub.0]. The challenger generates [A.sub.0] as a random matrix in [mathematical expression not reproducible], selects a new [mathematical expression not reproducible] with a special structure and a trapdoor [T.sub.G] for [mathematical expression not reproducible] for the challenger. The construction of -[A.sub.0][R.sub.i] remains as it is in Game 1, namely -[A.sub.0][R.sub.i] [left arrow] - [A.sub.0][R.sub.i] -H(id*)TG.

The challenger responds to private key queries using the trapdoor [T.sub.G]. To respond to a private key query for id [not equal to] id*, the challenger needs a short vector [mathematical expression not reproducible] where

[F.sub.id]=([A.sub.0]| -[A.sub.0][R.sub.i] -H(id*)TG + H(id)TG) = ([A.sub.0]|-[A.sub.0][R.sub.i] +(H(id)-H(id*))TG)

By construction, therefore H (id)-H (id*) is non-singular and [T.sub.G] is a trapdoor for [mathematical expression not reproducible]. The challenger can respond to the private key query like this:

e [left arrow] SampleRight([A.sub.0],(H(id)-H(id*))TG,-[R.sub.i], [T.sub.G],u,[sigma])

and sending S[K.sub.id]=e to A . When [sigma] >|| [T.sub.G] || [s.sub.R][omega]([square root of (logm)]), the generated e is distributed closed to [mathematical expression not reproducible], as in Game 1. Therefore [sigma] used in this system, as defined before, is sufficiently large to satisfy the conditions of algorithm SampleRight.

The challenger responds to re-encryption key queries like this:

First, the challenger obtains trapdoor of [[LAMBDA].sup.[perpendicular to]]([A.sub.0] | -[A.sub.0][R.sub.i] +(H(id)-H(id*))TG) by running

e' [left arrow] SampleRight([A.sub.0],(H(id)-H(id*))TG,-[R.sub.i], [T.sub.G],0,[sigma])

Then, using the trapdoor inversion algorithm SamplePre([[A.sub.0] | - [A.sub.0][R.sub.i] +(H(id)-H(id*))TG [13] which u is each column of the A. We sample column-wise for the sake of each column of the [A.sub.0] and obtain a 2m -dimensional column of the re-encryption key. After sampling m times, we chalk up a 2mxm matrix and divide it into two matrices [X.sub.11] and [X.sub.21] with Gaussian entries of parameter s.

[mathematical expression not reproducible]

continue sampling for the cosets of the -[A.sub.0][R.sub.i] +(H(id)-H(id*))TG,

[mathematical expression not reproducible]

the simulated re-encryption key

[mathematical expression not reproducible]

has the same distribution as a re-encryption key in the original scheme.

To answer the re-encryption query from [id.sub.i] to [id.sub.j], that is, we apply [mathematical expression not reproducible] generated before to re-encrypt ciphertext from [mathematical expression not reproducible] to [mathematical expression not reproducible]. The re-encryption transforms

[mathematical expression not reproducible]

to

[mathematical expression not reproducible]

, where [F.sub.id] =([A.sub.0]|-[A.sub.0][R.sub.i]+(H([id.sub.i])-H(id*))TG) and [mathematical expression not reproducible], decryption using key [e.sub.id] for identity id.

Game 3 In Game 3, we change the way the challenger generates challenge ciphertext CT = ([c.sub.0], [c.sub.1]), make it CT = ([c.sub.0]*,[c.sub.1]*) where ([c.sub.0]*,[c.sub.1]*) is always chosen as a random independent element in [mathematical expression not reproducible]. Since the challenge ciphertext is a fresh random in the ciphertext space, the advantage of A in Game 3 is zero.

Next, we will give a reduction from LWE problem to prove that Game 2 and Game 3 are computationally indistinguishable for a PPT adversary.

Reduction from LWE Presume A has non-negligible advantage in distinguishing Game 2 and Game 3. We use A to construct an LWE algorithm B.

An LWE problem instance is provided with a sampling oracle O which can be either truly random [O.sub.s] or a noisy pseudo-random [O.sub.s] for some secret [mathematical expression not reproducible]. The simulator B uses the adversary A to distinguish between two oracles as follows:

Instance B requests for O and receives a fresh pair [mathematical expression not reproducible] for each i = 0,...,m.

Targeting A announces to B the target identity id* that it intends to attack.

Setup B may construct the system's public parameters PP as follows:

* Assemble the random matrix [mathematical expression not reproducible] from m of the previously given LWE sample by letting the i-th column of [A.sub.0] be the n-vector [u.sub.i] for all i = 0,...,m.

* Assign the 0-th LWE sample (so far unused) to become the public random n-vector [mathematical expression not reproducible].

* Construct the remainder of the public parameters using id* and [R.sub.i]*, namely [A.sub.0][R.sub.i] and TG as in Game 2.

* Send PP = ([A.sub.0], [u.sub.0],H, TG,[A.sub.0][R.sub.i],i = 1,...,n) to A.

Queries B answers all kinds of queries from A as in Game 2.

Challenge B prepares, when prompted by A with a message bit b* [member of] {0,1}, a challenger ciphertext for the target identity id* as follows:

* Let [v.sub.0],.. .,[v.sub.m] be entries from the LWE instance and set [mathematical expression not reproducible].

* Blind the message bit by letting [c.sub.0]* = [v.sub.0] + b*[q/2].

* Set [mathematical expression not reproducible].

* Send CT* = ([c.sub.0]*,[c.sub.1]*) to the adversary.

We argue that when the LWE oracle is pseudorandom, that is, O = [O.sub.s], then CT* is distributed exactly as in Game 2. That is, first, observing that [F.sub.id]* = ([A.sub.0]| - [A.sub.0][R.sup.*.sub.i]). Second, by the definition of [O.sub.s], we know that [mathematical expression not reproducible] for some random noise vector [mathematical expression not reproducible] distributed as [[PSI].sub.[alpha]]. Therefore, [c.sub.1]* defined above satisfies

[mathematical expression not reproducible]

and the quantity on the right is precisely equal to the [c.sub.1] part of a valid challenge ciphertext in Game 2 except the second part add a minus sign. And also note that [mathematical expression not reproducible] for some x distributed as [[PSI].sub.[alpha]], and therefore [c*.sub.0] in step 2 satisfies [mathematical expression not reproducible], just as the [c.sub.0] part of a challenge ciphertext in Game 2.

When O = [O.sub.s], we have that [v.sub.0] is uniform in [Z.sub.q] and v* is uniform in [mathematical expression not reproducible]. Therefore [c.sub.1]* as defined above is uniform and independent in [mathematical expression not reproducible] by the standard leftover hash lemma where the hash function is defined by the matrix ([mathematical expression not reproducible]) and ensures that -[A.sub.0] [R.sub.i]* and [(R*).sup.T]v* are uniform independent quantities. Consequently, the challenge ciphertext is always uniform in [mathematical expression not reproducible], as in Game 3.

Guess After being allowed to make additional queries, A guess if it is interacting with a Game 2 or Game 3 challenger. Our simulator outputs A's guess as the answer to the LWE challenge, which it is trying to solve.

We already argued that when O = [O.sub.s] the adversary's view is the same as in Game 2. When O = [O.sub.$], the adversary's view is the same as in Game 3. Hence, B's advantage in solving LWE is the same as A's advantage in distinguishing Game 2 and Game 3, as required. This completes the description of algorithm B and completes the proof.

7. Conclusion

In this paper, we present an identity based proxy re-encryption scheme which is CPA secure in standard model. The scheme satisfies the properties of the non-interactivity, unidirectionality, anonymous and etc. The security of our scheme is based on the LWE assumption in the lattice. However, we have proved our scheme to be semantically secure in selective-ID, construction of adaptive-ID secure identity based proxy re-encryption scheme that is CCA secure in standard model is an open problem.

References

[1] Agrawal, S. and X. Boyen, "Identity-based encryption from lattices in the standard model," Manuscript, July,2009.

[2] Micciancio, D. and C. Peikert, "Trapdoors for lattices: Simpler, tighter, faster, smaller," EUROCRYPT 2012, pp. 700, 2012. Article (CrossRef Link)

[3] Agrawal, Shweta and Boneh, Dan and Boyen, Xavier, "Efficient lattice (H) IBE in the standard model," EUROCRYPT 2010, pp. 553-572, 2010. Article (CrossRef Link)

[4] Blaze Matt, Bleumer Gerrit and Strauss, Martin, "Divertible protocols and atomic proxy cryptography," EUROCRYPT 1998, pp.127-144, 1998. Article (CrossRef Link)

[5] Shamir, Adi, "How to share a secret," Communications of the ACM, vol. 22, no. 11, pp. 612-613, 1979. Article (CrossRef Link)

[6] Singh Kunwar, Pandu Rangan C and Banerjee AK, "Lattice based identity based proxy re-encryption scheme," Journal of Internet Services and Information Security (JISIS), vol. 3, no. 3/4, pp. 38-51, 2013.

[7] Kirshanova Elena, "Proxy Re-encryption from Lattices," in Proc. of International Workshop on Public Key Cryptography, pp. 77-94, 2014. Article (CrossRef Link)

[8] Chu, Cheng-Kang and Tzeng, Wen-Guey, "Identity-based proxy re-encryption without random oracles," in Proc. of International Conference on Information Security, pp. 189-202, 2007. Article (CrossRef Link)

[9] Aono Yoshinori, Boyen Xavier, Wang Lihua and others, "Key-Private Proxy Re-encryption under LWE," in Proc. of International Conference on Cryptology in India, pp. 1-18, 2013. Article (CrossRef Link)

[10] Green Matthew and Ateniese Giuseppe, "Identity-based proxy re-encryption," Applied Cryptography and Network Security, pp. 288-306, 2007. Article (CrossRef Link)

[11] Zhang Jiang, Zhang Zhenfeng and Chen Yu, "PRE: Stronger security notions and efficient construction with non-interactive opening," Theoretical Computer Science, vol. 542, pp. 1-16, 2014. Article (CrossRef Link)

[12] Canetti Ran and Hohenberger Susan, "Chosen-ciphertext secure proxy re-encryption," in Proc. of the 14th ACM conference on Computer and communications security, pp. 185-194, 2007. Article (CrossRef Link)

[13] Gentry Craig, Peikert Chris and Vaikuntanathan Vinod, "Trapdoors for hard lattices and new cryptographic constructions," in Proc. of the 40th annual ACM symposium on Theory of computing, pp. 197-206, 2008. Article (CrossRef Link)

[14] Cash David, Hofheinz Dennis and Kiltz Eike, "How to Delegate a Lattice Basis," IACR Cryptology ePrint Archive 2009, vol. 2009, pp. 351, 2009.

[15] Micciancio Daniele and Regev Oded, "Lattice-based cryptography," Post-quantum cryptography, pp. 147-191, 2009. Article (CrossRef Link)

[16] Xagawa, D. K, "Cryptography with lattices," 2010.

[17] Micciancio Daniele and Goldwasser Shafi, "Complexity of Lattice Problems: A Cryptographic Perspective," Siam Journal on Computing, vol. 671, 2002. Article (CrossRef Link)

[18] Ajtai, M, "Generating hard instances of lattice problems," in Proc. of the twenty-eighth annual ACM symposium on Theory of computing, pp. 99-108, 1996. Article (CrossRef Link)

[19] Regev Oded, "On lattices, learning with errors, random linear codes, and cryptography," Journal of the ACM (JACM), vol. 56, no. 6, pp. 34, 2009. Article (CrossRef Link)

[20] Cramer R. and I. Damgard, "On the amortized complexity of zero-knowledge protocols," Advances in Cryptology-CRYPTO 2009, pp. 177-191, 2009. Article (CrossRef Link)

[21] Micciancio Daniele and Regev Oded, "Worst-case to Average-case Reductions based on Gaussian Measures," SIAM Journal on Computing, vol. 37, no. 1, pp. 267-302, 2007. Article (CrossRef Link)

Wei Yin (1), Qiaoyan Wen (1), Wenmin Li (1), Hua Zhang (1,2), and Zheng Ping Jin (1)

(1,2) State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications Beijing, 100876 - China

[e-mail:zhanghua_288@bupt.edu.cn]

(*) Corresponding author: Hua Zhang

Received September 28, 2016; revised January 10, 2017; accepted September 3, 2017; Published December 31, 2017

https://doi.org/10.3837/tiis.2017.12.023

Wei Yin, received the B.S. degree in Mathematics and Applied Mathematics from Huaibei Normal University, Huaibei, Anhui, China, in 2012. His research interests include public key cryptography, lattice cryptography, and provable security. He is currently a PhD candidate in Beijing University of Posts and Telecommunications.

Qiaoyan Wen, received the B.S. and M.S. degrees in Mathematics from Shaanxi Normal University, Xi'an, Shaanxi, China, in 1981 and 1984, respectively, and the PhD degree in cryptography from Xidian University, Xi'an, Shaanxi, China, in 1997. Her present research interests include coding theory, cryptography, information security, Internet security, and applied mathematics. She is a professor in Beijing University of Posts and Telecommunications.

Wenmin Li, received the B.S. and M.S. degrees in Mathematics and Applied Mathematics from Shaanxi Normal University, Xi'an, Shaanxi, China, in 2004 and 2007, respectively, and the Ph.D. degree in Cryptology from Beijing University of Posts and Telecommunications, Beijing, China, in 2012. She is currently a post-doctoral in Beijing University of Posts and Telecommunications, Beijing, China. Her research interests include cryptography and information security.

Hua Zhang, received the B.S. degree in telecommunications engineering from the Xidian University in 1998, the M.S. degree in cryptology from Xidian University in 2005, and the PhD degree in cryptology from Beijing University of Posts and Telecommunications in 2008. Now she is an associate professor in Beijing University of Posts and Telecommunications. Her research interests include cryptography, information security and network security.

Zhengping Jin received the BS degree in Math and Applied Math, MS degree in Applied Math from Anhui Normal University in 2004 and in 2007 respectively, and the Ph.D degree in Cryptography from Beijing University of Posts and Telecommunications in 2010. Now he is a lecturer of Beijing University of Posts and Telecommunications. His research interests include cryptography, information security, internet security and applied mathematics.

Table 1. Comparison with the previous schemes Authors Security Unidirectional Standard Model Assumption Singh2013 CPA X X LWE Chu2007 CPA&CCA [check] [check] BDH MG2007 CPA&CCA [check] X DBDH PKC2014 CCA [check] [check] LWE Ours CPA [check] [check] LWE Authors Identity Based Singh2013 [check] Chu2007 [check] MG2007 [check] PKC2014 X Ours [check]

Printer friendly Cite/link Email Feedback | |

Title Annotation: | learning with error |
---|---|

Author: | Yin, Wei; Wen, Qiaoyan; Li, Wenmin; Zhang, Hua; Jin, Zheng Ping |

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Dec 1, 2017 |

Words: | 8330 |

Previous Article: | A SECURITY ARCHITECTURE FOR THE INTERNET OF THINGS. |

Next Article: | Periocular Recognition Using uMLBP and Attribute Features. |

Topics: |