# Improved Construction for Inner Product Functional Encryption

Authors: Qingsong Zhao; Qingkai Zeng; Ximeng Liu
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Functional encryption (FE) is a vast new paradigm for encryption scheme which allows tremendous flexibility in accessing encrypted data. In a FE scheme, a user can learn specific function of encrypted messages by restricted functional key and reveals nothing else about the messages. Besides the standard notion of data privacy in FE, it should protect the privacy of the function itself which is also crucial for practical applications. In this paper, we construct a secret key FE scheme for the inner product functionality using asymmetric bilinear pairing groups of prime order. Compared with the existing similar schemes, our construction reduces both necessary storage and computational complexity by a factor of 2 or more. It achieves simulation-based security, security strength which is higher than that of indistinguishability-based security, against adversaries who get hold of an unbounded number of ciphertext queries and adaptive secret key queries under the External Decisional Linear (XDLIN) assumption in the standard model. In addition, we implement the secret key inner product scheme and compare the performance with the similar schemes.


---

## Body

## 1. Introduction

Traditional public-key encryption provides all-or-nothing access to data: you can either recover the entire plaintext or reveal nothing from the ciphertext. Functional encryption (FE) [1–3] is a vast new paradigm for encryption scheme which allows tremendous flexibility in accessing encrypted data. In a FE scheme, a secret key skf embedded with a function f can be created from a master secret key msk. Then, given a ciphertext for x, a user learns f(x) and reveals nothing else about x. In recent years, the cryptographic community has made great progress in research on the security of FE and constructions for such schemes (see, for instance, [4–11] and any more).There are two notions of security for a FE scheme, i.e., indistinguishability-based security and simulation-based security. The former one requires that an adversary cannot distinguish between ciphertexts of any two messagesx0, x1 with access to a secret key skf for a function f such that f(x0)=f(x1). In contrast, the latter one requires that the view of the adversary can be simulated by a simulator, given only access to the secret keys and the function evaluated on the corresponding messages. Note that simulation-based security has higher security strength than indistinguishability-based security such that there exists an indistinguishability-based secure FE scheme for a certain functionality which is not able to be proved secure under simulation-based security [1, 3].The traditional FE only considers data privacy and omits to protect the privacy of the function itself which is also crucial for practical applications. Consider the case where Bob wants to store his files in a cloud. Before uploading his files to the cloud, he employs a FE scheme to encrypt them avoiding leakage of data privacy and then he uploads the encryption form to the cloud. Later on, Bob wants to query his data by offering the cloud a keyskf for a function f of his choice. However, if the FE scheme cannot support the privacy for the function, the key skf may reveal Bob’s query f entirely to the cloud, which is not desirable when the function includes confidential information.Due to the importance, some works focus on function privacy of FE, and this was first studied in [12] in the secret key setting. This is later followed by the work of [5, 13] in the secret key setting and that of [14, 15] in the public-key setting. During the two scenarios of the public-key setting and the secret key setting, the degree to which function privacy can be satisfied differs dramatically. Specifically, a public-key FE scheme is inherent in leaking confidential information about the function. Note that an attacker who holds a secret key skf can always generate, on its own, the ciphertext for xi for message xi of her choice and then use skf to learn f(xi). This can reveal nontrivial information about the function f. On the other hand, since an attacker holding a secret key skf cannot encrypt new messages in the secret key setting, such kind of attack is no longer applied.


### 1.1. Functional Encryption for Inner Product

Although FE supports the computation of general circuits relying on a wide spectrum of assumptions, there are two major problems with the state-of-the-art general FE constructions. First, the security of some constructions is only ensured so long as the adversary gets hold of a priori bounded number of secret keys [9, 10, 20]. Second, some solutions rely on tools such as multilinear maps [21] and indistinguishability obfuscation [8, 22] which are both impractical and founded on new security assumption undergone minimal scrutiny. This inspires us to explore constructions for firsthand and effective FE schemes for functionalities which focus on the inner product functionality as a first attempt [16–19, 23–26].In an inner product encryption (IPE) scheme, a ciphertextctx→ is related to a vector x→∈Zqn of length n and a secret key sky→ to a vector y→∈Zqn of length n. Given the ciphertext and the secret key, the decryption algorithm computes the inner product 〈x→,y→〉=∑i=1nxiyi. Notice that the formulation of IPE is distinct from that of inner product predicate encryption in [12, 13, 27–30]. The ciphertext for a message m in an inner product predicate encryption scheme comes along with an attribute x→∈Zqn, and a secret key corresponds to a vector y→∈Zqn. When the ciphertext with x→ is decrypted with the secret key for y→, the decryption algorithm outputs m iff 〈x→,y→〉=0. By contrast, the output in the IPE formulation is the actual value of the inner product. In this paper, we consider functional privacy in inner product encryption, i.e., secret key inner product encryption.


### 1.2. Related Work

Abdalla et al. [23] presented a direct construction of public-key IPE under an indistinguishability-based definition. The construction is only proved to be secure against selective adversaries which are asked to commit to their challenges at the beginning of the security game. Following work [24] presented adaptively secure schemes where the messages x0 and x1 may be adaptively chosen at any point in time, based on the previously collected information. Bishop et al. [16] proposed a function-hiding IPE scheme under the Symmetric External Diffie-Hellman (SXDH) assumption, which satisfies an indistinguishability-based definition, and considered adaptive adversaries. However, the scheme is available in a rather weak security model which places limit on adversaries' queries. Specially, all ciphertext queries x→0,x→1 and all secret key queries y→0,y→1 are constrained by 〈x→0,y→0〉=〈x→0,y→1〉=〈x→1,y→0〉=〈x→1,y→1〉. The constraint obviously weakens the security of the scheme, and this is in violation of the intuitive spirit of function privacy. Recently, Datta et al. [17] developed a function-hiding IPE scheme under the SXDH assumption where the restriction on adversaries' queries is only 〈x→0,y→0〉=〈x→1,y→1〉. Tomida et al. [18] constructed a more efficient function-hiding IPE scheme than that of [17] under the External Decisional Linear (XDLIN) assumption. Kim et al. [25] put forth a fully-secure function-hiding IPE scheme with less parameter sizes and run time complexity than in [16, 17]. The scheme is proved simulation-based secure in the generic model of bilinear maps. For the first time Zhao et al. [19] presented a simulation-based secure secret key IPE scheme under the SXDH assumption in the standard model. The scheme can tolerate an unbounded number of ciphertext queries and adaptive key queries.


### 1.3. Our Contribution

We construct an efficient simulation-based secure secret key IPE (SSSK-IPE) scheme in the standard model. We compare our scheme with related works in Table1 where group exponentiations on cyclic groups are involved in key generation algorithm and encryption algorithm, and pairing operations on bilinear pairing groups are involved in decryption algorithm. We achieve an outstanding reduction by a factor of 2 or more in computational complexity. Our scheme achieves n+6 group elements in secret key and ciphtertext, which also reduces storage complexity by a factor of 2 or more. Hence, performance in the SSSK-IPE scheme is superior to that in the previous schemes in both storage complexity and computation complexity. Furthermore, our scheme is based on the XDLIN assumption which is weaker than the SXDH assumption. In more detail, the SXDH assumption relies on type 3 bilinear pairing groups, while the XDLIN assumption relies on any type of bilinear pairing groups [18]. Therefore from this angle, the SXDH assumption is stronger than the XDLIN assumption. Although the construction of [18] was proved to be indistinguishability-based secure under the XDLIN assumption and also succeeded in improving efficiency, both storage complexity and computation complexity of our scheme are better than that of [18] and our scheme achieves simulation-base security, security strength of which is higher than that of indistinguishability-based security. In addition, we implement our SSSK-IPE scheme and compare the performance with the similar schemes in Section 5.Table 1
Comparison of our SSSK-IPE scheme.n is the dimension of vector. We have eight security notions xx-yy-zzz, where xx∈one, many refers to a single or multiple challenge ciphertexts; yy∈SEL, AD refers to selectively or adaptively chosen ciphertext queries; zzz∈IND, SIM refers to indistinguishability-based vs simulation-based security.
Scheme Master secret key Ciphertext Secret key Scalar multiplications Pairing operations Assum. Security BJK15[16] 8 n 2 + 8 2 n + 2 2 n + 2 2 n + 2 SXDH many-AD-IND DDM16[17] 8 n 2 + 12 n + 28 4 n + 8 4 n + 8 4 n + 8 SXDH many-AD-IND TAO16 [18] 4 n 2 + 18 n + 20 2 n + 5 2 n + 5 2 n + 5 XDLIN many-AD-IND ZZL17 [19] 6 n 2 + 10 n + 24 2 n + 4 2 n + 4 2 n + 4 SXDH many-AD-SIM This work 2 n 2 + 18 n + 36 n + 6 n + 6 n + 6 XDLIN many-AD-SIMTo guarantee correctness, our scheme requires that inner products be within a range of polynomial-size, which is consistent with other schemes in Table1. As pointed out in [16], this is reasonable for statistical computations because the computations, like the average over a polynomial-size database, will naturally be contained within a polynomial range. Furthermore, our scheme is simulation-based secure against adversaries who hold in an unbounded number of ciphertext queries and adaptive key queries. Although very basic functionalities such as IBE are simulation-based secure for a priori bounded number of ciphertext queries in the standard model [1, 3, 4], this is possible for an unbounded number of ciphertext queries if adversaries have an underlying polynomial-size range.


### 1.4. Technical Overview

Our SSSK-IPE scheme uses dual pairing vector spaces (DPVS) to construct, as in [16–19], which is brought forward by Okamoto et al. [31, 32]. DPVS has the features of hidden linear subspaces in prime order bilinear group setting. A DPVS of dimension n+6 is introduced in our construction, where n is the dimension of inner product vectors. Typically, we sample a pair of dual orthonormal bases (B,B∗) and only use the n+4 dimension B and the n+4 dimension B∗ to encode vector x→ and vector y→, respectively. Compared with the previous schemes, our scheme at least saves n dimensions of vector spaces. We preserve the remaining hidden dimensions of B and B∗ for the security reduction. Specially, between two hybrid experiments, a hidden dimension can be used for reducing a difference of one coefficient in a secret key or a cipertext to a XDLIN instance.


## 1.1. Functional Encryption for Inner Product

Although FE supports the computation of general circuits relying on a wide spectrum of assumptions, there are two major problems with the state-of-the-art general FE constructions. First, the security of some constructions is only ensured so long as the adversary gets hold of a priori bounded number of secret keys [9, 10, 20]. Second, some solutions rely on tools such as multilinear maps [21] and indistinguishability obfuscation [8, 22] which are both impractical and founded on new security assumption undergone minimal scrutiny. This inspires us to explore constructions for firsthand and effective FE schemes for functionalities which focus on the inner product functionality as a first attempt [16–19, 23–26].In an inner product encryption (IPE) scheme, a ciphertextctx→ is related to a vector x→∈Zqn of length n and a secret key sky→ to a vector y→∈Zqn of length n. Given the ciphertext and the secret key, the decryption algorithm computes the inner product 〈x→,y→〉=∑i=1nxiyi. Notice that the formulation of IPE is distinct from that of inner product predicate encryption in [12, 13, 27–30]. The ciphertext for a message m in an inner product predicate encryption scheme comes along with an attribute x→∈Zqn, and a secret key corresponds to a vector y→∈Zqn. When the ciphertext with x→ is decrypted with the secret key for y→, the decryption algorithm outputs m iff 〈x→,y→〉=0. By contrast, the output in the IPE formulation is the actual value of the inner product. In this paper, we consider functional privacy in inner product encryption, i.e., secret key inner product encryption.


## 1.2. Related Work

Abdalla et al. [23] presented a direct construction of public-key IPE under an indistinguishability-based definition. The construction is only proved to be secure against selective adversaries which are asked to commit to their challenges at the beginning of the security game. Following work [24] presented adaptively secure schemes where the messages x0 and x1 may be adaptively chosen at any point in time, based on the previously collected information. Bishop et al. [16] proposed a function-hiding IPE scheme under the Symmetric External Diffie-Hellman (SXDH) assumption, which satisfies an indistinguishability-based definition, and considered adaptive adversaries. However, the scheme is available in a rather weak security model which places limit on adversaries' queries. Specially, all ciphertext queries x→0,x→1 and all secret key queries y→0,y→1 are constrained by 〈x→0,y→0〉=〈x→0,y→1〉=〈x→1,y→0〉=〈x→1,y→1〉. The constraint obviously weakens the security of the scheme, and this is in violation of the intuitive spirit of function privacy. Recently, Datta et al. [17] developed a function-hiding IPE scheme under the SXDH assumption where the restriction on adversaries' queries is only 〈x→0,y→0〉=〈x→1,y→1〉. Tomida et al. [18] constructed a more efficient function-hiding IPE scheme than that of [17] under the External Decisional Linear (XDLIN) assumption. Kim et al. [25] put forth a fully-secure function-hiding IPE scheme with less parameter sizes and run time complexity than in [16, 17]. The scheme is proved simulation-based secure in the generic model of bilinear maps. For the first time Zhao et al. [19] presented a simulation-based secure secret key IPE scheme under the SXDH assumption in the standard model. The scheme can tolerate an unbounded number of ciphertext queries and adaptive key queries.


## 1.3. Our Contribution

We construct an efficient simulation-based secure secret key IPE (SSSK-IPE) scheme in the standard model. We compare our scheme with related works in Table1 where group exponentiations on cyclic groups are involved in key generation algorithm and encryption algorithm, and pairing operations on bilinear pairing groups are involved in decryption algorithm. We achieve an outstanding reduction by a factor of 2 or more in computational complexity. Our scheme achieves n+6 group elements in secret key and ciphtertext, which also reduces storage complexity by a factor of 2 or more. Hence, performance in the SSSK-IPE scheme is superior to that in the previous schemes in both storage complexity and computation complexity. Furthermore, our scheme is based on the XDLIN assumption which is weaker than the SXDH assumption. In more detail, the SXDH assumption relies on type 3 bilinear pairing groups, while the XDLIN assumption relies on any type of bilinear pairing groups [18]. Therefore from this angle, the SXDH assumption is stronger than the XDLIN assumption. Although the construction of [18] was proved to be indistinguishability-based secure under the XDLIN assumption and also succeeded in improving efficiency, both storage complexity and computation complexity of our scheme are better than that of [18] and our scheme achieves simulation-base security, security strength of which is higher than that of indistinguishability-based security. In addition, we implement our SSSK-IPE scheme and compare the performance with the similar schemes in Section 5.Table 1
Comparison of our SSSK-IPE scheme.n is the dimension of vector. We have eight security notions xx-yy-zzz, where xx∈one, many refers to a single or multiple challenge ciphertexts; yy∈SEL, AD refers to selectively or adaptively chosen ciphertext queries; zzz∈IND, SIM refers to indistinguishability-based vs simulation-based security.
Scheme Master secret key Ciphertext Secret key Scalar multiplications Pairing operations Assum. Security BJK15[16] 8 n 2 + 8 2 n + 2 2 n + 2 2 n + 2 SXDH many-AD-IND DDM16[17] 8 n 2 + 12 n + 28 4 n + 8 4 n + 8 4 n + 8 SXDH many-AD-IND TAO16 [18] 4 n 2 + 18 n + 20 2 n + 5 2 n + 5 2 n + 5 XDLIN many-AD-IND ZZL17 [19] 6 n 2 + 10 n + 24 2 n + 4 2 n + 4 2 n + 4 SXDH many-AD-SIM This work 2 n 2 + 18 n + 36 n + 6 n + 6 n + 6 XDLIN many-AD-SIMTo guarantee correctness, our scheme requires that inner products be within a range of polynomial-size, which is consistent with other schemes in Table1. As pointed out in [16], this is reasonable for statistical computations because the computations, like the average over a polynomial-size database, will naturally be contained within a polynomial range. Furthermore, our scheme is simulation-based secure against adversaries who hold in an unbounded number of ciphertext queries and adaptive key queries. Although very basic functionalities such as IBE are simulation-based secure for a priori bounded number of ciphertext queries in the standard model [1, 3, 4], this is possible for an unbounded number of ciphertext queries if adversaries have an underlying polynomial-size range.


## 1.4. Technical Overview

Our SSSK-IPE scheme uses dual pairing vector spaces (DPVS) to construct, as in [16–19], which is brought forward by Okamoto et al. [31, 32]. DPVS has the features of hidden linear subspaces in prime order bilinear group setting. A DPVS of dimension n+6 is introduced in our construction, where n is the dimension of inner product vectors. Typically, we sample a pair of dual orthonormal bases (B,B∗) and only use the n+4 dimension B and the n+4 dimension B∗ to encode vector x→ and vector y→, respectively. Compared with the previous schemes, our scheme at least saves n dimensions of vector spaces. We preserve the remaining hidden dimensions of B and B∗ for the security reduction. Specially, between two hybrid experiments, a hidden dimension can be used for reducing a difference of one coefficient in a secret key or a cipertext to a XDLIN instance.


## 2. Preliminaries

Letλ be the security parameter. If S is a set, x←$S denotes the process of choosing uniformly at random from S. Let X={Xn}n∈N and Y={Yn}n∈N be distribution ensembles. We say that X≈cY are computationally indistinguishable between X and Y, if for all nonuniform probabilistic polynomial time D and every n∈N, the difference between Pr[D(Xn)=1] and Pr[D(Yn)=1] is negligible. Let negl(λ) be a negligible function in λ. Moreover, we write x→ to denote a vector (x1,…,xn)∈Zqn of length n for some positive integer q and n. We use 〈a→,b→〉 to denote the inner product, ∑i=1naibi mod q, of vectors a→∈Zqn and b→∈Zqn. We use upper case boldface to denote matrices. XT denotes transpose of the matrix X. GL(n,Zq) denotes the general linear group of degree n over Zq. Zq× denotes a set of integers {1,…,q-1}.


### 2.1. Definition of SSSK-IPE

We introduce the definition of simulation-based secure secret key IPE (SSSK-IPE).Definition 1 (SSSK-IPE).
A SSSK-IPE scheme is composed of the four PPT algorithms defined below:(i)
SSSK-IPE.Setup  (1λ,n)→(msk,pp): The setup algorithm receives as input the security parameters λ and n, being vector length, and outputs a master secret key msk and public parameters pp.(ii)
SSSK-IPE.Encrypt  (msk,pp,x→)→ctx→: The encryption algorithm receives as input the master secret key msk, the public parameters pp, and a vector x→∈Zqn and outputs a ciphertext ctx→.(iii)
SSSK-IPE.KeyGen  (msk,pp,y→)→sky→: The key generation algorithm receives as input the master secret key msk, the public parameters pp, and a vector y→∈Zqn and outputs a secret key sky→.(iv)
SSSK-IPE.Decrypt  (pp,ctx→,sky→)→m∈Zq or ⊥: The decryption algorithm receives as input the public parameters pp, the ciphertext ctx→, and a secret key sky→ and outputs either a value m∈Zq or the dedicated symbol ⊥.We make the following correctness requirement: for all(msk,pp)←$SSSK-IPE.Setup(1λ,n), all x→,y→∈Zqn, and for ctx→←$SSSK-IPE.Encrypt(msk,pp,x→) and sky→←$SSSK-IPE.KeyGen(msk,pp,y→),SSSK-IPE.Decrypt(pp,ctx→,sky→) is sure to output 〈x→,y→〉 whenever 〈x→,y→〉≠⊥ with nonnegligible probability. The correctness requires the fact that it is 〈x→,y→〉 and not ⊥ when 〈x→,y→〉 is from a fixed polynomial range of value inside Zq.Definition 2 (indistinguishability-based security).
A SSSK-IPE scheme has indistinguishability-based security if for all PPT adversariesA, the advantage of A in the game defined as follows is negligible:(1)
A challenger runsSSSK-IPE.Setup to generate msk and pp, and pp is given to A. It also chooses a random bit b.(2)
The challenger responds to the following two types of queries made byA:
(i)
Secret key query:A submits a pair of vectors (y→0,y→1)∈Zqn and the challenger computes and returns sky→←SSSK-IPE.KeyGen(msk,pp,y→b).(ii)
Ciphertext query:A submits a pair of vectors (x→0,x→1)∈Zqn and the challenger computes and returns ctx→←SSSK-IPE.Encrypt(msk,pp,x→b).(3)
A outputs a bit b′, and wins if b′=b.
A SSSK-IPE scheme is indistinguishability-based secure if for all PPT adversariesA, the advantage of A in the above game, is AdvASSSK-IPE(λ)=|pr[ExpA,Game0(1λ)=1]-pr[ExpA,Game1(1λ)=1]|<negl(λ), where this game is by definition Game0 if b=0 and Game1 if b=1.Definition 3 (simulation-based security [1, 3, 7]).
For a SSSK-IPE scheme, if there exits a PPT adversaryA=(A1,A2) and a PPT simulator S, we define two experiments RealASSSK-IPE(1λ) and IdealA,SSSSK-IPE(1λ) in Box 1.  (in the public-key setting, the adversary A can encrypt plaintexts using the public parameters pp but A cannot in the secret key setting). Let l be the number of challenge messages output by A1 and p1 be the number of secret key queries in the first stage. The oracles O and O′ are defined as follows:(1)
The oracleO(msk,·) =SSSK-IPE.KeyGen(msk,·,·).(2)
The oracleO′(msk,st,·) is the second stage of S, i.e., S〈x→i,y→j〉(msk,st,·) for i∈[l],j∈[p1], where x→i and y→j are inputs of the ith ciphertext query and the jth secret key query by A1, respectively. The simulator S is stateful and after each query it updates the state st.
A SSSK-IPE scheme is simulation-based secure if there exists a PPT simulatorS such that, for all PPT adversaries A,(1)RealASSSK-IPE1λ≈cIdealA,SSSSK-IPE1λ.Box 1:Real and ideal experiments.
E x p e r i m e n t   R e a l A SSSK-IPE ( 1 λ ) :  E x p e r i m e n t   I d e a l A , S SSSK-IPE ( 1 λ ) : (msk, pp)←$ SSSK-IPE.Setup(1λ,n)(msk,st′)←$S(1λ,n) ( x → , s t ) ← $ A 1 SSSK-IPE.KeyGen ( msk , ⋅ , ⋅ )(pp)(x→,st)←$A1SSSK-IPE.KeyGen(msk,⋅,⋅)(pp) c t x → i ← $ SSSK-IPE.Encrypt(msk, pp, x→)(ctx→ii∈[l])←$S(x→i,y→ji∈[l],j∈[p1]) fori∈[l]where y→1,…,y→p1 are key queries made by A1 α ← $ A 2 O ( m s k , ⋅ , ⋅ ) ( c t x → i i ∈ [ l ] , s t )  α ← $ A 2 O ′ ( m s k , s t , ⋅ ) ( c t x → i i ∈ [ l ] , s t ) output(α)output(α)


### 2.2. Asymmetric Bilinear Pairing Groups

Definition 4 (asymmetric bilinear pairing groups).
We say that an algorithmGabpg(1λ) is an asymmetric bilinear group generator and it outputs a bilinear pairing group which is defined by the tuple (q,G1,G2,GT,e), where q is a prime and G1,G2,GT and are cyclic groups of order q, with a bilinear pairing e:G1×G2→GT with the following properties:(i)
(Bilinearity)∀g1∈G1,  g2∈G2,  a,b∈Zq,  e(g1a,g2b)=e(g1,g2)ab and(ii)
(Nondegeneracy)∃g1∈G1,  g2∈G2 such that e(g1,g2) has order q in GT.


### 2.3. External Decisional Linear Assumption

Definition 5 (external decisional linear (XDLIN) assumption [33]).
( q , G 1, G2,GT,e) is a tuple produced by Gabpg(1λ). Consider the following problem: given the distributions GbXDLIN(1λ)=((q,G1,G2,GT,e),ξg1,κg1, δξg1,σκg1,ξg2,κg2, δξg2,σκg2,Yb) for b∈0,1, where ξ,κ,δ,σ←$Zq,  Y0=(δ+σ)gc,  Y1=(δ+σ+ρ)gc,   ρ←$Zq and c∈{0,1}, output G0XDLIN if b is 0, and output G1XDLIN otherwise, we refer to the problem as the External Decisional Linear (XDLIN) problem.
For a PPT algorithmA, the advantage of A is defined as AdvAXDLIN(λ)=|Pr[A(1λ,G0XDLIN)→1]-Pr[A(1λ,G1XDLIN(1λ))→1]|. If for all PPT algorithms A, AdvAXDLIN(λ) is negligible in λ, we say that GbXDLIN(1λ) satisfies the XDLIN assumption.


### 2.4. Dual Pairing Vector Spaces

Definition 6 (dual pairing vector spaces (DPVS) [31, 32]).
A dual pairing vector space (DPVS)(q,V,V∗,GT,A,A∗,E) is directly defined by the tuple (q,G1,G2,GT,e)←$Gabpg(1λ).  V=G1n and V∗=G2n over Zqn are n-dimensional vector spaces. A={a→1,…,a→n} of V and A∗={a→1∗,…,a→n∗} of V∗ are canonical bases, where a→i=(0i-1,g1,0n-i) and a→i∗=(0i-1,g2,0n-i).  E:V×V∗→GT is pairing which is defined by E(x,y)=∏i=1ne(Xi,Yi)∈GT, where x=(X1,…Xn)∈V and y=(Y1,…Yn)∈V∗ with the following properties:(1)
(Bilinearity)E(ax→,by→)=E(x→,y→)ab for a,b∈Zq and(2)
(Nondegeneracy) ifE(x→,y→)=1 for all y→∈V∗, then x→=0→.
Let(q,V,V∗,GT,A,A∗,E) be the output of algorithm Gdpvs(1λ,n,(q,G1,G2,GT,e)), where n∈N.We then describe random dual orthonormal basis generatorGob(1λ,n) as follows:Gob(1λ,n):(q,V,V∗,GT,A,A∗,E)←$Gdpvs(1λ,n,(q,G1,G2,GT,e)), B=(χi,j)←$GL(n,Zq), (ϕi,j)=ψ(BT)-1,b→i=∑j=1nχi,ja→j, B={b→1,…,b→n},b→i∗=∑j=1nϕi,ja→j∗, B∗={b→1∗,…,b→n∗}, gT=e(g1,g2)ψ,returning (B,B∗).Let(x→)B denote ∑i=1nxib→i, where x→=(x1,…,xn)T∈Zqn and B={b→1,…,b→n}. Then we have(2)Ex→A,y→A∗=∏i=1nexig1,yig2=eg1,g2∑i=1nxiyi=eg1,g2x→,y→,Ex→B,y→B∗=EBx→A,ψBT-1y→A∗=eg1,g2ψBx→·BT-1y→=gTx→,y→.


## 2.1. Definition of SSSK-IPE

We introduce the definition of simulation-based secure secret key IPE (SSSK-IPE).Definition 1 (SSSK-IPE).
A SSSK-IPE scheme is composed of the four PPT algorithms defined below:(i)
SSSK-IPE.Setup  (1λ,n)→(msk,pp): The setup algorithm receives as input the security parameters λ and n, being vector length, and outputs a master secret key msk and public parameters pp.(ii)
SSSK-IPE.Encrypt  (msk,pp,x→)→ctx→: The encryption algorithm receives as input the master secret key msk, the public parameters pp, and a vector x→∈Zqn and outputs a ciphertext ctx→.(iii)
SSSK-IPE.KeyGen  (msk,pp,y→)→sky→: The key generation algorithm receives as input the master secret key msk, the public parameters pp, and a vector y→∈Zqn and outputs a secret key sky→.(iv)
SSSK-IPE.Decrypt  (pp,ctx→,sky→)→m∈Zq or ⊥: The decryption algorithm receives as input the public parameters pp, the ciphertext ctx→, and a secret key sky→ and outputs either a value m∈Zq or the dedicated symbol ⊥.We make the following correctness requirement: for all(msk,pp)←$SSSK-IPE.Setup(1λ,n), all x→,y→∈Zqn, and for ctx→←$SSSK-IPE.Encrypt(msk,pp,x→) and sky→←$SSSK-IPE.KeyGen(msk,pp,y→),SSSK-IPE.Decrypt(pp,ctx→,sky→) is sure to output 〈x→,y→〉 whenever 〈x→,y→〉≠⊥ with nonnegligible probability. The correctness requires the fact that it is 〈x→,y→〉 and not ⊥ when 〈x→,y→〉 is from a fixed polynomial range of value inside Zq.Definition 2 (indistinguishability-based security).
A SSSK-IPE scheme has indistinguishability-based security if for all PPT adversariesA, the advantage of A in the game defined as follows is negligible:(1)
A challenger runsSSSK-IPE.Setup to generate msk and pp, and pp is given to A. It also chooses a random bit b.(2)
The challenger responds to the following two types of queries made byA:
(i)
Secret key query:A submits a pair of vectors (y→0,y→1)∈Zqn and the challenger computes and returns sky→←SSSK-IPE.KeyGen(msk,pp,y→b).(ii)
Ciphertext query:A submits a pair of vectors (x→0,x→1)∈Zqn and the challenger computes and returns ctx→←SSSK-IPE.Encrypt(msk,pp,x→b).(3)
A outputs a bit b′, and wins if b′=b.
A SSSK-IPE scheme is indistinguishability-based secure if for all PPT adversariesA, the advantage of A in the above game, is AdvASSSK-IPE(λ)=|pr[ExpA,Game0(1λ)=1]-pr[ExpA,Game1(1λ)=1]|<negl(λ), where this game is by definition Game0 if b=0 and Game1 if b=1.Definition 3 (simulation-based security [1, 3, 7]).
For a SSSK-IPE scheme, if there exits a PPT adversaryA=(A1,A2) and a PPT simulator S, we define two experiments RealASSSK-IPE(1λ) and IdealA,SSSSK-IPE(1λ) in Box 1.  (in the public-key setting, the adversary A can encrypt plaintexts using the public parameters pp but A cannot in the secret key setting). Let l be the number of challenge messages output by A1 and p1 be the number of secret key queries in the first stage. The oracles O and O′ are defined as follows:(1)
The oracleO(msk,·) =SSSK-IPE.KeyGen(msk,·,·).(2)
The oracleO′(msk,st,·) is the second stage of S, i.e., S〈x→i,y→j〉(msk,st,·) for i∈[l],j∈[p1], where x→i and y→j are inputs of the ith ciphertext query and the jth secret key query by A1, respectively. The simulator S is stateful and after each query it updates the state st.
A SSSK-IPE scheme is simulation-based secure if there exists a PPT simulatorS such that, for all PPT adversaries A,(1)RealASSSK-IPE1λ≈cIdealA,SSSSK-IPE1λ.Box 1:Real and ideal experiments.
E x p e r i m e n t   R e a l A SSSK-IPE ( 1 λ ) :  E x p e r i m e n t   I d e a l A , S SSSK-IPE ( 1 λ ) : (msk, pp)←$ SSSK-IPE.Setup(1λ,n)(msk,st′)←$S(1λ,n) ( x → , s t ) ← $ A 1 SSSK-IPE.KeyGen ( msk , ⋅ , ⋅ )(pp)(x→,st)←$A1SSSK-IPE.KeyGen(msk,⋅,⋅)(pp) c t x → i ← $ SSSK-IPE.Encrypt(msk, pp, x→)(ctx→ii∈[l])←$S(x→i,y→ji∈[l],j∈[p1]) fori∈[l]where y→1,…,y→p1 are key queries made by A1 α ← $ A 2 O ( m s k , ⋅ , ⋅ ) ( c t x → i i ∈ [ l ] , s t )  α ← $ A 2 O ′ ( m s k , s t , ⋅ ) ( c t x → i i ∈ [ l ] , s t ) output(α)output(α)


## 2.2. Asymmetric Bilinear Pairing Groups

Definition 4 (asymmetric bilinear pairing groups).
We say that an algorithmGabpg(1λ) is an asymmetric bilinear group generator and it outputs a bilinear pairing group which is defined by the tuple (q,G1,G2,GT,e), where q is a prime and G1,G2,GT and are cyclic groups of order q, with a bilinear pairing e:G1×G2→GT with the following properties:(i)
(Bilinearity)∀g1∈G1,  g2∈G2,  a,b∈Zq,  e(g1a,g2b)=e(g1,g2)ab and(ii)
(Nondegeneracy)∃g1∈G1,  g2∈G2 such that e(g1,g2) has order q in GT.


## 2.3. External Decisional Linear Assumption

Definition 5 (external decisional linear (XDLIN) assumption [33]).
( q , G 1, G2,GT,e) is a tuple produced by Gabpg(1λ). Consider the following problem: given the distributions GbXDLIN(1λ)=((q,G1,G2,GT,e),ξg1,κg1, δξg1,σκg1,ξg2,κg2, δξg2,σκg2,Yb) for b∈0,1, where ξ,κ,δ,σ←$Zq,  Y0=(δ+σ)gc,  Y1=(δ+σ+ρ)gc,   ρ←$Zq and c∈{0,1}, output G0XDLIN if b is 0, and output G1XDLIN otherwise, we refer to the problem as the External Decisional Linear (XDLIN) problem.
For a PPT algorithmA, the advantage of A is defined as AdvAXDLIN(λ)=|Pr[A(1λ,G0XDLIN)→1]-Pr[A(1λ,G1XDLIN(1λ))→1]|. If for all PPT algorithms A, AdvAXDLIN(λ) is negligible in λ, we say that GbXDLIN(1λ) satisfies the XDLIN assumption.


## 2.4. Dual Pairing Vector Spaces

Definition 6 (dual pairing vector spaces (DPVS) [31, 32]).
A dual pairing vector space (DPVS)(q,V,V∗,GT,A,A∗,E) is directly defined by the tuple (q,G1,G2,GT,e)←$Gabpg(1λ).  V=G1n and V∗=G2n over Zqn are n-dimensional vector spaces. A={a→1,…,a→n} of V and A∗={a→1∗,…,a→n∗} of V∗ are canonical bases, where a→i=(0i-1,g1,0n-i) and a→i∗=(0i-1,g2,0n-i).  E:V×V∗→GT is pairing which is defined by E(x,y)=∏i=1ne(Xi,Yi)∈GT, where x=(X1,…Xn)∈V and y=(Y1,…Yn)∈V∗ with the following properties:(1)
(Bilinearity)E(ax→,by→)=E(x→,y→)ab for a,b∈Zq and(2)
(Nondegeneracy) ifE(x→,y→)=1 for all y→∈V∗, then x→=0→.
Let(q,V,V∗,GT,A,A∗,E) be the output of algorithm Gdpvs(1λ,n,(q,G1,G2,GT,e)), where n∈N.We then describe random dual orthonormal basis generatorGob(1λ,n) as follows:Gob(1λ,n):(q,V,V∗,GT,A,A∗,E)←$Gdpvs(1λ,n,(q,G1,G2,GT,e)), B=(χi,j)←$GL(n,Zq), (ϕi,j)=ψ(BT)-1,b→i=∑j=1nχi,ja→j, B={b→1,…,b→n},b→i∗=∑j=1nϕi,ja→j∗, B∗={b→1∗,…,b→n∗}, gT=e(g1,g2)ψ,returning (B,B∗).Let(x→)B denote ∑i=1nxib→i, where x→=(x1,…,xn)T∈Zqn and B={b→1,…,b→n}. Then we have(2)Ex→A,y→A∗=∏i=1nexig1,yig2=eg1,g2∑i=1nxiyi=eg1,g2x→,y→,Ex→B,y→B∗=EBx→A,ψBT-1y→A∗=eg1,g2ψBx→·BT-1y→=gTx→,y→.


## 3. Our SSSK-IPE Scheme

In this section, we present the construction of SSSK-IPE.SSSK-IPE.Setup(1λ, n)→ (msk, pp): The setup algorithm runs (q,G1,G2,GT,e)←$Gabpg(1λ). It then generates(3)q,V,V∗,GT,A,A∗,E←$Gdpvs1λ,n+6,q,G1,G2,GT,e,B=b→1,…,b→n+6,B∗=b→1∗,…,b→n+6∗←$Gob1λ,n+6.The algorithm outputs msk=(B^,B^∗), where B^={b→1,…,b→n,b→n+1,b→n+2,b→n+5},  B^∗={b→1∗,…,b→n∗,b→n+3∗,b→n+4∗,b→n+6∗}, and pp=(q,V,V∗,GT,A1,A1∗,E).SSSK-IPE.Encrypt(msk, pp, x→)→ctx→: The encryption algorithm samples α,β,η←$Zq independently and uniformly at random and outputs(4)ctx→=x→,α,β,0,0,η,0B.SSSK-IPE.KeyGen(msk, pp, y→)→sky→: The secret key generation algorithm samples θ,γ,ζ←$Zq independently and uniformly at random and outputs(5)sky→=y→,0,0,θ,γ,0,ζB∗.SSSK-IPE.Decrypt (pp, ctx→,sky→)→m∈Zq or ⊥: The decryption algorithm outputs(6)d=Ectx→,sky→.It then attempts to determinem∈Zq such that gTm=d. If there is m that satisfies the equation, the algorithm outputs m. Otherwise, it outputs ⊥. Due to a polynomial-size range of possible values for m, the decryption algorithm certainly runs in polynomial time.Correctness.For any ctx→ and sky→ by callingSSSK-IPE.Encrypt(msk, pp, x→) andSSSK-IPE.KeyGen(msk, pp, y→), respectively, the pairing evaluations in the decryption algorithm proceed as follows:(7)d=Ectx→,sky→=gTx→,y→.If the decryption algorithm takes polynomial time in the size of the plaintext space, it will outputm=〈x→,y→〉 as desired.Remark 7.
We can easily notice that our scheme is malleable, where a ciphertext can be created from certain other ciphertexts. The scheme in [18] is also malleable, while it seems difficult to prove the schemes in [16, 17, 19] to be malleable.Remark 8.
In contrast to the scheme of Tomida et al. [18], we provides a more efficient scheme with better security strength. The construction of [18] achieves indistinguishability-based security where the constraint on the adversaries is that, for all ciphertext queries (x→0,x→1) and all key queries (y→0,y→1), 〈x→0,y→0〉=〈x→1,y→1〉 should hold. B and B∗ of dimension 2n+5 are introduced in their construction. There are at least 2n dimensions of vector spaces because of changing a ciphertext including x→0 (respectively, a secret key including y→0) into one including x→1 (respectively, a secret key including y→1) in the security game. As mentioned in Section 1, in our scheme, a hidden dimension can be used to convert a corresponding coefficient to another coefficient in a secret key or a ciphertext, so that no PPT adversary can distinguish the two hybrid experiments. Our scheme therefore saves n dimensions of vector spaces.


## 4. Security Proof

### 4.1. Theorem9

Now, we prove that our construction has many-AD-SIM (many messages secure, adaptive simulation definition) security from the XDLIN assumption in the standard model against adaptive adversaries obtaining an unbounded number of ciphertexts and secret keys.Theorem 9.
Under the XDLIN assumption the proposed scheme is many-AD-SIM-secure.We will show Lemmas15, 16, 17, 18, and 19 for the security proof of Theorem 9.


### 4.2. Lemmas

Definition 10 (problem 0).
Problem 0 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2), where(q,G1,G2,GT,e)←$Gabpg(1λ),B=(χi,j)←$GL(3,Zq) and (ϕi,j)=(BT)-1,κ←$Zq,b→i=κ∑j=1nχi,ja→j for i=1,2,3, B={b→1,b→2,b→3},ξ←$Zq,b→i∗=ξ∑j=1nϕi,ja→j∗ for i=1,3, B^∗={b→1∗,b→3∗},gT=e(g1,g2)κξand δ,σ←$Zq, ρ←$Zq×, andy→0=(δ,0,σ)B and  y→1=(δ,ρ,σ)B.Definition 11 (problem 1).
Problem 1 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2,b→n+5},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗},α,β←$Zq, η←$Zq×, andY→0=(0n,α,β,0,0,η,0)B and Y→1=(0n,α,β,0,0,η,ζ′)B.Definition 12 (problem 2).
Problem 2 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2,b→n+6},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗},α,β,η←$Zq,  ζ′←$Zq×, andY→0=(0n,α,β,0,0,η,ζ′)Band Y→1=(0n,α,β,0,0,0,ζ′)B.Definition 13 (problem 3).
Problem 3 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b∗), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗,b→n+6∗},θ,γ,ζ←$Zq, η′←$Zq×, andY→0∗=(0n,0,0,θ,γ,0,ζ)B∗ and Y→1∗=(0n,0,0,θ,γ,η′,ζ)B∗.Definition 14 (problem 4).
Problem 4 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b∗), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗,b→n+5∗},θ,γ,ζ←$Zq, η′←$Zq×, andY→0∗=(0n,0,0,θ,γ,η′,ζ)B∗ and   Y→1∗=(0n,0,0,θ,γ,η′,0)B∗.For a PPT adversaryA, the advantage of A for Problem n, where n=0,1,2,3,4, is defined as(8)AdvAProbnλ=PrExpAP01λ=1-PrExpAP11λ=1,where the instance is by definition P0 if b=0 and P1 if b=1.Lemma 15.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb0(λ)≤AdvAXDLIN(λ)+5/q.Proof.
LetW be a random linear transformation. On inputting an instance of XDLIN ((q,G1,G2,GT,e),ξg1,κg1,δξg1, σκg1,ξg2,κg2, δξg2,σκg2,Yb), A setsgT=e(κG1,ξG2), u→1=(ξ,0,1)A, and u→2=(0,0,1)A,u→3=(0,κ,1)A,u→1∗=(κ,0,0)A∗, and u→2∗=(-κ,-ξ,κξ)A∗,u→3∗=(0,ξ,0)A∗ and w→b=(δξG1,σκG1,Yb).
A can calculate u→i for i=1,2,3 and u→i∗ for i=1,3. Next, A generates b→i=W(u→i) for i=1,2,3,  b→i∗=(W-1)T(u→i∗) for i=1,2,3, and y→b=W(w→b). Then A sets B=(b→1,b→2,b→3),B^∗=(b→1∗,b→3∗). Finally, A gives B((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2).
Ifb=0 and  Yb=Y0=(δ+σ)G1, then w→0=(δξG1,σκG1,(δ+σ)G1)=(δξ,σκ,(δ+σ))A=δu→1+σu→2 and y0=W(w→0)=W(δu→1+σu→2)=(δ,0,σ)B when κ≠0 and ξ≠0 (with probability 2/q).
Ifb=1 and  Yb=Y1=(δ+ρ+σ)G1, then w→1=(δξG1,σκG1,(δ+ρ+σ)G1)=(δξ,σκ,(δ+ρ+σ))A=δu→1+ρu→2+σu→3 and y1=W(w→1)=W(δu→1+ρu→2+σu→3)=(δ,ρ,σ)B when κ≠0, ξ≠0 and ρ≠0 (with probability 3/q). Therefore, AdvBProb0(λ)≤AdvAXDLIN(λ)+5/q.Lemma 16.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb1(λ)≤AdvAProb0(λ).Proof.
LetW be a random linear transformation. On inputting an instance of Porblem 0 ((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2), A calculateshi=W(0i+2,κg1,0n+3-i) for i=1,…,n,hi=W(0i,κg1,0n+5-i) for i=n+3,n+4,n+5,hn+1=W(b→1,0n+3), hn+2=W(b→3,0n+3),hn+6=W(b→2,0n+3),hi∗=(W-1)T(0i+2,ξg2,0n+3-i) for i=1,…,n,hi∗=(W-1)T(0i,ξg2,0n+5-i) for i=n+3,n+4,n+5,hn+1∗=(W-1)T(b→1∗,0n+3),  hn+2∗=(W-1)T(b→3∗,0n+3),hn+6∗=(W-1)T(b→2∗,0n+3) and  Y→b=W(y→b,0n+3),H=(h→1,…,h→n+6) and  H∗=(h→1∗,…,h→n+6∗).
ThenA sets H^=(h→1,…,h→n,h→n+1,h→n+2,h→n+5) and H^∗=(h→1∗,…,h→n∗,h→n+3∗,h→n+4∗). Finally, A gives B((q,G1,G2,GT,e),H^,H^∗,Y→b). If b=0,  Y→0=(0n,α,β,0,0,η,0)H, and if b=1,  Y→1=(0n,α,β,0,0,η,ζ′)H), where δ=α,  ρ=ζ′, and σ=β. This is the same as an instance of Problem 0.Lemma 17.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb2(λ)≤AdvAProb0(λ).Proof.
LetW be a random linear transformation. On inputting an instance of Porblem 0 ((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2), A calculateshi=W(0i+2,κg1,0n+3-i) for i=1,...,n,hi=W(0i,κg1,0n+5-i) for i=n+3,n+4,n+6,hn+1=W(b→1,0n+3) and  hn+2=W(b→3,0n+3),hn+5=W(b→2,0n+3),hi∗=(W-1)T(0i+2,ξg2,0n+3-i) for i=1,…,n,hi∗=(W-1)T(0i,ξg2,0n+5-i) for i=n+3,n+4,n+6,hn+1∗=(W-1)T(b→1∗,0n+3) and hn+2∗=(W-1)T(b→3∗,0n+3),hn+5∗=(W-1)T(b→2∗,0n+3) and  Y→b=W(y→b,0n+3),H=(h→1,…,h→n+6), and H∗=(h→1∗,…,h→n+6∗).
ThenA sets H^=(h→1,…,h→n,h→n+1,h→n+2,h→n+6) and H^∗=(h→1∗,…,h→n∗,h→n+3∗,h→n+4∗). Finally, A gives B((q,G1,G2,GT,e),H^,H^∗,Y→b). If b=0,  Y→0=(0n,α,β,0,0,η,ζ′)H, and if b=1,  Y→1=(0n,α,β,0,0,0,ζ′)H, where δ=α,  ρ=η, and σ=β. This is the same as an instance of Problem 0.Lemma 18.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb3(λ)≤AdvAProb0(λ).Proof.
The proof follows in the same manner as Lemma16.Lemma 19.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb4(λ)≤AdvAProb0(λ).Proof.
The proof follows in the same manner as Lemma17.


### 4.3. Security Proof of Theorem9

For the security proof, we follow the simulation-based security notion [1, 3]. A simulator responds to queries by an adversary A and provides simulated secret keys and simulated ciphertexts to A. The simulator is made of three algorithms: Setup~,  Encrypt~, and KeyGen~.S e t u p : ~ It generates a master secret key msk and public parameters pp, which is transferred to A. Specially, on input (1λ,n), it sets (msk, pp)←SSSK-IPE.Setup. The simulator will use the master secret key and the public parameters to answer the queries of A in Encrypt~ and KeyGen~.E n c r y p t : ~ It simulates the ciphertexts of challenge messages x→1,…,x→l, where x→1,…,x→l are output by A and l is the number of the challenge messages. Let p1 be the number of secret key queries in the first stage. Encrypt~ receives as input msk, pp, nonadaptive secret key queries y→1,…,y→p1 made by A, together with (〈x→i,y→1〉,…,〈x→i,y→p1〉) for each 1≤i≤l, and the secret keys (y→1,sky→1),…,(y→p1,sky→p1). The normal ciphertext is (x→,α,β,0,0,η,0)B generated bySSSK-IPE.Encrypt, where α,β,η←$Zq. The simulated ciphertext is (x→,α,β,0,0,0,ζ′)B generated by Encrypt~, where ζ′←$Zq×. In order to prove the views of A inSSSK-IPE.Encrypt and that in Encrypt~ have the same distribution, we define a new algorithm Encrypt′~, where ctx→=(x→,α,β,0,0,η,ζ′)B.K e y G e n : ~ It simulates the answer to the second stage queries of A. It receives as input msk, pp, the vector y→, where y→ is the secret key query made by A, and the values 〈x→1,y→〉,…,〈x→l,y→〉, where x→1,…,x→l are the challenge messages. The normal secret key is (y→,0,0,θ,γ,0,ζ)B∗ generated bySSSK-IPE.KeyGen, where θ,γ,ζ←$Zq. The simulated secret key is (y→,0,0,θ,γ,η′,0)B∗ generated by KeyGen~, where η′←$Zq×. Analogous to Encrypt~, we also define a new algorithm KeyGen~′ where sky→=(y→,0,0,θ,γ,η′,ζ)B∗.Next, we will prove it is indistinguishable between the output of an ideal world experiment and the output of the real world experiment via a hybrid argument.Proof.
A high-level overview of the security proof is given in Figure1. By a standard hybrid argument, we prove the distributions of the outputs of Encrypt~ and KeyGen~ are computationally indistinguishable from that of the normal ciphertexts and the normal secret keys, respectively. We proceed via a series of hybrid experiments H0,…,H5, where H0 is the real world experiment and H5 is the ideal world experiment. We then prove that each hybrid experiment is indistinguishable from the neighboring one.(i)
HybridH0: This is the real experiment.(ii)
HybridH1: This experiment is the same as H0 except that the master secret key and the public parameters are generated by Setup~.(iii)
HybridH2: This experiment is the same as H1 except that every challenge ciphertext is ctx→=(x→,α,β,0,0,η,ζ′)B which is generated by Encrypt′~.(iv)
HybridH3: This experiment is the same as H2 except that, for every key query y→, the corresponding secret key is sky→=(y→,0,0,θ,γ,η′,ζ)B∗ which is generated by KeyGen~′.(v)
HybridH4: This experiment is the same as H3 except that, for every key query y→, the corresponding secret key is sky→=(y→,0,0,θ,γ,η′,0)B∗ which is generated by KeyGen~.(vi)
HybridH5: This experiment is the same as H4 except that every challenge ciphertext is ctx→=(x→,α,β,0,0,0,ζ′)B which is generated by Encrypt~.Figure 1
An overview of the security proof.Lemma 20.
For all PPT adversariesA, H0≈cH1.Proof.
Because the master secret key and the public parameters are all generated bySSSK-IPE.Setup in H0 and H1, the view of A in H0 and that in H1 has the same distribution.Lemma 21.
Assuming that Problem 1 holds, for all PPT adversariesA, H1≈cH2.Proof.
Suppose that there exists a PPT adversaryA that can distinguish the output distributions of H1 and H2. Then, we construct a PPT algorithm B which is given an instance of Problem 1 ((q,G1,G2,GT,e),B^,B^∗,Y→b) for b∈{0,1} and simulates H1 and H2.
Setup: B runsSSSK-IPE.Setup(1λ, n) and outputs msk=(B^,B^∗) and pp=(q,V,V∗,GT,A,A∗,E). B gives A the public parameters pp and the master secret key msk is only known to B.
Secret Key Queries: To answer the key queries made by A, B runs algorithmSSSK-IPE.Encrypt to respond with sky→=(y→,0,0,θ,γ,0,ζ)B∗.
Simulated Ciphertexts: B randomly chooses k={1,…,l}, where l is the number of the ciphertext queries asked by the adversary A. To answer the ith ciphertext query that A makes, B chooses α,β,η←$Zq and ζ′←$Zq× and computes and answers asctx→=∑i=1nxib→i+αb→n+1+βb→n+2+ηb→n+5+ζ′b→n+6 if i<k,ctx→=∑i=1nxib→i+Y→b if i=k,ctx→=∑i=1nxib→i+αb→n+1+βb→n+2+ηb→n+5 if i>k.
The view ofA is composed of the public parameters and the answers of the secret key queries and the ciphertext query. The public parameters in H1 and H2 are all generated bySSSK-IPE.Setup and thus have the same distribution, similar to the answers to the secret key queries. As for the answer to the ith ciphertext query, if b=0 then the answer is distributed as in H1 and if b=1 then the answer is distributed as in H2.Lemma 22.
Assuming that Problem 3 holds, for all PPT adversariesA, H2≈cH3.Proof.
Suppose that there exists a PPT adversaryA that can distinguish the output distributions of H2 and H3. Then, we construct a PPT algorithm B which is given an instance of Problem 3 ((q,G1,G2,GT,e),B^,B^∗,Y→b∗) for b∈{0,1} and simulates H2 and H3.
Setup: B runsSSSK-IPE.Setup(1λ, n) and outputs msk=(B^,B^∗) and pp=(q,V,V∗,GT,A,A∗,E). B gives A the public parameters pp, and the master secret key msk is only known to B.
First stage key queries: To answer every key query made by A, B chooses random θ,γ,ζ←$Zq, runsSSSK-IPE.KeyGen (msk, pp, y→), and responds with sky→=(y→,0,0,θ,γ,0,ζ)B∗.
Simulated ciphertexts: To answer every ciphertext query that A makes, B chooses random α,β,η←$Zq and ζ′←$Zq×, runs Encrypt′~, and answers as ctx→=(x→,α,β,0,0,η,ζ′)B.
Second stage key queries: B randomly chooses k={1,…,p2}, where p2 is the number of the ciphertext queries asked by the adversary A in the second stage. To answer the ith key query that A makes, B chooses random θ,γ,ζ←$Zq and η′←$Zq× and computes and answers assky→=∑i=1nyib→i∗+θb→n+3∗+γb→n+4∗+η′b→n+5∗+ζb→n+6∗ if i<k,sky→=∑i=1nyib→i∗+Y→b if i=k,sky→=∑i=1nyib→i∗+θb→n+3∗+γb→n+4∗+ζb→n+6∗ if i>k.
We observe the view ofA in its interaction with B. The public parameters in H2 and H3 are all generated bySSSK-IPE.Setup and thus have the same distribution, similarly for the answers to every ciphertext query where ctx→ in H2 and H3 are all generated by Encrypt′~. As for the answer to the ith key query, if b=0 then the answer is distributed as in H2 and if b=1 then the answer is distributed as in H3.Lemma 23.
Assuming that Problem 4 holds, for all PPT adversariesA, H3≈cH4.Proof.
The proof follows in the same manner as Lemma22.Lemma 24.
Assuming that Problem 2 holds, for all PPT adversariesA, H4≈cH5.Proof.
The proof follows in the same manner as Lemma21.


## 4.1. Theorem9

Now, we prove that our construction has many-AD-SIM (many messages secure, adaptive simulation definition) security from the XDLIN assumption in the standard model against adaptive adversaries obtaining an unbounded number of ciphertexts and secret keys.Theorem 9.
Under the XDLIN assumption the proposed scheme is many-AD-SIM-secure.We will show Lemmas15, 16, 17, 18, and 19 for the security proof of Theorem 9.


## 4.2. Lemmas

Definition 10 (problem 0).
Problem 0 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2), where(q,G1,G2,GT,e)←$Gabpg(1λ),B=(χi,j)←$GL(3,Zq) and (ϕi,j)=(BT)-1,κ←$Zq,b→i=κ∑j=1nχi,ja→j for i=1,2,3, B={b→1,b→2,b→3},ξ←$Zq,b→i∗=ξ∑j=1nϕi,ja→j∗ for i=1,3, B^∗={b→1∗,b→3∗},gT=e(g1,g2)κξand δ,σ←$Zq, ρ←$Zq×, andy→0=(δ,0,σ)B and  y→1=(δ,ρ,σ)B.Definition 11 (problem 1).
Problem 1 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2,b→n+5},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗},α,β←$Zq, η←$Zq×, andY→0=(0n,α,β,0,0,η,0)B and Y→1=(0n,α,β,0,0,η,ζ′)B.Definition 12 (problem 2).
Problem 2 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2,b→n+6},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗},α,β,η←$Zq,  ζ′←$Zq×, andY→0=(0n,α,β,0,0,η,ζ′)Band Y→1=(0n,α,β,0,0,0,ζ′)B.Definition 13 (problem 3).
Problem 3 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b∗), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗,b→n+6∗},θ,γ,ζ←$Zq, η′←$Zq×, andY→0∗=(0n,0,0,θ,γ,0,ζ)B∗ and Y→1∗=(0n,0,0,θ,γ,η′,ζ)B∗.Definition 14 (problem 4).
Problem 4 is to guessb∈{0,1}, given ((q,G1,G2,GT,e),B^,B^∗,Y→b∗), where(B,B∗,(q,G1,G2,GT,e))←$Gob(1λ,n+6),B^={b→1,…,b→n,b→n+1,b→n+2},B^∗={b→1∗,…,b→n∗,b→n+3∗, b→n+4∗,b→n+5∗},θ,γ,ζ←$Zq, η′←$Zq×, andY→0∗=(0n,0,0,θ,γ,η′,ζ)B∗ and   Y→1∗=(0n,0,0,θ,γ,η′,0)B∗.For a PPT adversaryA, the advantage of A for Problem n, where n=0,1,2,3,4, is defined as(8)AdvAProbnλ=PrExpAP01λ=1-PrExpAP11λ=1,where the instance is by definition P0 if b=0 and P1 if b=1.Lemma 15.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb0(λ)≤AdvAXDLIN(λ)+5/q.Proof.
LetW be a random linear transformation. On inputting an instance of XDLIN ((q,G1,G2,GT,e),ξg1,κg1,δξg1, σκg1,ξg2,κg2, δξg2,σκg2,Yb), A setsgT=e(κG1,ξG2), u→1=(ξ,0,1)A, and u→2=(0,0,1)A,u→3=(0,κ,1)A,u→1∗=(κ,0,0)A∗, and u→2∗=(-κ,-ξ,κξ)A∗,u→3∗=(0,ξ,0)A∗ and w→b=(δξG1,σκG1,Yb).
A can calculate u→i for i=1,2,3 and u→i∗ for i=1,3. Next, A generates b→i=W(u→i) for i=1,2,3,  b→i∗=(W-1)T(u→i∗) for i=1,2,3, and y→b=W(w→b). Then A sets B=(b→1,b→2,b→3),B^∗=(b→1∗,b→3∗). Finally, A gives B((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2).
Ifb=0 and  Yb=Y0=(δ+σ)G1, then w→0=(δξG1,σκG1,(δ+σ)G1)=(δξ,σκ,(δ+σ))A=δu→1+σu→2 and y0=W(w→0)=W(δu→1+σu→2)=(δ,0,σ)B when κ≠0 and ξ≠0 (with probability 2/q).
Ifb=1 and  Yb=Y1=(δ+ρ+σ)G1, then w→1=(δξG1,σκG1,(δ+ρ+σ)G1)=(δξ,σκ,(δ+ρ+σ))A=δu→1+ρu→2+σu→3 and y1=W(w→1)=W(δu→1+ρu→2+σu→3)=(δ,ρ,σ)B when κ≠0, ξ≠0 and ρ≠0 (with probability 3/q). Therefore, AdvBProb0(λ)≤AdvAXDLIN(λ)+5/q.Lemma 16.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb1(λ)≤AdvAProb0(λ).Proof.
LetW be a random linear transformation. On inputting an instance of Porblem 0 ((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2), A calculateshi=W(0i+2,κg1,0n+3-i) for i=1,…,n,hi=W(0i,κg1,0n+5-i) for i=n+3,n+4,n+5,hn+1=W(b→1,0n+3), hn+2=W(b→3,0n+3),hn+6=W(b→2,0n+3),hi∗=(W-1)T(0i+2,ξg2,0n+3-i) for i=1,…,n,hi∗=(W-1)T(0i,ξg2,0n+5-i) for i=n+3,n+4,n+5,hn+1∗=(W-1)T(b→1∗,0n+3),  hn+2∗=(W-1)T(b→3∗,0n+3),hn+6∗=(W-1)T(b→2∗,0n+3) and  Y→b=W(y→b,0n+3),H=(h→1,…,h→n+6) and  H∗=(h→1∗,…,h→n+6∗).
ThenA sets H^=(h→1,…,h→n,h→n+1,h→n+2,h→n+5) and H^∗=(h→1∗,…,h→n∗,h→n+3∗,h→n+4∗). Finally, A gives B((q,G1,G2,GT,e),H^,H^∗,Y→b). If b=0,  Y→0=(0n,α,β,0,0,η,0)H, and if b=1,  Y→1=(0n,α,β,0,0,η,ζ′)H), where δ=α,  ρ=ζ′, and σ=β. This is the same as an instance of Problem 0.Lemma 17.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb2(λ)≤AdvAProb0(λ).Proof.
LetW be a random linear transformation. On inputting an instance of Porblem 0 ((q,G1,G2,GT,e),B,B^∗,y→b,κg1,ξg2), A calculateshi=W(0i+2,κg1,0n+3-i) for i=1,...,n,hi=W(0i,κg1,0n+5-i) for i=n+3,n+4,n+6,hn+1=W(b→1,0n+3) and  hn+2=W(b→3,0n+3),hn+5=W(b→2,0n+3),hi∗=(W-1)T(0i+2,ξg2,0n+3-i) for i=1,…,n,hi∗=(W-1)T(0i,ξg2,0n+5-i) for i=n+3,n+4,n+6,hn+1∗=(W-1)T(b→1∗,0n+3) and hn+2∗=(W-1)T(b→3∗,0n+3),hn+5∗=(W-1)T(b→2∗,0n+3) and  Y→b=W(y→b,0n+3),H=(h→1,…,h→n+6), and H∗=(h→1∗,…,h→n+6∗).
ThenA sets H^=(h→1,…,h→n,h→n+1,h→n+2,h→n+6) and H^∗=(h→1∗,…,h→n∗,h→n+3∗,h→n+4∗). Finally, A gives B((q,G1,G2,GT,e),H^,H^∗,Y→b). If b=0,  Y→0=(0n,α,β,0,0,η,ζ′)H, and if b=1,  Y→1=(0n,α,β,0,0,0,ζ′)H, where δ=α,  ρ=η, and σ=β. This is the same as an instance of Problem 0.Lemma 18.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb3(λ)≤AdvAProb0(λ).Proof.
The proof follows in the same manner as Lemma16.Lemma 19.
Suppose that the XDLIN assumption holds inG1 and G2. Then for all PPT adversary B, there is an adversary A such that AdvBProb4(λ)≤AdvAProb0(λ).Proof.
The proof follows in the same manner as Lemma17.


## 4.3. Security Proof of Theorem9

For the security proof, we follow the simulation-based security notion [1, 3]. A simulator responds to queries by an adversary A and provides simulated secret keys and simulated ciphertexts to A. The simulator is made of three algorithms: Setup~,  Encrypt~, and KeyGen~.S e t u p : ~ It generates a master secret key msk and public parameters pp, which is transferred to A. Specially, on input (1λ,n), it sets (msk, pp)←SSSK-IPE.Setup. The simulator will use the master secret key and the public parameters to answer the queries of A in Encrypt~ and KeyGen~.E n c r y p t : ~ It simulates the ciphertexts of challenge messages x→1,…,x→l, where x→1,…,x→l are output by A and l is the number of the challenge messages. Let p1 be the number of secret key queries in the first stage. Encrypt~ receives as input msk, pp, nonadaptive secret key queries y→1,…,y→p1 made by A, together with (〈x→i,y→1〉,…,〈x→i,y→p1〉) for each 1≤i≤l, and the secret keys (y→1,sky→1),…,(y→p1,sky→p1). The normal ciphertext is (x→,α,β,0,0,η,0)B generated bySSSK-IPE.Encrypt, where α,β,η←$Zq. The simulated ciphertext is (x→,α,β,0,0,0,ζ′)B generated by Encrypt~, where ζ′←$Zq×. In order to prove the views of A inSSSK-IPE.Encrypt and that in Encrypt~ have the same distribution, we define a new algorithm Encrypt′~, where ctx→=(x→,α,β,0,0,η,ζ′)B.K e y G e n : ~ It simulates the answer to the second stage queries of A. It receives as input msk, pp, the vector y→, where y→ is the secret key query made by A, and the values 〈x→1,y→〉,…,〈x→l,y→〉, where x→1,…,x→l are the challenge messages. The normal secret key is (y→,0,0,θ,γ,0,ζ)B∗ generated bySSSK-IPE.KeyGen, where θ,γ,ζ←$Zq. The simulated secret key is (y→,0,0,θ,γ,η′,0)B∗ generated by KeyGen~, where η′←$Zq×. Analogous to Encrypt~, we also define a new algorithm KeyGen~′ where sky→=(y→,0,0,θ,γ,η′,ζ)B∗.Next, we will prove it is indistinguishable between the output of an ideal world experiment and the output of the real world experiment via a hybrid argument.Proof.
A high-level overview of the security proof is given in Figure1. By a standard hybrid argument, we prove the distributions of the outputs of Encrypt~ and KeyGen~ are computationally indistinguishable from that of the normal ciphertexts and the normal secret keys, respectively. We proceed via a series of hybrid experiments H0,…,H5, where H0 is the real world experiment and H5 is the ideal world experiment. We then prove that each hybrid experiment is indistinguishable from the neighboring one.(i)
HybridH0: This is the real experiment.(ii)
HybridH1: This experiment is the same as H0 except that the master secret key and the public parameters are generated by Setup~.(iii)
HybridH2: This experiment is the same as H1 except that every challenge ciphertext is ctx→=(x→,α,β,0,0,η,ζ′)B which is generated by Encrypt′~.(iv)
HybridH3: This experiment is the same as H2 except that, for every key query y→, the corresponding secret key is sky→=(y→,0,0,θ,γ,η′,ζ)B∗ which is generated by KeyGen~′.(v)
HybridH4: This experiment is the same as H3 except that, for every key query y→, the corresponding secret key is sky→=(y→,0,0,θ,γ,η′,0)B∗ which is generated by KeyGen~.(vi)
HybridH5: This experiment is the same as H4 except that every challenge ciphertext is ctx→=(x→,α,β,0,0,0,ζ′)B which is generated by Encrypt~.Figure 1
An overview of the security proof.Lemma 20.
For all PPT adversariesA, H0≈cH1.Proof.
Because the master secret key and the public parameters are all generated bySSSK-IPE.Setup in H0 and H1, the view of A in H0 and that in H1 has the same distribution.Lemma 21.
Assuming that Problem 1 holds, for all PPT adversariesA, H1≈cH2.Proof.
Suppose that there exists a PPT adversaryA that can distinguish the output distributions of H1 and H2. Then, we construct a PPT algorithm B which is given an instance of Problem 1 ((q,G1,G2,GT,e),B^,B^∗,Y→b) for b∈{0,1} and simulates H1 and H2.
Setup: B runsSSSK-IPE.Setup(1λ, n) and outputs msk=(B^,B^∗) and pp=(q,V,V∗,GT,A,A∗,E). B gives A the public parameters pp and the master secret key msk is only known to B.
Secret Key Queries: To answer the key queries made by A, B runs algorithmSSSK-IPE.Encrypt to respond with sky→=(y→,0,0,θ,γ,0,ζ)B∗.
Simulated Ciphertexts: B randomly chooses k={1,…,l}, where l is the number of the ciphertext queries asked by the adversary A. To answer the ith ciphertext query that A makes, B chooses α,β,η←$Zq and ζ′←$Zq× and computes and answers asctx→=∑i=1nxib→i+αb→n+1+βb→n+2+ηb→n+5+ζ′b→n+6 if i<k,ctx→=∑i=1nxib→i+Y→b if i=k,ctx→=∑i=1nxib→i+αb→n+1+βb→n+2+ηb→n+5 if i>k.
The view ofA is composed of the public parameters and the answers of the secret key queries and the ciphertext query. The public parameters in H1 and H2 are all generated bySSSK-IPE.Setup and thus have the same distribution, similar to the answers to the secret key queries. As for the answer to the ith ciphertext query, if b=0 then the answer is distributed as in H1 and if b=1 then the answer is distributed as in H2.Lemma 22.
Assuming that Problem 3 holds, for all PPT adversariesA, H2≈cH3.Proof.
Suppose that there exists a PPT adversaryA that can distinguish the output distributions of H2 and H3. Then, we construct a PPT algorithm B which is given an instance of Problem 3 ((q,G1,G2,GT,e),B^,B^∗,Y→b∗) for b∈{0,1} and simulates H2 and H3.
Setup: B runsSSSK-IPE.Setup(1λ, n) and outputs msk=(B^,B^∗) and pp=(q,V,V∗,GT,A,A∗,E). B gives A the public parameters pp, and the master secret key msk is only known to B.
First stage key queries: To answer every key query made by A, B chooses random θ,γ,ζ←$Zq, runsSSSK-IPE.KeyGen (msk, pp, y→), and responds with sky→=(y→,0,0,θ,γ,0,ζ)B∗.
Simulated ciphertexts: To answer every ciphertext query that A makes, B chooses random α,β,η←$Zq and ζ′←$Zq×, runs Encrypt′~, and answers as ctx→=(x→,α,β,0,0,η,ζ′)B.
Second stage key queries: B randomly chooses k={1,…,p2}, where p2 is the number of the ciphertext queries asked by the adversary A in the second stage. To answer the ith key query that A makes, B chooses random θ,γ,ζ←$Zq and η′←$Zq× and computes and answers assky→=∑i=1nyib→i∗+θb→n+3∗+γb→n+4∗+η′b→n+5∗+ζb→n+6∗ if i<k,sky→=∑i=1nyib→i∗+Y→b if i=k,sky→=∑i=1nyib→i∗+θb→n+3∗+γb→n+4∗+ζb→n+6∗ if i>k.
We observe the view ofA in its interaction with B. The public parameters in H2 and H3 are all generated bySSSK-IPE.Setup and thus have the same distribution, similarly for the answers to every ciphertext query where ctx→ in H2 and H3 are all generated by Encrypt′~. As for the answer to the ith key query, if b=0 then the answer is distributed as in H2 and if b=1 then the answer is distributed as in H3.Lemma 23.
Assuming that Problem 4 holds, for all PPT adversariesA, H3≈cH4.Proof.
The proof follows in the same manner as Lemma22.Lemma 24.
Assuming that Problem 2 holds, for all PPT adversariesA, H4≈cH5.Proof.
The proof follows in the same manner as Lemma21.


## 5. Evaluation

To assess the practicality of the SSSK-IPE scheme in Section3, we implement it similar to FHIPE [25], where two libraries are used: the Charm [34] for the pairing group operations and FLINT [35] for the finite field arithmetic in Zq, and the algorithm in [36] is used for evaluating discrete logs. Then we make a comparison among the SSSK-IPE scheme and the previous schemes in Table 1 on the performance. The experiments are performed on a personal computer with a 3.4G 8-core processor and 4GB RAM memory.


### 5.1. Microbenchmarks

We denoteN as the length of the binary vectors x→,y→ in the SSSK-IPE scheme. (We take binary vectors for the microbenchmarks, because they can make our search space small during decryption. TThis is similar to PHIPE in [25].). In the microbenchmarks (Tables 2 and 3), we evaluate the run times ofEncrypt,KeyGen, andDecrypt, respectively, and the ciphertext sizes |sky→| which change with the values of N. Both 80 bit security level and 112 bit security level in which pairing curves are MNT159 and MNT224, respectively, are considered, respectively. In the offline stage, the algorithmSetup computes the inverse of BT, naive computation complexity of which is O(n3), in order to generate B∗ from B. Note that we consider an amortized complexity model, in which a larger amount of computational work is invested in the offline phase for obtaining efficiency during the online phase. AlthoughEncrypt andKeyGen have the same number of group exponentiations over G1 and G2, respectively, there is a difference in the run times between them. This is because the artificial distinction of implementing asymmetric pairing groups. The run time ofDecrypt is more than that ofEncrypt orKeyGen, as a pairing operation consumes more time than a group exponentiation.Table 2
Performance of80 bit security level.
N Encrypt KeyGen Decrypt | s k y → | 10 1.5ms 10.6ms 60.6ms 2.2KB 30 3.7ms 23.8ms 130.7ms 4.8KB 50 7.0ms 39.7ms 202.4ms 7.3KB 100 15.8ms 73.5ms 374.7ms 13.8KB 300 92.9ms 257.1ms 1.1s 39.6KB 500 242.7ms 516.4ms 1.8s 65.3KB 750 506.4ms 939.4ms 2.6s 97.5KB 1000 891.3ms 1.5s 3.5s 129.8KBTable 3
Performance of112 bit security level.
N Encrypt KeyGen Decrypt | s k y → | 10 3.3ms 21.5ms 109.9ms 3.0KB 30 7.0ms 43.8ms 232.5ms 6.5KB 50 11.2ms 66.3ms 344.4ms 10.0KB 100 23.2ms 123.1ms 638.5ms 18.8KB 300 114.3ms 391.3ms 1.8s 54.0KB 500 269.9ms 728.8ms 2.9s 89.1KB 750 561.5ms 1.2s 4.4s 133.0KB 1000 964.6ms 1.9s 5.9s 177.0KB


### 5.2. Comparison with Previous Schemes

In Figures2 and 3, we compare our scheme with related works in Table 1. Of all the three schemes BJK15[16], TAO16 [18], and ZZL17 [19] in Table 1, BJK15 is selected as the representative of comparison, because the numbers of both group exponentiations and pairing operations of them are almost equal. Figure 2 shows that the run times of the schemes increase with N ranging from 50 to 300. This is due to the increase in vector length N which results in more group exponentiations and more pairing operations. Compared with BJK15 and DDM16, the SSSK-IPE scheme is 1.8-2.1 times faster and 3.6-5 times faster, respectively. Figure 3 shows that the ciphertext sizes of the schemes increase with vector length N. Compared with BJK15 and DDM16, the ciphertext size of the SSSK-IPE scheme is 1.2 - 2.1 times less and 2.5 - 4 times less, respectively.Figure 2
Run times relative to prior schemes varying with vector lengthN (80 bit security level).Figure 3
Ciphertext sizes relative to prior schemes varying with vector lengthN (80 bit security level).


## 5.1. Microbenchmarks

We denoteN as the length of the binary vectors x→,y→ in the SSSK-IPE scheme. (We take binary vectors for the microbenchmarks, because they can make our search space small during decryption. TThis is similar to PHIPE in [25].). In the microbenchmarks (Tables 2 and 3), we evaluate the run times ofEncrypt,KeyGen, andDecrypt, respectively, and the ciphertext sizes |sky→| which change with the values of N. Both 80 bit security level and 112 bit security level in which pairing curves are MNT159 and MNT224, respectively, are considered, respectively. In the offline stage, the algorithmSetup computes the inverse of BT, naive computation complexity of which is O(n3), in order to generate B∗ from B. Note that we consider an amortized complexity model, in which a larger amount of computational work is invested in the offline phase for obtaining efficiency during the online phase. AlthoughEncrypt andKeyGen have the same number of group exponentiations over G1 and G2, respectively, there is a difference in the run times between them. This is because the artificial distinction of implementing asymmetric pairing groups. The run time ofDecrypt is more than that ofEncrypt orKeyGen, as a pairing operation consumes more time than a group exponentiation.Table 2
Performance of80 bit security level.
N Encrypt KeyGen Decrypt | s k y → | 10 1.5ms 10.6ms 60.6ms 2.2KB 30 3.7ms 23.8ms 130.7ms 4.8KB 50 7.0ms 39.7ms 202.4ms 7.3KB 100 15.8ms 73.5ms 374.7ms 13.8KB 300 92.9ms 257.1ms 1.1s 39.6KB 500 242.7ms 516.4ms 1.8s 65.3KB 750 506.4ms 939.4ms 2.6s 97.5KB 1000 891.3ms 1.5s 3.5s 129.8KBTable 3
Performance of112 bit security level.
N Encrypt KeyGen Decrypt | s k y → | 10 3.3ms 21.5ms 109.9ms 3.0KB 30 7.0ms 43.8ms 232.5ms 6.5KB 50 11.2ms 66.3ms 344.4ms 10.0KB 100 23.2ms 123.1ms 638.5ms 18.8KB 300 114.3ms 391.3ms 1.8s 54.0KB 500 269.9ms 728.8ms 2.9s 89.1KB 750 561.5ms 1.2s 4.4s 133.0KB 1000 964.6ms 1.9s 5.9s 177.0KB


## 5.2. Comparison with Previous Schemes

In Figures2 and 3, we compare our scheme with related works in Table 1. Of all the three schemes BJK15[16], TAO16 [18], and ZZL17 [19] in Table 1, BJK15 is selected as the representative of comparison, because the numbers of both group exponentiations and pairing operations of them are almost equal. Figure 2 shows that the run times of the schemes increase with N ranging from 50 to 300. This is due to the increase in vector length N which results in more group exponentiations and more pairing operations. Compared with BJK15 and DDM16, the SSSK-IPE scheme is 1.8-2.1 times faster and 3.6-5 times faster, respectively. Figure 3 shows that the ciphertext sizes of the schemes increase with vector length N. Compared with BJK15 and DDM16, the ciphertext size of the SSSK-IPE scheme is 1.2 - 2.1 times less and 2.5 - 4 times less, respectively.Figure 2
Run times relative to prior schemes varying with vector lengthN (80 bit security level).Figure 3
Ciphertext sizes relative to prior schemes varying with vector lengthN (80 bit security level).


## 6. Applications

In this section, we show some direct applications of secret key IPE scheme.


### 6.1. Search on Encrypted Data

An interesting application of secret key IPE is to achieve encrypted data searching. Consider that a company uses a cloud to back up a large number of files. The company wishes to protect the privacy of these files by encrypting vectors representation of them prior to uploading them to the cloud. The company provides the master secret key for the secret key IPE scheme to an authorized employee who can search encrypted files in the cloud. Later on, the employee wants to search files corresponding to respective function. Firstly he transitions his query into a vector, computes the secret key of it, and sends the secret key to the cloud. The cloud then builds searches on disjunction queries, conjunction queries, and arbitrary CNF and DNF formulas and returns those files which satisfy queries, as shown in Figure4.Figure 4
Search on encrypted data.Specifically, to encrypt a keyword valuea in the finite field Zq, we can encode the value into a vector x→=(1,a,…,an-1). Assume a secret key is created based on a disjunction query “a1 OR a2 Or a3”. It can be considered as the univariate polynomial p(x)=(x-a1)(x-a2)(x-a3) which is expanded in standard form as p(x)=c0+c1x+c2x2+c3x3, where ci are the corresponding coefficients. The polynomial p(x) is encoded as a vector y→=(c0,c1,c2,c3,0,…,0). Note that 〈x→,y→〉=c0+c1a+c2a2+c3a3. If a=a1 or a=a2 or a=a3 such that p(x)=0, the secret key will match the ciphertext for the value a. However, we notice that expressiveness of IPE is less than general relations of FE. When IPE is used for such general relations, formulas must be expressed in CNF or DNF form, which can result in a superpolynomial blowup in size for arbitrary formulas.


### 6.2. Biometric Authentication

In [24, 25], it is shown that secret key IPE can be used for biometric authentication. Consider that a company wants to limit access to certain area in a building. It can employ a biometric-based authentication system, for example, fingerprint readers or iris scanners. The biometric scanner is connected to an external authentication server. The server holds the list of employee biometric signatures and their authorization policies. However, as password-based authentication system employs salted password hashing to protect each user's password, the server should store each employee's biometric information in the form of ciphertext. Due to the noisy nature of biometrics, authentication should be successful when the provided biometric is near to a user’s stored credential. It is achieved by computing the Hamming distance between them, which is the number of bits differing from each other. IPE can be employed to compute the Hamming distance between an encrypted n-bit vector c→=(c1,…,cn)∈{0,1}n and another binary vector d→=(d1,…,dn)∈{0,1}n embedded in the secret key. We can encode c→ and d→ as C→=(C1,…,C2n)∈{-1,1}2n and D→=(D1,…,D2n)∈{-1,1}2n, respectively, where C2i=D2i=1 and C2i+1=-(-1)ci and D2i+1=(-1)di for each i∈{1,…,n}. Then 〈C→,D→〉=∑i=1n(1-(-1)ci+di) is exactly twice the Hamming distance between c→ and d→.Suppose an employee attempts to authenticate using a fingerprint scanner, which stores the master secret key for a secret key IPE scheme. The scanner may accomplish authentication by the secret key IPE scheme, to read the fingerprint of the employee, compute the ciphertext of the fingerprint with the master secret key, and send it to the server. The server has stored the ciphertext of each user’s fingerprint under the secret key in advance. The server can compute the Hamming distance between the encrypted fingerprint and the stored fingerprint for the employee. If the result is small, authentication will succeed.


## 6.1. Search on Encrypted Data

An interesting application of secret key IPE is to achieve encrypted data searching. Consider that a company uses a cloud to back up a large number of files. The company wishes to protect the privacy of these files by encrypting vectors representation of them prior to uploading them to the cloud. The company provides the master secret key for the secret key IPE scheme to an authorized employee who can search encrypted files in the cloud. Later on, the employee wants to search files corresponding to respective function. Firstly he transitions his query into a vector, computes the secret key of it, and sends the secret key to the cloud. The cloud then builds searches on disjunction queries, conjunction queries, and arbitrary CNF and DNF formulas and returns those files which satisfy queries, as shown in Figure4.Figure 4
Search on encrypted data.Specifically, to encrypt a keyword valuea in the finite field Zq, we can encode the value into a vector x→=(1,a,…,an-1). Assume a secret key is created based on a disjunction query “a1 OR a2 Or a3”. It can be considered as the univariate polynomial p(x)=(x-a1)(x-a2)(x-a3) which is expanded in standard form as p(x)=c0+c1x+c2x2+c3x3, where ci are the corresponding coefficients. The polynomial p(x) is encoded as a vector y→=(c0,c1,c2,c3,0,…,0). Note that 〈x→,y→〉=c0+c1a+c2a2+c3a3. If a=a1 or a=a2 or a=a3 such that p(x)=0, the secret key will match the ciphertext for the value a. However, we notice that expressiveness of IPE is less than general relations of FE. When IPE is used for such general relations, formulas must be expressed in CNF or DNF form, which can result in a superpolynomial blowup in size for arbitrary formulas.


## 6.2. Biometric Authentication

In [24, 25], it is shown that secret key IPE can be used for biometric authentication. Consider that a company wants to limit access to certain area in a building. It can employ a biometric-based authentication system, for example, fingerprint readers or iris scanners. The biometric scanner is connected to an external authentication server. The server holds the list of employee biometric signatures and their authorization policies. However, as password-based authentication system employs salted password hashing to protect each user's password, the server should store each employee's biometric information in the form of ciphertext. Due to the noisy nature of biometrics, authentication should be successful when the provided biometric is near to a user’s stored credential. It is achieved by computing the Hamming distance between them, which is the number of bits differing from each other. IPE can be employed to compute the Hamming distance between an encrypted n-bit vector c→=(c1,…,cn)∈{0,1}n and another binary vector d→=(d1,…,dn)∈{0,1}n embedded in the secret key. We can encode c→ and d→ as C→=(C1,…,C2n)∈{-1,1}2n and D→=(D1,…,D2n)∈{-1,1}2n, respectively, where C2i=D2i=1 and C2i+1=-(-1)ci and D2i+1=(-1)di for each i∈{1,…,n}. Then 〈C→,D→〉=∑i=1n(1-(-1)ci+di) is exactly twice the Hamming distance between c→ and d→.Suppose an employee attempts to authenticate using a fingerprint scanner, which stores the master secret key for a secret key IPE scheme. The scanner may accomplish authentication by the secret key IPE scheme, to read the fingerprint of the employee, compute the ciphertext of the fingerprint with the master secret key, and send it to the server. The server has stored the ciphertext of each user’s fingerprint under the secret key in advance. The server can compute the Hamming distance between the encrypted fingerprint and the stored fingerprint for the employee. If the result is small, authentication will succeed.


## 7. Conclusion

In this work, we presented an efficient simulation-based inner product encryption scheme with a polynomial-size range in the standard model. Our scheme uses asymmetric bilinear pairing groups of prime order under the XDLIN assumption. Our work raises several interesting open problems on constructions of inner product encryption schemes. One open problem is to explore the simulation-based security notion in IPE with full-hiding security, considering confidentiality for functional keys and encrypted data in a completely symmetric manner, in the secret key setting [17]. Another open problem is to study how to achieve many-AD-SIM security for a multi-input inner product functional encryption scheme with a polynomial-size range [37].



---

*Source: 6561418-2018-08-13.xml*