1 Introduction
1.1 Background
Functional encryption (FE) is an advanced concept of encryption or a generalization of public-key encryption (PKE) and identity-based encryption (IBE). In FE systems, a receiver can decrypt a ciphertext using a secret-key corresponding to a parameter v if and only if v is suitably related to another parameter x specified for the ciphertext, or \(R(v,x)=1\) for some relation R (i.e., relation R holds for (v, x)). More generally, a secret key in FE is associated with a function f and a ciphertext of plaintext x is decrypted to f(x) by the secret key [9, 28].
The first flavor of functional encryption traces back to the work of Sahai and Waters [29], which was subsequently extended in [2, 3, 6, 10, 13, 14, 17, 18, 20, 25, 32]. In their concept called attribute-based encryption (ABE), for example, parameter v for a secret-key is an access control policy, and parameter x for a ciphertext is a set of attributes. Decryption requires attribute set x to satisfy policy v, i.e., relation \(R^\mathsf{ABE} (v,x) = 1\) iff x satisfies v. Identity-based broadcast encryption (IBBE) [1, 8, 12, 16, 30] and revocation (IBR) [21] schemes can also be thought of as functional encryption systems where a ciphertext is encrypted for a set of identities \(S = \{ ID_1, \ldots ,ID_n \}\) in IBBE (resp. IBR) systems, and to decrypt it by a secret-key associated with ID requires that \(ID \in S\) (resp. \(ID \not \in S\)), i.e., relation \(R^\mathsf{IBBE}(ID,S) = 1\) (resp. \(R^\mathsf{{IBR}}(ID,S)=1\)) iff \(ID \in S\) (resp. \(ID \not \in S\)).
Anzeige
Katz et al. [19] introduced a functional encryption scheme for zero inner products, zero inner product encryption (ZIPE) where a ciphertext encrypted with vector \(\vec {x}\) can be decrypted by any key associated with vector \(\vec {v}\) such that \(\vec {v}\cdot \vec {x} = 0\), i.e., relation \(R^\mathsf{ZIPE}(\vec {v},\vec {x})=1\) iff \(\vec {v}\cdot \vec {x} = 0\). Their scheme is selectively secure in the standard model and the ciphertext size is linear in the dimension of vectors, n, although it achieves an additional security property, attribute-hiding, in which \(\vec {x}\) is hidden from the ciphertext. As shown in [19], ZIPE provides functional encryption for a wide class of relations corresponding to equalities, polynomials and CNF/DNF formulae.
Attrapadung and Libert [4] proposed a ZIPE scheme as well as a non-zero IPE (NIPE) scheme, where NIPE relation \(R^\mathsf{NIPE}(\vec {v},\vec {x})=1\) iff \(\vec {v}\cdot \vec {x} \not = 0\). NIPE supports a wide class of relations corresponding to the complement of those for ZIPE. In their ZIPE and NIPE schemes, without retaining the attribute-hiding property, the ciphertext size reduces to a constant in n (the dimension of vectors, \(\vec {v}\) and \(\vec {x}\)), as long as the description of the vector is not considered a part of the ciphertext, which is a common assumption in the broadcast encryption/revocation applications. Hereafter in this paper, “constant” will be used in this sense. In addition, the number of pairing operations for decryption in [4] is constant. Their ZIPE system is adaptively secure in the standard model, but the NIPE scheme is not adaptively secure (co-selectively secure) in the standard model.
The ZIPE system [4] implies an adaptively secure identity-based broadcast encryption (IBBE) scheme with constant-size ciphertexts in the standard model, while previous IBBE schemes with constant-size ciphertexts were either only selective-ID secure [1, 8, 12] or secure in a non-standard model [16, 30]. Among IBBE systems with short ciphertexts (including selective-ID secure ones), the IBBE scheme [4] is the only one relying on standard assumptions, namely the DBDH and DLIN assumptions. The NIPE scheme [4] implies a co-selectively secure (not adaptively secure) identity-based revocation (IBR) system [21] with constant-size ciphertexts in the standard model. Lewko et al. [21] presented IBR systems with constant-size public and secret keys that are not adaptively secure. Hence, the following problems are still remained.
1.
No NIPE scheme with constant-size ciphertexts is adaptively secure in the standard model, and no IBR scheme with constant-size ciphertexts or constant-size secret-keys is adaptively secure in the standard model. No NIPE scheme with constant-size secret-keys has been presented.
2.
No ZIPE (or no IBBE) scheme with constant-size ciphertexts is adaptively (or selectively) secure under a single standard assumption in the standard model. No ZIPE scheme with constant-size secret-keys has been presented.
1.2 Our result
We address the problems. Note that all of our results are obtained in the standard model.The number of pairing operations for decryption is constant in all the proposed schemes. We summarize a comparison of our results with those of [4] in Table 1 in Sect. 11 (see the items of ‘Security’, ‘Assump.’, ‘CT Size’ and ‘SK Size’ in Table 1, for the features discussed in Sects. 1.1 and 1.2).
1.
This paper presents the first adaptively secure NIPE scheme that has constant-size ciphertexts or constant-size secret-keys (Sects. 6 and 7). The security assumption is a standard one, the decisional linear (DLIN) assumption. This implies the first adaptively secure IBR scheme with constant-size ciphertexts or constant-size secret-keys.
2.
This paper also presents the first ZIPE scheme that has constant-size ciphertexts or constant-size secret-keys and is adaptively secure solely under a single standard assumption, the DLIN assumption (Sects. 8 and 9). This implies the first IBBE scheme with constant-size ciphertexts that is adaptively secure solely under a single standard assumption.
3.
We present two extensions of the proposed ZIPE schemes. One is a fully-attribute-hiding ZIPE scheme with constant-size secret-keys (Sect. 10). It is obtained by applying the technique of the fully-attribute-hiding ZIPE scheme in [27] to the proposed ZIPE scheme with constant-size secret-keys in Sect. 9, while the ZIPE scheme in Sect. 9 is weakly-attribute-hiding. The other extension is a hierarchical ZIPE scheme with constant-size ciphertexts (Sect. 12). These schemes are adaptively secure under the DLIN assumption.
Anzeige
1.3 Related works
Adaptively secure and attribute-hiding ZIPE scheme under the DLIN assumption has been presented [25], but the ciphertext-size is linear in n (not constant), while our ZIPE scheme has constant-size ciphertexts and is adaptively secure but not attribute-hiding.
After the publication of the preliminary version [26] of this paper, Chen–Wee [11] constructed a constant-size ciphertext and adaptively secure spatial encryption scheme, which includes ZIPE as a special case. Although both of our ZIPE scheme and Chen–Wee’s scheme have constant-size ciphertexts, the concrete size of a ciphertext in their scheme is shorter than ours.
1.4 Key techniques
All of the proposed schemes in this paper are constructed on dual system encryption [22, 31] and dual pairing vector spaces (DPVS) [20, 24, 25]. See Sect. 1.5 for some notations in this section. In DPVS, a pair of dual (or orthonormal) bases, \(\mathbb {B}\) and \(\mathbb {B}^*\), are randomly generated using a fully random linear transformation \(X \mathop {\leftarrow }\limits ^{\ \mathsf{U}}GL(N,\mathbb {F}_q)\) (N: dimension of \(\mathsf{span}\langle \mathbb {B}\rangle \) and \(\mathsf{span}\langle \mathbb {B}^* \rangle \)) such that \(\mathbb {B}\) and \(\mathbb {B}^*\) are transformed from canonical basis \(\mathbb {A}\) by X and \((X^{-1})^{\mathrm {T}}\), respectively (see Sect. 2 and [20, 24, 25]). In a typical application of DPVS to cryptography, a portion of \(\mathbb {B}\) (say \(\hat{\mathbb {B}}\)) is used as a public key and the corresponding portion of \(\mathbb {B}^*\) (say \(\hat{\mathbb {B}}^*\)) is used as a secret key or trapdoor.
In this paper, we develop a novel technique on DPVS, where we employ a special form of random linear transformation \(X \in GL(N,\mathbb {F}_q)\), or \(X \in \mathcal{L}(4,n, \mathbb {F}_q)\) of Eq. (3) in Sect. 6.2, in place of fully random linear transformation \(X \mathop {\leftarrow }\limits ^{\ \mathsf{U}}GL(N,\mathbb {F}_q)\). This form of X provides us a framework to achieve short ciphertexts or short secret-keys as well as a small number of pairing operations in decryption. It, however, is a challenging task to find such a special form of X like Eq. (3) that meet the several requirements for the dual system encryption method to prove the adaptive security of ZIPE and NIPE schemes under the DLIN assumption. Such requirements are given hereafter. To reduce the security of our schemes, especially Problems 1 and 2 in this paper, to the DLIN assumption, the form of X should be consistent with the distribution of the DLIN problem. The form of X should be sparse enough to achieve short ciphertexts or secret-keys. We should also have a special pairwise independence lemma, Lemma 6 in Sect. 6.4, that is due to the special form of X, where linear random transformations U and Z are more restricted (or specific) than those of previous results, e.g., [25], with fully random X. See Sect. 6.1 for more details.
1.5 Notations
When A is a random variable or distribution, \(y \mathop {\leftarrow }\limits ^{\ \mathsf{R}}A\) denotes that y is randomly selected from A according to its distribution. When A is a set, \(y \mathop {\leftarrow }\limits ^{\ \mathsf{U}}A\) denotes that y is uniformly selected from A. A vector symbol denotes a vector representation over \(\mathbb {F}_q\), e.g., \(\vec {x}\) denotes \((x_{1},\ldots ,x_{n}) \in \mathbb {F}_q^{\, n}\). For two vectors \(\vec {x} = (x_{1},\ldots ,x_{n})\) and \(\vec {v} = (v_{1},\ldots ,v_{n})\), \(\vec {x} \cdot \vec {v}\) denotes the inner-product \(\sum _{i=1}^{n} x_i v_i\). The vector \(\vec {0}\) is used to denote the zero vector in \(\mathbb {F}_q^{\, n}\) for any n. \(X^{\mathrm T}\) denotes the transpose of matrix X. \(I_\ell \) denotes the \(\ell \times \ell \) identity matrix. A boldface letter denotes an element of vector space \(\mathbb {V}\), e.g., \(\varvec{x}\in \mathbb {V}\). When \(\varvec{b}_i \in \mathbb {V}\) (\(i=1,\ldots ,\ell \)), \(\mathsf{span}\langle \varvec{b}_1, \ldots , \varvec{b}_{\ell } \rangle \subseteq \mathbb {V}\) (resp. \(\mathsf{span}\langle \vec {x}_1, \ldots , \vec {x}_{\ell } \rangle \)) denotes the subspace generated by \(\varvec{b}_1, \ldots , \varvec{b}_{\ell }\) (resp. \(\vec {x}_1, \ldots , \vec {x}_{\ell }\)). For bases \({\mathbb {B}} :{=}(\varvec{b}_1,\ldots ,\varvec{b}_N)\) and \({\mathbb {B}}^* :{=}(\varvec{b}^*_1,\ldots ,\varvec{b}^*_N)\), \((x_1, \ldots , x_{N})_{\mathbb {B}} :{=}\sum _{i=1}^N x_i \varvec{b}_i\) and \((y_1, \ldots , y_{N})_{{\mathbb {B}}^*} :{=}\sum _{i=1}^N y_i \varvec{b}^*_i\). An n-dimensional vector \(\vec {e}_{j}\) denotes the canonical basis vector \((\overbrace{0\cdots 0}^{j-1},1,\overbrace{0\cdots 0}^{n-j}) \in \mathbb {F}_q^{\,n}\) for \(j=1,\ldots ,n\). \(GL(n,\mathbb {F}_q)\) denotes the general linear group of degree n over \(\mathbb {F}_q\). For a linear subspace \(V \subset \mathbb {F}_q^{\,n}\), \(V^{\bot }\) denotes the orthogonal complement, i.e., \(V^{\bot } :{=}\{ \vec {w} \in \mathbb {F}_q^{\,n} | \vec {w} \cdot \vec {v} = 0 \ \mathrm {for \ all} \ \vec {v} \in V \}\).
2 Dual pairing vector spaces by direct product of symmetric pairing groups
In this paper, for simplicity of description, we will present the proposed schemes on the symmetric version of dual pairing vector spaces (DPVS) [23, 24] constructed using symmetric bilinear pairing groups given in Definition 1. Owing to the abstraction of DPVS, the presentation and the security proof of the proposed schemes are essentially the same as those on the asymmetric version of DPVS, \((q, \mathbb {V}, \mathbb {V}^*, \mathbb {G}_T, {\mathbb {A}}, {\mathbb {A}}^*, e)\), for which see Appendix “Proofs of Lemmas 4‐12 in Sect. 6” in the full version of [25]. The symmetric version is a specific (self-dual) case of the asymmetric version, where \(\mathbb {V}= \mathbb {V}^*\) and \({\mathbb {A}}= {\mathbb {A}}^*\).
Definition 1
(Symmetric bilinear pairing groups) \((q,\mathbb {G},\mathbb {G}_T,G,e)\) are a tuple of a prime q, cyclic additive group \(\mathbb {G}\) and multiplicative group \(\mathbb {G}_T\) of order q, \(G \ne 0 \in \mathbb {G}\), and a polynomial-time computable nondegenerate bilinear pairing \(e: \mathbb {G}\times \mathbb {G}\rightarrow \mathbb {G}_T\) i.e., \(e(sG ,tG) = e(G,G)^{st}\) and \(e(G,G) \ne 1\).
Let \(\mathcal G_\mathsf{bpg}\) be an algorithm that takes input \(1^\lambda \) and outputs a description of bilinear pairing groups \((q,\mathbb {G},\mathbb {G}_T,\)
G, e) with security parameter \(\lambda \).
Definition 2
(Dual pairing vector spaces (DPVS)) \((q, \mathbb {V}, \mathbb {G}_T, {\mathbb {A}}, e)\) by a direct product of symmetric pairing groups \((q,\mathbb {G},\mathbb {G}_T,G,e)\) are a tuple of prime q, \({N}\)-dimensional vector space \(\mathbb {V}:{=}\overbrace{\mathbb {G}\times \cdots \times \mathbb {G}}^{{N}}\) over \(\mathbb {F}_q\), cyclic group \(\mathbb {G}_T\) of order q, canonical basis \({\mathbb {A}}:{=}(\varvec{a}_1,\ldots ,\varvec{a}_{N})\) of \(\mathbb {V}\), where \(\varvec{a}_i :{=}(\overbrace{0,\ldots ,0}^{i-1},G,\)
\( \overbrace{0,\ldots ,0}^{{N}-i})\), and pairing \(e : \mathbb {V}\times \mathbb {V}\rightarrow \mathbb {G}_T\). The pairing is defined by \(e(\varvec{x},\varvec{y}) :{=}\prod _{i=1}^N e(G_i,H_i) \in \mathbb {G}_T\) where \(\varvec{x}:{=}(G_1,\ldots ,\)
\(G_N) \in \mathbb {V}\) and \(\varvec{y}:{=}(H_1,\ldots ,H_N) \in \mathbb {V}\). This is nondegenerate bilinear i.e., \(e(s \varvec{x},t \varvec{y}) = e(\varvec{x},\varvec{y})^{st}\) and if \(e(\varvec{x},\varvec{y})=1\) for all \(\varvec{y}\in \mathbb {V}\), then \(\varvec{x}= \varvec{0}\). For all i and j, \(e(\varvec{a}_i, \varvec{a}_j) = e(G,G)^{\delta _{i,j}}\) where \(\delta _{i,j} = 1\) if \(i=j\), and 0 otherwise, and \(e(G,G) \ne 1 \in \mathbb {G}_T\).
DPVS also has linear transformations \(\phi _{i,j}\) on \(\mathbb {V}\) s.t. \(\phi _{i,j}(\varvec{a}_j) = \varvec{a}_i\) and \(\phi _{i,j}(\varvec{a}_k)\)
\( = \varvec{0}\) if \(k \ne j\), which can be easily achieved by \(\phi _{i,j}(\varvec{x}) :{=}(\overbrace{0,\ldots ,0}^{i-1},G_j, \overbrace{0,\ldots ,0}^{N-i})\) where \(\varvec{x}:{=}(G_1,\ldots ,G_N)\). We call \(\phi _{i,j}\) “canonical maps”.
DPVS generation algorithm \({{\mathcal{G}_\mathsf{dpvs}}}\) takes input \(1^\lambda \) (\(\lambda \in \mathbb {N}\)) and \({N}\in \mathbb {N}\), and outputs a description of \(\mathsf{param}_{\mathbb {V}} :{=}(q,\mathbb {V},\mathbb {G}_T,{\mathbb {A}}, e)\) with security parameter \(\lambda \) and \({N}\)-dimensional \(\mathbb {V}\). It can be constructed by using \(\mathcal G_\mathsf{bpg}\).
3 Definitions of zero and non-zero inner-product encryption (ZIPE/NIPE)
This section defines zero and non-zero inner-product encryption (ZIPE/NIPE) and their security. The relations \(R^\mathsf{ZIPE}\) of ZIPE and \(R^\mathsf{NIPE}\) of NIPE are defined over vectors \(\vec {x} \in {\mathbb {F}}_q^{\, n} \setminus \{ \vec {0} \}\) and \(\vec {v} \in {\mathbb {F}}_q^{\, n} \setminus \{ \vec {0} \}\), where \(R^\mathsf{ZIPE}(\vec {v}, \vec {x}) :{=}1\) iff \(\vec {x} \cdot \vec {v} = 0\), and \(R^\mathsf{NIPE}(\vec {v}, \vec {x}) :{=}1\) iff \(\vec {x} \cdot \vec {v} \ne 0\), respectively.
Definition 3
(Zero and non-zero inner-product encryption: ZIPE/NIPE) Let a relation R be \(R^\mathsf{ZIPE}\) or \(R^\mathsf{NIPE}\). A zero (resp. non-zero) inner-product encryption scheme consists of four algorithms with \(R :{=}R^\mathsf{ZIPE}\) (resp. R
\(:{=}R^\mathsf{NIPE}\)).
\(\mathsf{Setup}\)
This is a randomized algorithm that takes as input security parameter. It outputs public parameters pk and master secret key sk.
\(\mathsf{KeyGen}\)
This is a randomized algorithm that takes as input vector \(\vec {v}\), pk and sk. It outputs a decryption key \(\mathsf{sk}_{\vec {v}}\).
\(\mathsf{Enc}\)
This is a randomized algorithm that takes as input message m, a vector, \(\vec {x}\), and public parameters pk. It outputs a ciphertext \(\mathsf{ct}_{\vec {x}}\).
\(\mathsf{Dec}\)
This takes as input ciphertext \(\mathsf{ct}_{\vec {x}}\) that was encrypted under a vector \(\vec {x}\), decryption key \(\mathsf{sk}_{\vec {v}}\) for vector \(\vec {v}\), and public parameters pk. It outputs either plaintext m or the distinguished symbol \(\bot \).
A ZIPE (or NIPE) scheme should have the following correctness property: for all \((\mathsf{pk}, \mathsf{sk}) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Setup}(1^\lambda )\), all vectors \(\vec {v}\), all decryption keys \(\mathsf{sk}_{\vec {v}} \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, \vec {v})\), all messages m, all vectors \(\vec {x}\), all ciphertexts \(\mathsf{ct}_{\vec {x}} \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Enc}(\mathsf{pk}, m, \vec {x})\), it holds that \(m = \mathsf{Dec}(\mathsf{pk}, \mathsf{sk}_{\vec {v}}, \mathsf{ct}_{\vec {x}})\) with overwhelming probability, if \(R(\vec {v}, \vec {x})=1\).
Definition 4
(Adaptively payload-hiding security) The model for proving the adaptively payload-hiding security of ZIPE (or NIPE) under chosen plaintext attacks is given hereafter.
Setup
The challenger runs the setup algorithm, \((\mathsf{pk}, \mathsf{sk})\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Setup}(1^\lambda )\), and gives public parameters \(\mathsf{pk}\) to the adversary.
Phase 1
The adversary is allowed to adaptively issue a polynomial number of queries, \(\vec {v}\), to the challenger or oracle \(\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, \cdot )\) for private keys, \(\mathsf{sk}_{\vec {v}}\), associated with \(\vec {v}\).
Challenge
The adversary submits two messages, \(m^{(0)}\) and \(m^{(1)}\), and a vector, \(\vec {x}\), provided that no \(\vec {v}\) queried to the challenger in Phase 1 satisfies \(R(\vec {v}, \vec {x})=1\). The challenger flips a coin \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\), and computes \(\mathsf{ct}_{\vec {x}}^{(b)}\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Enc}(\mathsf{pk},m^{(b)},\vec {x})\). It gives \(\mathsf{ct}_{\vec {x}}^{(b)}\) to the adversary.
Phase 2
The adversary is allowed to adaptively issue a polynomial number of queries, \(\vec {v}\), to the challenger or oracle \(\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, \cdot )\) for private keys, \(\mathsf{sk}_{\vec {v}}\), associated with \(\vec {v}\), provided that \(R(\vec {v}, \vec {x}) \ne 1\).
Guess
The adversary outputs a guess \(b'\) of b.
The advantage of adversary \(\mathcal{A}\) in the above game, \(\mathsf{Adv}^\mathsf{ZIPE,PH}_\mathcal{A}(\lambda )\) (or \(\mathsf{Adv}^\mathsf{NIPE,PH}_\mathcal{A}\)
\((\lambda )\)), is defined by \(\Pr [b'=b]-1/2\) for any security parameter \(\lambda \). A ZIPE (or NIPE) scheme is adaptively payload-hiding secure if all polynomial time adversaries have at most a negligible advantage in the game.
Remark 1
We have two remarks on variants of the above security notion.
-
In a weaker security notion, selectively payload-hiding, the adversary is required to declare the challenge vector \(\vec {x}\) at the beginning of the game (before Setup). Similarly, the weaker (selective) security variants can be defined in place of the two (adaptive) security notions in Definitions 5 and 6.
-
The above security notion, which is secure against chosen-plaintext attacks (CPA), can be easily extended to the security notion against chosen-ciphertext attacks (CCA) by allowing an adversary to give decryption queries in Phases 1 and 2. Since there is a standard (efficient) methodology to transform a CPA-secure FE (including NIPE/ZIPE) scheme to a CCA-secure FE scheme by using the Canetti–Halevi–Katz (CHK) transformation or the Boneh–Katz (BK) transformation [7] as is given in [25], we only present CPA-secure NIPE/ZIPE schemes in this paper.
Definition 5
(Adaptively weakly-attribute-hiding security) The model for proving the adaptively weakly-attribute-hiding security of ZIPE under chosen plaintext attacks is obtained from the above game by replacing Challenge and Phase 2 steps by the following:
Challenge
The adversary submits two messages, \((m^{(0)},m^{(1)})\), and two vectors, \((\vec {x}^{(0)}, \vec {x}^{(1)})\), provided that no \(\vec {v}\) queried to the challenger in Phase 1 satisfies \(R(\vec {v}, \vec {x}^{(0)})=1\) or \(R(\vec {v}, \vec {x}^{(1)})=1\). The challenger flips a coin \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\), and computes \(\mathsf{ct}_{\vec {x}^{(b)}}\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Enc}(\mathsf{pk},m^{(b)},\vec {x}^{(b)})\). It gives \(\mathsf{ct}_{\vec {x}^{(b)}}\) to the adversary.
Phase 2
The adversary is allowed to adaptively issue a polynomial number of queries, \(\vec {v}\), to the challenger or oracle \(\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, \cdot )\) for private keys, \(\mathsf{sk}_{\vec {v}}\), associated with \(\vec {v}\), provided that \(R(\vec {v}, \vec {x}^{(0)}) \ne 1\) and \(R(\vec {v}, \vec {x}^{(1)}) \ne 1\).
The advantage of adversary \(\mathcal{A}\) in the above game, \(\mathsf{Adv}^\mathsf{ZIPE,wAH}_\mathcal{A}(\lambda )\), is defined by \(\Pr [b'=b]-1/2\) for any security parameter \(\lambda \). A ZIPE scheme is adaptively weakly-attribute-hiding secure if all polynomial time adversaries have at most a negligible advantage in the game.
Informally, in adaptively fully-attribute-hiding security game, adversary is allowed to issue both types of key queries, \(R(\vec {v}, \vec {x}^{(b)}) = 0\) and \(R(\vec {v}, \vec {x}^{(b)}) = 1\), in a single security game. It gives a strong security than Definition 5 and is given in the following Definition 6.
Definition 6
(Adaptively fully-attribute-hiding security) The model for proving the adaptively fully-attribute-hiding security of ZIPE under chosen plaintext attacks is obtained from the above game by replacing Challenge and Phase 2 steps by the following:
The challenger flips a coin \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\), and computes \(\mathsf{ct}_{\vec {x}^{(b)}}\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathsf{Enc}(\mathsf{pk},m^{(b)},\vec {x}^{(b)})\). It gives \(\mathsf{ct}_{\vec {x}^{(b)}}\) to the adversary.
The advantage of adversary \(\mathcal{A}\) in the above game is defined as \(\mathsf{Adv}^\mathsf{ZIPE, AH}_{\mathcal{A}}(\lambda ) :{=}\mathsf{Pr}[ \mathcal{A} \ \mathrm {wins} \ ] - 1/2\) for any security parameter \(\lambda \). An IPE scheme is adaptively fully-attribute-hiding (AH) (against chosen plaintext attacks) if all probabilistic polynomial-time adversaries \(\mathcal{A}\) have at most negligible advantage in the above game.
Challenge
The adversary submits challenge attribute vector \((\vec {x}^{(0)},\vec {x}^{(1)})\) and challenge plaintexts \((m^{(0)}, m^{(1)})\), subject to the following restrictions:
-
\(\vec {v}\cdot \vec {x}^{(0)} \not =0\) and \(\vec {v}\cdot \vec {x}^{(1)} \not =0\) for all the key queried predicate vectors, \(\vec {v}\).
-
Two challenge plaintexts are equal, i.e., \(m^{(0)} = m^{(1)}\), and any key query \(\vec {v}\) satisfies \(R(\vec {v}, \vec {x}^{(0)}) = R(\vec {v},\vec {x}^{(1)})\), i.e., one of the following conditions.
-
\(\vec {v}\cdot \vec {x}^{(0)} =0\) and \(\vec {v}\cdot \vec {x}^{(1)} =0\),
-
\(\vec {v}\cdot \vec {x}^{(0)} \not =0\) and \(\vec {v}\cdot \vec {x}^{(1)} \not =0\),
-
Phase 2
The adversary is allowed to adaptively issue a polynomial number of queries, \(\vec {v}\), to the challenger or oracle \(\mathsf{KeyGen}(\mathsf{pk}, \mathsf{sk}, \cdot )\) for private keys, \(\mathsf{sk}_{\vec {v}}\), associated with \(\vec {v}\), subject to the restriction given in the challenge step.
For each run of the game, the variable \({s}\) is defined as \({s}:{=}0\) if \(m^{(0)} \ne m^{(1)}\) for challenge plaintexts \(m^{(0)}\) and \(m^{(1)}\), and \({s}:{=}1\) otherwise.
4 Decisional linear (DLIN) assumption
Definition 7
The DLIN problem is to guess \(\beta \in \{ 0,1 \}\), given \(( \mathsf{param}_{\mathbb {G}}, {G},{\xi }{G},{\kappa }{G},\delta {\xi }{G}, \sigma {\kappa }{G}, Y_\beta )\)
\( \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{\mathcal{G}}_{\beta }^\mathsf{DLIN}(1^\lambda )\), where \( {\mathcal{G}}_{\beta }^\mathsf{DLIN}(1^\lambda ): \mathsf{param}_{\mathbb {G}} :{=}(q,\mathbb {G},\mathbb {G}_T,{G},e)\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathcal{G}_\mathsf{bpg}(1^\lambda ), \ {\kappa }, \delta , {\xi },\sigma \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ Y_0 :{=}(\delta + \sigma ) {G}, \ Y_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {G}, \ \mathrm {return} \ ( \mathsf{param}_{\mathbb {G}}, {G},{\xi }{G}, {\kappa }{G},\)
\( \delta {\xi }{G}, \sigma {\kappa }{G}, Y_\beta ), \) for \(\beta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}\). For a probabilistic machine \(\mathcal{E}\), we define the advantage of \(\mathcal{E}\) for the DLIN problem as: \(\mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}}(\lambda ) :{=}\ \left| \mathsf{Pr}\left[ \mathcal{E}(1^\lambda ,\varrho ) \rightarrow 1 \left| \varrho \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}}_0^\mathsf{DLIN}}(1^\lambda ) \right. \right] - \mathsf{Pr}\left[ \mathcal{E}(1^\lambda ,\varrho ) \rightarrow 1\right. \right. \left. \left. \left| \varrho \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}}_1^\mathsf{DLIN}}(1^\lambda ) \right. \right] \right| .\) The DLIN assumption is: For any probabilistic polynomial-time adversary \(\mathcal{E}\), the advantage \(\mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}}(\lambda )\) is negligible in \(\lambda \).
5 Special matrix subgroups
Lemmas 1–3 are key lemmas for the security proof for our (H)IPE schemes. For a positive integer n, let
$$\begin{aligned}&\mathcal{H}(n, \mathbb {F}_q) :{=}\left\{ \left. \left( \begin{array}{cccc} u &{} &{} &{} u'_{1} \\ &{} \ddots &{} &{} \vdots \\ &{} &{} u &{} u'_{n-1} \\ &{} &{} &{} u'_{n} \end{array} \right) \right| \begin{array}{l} u, u'_l \in \mathbb {F}_q\ \mathrm {for} \ l=1,\ldots ,n, \\ \mathrm {a \ blank \ element \ in \ the \ matrix} \\ \mathrm {denotes} \ 0 \in \mathbb {F}_q\end{array} \right\} , \end{aligned}$$
(1)
$$\begin{aligned}&\widetilde{\mathcal{H}}(n, \mathbb {F}_q) :{=}\left\{ \left. \left( \begin{array}{cccc} u'_1 &{} &{} &{} \\ u'_2 &{} u &{} &{} \\ \vdots &{} &{} \ddots &{} \\ u'_{n} &{} &{} &{} u \end{array} \right) \right| \begin{array}{l} u, u'_l \in \mathbb {F}_q\ \mathrm {for} \ l=1,\ldots ,n, \\ \mathrm {a \ blank \ element \ in \ the \ matrix} \\ \mathrm {denotes} \ 0 \in \mathbb {F}_q\end{array} \right\} . \end{aligned}$$
(2)
Lemma 1
\(\mathcal{H}(n,\mathbb {F}_q) \ \cap \ GL(n,\mathbb {F}_q)\) and \(\widetilde{\mathcal{H}}(n,\mathbb {F}_q) \ \cap \ GL(n,\mathbb {F}_q)\) are subgroups of \(GL(n,\mathbb {F}_q)\).
Lemma 1 is directly verified from the definition of groups. \(\square \)
For positive integers w and n, let
$$\begin{aligned}&\mathcal{L}(w, n, \mathbb {F}_q) :{=}\nonumber \\&\ \ \ \left\{ \left. X :{=}\left( \begin{array}{cccccccc} X_{1,1} &{} \cdots &{} X_{1,w} \\ \vdots &{} &{} \vdots \\ X_{w,1} &{} \cdots &{} X_{w,w} \end{array} \right) \right| X_{i,j} :{=}\left( \begin{array}{cccc} \mu _{i,j} &{} &{} &{} \mu '_{i,j,1} \\ &{} \ddots &{} &{} \vdots \\ &{} &{} \mu _{i,j} &{} \mu '_{i,j,n-1} \\ &{} &{} &{} \mu '_{i,j,n} \end{array} \right) \begin{array}{l} \in \mathcal{H}(n, \mathbb {F}_q) \\ \ \mathrm {for} \ i,j= \\ \ \ 1,\ldots ,w\end{array} \right\} \nonumber \\&\ \ \ \ \ \ \ \ \ \bigcap \ GL(wn, \mathbb {F}_q), \end{aligned}$$
(3)
$$\begin{aligned}&\widetilde{\mathcal{L}}(w, n, \mathbb {F}_q) :{=}\nonumber \\&\ \ \ \left\{ \left. X :{=}\left( \begin{array}{cccccccc} X_{1,1} &{} \cdots &{} X_{1,w} \\ \vdots &{} &{} \vdots \\ X_{w,1} &{} \cdots &{} X_{w,w} \end{array} \right) \right| X_{i,j} :{=}\left( \begin{array}{cccc} \mu '_{i,j,1} &{} &{} &{} \\ \mu '_{i,j,2} &{} \mu _{i,j} &{} &{} \\ \vdots &{} &{} \ddots &{} \\ \mu '_{i,j,n} &{} &{} &{} \mu _{i,j} \end{array} \right) \begin{array}{l} \in \widetilde{\mathcal{H}}(n, \mathbb {F}_q) \\ \ \mathrm {for} \ i,j= \\ \ \ 1,\ldots ,w\end{array} \right\} \nonumber \\&\ \ \ \ \ \ \ \ \ \bigcap \ GL(wn, \mathbb {F}_q). \end{aligned}$$
(4)
Lemma 2
\(\mathcal{L}(w,n,\mathbb {F}_q)\) and \(\widetilde{\mathcal{L}}(w,n,\mathbb {F}_q)\) are subgroups of \(GL(wn, \mathbb {F}_q)\).
$$\begin{aligned}&\mathcal{L}^{+}(w, n, \mathbb {F}_q) :{=}\left\{ \left. X :{=}\left( \begin{array}{cccccccc} \chi _{0,0} &{} \chi _{0,1} \vec {e}_n &{} \cdots &{} \chi _{0,w} \vec {e}_n \\ \vec {\chi }^{\mathrm {T}}_{1,0} &{} X_{1,1} &{} \cdots &{} X_{1,w} \\ \vdots &{} \vdots &{} &{} \vdots \\ \vec {\chi }^{\mathrm {T}}_{w,0} &{} X_{w,1} &{} \cdots &{} X_{w,w} \end{array} \right) \right| \begin{array}{l} X_{i,j} \in \mathcal{H}(n, \mathbb {F}_q), \\ \vec {\chi }_{i,0} :{=}(\chi _{i,0,l})_{l=1,\ldots ,n} \in \mathbb {F}_q^n, \\ \chi _{0,0}, \chi _{0,j} \in \mathbb {F}_q\\ \ \mathrm {for} \ i,j=1,\ldots ,w\end{array} \right\} \nonumber \\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \bigcap \ GL(wn + 1, \mathbb {F}_q). \end{aligned}$$
(5)
Lemma 3
\(\mathcal{L}^{+}(w,n,\mathbb {F}_q)\) is a subgroup of \(GL(wn+1,\mathbb {F}_q)\).
6 NIPE scheme with constant-size ciphertexts
6.1 Key ideas in constructing the proposed NIPE scheme
In this section, we will explain the key ideas of constructing and proving the security of the proposed NIPE scheme.
First, we will show how short ciphertexts and efficient decryption can be achieved in our scheme. Here, we will use a simplified (or toy) version of the proposed NIPE scheme, for which the security is no more ensured in the standard model under the DLIN assumption.
A ciphertext in the simplified NIPE scheme consists of two vector elements, \((\varvec{c}_0,\varvec{c}_1) \in \mathbb {G}^5 \times \mathbb {G}^n\), and \(c_3 \in \mathbb {G}_T\). A secret-key consists of two vector elements, \((\varvec{k}^*_0,\varvec{k}^*_1) \in \mathbb {G}^5 \times \mathbb {G}^n\). Therefore, to achieve constant-size ciphertexts, we have to compress \(\varvec{c}_1 \in \mathbb {G}^n\) to a constant size in n. We now employ a special form of basis generation matrix, \(X :{=}\left( \begin{array}{cccc} \mu &{} &{} &{} \mu '_{1} \\ &{} \ddots &{} &{} \vdots \\ &{} &{} \mu &{} \mu '_{n-1} \\ &{} &{} &{} \mu '_{n} \end{array} \right) \in \mathcal{H}(n, \mathbb {F}_q)\) of Eq. (1) in Sect. 6.2, where \(\mu ,\mu '_1,\ldots ,\mu '_n \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and a blank in the matrix denotes \(0 \in \mathbb {F}_q\). The system parameter or DPVS public basis is \({{\mathbb {B}}:{=}} \left( \begin{array}{c} \varvec{b}_1 \\ \vdots \\ \\ \varvec{b}_n \end{array} \right) :{=}\left( \begin{array}{cccc} \mu G &{} &{} &{} \mu '_{1} G \\ &{} \ddots &{} &{} \vdots \\ &{} &{} \mu G &{} \mu '_{n-1} G \\ &{} &{} &{} \mu '_{n} G \end{array} \right) \). Let a ciphertext associated with \(\vec {x} :{=}(x_1,\ldots ,x_n)\) be \(\varvec{c}_1 :{=}(\omega \vec {x})_{{\mathbb {B}}} = \omega (x_1 \varvec{b}_1 + \cdots + x_n \varvec{b}_n) = (x_1 \omega \mu G, \ldots , x_{n-1} \omega \mu G, \omega (\sum _{i=1}^n x_i \mu '_i) G)\), where \(\omega \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\). Then, \(\varvec{c}_1\) can be compressed to only two group elements \((C_1 :{=}\omega \mu G,\ C_2 :{=}\omega (\sum _{i=1}^n x_i \mu '_i) G)\) as well as \(\vec {x}\), since \(\varvec{c}_1\) can be obtained by \((x_1C_1, \ldots ,\)
\(x_{n-1}C_1, C_2)\) (note that \(x_i C_1 = x_i \omega \mu G\) for \(i=1,\ldots ,n-1\)). That is, a ciphertext (excluding \(\vec {x}\)) can be just two group elements, or the size is constant in n.
Let \({\mathbb {B}}^* :{=}(\varvec{b}^*_i)\) be the dual orthonormal basis of \({\mathbb {B}}:{=}(\varvec{b}_i)\), and \({\mathbb {B}}^*\) be the master secret key in the simplified NIPE scheme. We specify \((\varvec{c}_0, \varvec{k}^*_0, c_3)\) such that \(e(\varvec{c}_0, \varvec{k}^*_0) = g_T^\zeta \cdot g_T^{\omega \delta }\) and \(c_3 :{=}g_T^\zeta m \in \mathbb {G}_T\). We also set a secret-key for \(\vec {v}\) as \(\varvec{k}^*_1 :{=}(\delta \vec {v})_{{\mathbb {B}}^*} = \delta (v_1 \varvec{b}^*_1 + \cdots + v_n \varvec{b}^*_n)\). From the dual orthonormality of \({\mathbb {B}}\) and \({\mathbb {B}}^*\), it then holds that \(e(\varvec{c}_1, \varvec{k}^*_1) = g_T^{\omega \delta (\vec {x} \cdot \vec {v})}\). Hence, a decryptor can compute \(g_T^{\omega \delta }\) if and only if \(\vec {x} \cdot \vec {v} \ne 0\), i.e., can obtain plaintext m by \(c_3 \cdot e(\varvec{c}_0, \varvec{k}^*_0)^{-1} \cdot e(\varvec{c}_1, \varvec{k}^*_1)^{(\vec {x} \cdot \vec {v})^{-1}}\). Since \(\varvec{c}_1\) is expressed as \((x_1 C_1, \ldots , x_{n-1} C_1, C_2) \in \mathbb {G}^n\) and \(\varvec{k}^*_1\) is parsed as a n-tuple \((K_1,\ldots ,K_n) \in \mathbb {G}^n\), the value of \(e(\varvec{c}_1, \varvec{k}^*_1)\) is \(\prod _{i=1}^{n-1} e(x_i C_1, K_i) \cdot e(C_2, K_n) = \prod _{i=1}^{n-1} e(C_1, x_i K_i) \cdot e(C_2, K_n) = e(C_1, \sum _{i=1}^{n-1} x_i K_i) \cdot e(C_2, K_n)\). That is, \(n-1\) scalar multiplications in \(\mathbb {G}\) and two pairing operations are enough for computing \(e(\varvec{c}_1, \varvec{k}^*_1)\). Therefore, only a small (constant) number of pairing operations are required for decryption.
We then explain how our full NIPE scheme is constructed on the above-mentioned simplified NIPE scheme. The target of designing the full NIPE scheme is to achieve adaptive security under the DLIN assumption. Here, we adopt a strategy similar to that of [25], in which the dual system encryption methodology is employed in a modular or hierarchical manner. That is, two top level assumptions, the security of Problems 1 and 2, are directly used in the dual system encryption methodology and these assumptions are reduced to a primitive assumption, the DLIN assumption.
To meet the requirements for applying to the dual system encryption methodology and reducing to the DLIN assumption, the underlying vector space as well as the basis generator matrix X is four times larger than that of the above-mentioned simplified scheme. For example, \(\varvec{k}^*_1 :{=}( \ \delta \vec {v}, \ 0^{n}, \ \vec {\varphi }_1, \ 0^{n} \ )_{{\mathbb {B}}^*}, \)
\( \varvec{c}_1 = ( \omega \vec {x}, 0^{n}, 0^{n}, \eta _1 \vec {x} )_{{\mathbb {B}}}, \) and \( X :{=}\left( \begin{array}{cccccccc} X_{1,1} &{} \cdots &{} X_{1,4} \\ \vdots &{} &{} \vdots \\ X_{4,1} &{} \cdots &{} X_{4,4} \end{array} \right) \in \mathcal{L}(4,n, \mathbb {F}_q)\) of Eq. (3) in Sect. 6.2, where each \(X_{i,j}\) is of the form of \(X \in \mathcal{H}(n, \mathbb {F}_q)\) in the simplified scheme. The vector space consists of four orthogonal subspaces, i.e., real encoding part, hidden part, secret-key randomness part, and ciphertext randomness part. The simplified NIPE scheme corresponds to the first real encoding part.
A key fact in the security reduction is that \(\mathcal{L}(4,n,\mathbb {F}_q)\) is a subgroup of \(GL(4n, \mathbb {F}_q)\) (Lemma 2), which enables a random-self-reducibility argument for reducing the DLIN problem to Problems 1 and 2 in this paper. The property that \(\mathcal{H}(n,\mathbb {F}_q) \cap GL(n,\mathbb {F}_q)\) is a subgroup of \(GL(n,\mathbb {F}_q)\) is also crucial for a special form of pairwise independence lemma in this paper (Lemma 6), where \(\mathcal{H}(n,\mathbb {F}_q)\) is specified in \(\mathcal{L}(4,n,\mathbb {F}_q)\) or X. Our Problem 2, which is based on this lemma, employs special form matrices \(U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{H}(n,\mathbb {F}_q) \cap GL(n,\mathbb {F}_q)\) and \(Z :{=}(U^{-1})^{\mathrm {T}}\). Informally, our pairwise independence lemma implies that, for all \((\vec {x},\vec {v})\), a pair, \((\vec {x} U, \vec {v} Z)\), is uniformly distributed over \((\mathsf{span}\langle \vec {x}, \vec {e}_n \rangle \setminus \mathsf{span}\langle \vec {e}_n \rangle ) \times (\mathbb {F}_q^{\,n} \setminus \mathsf{span}\langle \vec {e}_n \rangle ^{\bot })\) with preserving the inner-product value, \(\vec {x}\cdot \vec {v}\), i.e., \((\vec {x} U, \vec {v} Z)\) reveal no information but \(\vec {x}\) and \(\vec {x} \cdot \vec {v}\).
A difference of matrix X with the ZIPE scheme will be noted in Remark 10.
6.2 Dual orthonormal basis generator
We describe random dual orthonormal basis generator \({{\mathcal{G}^\mathsf{NIPE, CT}_\mathsf{ob}}}\) below, which is used as a subroutine in the proposed NIPE scheme.
$$\begin{aligned}&{{\mathcal{G}^\mathsf{NIPE, CT}_\mathsf{ob}}}(1^\lambda , 4, n): \ \ \mathsf{param}_\mathbb {G}:{=}(q,\mathbb {G},\mathbb {G}_T,{G},e) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathcal{G}_\mathsf{bpg}(1^\lambda ), \ \ {N}_0 :{=}5, \ {N}_1 :{=}4 n, \\&\ \ \ \mathsf{param}_{\mathbb {V}_t} :{=}(q, \mathbb {V}_t, \mathbb {G}_T, {\mathbb {A}}_t, e) :{=}{{\mathcal{G}_\mathsf{dpvs}}}(1^\lambda , {N}_t, \mathsf{param}_\mathbb {G}) \ \ \mathrm {for} \ t=0,1, \\&\ \ \ \psi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}_q^{\,\times }}, \ g_T :{=}e({G}, {G})^\psi , \ \mathsf{param}_{n} :{=}(\{ \mathsf{param}_{\mathbb {V}_t} \}_{t=0,1}, \ g_T), \ \\&\ \ \ X_0 :{=}(\chi _{0,i,j})_{i,j=1,\ldots ,5} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}GL(N_0, \mathbb {F}_q), \ X_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{L}(4, n, \mathbb {F}_q), \ \mathrm {hereafter, \ } \\&\ \ \ \ \{ \mu _{i,j}, \mu '_{i,j,l} \}_{i,j =1,\ldots 4; l=1,\ldots ,n} \ \mathrm {denotes non\hbox {-}zero entries of} X_1 \mathrm { \ as \ in \ Eq.\,(3)}, \\&\ \ \ {\textstyle \varvec{b}_{0,i} :{=}(\chi _{0,i,1}, \ldots , \chi _{0,i,5})_{{\mathbb {A}}} = \sum _{j=1}^{5} \chi _{0,i,j} \varvec{a}_{j} \ \mathrm {for} \ i=1,\ldots ,5, \ {\mathbb {B}}_0 :{=}(\varvec{b}_{0,1},\ldots ,\varvec{b}_{0,5}), } \\&\ \ \ B_{i,j} :{=}\mu _{i,j} G, \ B'_{i,j,l} :{=}\mu '_{i,j,l} G \ \ \mathrm {for} \ i,j=1,\ldots ,4; l=1,\ldots ,n, \\&\ \ \ \mathrm {for} \ t=0,1, \ (\vartheta _{t,i,j})_{i,j=1,\ldots ,N_t} :{=}\psi \cdot (X_t^{\text {T}})^{-1}, \\&\ \ \ \ {\textstyle \varvec{b}^{*}_{t,i} :{=}(\vartheta _{t,i,1}, \ldots , \vartheta _{t,i,{N}_t})_{{\mathbb {A}}} \!=\! \sum _{j=1}^{{N}_t} \vartheta _{t,i,j} \varvec{a}_{j} \ \mathrm {for} \ i\!=\!1,\ldots ,N_t, \ {\mathbb {B}}_t^{*} :{=}(\varvec{b}^{*}_{t,1},\ldots ,\varvec{b}^{*}_{t,{N}_t}), } \\&\ \ \ \mathrm{return} \ \ (\mathsf{param}_{n}, {\mathbb {B}}_0, {\mathbb {B}}_0^*, \{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\mathbb {B}}_1^* ). \end{aligned}$$
Remark 2
Let where a blank element in the matrix denotes \(0 \in {\mathbb {G}}\). \({\mathbb {B}}_1\) is the dual orthonormal basis of \({\mathbb {B}}^*_1\), i.e., \(e(\varvec{b}_{1,i},\varvec{b}^*_{1,i}) = g_T\) and \(e(\varvec{b}_{1,i},\varvec{b}^*_{1,j}) = 1\) for \(1 \le i \ne j \le 4n\).
$$\begin{aligned}&\left. \begin{array}{l} \left( \begin{array}{c} \varvec{b}_{1,(i-1)n+1} \\ \vdots \\ \varvec{b}_{1,in} \end{array} \right) :{=}\left( \begin{array}{cccc} B_{i,1} &{} &{} &{} B'_{i,1,1} \\ &{} \ddots &{} &{} \vdots \\ &{} &{} B_{i,1} &{} B'_{i,1,n-1} \\ &{} &{} &{} B'_{i,1,n} \end{array} \cdots \begin{array}{cccc} B_{i,4} &{} &{} &{} B'_{i,4,1} \\ &{} \ddots &{} &{} \vdots \\ &{} &{} B_{i,4} &{} B'_{i,4,n-1} \\ &{} &{} &{} B'_{i,4,n} \end{array} \right) \\ \ \ \ \ \ \ \ \ \mathrm {for} \ i=1,\ldots ,4, \\ {\mathbb {B}}_1 :{=}(\varvec{b}_{1,1},\ldots ,\varvec{b}_{1,4n}), \end{array} \right\} \end{aligned}$$
(6)
6.3 Construction
In the description of the scheme, we assume that input vector, \(\vec {x} :{=}(x_1, \ldots , x_n)\), has an index l (\(1 \le l \le n-1\)) with \(x_l \ne 0\), and that input vector, \(\vec {v} :{=}(v_1, \ldots , v_n)\), satisfies \(v_n \ne 0\). The plaintext space is \({\mathbb {G}}_T\).
$$\begin{aligned}&\mathsf{Setup}(1^\lambda , \ n): (\mathsf{param}_{n}, {\mathbb {B}}_0, {\mathbb {B}}_0^*, \{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\mathbb {B}}_1^* ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}^\mathsf{NIPE, CT}_\mathsf{ob}}}(1^\lambda , 4, n), \\&{\widehat{\mathbb {B}}}_0 :{=}(\varvec{b}_{0,1},\varvec{b}_{0,3},\varvec{b}_{0,5}), {\widehat{\mathbb {B}}}^*_0 :{=}(\varvec{b}^*_{0,1},\varvec{b}^*_{0,3},\varvec{b}^*_{0,4}), {\widehat{\mathbb {B}}}^*_1 :{=}(\varvec{b}^*_{1,1},\ldots ,\varvec{b}^*_{1,n}, \varvec{b}^*_{1,2n+1},\ldots ,\varvec{b}^*_{1,3n}), \\&\mathrm {return} \ \ \mathsf{pk} :{=}(1^\lambda , \mathsf{param}_{n}, {\widehat{\mathbb {B}}}_0, \{ B_{i,j}, B'_{i,j,l} \}_{i=1,4; j=1,\ldots ,4; l=1,\ldots ,n}), \ \mathsf{sk} :{=}\{{\widehat{\mathbb {B}}}^{*}_t \}_{t=0,1}. \\&\mathsf{KeyGen}(\mathsf{pk}, \ \mathsf{sk}, \ \vec {v}) : \ \ \ \delta , \varphi _0 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \vec {\varphi }_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n, \ \ \ \varvec{k}^*_0 :{=}(\delta , \ 0, \ 1, \ \varphi _0, \ 0)_{{\mathbb {B}}^*_0}, \\&\ \ \ \varvec{k}^*_1 :{=}( \ \overbrace{\delta \vec {v}}^n, \ \overbrace{0^{n}}^n, \ \overbrace{\ \vec {\varphi }_1 \ }^n, \ \overbrace{0^{n}}^n \ )_{{\mathbb {B}}^*_1}, \ \ \ \mathrm {return} \ \ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, \varvec{k}^*_0, \varvec{k}^*_1). \\&\mathsf{Enc}(\mathsf{pk}, \ m, \ \vec {x}): \ \ \ \omega , \eta _0, \eta _1, \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \ \ \varvec{c}_0 :{=}(-\omega , \ 0, \ \zeta , \ 0, \ \eta _0)_{{\mathbb {B}}_0}, \ \ c_3 :{=}g_T^\zeta m, \\&\textstyle \ \ \ C_{1,j} :{=}\omega B_{1,j} + \eta _1 B_{4,j}, \ \ C_{2,j} :{=}\sum _{l=1}^n x_l (\omega B'_{1,j,l} + \eta _1 B'_{4,j,l}) \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \mathrm {return} \ \ \mathsf{ct}_{\vec {x}} :{=}(\vec {x}, \varvec{c}_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3). \\&\mathsf{Dec}(\mathsf{pk},\ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, \varvec{k}^*_{0}, \varvec{k}^*_1 ), \ \mathsf{ct}_{\vec {x}} :{=}(\vec {x}, \varvec{c}_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3)) : \\&\textstyle \ \ \ \text {Parse} \ \varvec{k}^*_1 \ \text {as a} \ 4n\text {-tuple } (K^*_{1},\ldots ,K^*_{4n}) \in {\mathbb {G}}^{4n}, \\&\ \ \ \textstyle D^*_j :{=}\sum _{l=1}^{n-1} ((\vec {x} \cdot \vec {v})^{-1} x_l) \, K^*_{(j-1)n+l} \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \textstyle F :{=}e(\varvec{c}_0,\varvec{k}^*_0) \cdot \prod _{j=1}^4 \left( e(C_{1,j},D^*_j) \cdot e(C_{2,j},K^*_{jn}) \right) , \ \ \ \mathrm {return} \ \ m' :{=}c_3/F. \end{aligned}$$
Remark 3
A part of output of \(\mathsf{Setup}(1^\lambda , n)\), \(\{ B_{i,j}, B'_{i,j,l} \}_{i=1,4; j=1,\ldots ,4; l=1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}_1 :{=}(\varvec{b}_{1,1}, \ldots ,\varvec{b}_{1,n},\varvec{b}_{1,3n+1},\ldots ,\varvec{b}_{1,4n})\) through the form of Eq. (6), while \({\mathbb {B}}_1 :{=}(\varvec{b}_{1,1},\ldots ,\)
\(\varvec{b}_{1,4n})\) is identified with \(\{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; \, l=1,\ldots ,n}\) by Eq. (6). Decryption \(\mathsf{Dec}\) can be alternatively described as:
[Correctness] Using the alternate decryption \(\mathsf{Dec}'\), \( F = e(\varvec{c}_0,\varvec{k}^*_0) \cdot e(\varvec{c}_1, (\vec {x} \cdot \vec {v})^{-1} \varvec{k}^*_1) = g_T^{-\omega \delta + \zeta } g_T^{\omega \delta ( \vec {x} \cdot \vec {v} )/(\vec {x} \cdot \vec {v})} = g_T^{\zeta } \ \ \ \mathrm {if} \ \vec {x} \cdot \vec {v} \ne 0. \)
6.4 Security
Theorem 1
The proposed NIPE scheme is adaptively payload-hiding against chosen plaintext attacks under the DLIN assumption.
For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_{1}, \mathcal{E}_{2\hbox {-}1}\) and \(\mathcal{E}_{2\hbox {-}2}\) whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \( \textstyle \mathsf{Adv}^\mathsf{NIPE, PH}_\mathcal{A}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1}}(\lambda ) + \sum _{h=1}^{\nu } \left( \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h\hbox {-}1}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h\hbox {-}2}}(\lambda ) \right) \)
\(+ \epsilon , \) where \(\mathcal{E}_{2\hbox {-}h\hbox {-}1}(\cdot ) :{=}\mathcal{E}_{2\hbox {-}1}(h,\cdot )\), \(\mathcal{E}_{2\hbox {-}h\hbox {-}2}(\cdot ) :{=}\mathcal{E}_{2\hbox {-}2}(h,\cdot )\), \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries and \(\epsilon :{=}(11 \nu + 6)/q\).
6.4.1 Lemmas for the Proof of Theorem 1
Definition 8
(Problem 1) Problem 1 is to guess \(\beta \), given \((\mathsf{param}_{n}, {\mathbb {B}}_0, {\widehat{\mathbb {B}}}^*_0,\varvec{e}_{\beta ,0},\)
\( \{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\widehat{\mathbb {B}}}^*_1, \{ E_{\beta ,j}, E'_{\beta ,j,l} \}_{j=1,\ldots ,4; l=1,\ldots ,n} ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{\mathcal{G}}_{\beta }^\mathsf{P1}(1^\lambda , n) \), wherefor \(\beta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}\). For a probabilistic machine \(\mathcal{B}\), we define the advantage of \(\mathcal{B}\) as the quantity \(\mathsf{Adv}^\mathsf{P1}_{\mathcal{B}}(\lambda ) :{=}\left| \mathsf{Pr}\left[ \mathcal{B}(1^\lambda , \varrho ) \rightarrow 1 \left| \varrho \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{\mathcal{G}}_0^\mathsf{P1}(1^\lambda , n) \right. \right] - \mathsf{Pr}\left[ \mathcal{B}(1^\lambda , \varrho ) \rightarrow 1\right. \right. \left. \left. \left| \varrho \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{\mathcal{G}}_1^\mathsf{P1}(1^\lambda , n) \right. \right] \right| . \)
$$\begin{aligned}&{\mathcal{G}}_{\beta }^\mathsf{P1}(1^\lambda , n): \ \ \ (\mathsf{param}_{n}, {\mathbb {B}}_0, {\mathbb {B}}^*_0, \{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\widehat{\mathbb {B}}}^*_1 ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}^\mathsf{NIPE, CT}_\mathsf{ob}}}(1^\lambda , 4, n), \\&\ \ \ {\widehat{\mathbb {B}}}^*_0 :{=}(\varvec{b}^*_{0,1},\varvec{b}^*_{0,3},\ldots ,\varvec{b}^*_{0,5}), \ {\widehat{\mathbb {B}}}^*_1 :{=}(\varvec{b}^*_{1,1},\ldots , \varvec{b}^*_{1,n}, \varvec{b}^*_{t,2n+1},\ldots , \varvec{b}^*_{t,4n}), \\&\ \ \ \omega , \tau , \eta _0, \eta _1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{H}(n,\mathbb {F}_q) \cap GL(n, \mathbb {F}_q), \ \mathrm {hereafter}, \ u, u'_n \in {\mathbb {F}_q^{\,\times }}, \\&\ \ \ \ \ u'_1, \ldots , u'_{n-1} \in \mathbb {F}_q\ \mathrm {denote \ non\hbox {-}zero \ entries \ of} \ U, \ \mathrm {as \ in \ Eq.}\,(1), \\&\ \ \ \varvec{e}_{0,0} :{=}(\omega , 0, 0, 0, \eta _0)_{{\mathbb {B}}_0}, \ \ \ \varvec{e}_{1,0} :{=}(\omega , \tau , 0, 0, \eta _0)_{{\mathbb {B}}_0}, \\&\ \ \ \mathrm {for} \ j=1,\ldots ,4; \\&\ \ \ \ \ E_{0,j} :{=}\omega B_{1,j} + \eta _1 B_{4,j}, \ E'_{0,j,l} :{=}\omega B'_{1,j,l} + \eta _1 B'_{4,j,l} \ \mathrm {for} \ l=1,\ldots ,n, \\&\ \ \ \ \ E_{1,j} :{=}\omega B_{1,j} + \tau u B_{2,j} + \eta _1 B_{4,j}, \\&\ \ \ \ \ E'_{1,j,l} :{=}\omega B'_{1,j,l} + \tau u B'_{2,j,l} + \tau u'_l B'_{2,j,n} + \eta _1 B'_{4,j,l} \\&\ \ \ \ \ \ \ \ \mathrm {for} \ l=1,\ldots ,n-1, \ \mathrm {and} \ E'_{1,j,n} :{=}\omega B'_{1,j,n} + \tau u'_n B'_{2,j,n} + \eta _1 B'_{4,j,n}, \\&\ \ \ \mathrm{return} \ \ (\mathsf{param}_{n}, {\mathbb {B}}_0, {\widehat{\mathbb {B}}}^*_0,\varvec{e}_{\beta ,0}, \{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\widehat{\mathbb {B}}}^*_1, \\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \{ E_{\beta ,j}, E'_{\beta ,j,l} \}_{j=1,\ldots ,4; l=1,\ldots ,n} ), \end{aligned}$$
Remark 4
A part of output of \({\mathcal{G}}_{\beta }^\mathsf{P1}(1^\lambda , n)\), \(\{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}\), is identified with \({\mathbb {B}}_1 :{=}(\varvec{b}_{1,1},\)
\(\ldots ,\varvec{b}_{1,4n})\) [(Eq. (6)]. If we make \(\varvec{e}_{\beta ,1,l} \in {\mathbb {V}}_1\) for \(\beta = 0,1; l=1,\ldots ,n\) as:
they are expressed over \({\mathbb {B}}_1\) as:
Using these vector expressions, the output of \({\mathcal{G}}_{\beta }^\mathsf{P1}(1^\lambda , n)\) is expressed as \( (\mathsf{param}_{n}, {\mathbb {B}}_0, {\widehat{\mathbb {B}}}^*_0,\varvec{e}_{\beta ,0}, {\mathbb {B}}_1, \)
\({\widehat{\mathbb {B}}}^*_1, \{ \varvec{e}_{\beta ,1,l} \}_{l=1,\ldots ,n} )\).
Lemma 4
For any machine \(\mathcal{B}\), there exists a probabilistic machine \(\mathcal{E}\), whose running times are essentially the same as that of \(\mathcal{B}\), such that for any security parameter \(\lambda \), \( \mathsf{Adv}^\mathsf{P1}_{\mathcal{B}}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}}(\lambda ) + 5/q. \)
Definition 9
(Problem 2) Problem 2 is to guess \(\beta \), given
\((\mathsf{param}_{n}, {\widehat{\mathbb {B}}}_0, {\mathbb {B}}^*_0, \varvec{h}^*_{\beta ,0}, \varvec{e}_0, \{ B_{i,j}, B'_{i,j,l} \}_{i=1,3,4; j=1,\ldots ,4; l=1,\ldots ,n}, {\mathbb {B}}^*_1, \{ \varvec{h}^{*}_{\beta ,1,l}, E_j, E'_{j,l} \}_{j=1,\ldots ,4; l=1,\ldots ,n}) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\)
\({\mathcal{G}}_{\beta }^\mathsf{P2}(1^\lambda , n)\), where
for \(\beta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}\). For a probabilistic adversary \(\mathcal{B}\), the advantage of \(\mathcal{B}\) for Problem 2, \(\mathsf{Adv}^\mathsf{P2}_{\mathcal{B}}(\lambda )\), is similarly defined as in Definition 8.
Remark 5
A part of output of \({\mathcal{G}}_{\beta }^\mathsf{P2}(1^\lambda , n)\), \(\{ B_{i,j}, B'_{i,j,l} \}_{i=1,3,4; j=1,\ldots ,4; l=1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}_1 :{=}(\varvec{b}_{1,1},\ldots ,\varvec{b}_{1,n},\varvec{b}_{1,2n+1},\ldots ,\varvec{b}_{1,4n})\) in the form of Eq. (6), while \({\mathbb {B}}_1 :{=}(\varvec{b}_{1,1},\ldots ,\varvec{b}_{1,4n})\) is identified with \(\{ B_{i,j}, \)
\(B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}\) by Eq. (6). If we make \(\varvec{e}_{1,l} \in {\mathbb {V}}_1\) for \(l=1,\ldots ,n\) as:
they are expressed over \({\mathbb {B}}_1\) as:
Using these vector expressions, the output of \({\mathcal{G}}_{\beta }^\mathsf{P2}(1^\lambda , n)\) is expressed as \( (\mathsf{param}_{n}, {\widehat{\mathbb {B}}}_0, {\mathbb {B}}^*_0, \varvec{h}^*_{\beta ,0}, \varvec{e}_0, \)
\({\widehat{\mathbb {B}}}_1, {\mathbb {B}}^*_1, \{ \varvec{h}^{*}_{\beta ,1,l}, \varvec{e}_{1,l} \}_{l=1,\ldots ,n} )\).
Lemma 5
For any machine \(\mathcal{B}\), there exists a probabilistic machine \(\mathcal{E}\), whose running time is essentially the same as that of \(\mathcal{B}\), such that for any security parameter \(\lambda \), \( \textstyle \mathsf{Adv}^\mathsf{P2}_{\mathcal{B}}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}}(\lambda ) + 5/q. \)
Lemma 6
Let \(\vec {e}_n :{=}(0,\ldots ,0,1) \in \mathbb {F}_q^{\,n}\). For all \(\vec {x} \in \mathbb {F}_q^{\,n} \setminus \mathsf{span}\langle \vec {e}_n \rangle \) and \(\pi \in \mathbb {F}_q\), let \(W_{\vec {x}, \pi } :{=}\{ (\vec {r}, \vec {w}) \in (\mathsf{span}\langle \vec {x}, \vec {e}_n \rangle \setminus \mathsf{span}\langle \vec {e}_n \rangle ) \times (\mathbb {F}_q^{\,n} \setminus \mathsf{span}\langle \vec {e}_n \rangle ^{\bot }) \ | \ \vec {r} \cdot \vec {w} = \pi \}. \)
For all \((\vec {x},\vec {v}) \in \left( \mathbb {F}_q^{\,n} \setminus \mathsf{span}\langle \vec {e}_n \rangle \right) \times \left( \mathbb {F}_q^{\,n} \setminus \mathsf{span}\langle \vec {e}_n \rangle ^{\bot } \right) \), for all \((\vec {r},\vec {w}) \in W_{\vec {x}, (\vec {x} \cdot \vec {v})}\), \( \Pr \left[ \, \vec {x} U = \vec {r} \, \wedge \, \right. \)
\(\left. \vec {v} Z = \vec {w} \, \right] = 1 \big / \sharp \,W_{\vec {x}, (\vec {x} \cdot \vec {v})}, \) where \(U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{H}(n,\mathbb {F}_q) \cap GL(n,\mathbb {F}_q)\) and \(Z :{=}(U^{-1})^{\mathrm {T}}\).
6.4.2 Proof outline
At the top level of strategy of the security proof, we follow the dual system encryption methodology proposed by Waters [31]. In the methodology, ciphertexts and secret keys have two forms, normal and semi-functional. In the proof herein, we also introduce other forms of secret keys called 1st-pre-semi-functional and 2nd-pre-semi-functional. The real system uses only normal ciphertexts and normal secret keys, and semi-functional ciphertexts and semi-functional/1st-pre-semi-functional/2nd-pre-semi-functional keys are used only in a sequence of security games for the security proof. To prove this theorem, we employ Game 0 (original adaptive-security game) through Game 3. In Game 1, the challenge ciphertext is changed to semi-functional. When at most \(\nu \) secret key queries are issued by an adversary, there are \(3\nu \) game changes from Game 1 (Game 2-0-3), Game 2-1-1, Game 2-1-2, Game 2-1-3 through Game 2-\(\nu \)-3.
In Game 2-h-1, the first \((h-1)\) keys are semi-functional and the h-th key is 1st-pre-semi-functional, while the remaining keys are normal, and the challenge ciphertext is semi-functional. In Game 2-h-2, the first \((h-1)\) keys are semi-functional and the h-th key is 2nd-pre-semi-functional, while the remaining keys are normal, and the challenge ciphertext is semi-functional. In Game 2-h-3, the first h keys are semi-functional (i.e., and the h-th key is semi-functional), while the remaining keys are normal, and the challenge ciphertext is semi-functional.
The final game (Game 3) with advantage 0 is conceptually changed from Game 2-\(\nu \)-3. As usual, we prove that the advantage gaps between neighboring games are negligible.
When at most \(\nu \) key queries are issued by an adversary, we set a sequence of \(\mathsf{sk} :{=}\mathsf{sk}_{\vec {v}}\)’s, i.e., \((\mathsf{sk}^{(1)*},\ldots ,\mathsf{sk}^{(\nu )*})\), in the order of the adversary’s queries. Here we focus on \(\vec {\varvec{k}}^{(h) *}_{\vec {v}} :{=}(\varvec{k}_0^{(h) *},\varvec{k}_1^{(h) *})\), and \(\vec {\varvec{c}}_{\vec {x}} :{=}(\varvec{c}_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4},c_3)\), and ignore the other part of \(\mathsf{sk}_{\vec {v}}\) (resp. \(\mathsf{ct}_{\vec {x}}\)), i.e., \(\vec {v}\) (resp. i.e., \(\vec {x}\)), and call them secret key and ciphertext, respectively, in this proof outline. In addition, we ignore a negligible factor in the (informal) descriptions of this proof outline. For example, we say “A is bounded by B” when \(A \le B + \epsilon (\lambda )\) where \(\epsilon (\lambda )\) is negligible in security parameter \(\lambda \).
A normal secret key, \(\vec {\varvec{k}}^{(h) * \mathsf{norm}}_{\vec {v}}\), is the correct form of the secret key of the proposed NIPE scheme, and is expressed by Eq. (7). Similarly, a normal ciphertext \(\vec {\varvec{c}}^\mathsf{\ norm}_{\vec {x}}\), is expressed by Eq. (8). A 1st-pre-semi-functional secret key, \(\vec {\varvec{k}}^{(h) * \ \mathsf{1st\hbox {-}psemi}}_{\vec {v}}\), is expressed by Eq. (10), a 2nd-pre-semi-functional secret key, \(\vec {\varvec{k}}^{(h) * \ \mathsf{2nd\hbox {-}psemi}}_{\vec {v}}\), is expressed by Eq. (11), a semi-functional secret key, \(\vec {\varvec{k}}^{(h) * \ \mathsf{semi}}_{\vec {v}}\), is expressed by Eq. (12), and a semi-functional ciphertext, \(\vec {\varvec{c}}^\mathsf{\ semi}_{\vec {x}}\), is expressed by Eq. (9).
To prove that the advantage gap between Games 0 and 1 is bounded by the advantage of Problem 1 (to guess \(\beta \in \{0,1\}\)), we construct a simulator of the challenger of Game 0 (or 1) (against an adversary \(\mathcal{A}\)) by using an instance with \(\beta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}\) of Problem 1. We then show that the distribution of the secret keys and challenge ciphertext replied by the simulator is equivalent to those of Game 0 when \(\beta =0\) and Game 1 when \(\beta =1\). That is, the advantage gap between Games 0 and 1 is bounded by the advantage of Problem 1 (Lemma 7). The advantage of Problem 1 is proven to be bounded by that of the DLIN assumption (Lemma 4). The advantage gap between Games 2-\((h-1)\)-3 and 2-h-1 is similarly shown to be bounded by the advantage of Problem 2 (i.e., advantage of the DLIN assumption) (Lemmas 8 and 5). The distributions of 1st-pre-semi-functional secret key \(\vec {\varvec{k}}^{(h) * \ \mathsf{1st\hbox {-}psemi}}_{\vec {v}}\) (Eq. (10)) and 2nd-pre-semi-functional secret key \(\vec {\varvec{k}}^{(h) * \ \mathsf{2nd\hbox {-}psemi}}_{\vec {v}}\) (Eq. (11)) are distinguishable by the simulator or challenger, but the joint distributions of \((\vec {\varvec{k}}^{(h) * \ \mathsf{1st\hbox {-}psemi}}_{\vec {v}},\)
\( \vec {\varvec{c}}^\mathsf{\ semi}_{\vec {x}})\) and \((\vec {\varvec{k}}^{(h) * \ \mathsf{2nd\hbox {-}psemi}}_{\vec {v}}, \vec {\varvec{c}}^\mathsf{\ semi}_{\vec {x}})\) along with the other keys are (information theoretically) equivalent for the adversary’s view, when \(\vec {x} \cdot \vec {v} = 0\), i.e., \(R^\mathsf{NIPE}(\vec {x}, \vec {v}) \ne 1\). Therefore, as shown in Lemma 9, the advantages of Games 2-h-1 and 2-h-2 are equivalent. The advantage gap between Games 2-h-2 and 2-h-3 is similarly shown to be bounded by the advantage of Problem 2 (i.e., advantage of the DLIN assumption) (Lemmas 10 and 5). Finally we show that Game 2-\(\nu \)-3 can be conceptually changed to Game 3 (Lemma 11) by using the fact that basis vectors \(\varvec{b}_{0,2}\) and \(\varvec{b}^*_{0,3}\) are unknown to the adversary.
6.4.3 Proof of Theorem 1
To prove Theorem 1, we consider the following \((3\nu +3)\) games. In Game 0, a part framed by a box indicates coefficients to be changed in a subsequent game. In the other games, a part framed by a box indicates coefficients that were changed in a game from the previous game.
Game 0 Original game. That is, the reply to a key query for \(\vec {v}\) is
where \(\delta , \varphi _0 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \vec {\varphi }_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\) and \(\vec {v} :{=}(v_1,\ldots ,v_n) \in \mathbb {F}_q^{\,n}\) with \(v_n \ne 0\). The challenge ciphertext for challenge plaintexts \((m^{(0)},m^{(1)})\) and \(\vec {x}\), \((\vec {x}, \varvec{c}_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3)\), which is identified with \((\vec {x}, \varvec{c}_0, \varvec{c}_1, c_3)\) in Remark 3, is
where \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}; \omega , \zeta , \eta _0, \eta _1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and \(\vec {x} :{=}(x_1,\ldots ,x_n) \in \mathbb {F}_q^{\,n}\) with \(x_l \ne 0\) for some \(l \in \{1,\ldots ,n-1\}\).
(7)
(8)
Game 1 Same as Game 0 except that the challenge ciphertext for challenge plaintexts \((m^{(0)},m^{(1)})\) and \(\vec {x}\) is
where \(\tau \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{H}(n,\mathbb {F}_q) \cap GL(n,\mathbb {F}_q)\), and all the other variables are generated as in Game 0.
(9)
\(\mathbf{Game~2}\hbox {-}{\varvec{h}}\hbox {-}\mathbf{1} \mathbf{(}\hbox {h}\mathbf{=1},\mathbf{\ldots },{\varvec{\nu }}\mathbf{) }\) Game 2-0-3 is Game 1. Game 2-h-1 is the same as Game 2-\((h-1)\)-3 except that the reply to the h-th key query for \(\vec {v}\), \((\varvec{k}^*_0, \varvec{k}^*_1)\), is
where \(\rho \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, Z :{=}(U^{-1})^{\mathrm {T}}\) for \(U \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{H}(n,\mathbb {F}_q) \cap GL(n,\mathbb {F}_q)\) used in Eq. (9) and all the other variables are generated as in Game 2-\((h-1)\)-3.
(10)
\(\mathbf{Game~2}\hbox {-}{\varvec{h}}\hbox {-}\mathbf{2} \mathbf{(}{\varvec{h}}\mathbf{=1,\ldots },{\varvec{\nu }}\mathbf{) } \) Game 2-h-2 is the same as Game 2-h-1 except that a part of the reply to the h-th key query for \(\vec {v}\), \((\varvec{k}^*_0, \varvec{k}^*_1)\), is
where \(w \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 2-h-1.
(11)
\(\mathbf{Game~2}\hbox {-}{\varvec{h}}\hbox {-}\mathbf{3 (}{\varvec{h}}\mathbf{=1,\ldots },{\varvec{\nu }}\mathbf{) } \) Game 2-h-3 is the same as Game 2-h-2 except that the reply to the h-th key query for \(\vec {v}\), \((\varvec{k}^*_0, \varvec{k}^*_1)\), is
where all the variables are generated as in Game 2-h-2.
(12)
Game 3 Same as Game 2-\(\nu \)-3 except that \(\varvec{c}_0\) and \(c_3\) of the challenge ciphertext are
where \(\zeta ' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) (i.e., independent from \(\zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\)), and all the other variables are generated as in Game 2-\(\nu \)-3.
Let \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}\iota )}(\lambda )\) (\(h=1,\ldots , \nu ; \iota =1,2,3\)) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\) be the advantage of \(\mathcal{A}\) in Game \(0,1,2\hbox {-}h\hbox {-}\iota \) and 3, respectively. \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda )\) is equivalent to \(\mathsf{Adv}^\mathsf{NIPE, PH}_\mathcal{A}(\lambda )\) and it is obtained that \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )=0\) by Lemma 12. We will show five lemmas (Lemmas 7–11) that evaluate the gaps between pairs of \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ), \)
\( \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}\iota )}(\lambda )\) for \(h=1,\ldots ,\nu ; \iota =1,2,3\) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\). From these lemmas and Lemmas 4 and 5, we obtain Theorem 1. \(\square \)
Lemma 7
For any machine \(\mathcal{A}\), there exists a probabilistic machine \(\mathcal{B}_1\), whose running time is essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ) | \le \mathsf{Adv}_{\mathcal{B}_1}^\mathsf{P1}(\lambda ). \)
Lemma 8
For any machine \(\mathcal{A}\), there exists a probabilistic machine \(\mathcal{B}_{2\hbox {-}1}\), whose running time is essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}(h-1)\hbox {-}3)}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}1)}(\lambda ) | \le \mathsf{Adv}_{\mathcal{B}_{2\hbox {-}h\hbox {-}1}}^\mathsf{P2}(\lambda ), \) where \(\mathcal{B}_{2\hbox {-}h\hbox {-}1}(\cdot ) :{=}\mathcal{B}_{2\hbox {-}1}(h,\cdot )\).
Lemma 9
For any machine \(\mathcal{A}\), for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}1)}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}2)}(\lambda )| \le 1/q. \)
Lemma 10
For any machine \(\mathcal{A}\), there exists a probabilistic machine \(\mathcal{B}_{2\hbox {-}2}\), whose running time is essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}2)}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}3)}(\lambda ) | \le \mathsf{Adv}_{\mathcal{B}_{2\hbox {-}h\hbox {-}2}}^\mathsf{P2}(\lambda ), \) where \(\mathcal{B}_{2\hbox {-}h\hbox {-}2}(\cdot ) :{=}\mathcal{B}_{2\hbox {-}2}(h,\cdot )\).
Lemma 11
For any machine \(\mathcal{A}\), for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}\nu \hbox {-}3)}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )| \le 1/q. \)
Lemma 12
For any machine \(\mathcal{A}\), for any security parameter \(\lambda \), \( \mathsf{Adv}_\mathcal{A}^{(3)}(\lambda ) = 0. \)
7 NIPE scheme with constant-size secret-keys
7.1 Dual orthonormal basis generator
We describe random dual orthonormal basis generator \({{\mathcal{G}^\mathsf{NIPE, SK}_\mathsf{ob}}}\) below, which is used as a subroutine in the proposed NIPE scheme, where \({{\mathcal{G}^\mathsf{NIPE, CT}_\mathsf{ob}}}\) is given in Sect. 6.2.
$$\begin{aligned}&{{\mathcal{G}^\mathsf{NIPE, SK}_\mathsf{ob}}}(1^\lambda , 4, n): \, (\mathsf{param}_{n}, {\mathbb {D}}_0, {\mathbb {D}}_0^*, \{ D_{i,j}, D'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\mathbb {D}}_1^* ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}^\mathsf{NIPE, CT}_\mathsf{ob}}} \\&\quad (1^\lambda , 4, n), \\&\ \ \ {\mathbb {B}}_0 :{=}{\mathbb {D}}_0^*, \ {\mathbb {B}}^*_0 :{=}{\mathbb {D}}_0, \ {\mathbb {B}}_1 :{=}{\mathbb {D}}_1^*, \ B^*_{i,j} :{=}D_{i,j}, \ B^{\prime \, *}_{i,j,l} :{=}D'_{i,j,l} \\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathrm {for} \ i,j=1,\ldots ,4; l=1,\ldots ,n, \\&\ \ \ \mathrm{return} \ \ (\mathsf{param}_{n}, {\mathbb {B}}_0, {\mathbb {B}}_0^*, {\mathbb {B}}_1, \{ B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n} ). \end{aligned}$$
Remark 6
From Remark 2, \(\{ B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}\) is identified with basis \({\mathbb {B}}^*_1 :{=}(\varvec{b}^*_{1,1}, \ldots , \)
\(\varvec{b}^*_{1,4n})\) dual to \({\mathbb {B}}_1\).
7.2 Construction and security
In the description of the scheme, we assume that input vector, \(\vec {v} :{=}(v_1, \ldots , v_n)\), has an index l (\(1 \le l \le n-1\)) with \(v_l \ne 0\), and that input vector, \(\vec {x} :{=}(x_1, \ldots , x_n)\), satisfies \(x_n \ne 0\). The plaintext space is \({\mathbb {G}}_T\).
$$\begin{aligned}&\mathsf{Setup}(1^\lambda , \ n):\! (\mathsf{param}_{n}, {\mathbb {B}}_0, {\mathbb {B}}_0^*, {\mathbb {B}}_1, \{ B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,4; \, l=1,\ldots ,n} ) \!\mathop {\leftarrow }\limits ^{\ \mathsf{R}}\! {{\mathcal{G}^\mathsf{NIPE, SK}_\mathsf{ob}}}(1^\lambda , 4, n), \\&\ {\widehat{\mathbb {B}}}_0 :{=}(\varvec{b}_{0,1},\varvec{b}_{0,3},\varvec{b}_{0,5}), \, {\widehat{\mathbb {B}}}^*_0 :{=}(\varvec{b}^*_{0,1},\varvec{b}^*_{0,3},\varvec{b}^*_{0,4}), \\&\ {\widehat{\mathbb {B}}}_1 :{=}(\varvec{b}_{1,1},\ldots ,\varvec{b}_{1,n}, \varvec{b}_{1,3n+1},\ldots ,\varvec{b}_{1,4n}), \\&\ \mathrm {return} \ \mathsf{pk} :{=}(1^\lambda , \mathsf{param}_{n}, \{ {\widehat{\mathbb {B}}}_t \}_{t=0,1} ), \, \mathsf{sk} :{=}({\widehat{\mathbb {B}}}^{*}_0, \{ B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,3;\, j=1,\ldots ,4;\, l=1,\ldots ,n}). \\&\mathsf{KeyGen}(\mathsf{pk}, \ \mathsf{sk}, \ \vec {v} ) : \ \ \ \delta , \varphi _0, \varphi _1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \ \ \varvec{k}^*_0 :{=}(\delta , \ 0, \ 1, \ \varphi _0, \ 0)_{{\mathbb {B}}^*_0}, \\&\textstyle \ \ \ K^*_{1,j} :{=}\delta B^*_{1,j} + \varphi _1 B^*_{3,j}, \ \ K^*_{2,j} :{=}\sum _{l=1}^n v_l (\delta B^{\prime \, *}_{1,j,l} + \varphi _1 B^{\prime \, *}_{3,j,l}) \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \mathrm {return} \ \ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, \varvec{k}^*_{0}, \{ K^*_{1,j}, K^*_{2,j} \}_{j=1,\ldots ,4} ). \\&\mathsf{Enc}(\mathsf{pk}, \ m, \ \vec {x} ) : \ \ \ \omega , \eta _0, \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \vec {\eta }_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n, \ \ \ \varvec{c}_0 :{=}(-\omega , \ 0, \ \zeta , \ 0, \ \eta _0)_{{\mathbb {B}}_0}, \\&\ \ \ \varvec{c}_1 :{=}( \omega \vec {x}, \ 0^{n}, \ 0^{n}, \ \vec {\eta }_1 )_{{\mathbb {B}}_1}, \ \ \ c_3 :{=}g_T^\zeta m, \ \ \ \mathrm {return} \ \ \mathsf{ct}_{\vec {x}} :{=}(\vec {x}, \varvec{c}_0, \varvec{c}_1, c_3). \\&\mathsf{Dec}(\mathsf{pk},\ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, \varvec{k}^*_{0}, \{ K^*_{1,j}, K^*_{2,j} \}_{j=1,\ldots ,4}), \ \mathsf{ct}_{\vec {x}} :{=}(\vec {x}, \varvec{c}_0, \varvec{c}_1, c_3) ) : \\&\ \ \ \text {Parse} \ \varvec{c}_1 \ \text {as a} \ 4n\text {-tuple } (C_{1},\ldots ,C_{4n}) \in {\mathbb {G}}^{4n}, \\&\ \ \ \textstyle D_j :{=}\sum _{l=1}^{n-1} ((\vec {x} \cdot \vec {v})^{-1} v_l) \,C_{(j-1)n+l} \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \textstyle F :{=}e(\varvec{c}_0,\varvec{k}^*_0) \cdot \prod _{j=1}^4 \left( e(D_j,K^*_{1,j}) \cdot e(C_{jn},K^*_{2,j}) \right) , \ \ \ \mathrm {return} \ \ m' :{=}c_3/F. \end{aligned}$$
Remark 7
A part of output of \(\mathsf{Setup}(1^\lambda , n)\), \(\{ B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,3; j=1,\ldots ,4; l=1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}^*_1 :{=}(\varvec{b}^*_{1,1}, \ldots ,\varvec{b}^*_{1,n},\varvec{b}^*_{1,2n+1},\ldots ,\varvec{b}^*_{1,3n})\), while \({\mathbb {B}}^*_1 :{=}(\varvec{b}^*_{1,1},\ldots ,\varvec{b}^*_{1,4n})\) is identified with \(\{ B^*_{i,j}, \)
\(B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}\) in Remark 6. Decryption \(\mathsf{Dec}\) can be alternatively described as:
Theorem 2
The proposed NIPE scheme is adaptively payload-hiding against chosen plaintext attacks under the DLIN assumption.
For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_{1}, \mathcal{E}_{2\hbox {-}1}\) and \(\mathcal{E}_{2\hbox {-}2}\) whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \(\textstyle \mathsf{Adv}^\mathsf{NIPE, PH}_\mathcal{A}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1}}(\lambda ) + \sum _{h=1}^{\nu } \left( \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h\hbox {-}1}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h\hbox {-}2}}(\lambda ) \right) \)
\(+ \epsilon ,\) where \(\mathcal{E}_{2\hbox {-}h\hbox {-}1}(\cdot ) :{=}\mathcal{E}_{2\hbox {-}1}(h,\cdot )\), \(\mathcal{E}_{2\hbox {-}h\hbox {-}2}(\cdot ) :{=}\mathcal{E}_{2\hbox {-}2}(h,\cdot )\), \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries and \(\epsilon :{=}(11 \nu + 6)/q\).
8 ZIPE scheme with constant-size ciphertexts
8.1 Dual orthonormal basis generator
We describe random dual orthonormal basis generator \({{\mathcal{G}^\mathsf{ZIPE, CT}_\mathsf{ob}}}\) below, which is used as a subroutine in the proposed Zero IPE scheme. Since the definition is employed for the scheme with \(w= 5\) in Sect. 10, we describe \({{\mathcal{G}^\mathsf{ZIPE, CT}_\mathsf{ob}}}\) for general \(w\). (We use only the cases with \(w= 4,5\)).
$$\begin{aligned}&{{\mathcal{G}^\mathsf{ZIPE, CT}_\mathsf{ob}}}(1^\lambda , w, n): \ \ \mathsf{param}_\mathbb {G}:{=}(q,\mathbb {G},\mathbb {G}_T,{G},e) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathcal{G}_\mathsf{bpg}(1^\lambda ), \ {N}:{=}wn + 1, \\&\ \psi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}_q^{\,\times }}, \ g_T :{=}e({G}, {G})^\psi , \ \mathsf{param}_{\mathbb {V}} :{=}(q, \mathbb {V}, \mathbb {G}_T, {\mathbb {A}}, e) :{=}{{\mathcal{G}_\mathsf{dpvs}}}(1^\lambda , {N}, \mathsf{param}_\mathbb {G}), \ \ \\&\ \mathsf{param}_{n} :{=}(\mathsf{param}_{\mathbb {V}}, \ g_T), \ X \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathcal{L}^{+}(w, n, \mathbb {F}_q), \ \mathrm {hereafter, \ } \\&\ \{ \chi _{0,0}, \chi _{0,j}, \chi _{i,0,l}, \mu _{i,j}, \mu '_{i,j,l} \}_{i,j =1,\ldots w; l=1,\ldots ,n} \ \mathrm {denotes} \mathrm { \ non\hbox {-}zero \ entries \ of \ } X, \\&\ \mathrm { where \ } \{ \mu _{i,j}, \mu '_{i,j,l} \} \mathrm { \ are \ non\hbox {-}zero \ entries \ of \ submatrices \ } X_{i,j} \mathrm { \ of \ } X \\&\ \mathrm { as \ given \ in \ Eqs.\,(5) \ and \ (1)}, \ \ (\vartheta _{i,j})_{i,j=0,\ldots ,wn} :{=}\psi \cdot (X^{\text {T}})^{-1}, \\&\ B_{0,0} :{=}\chi _{0,0} G, \ B_{0,j} :{=}\chi _{0,j} G, \ B_{i,0,l} :{=}\chi _{i,0,l} G, \ B_{i,j} :{=}\mu _{i,j} G, \ B'_{i,j,l} :{=}\mu '_{i,j,l} G \\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mathrm {for} \ i,j=1,\ldots ,w; l=1,\ldots ,n, \\&\ {\textstyle \varvec{b}^{*}_{i} :{=}(\vartheta _{i,1}, \ldots , \vartheta _{i,{N}})_{{\mathbb {A}}} = \sum _{j=0}^{wn} \vartheta _{i,j} \varvec{a}_{j} \ \mathrm {for} \ i=0,\ldots ,wn, \ {\mathbb {B}}^{*} :{=}(\varvec{b}^{*}_0,\ldots ,\varvec{b}^{*}_{wn}), } \\&\ \ \ \mathrm{return} \ \ (\mathsf{param}_{n}, \{ B_{0,0}, B_{0,j}, B_{i,0,l}, B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,w; l=1,\ldots ,n}, {\mathbb {B}}^* ). \end{aligned}$$
Remark 8
\(\{ B_{0,0}, B_{0,j}, B_{i,0,l}, B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,w; l=1,\ldots ,n}\) is identified with basis \({\mathbb {B}} :{=} (\varvec{b}_{0},\ldots ,\)
\(\varvec{b}_{wn})\) dual to \({\mathbb {B}}^*\) as in Remark 2.
8.2 Construction and security
In the description of the scheme, we assume that input vector, \(\vec {x} :{=}(x_1, \ldots , x_n)\), has an index l (\(1 \le l \le n-1\)) with \(x_l \ne 0\), and that input vector, \(\vec {v} :{=}(v_1, \ldots , v_n)\), satisfies \(v_n \ne 0\). The plaintext space is \({\mathbb {G}}_T\).
$$\begin{aligned}&\mathsf{Setup}(1^\lambda , \ n): \\&\ \ \ (\mathsf{param}_{n}, \{ B_{0,0}, B_{0,j}, B_{i,0,l}, B_{i,j}, B'_{i,j,l} \}_{i,j =1,\ldots ,4; \, l=1,\ldots ,n}, {\mathbb {B}}^*) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}^\mathsf{ZIPE, CT}_\mathsf{ob}}}(1^\lambda , 4, n), \\&\ \ \ {\widehat{\mathbb {B}}}^* :{=}(\varvec{b}^*_{0},\ldots ,\varvec{b}^*_{n}, \varvec{b}^*_{2n+1},\ldots ,\varvec{b}^*_{3n}), \\&\ \ \ \mathrm {return} \ \ \mathsf{pk} :{=}(1^\lambda , \mathsf{param}_{n}, \{ B_{0,0}, B_{0,j}, B_{i,0,l}, B_{i,j}, B'_{i,j,l} \}_{i=1,4; j=1,\ldots ,4; l=1,\ldots ,n}), \\&\quad \mathsf{sk} :{=}{\widehat{\mathbb {B}}}^{*}. \\&\mathsf{KeyGen}(\mathsf{pk}, \ \mathsf{sk}, \ \vec {v}) : \ \delta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \vec {\varphi } \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n, \ \varvec{k}^* :{=}( \ 1, \ \overbrace{\ \delta \vec {v}, \ }^n \ \overbrace{\ 0^{n}, \ }^n \ \overbrace{\ \vec {\varphi }, \ }^n \ \overbrace{\ 0^{n}\ }^n \ )_{{\mathbb {B}}^*}, \\&\quad \mathrm {return} \ \ \mathsf{sk}_{\vec {v}} :{=}\varvec{k}^*. \\&\mathsf{Enc}(\mathsf{pk}, \ m, \ \vec {x}): \ \ \ \omega , \eta , \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \ \ \textstyle C_0 :{=}\zeta B_{0,0} + \sum _{l=1}^n x_l (\omega B_{1,0,l} + \eta B_{4,0,l}), \\&\ \ \ c_3 :{=}g_T^\zeta m, \textstyle \ \ \ C_{1,j} :{=}\omega B_{1,j} + \eta B_{4,j}, \ \ \\&\textstyle \ \ \ C_{2,j} :{=}\zeta B_{0,j} + \sum _{l=1}^n x_l (\omega B'_{1,j,l} + \eta B'_{4,j,l}) \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \mathrm {return} \ \ \mathsf{ct}_{\vec {x}} :{=}(\vec {x}, C_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3). \\&\mathsf{Dec}(\mathsf{pk},\ \mathsf{sk}_{\vec {v}} :{=}\varvec{k}^*, \ \mathsf{ct}_{\vec {x}} :{=}(\vec {x}, C_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3)) : \\&\ \ \ \text {Parse} \ \varvec{k}^* \ \text {as a} \ (4n+1)\text {-tuple } (K^*_0,\ldots ,K^*_{4n}) \in {\mathbb {G}}^{4n+1}, \ \\&\ \ \ \textstyle D^*_j :{=}\sum _{l=1}^{n-1} x_l K^*_{(j-1)n+l} \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \textstyle F :{=}e(C_0, K_0^*) \cdot \prod _{j=1}^4 \left( e(C_{1,j},D^*_j) \cdot e(C_{2,j},K^*_{jn}) \right) , \ \ \ \mathrm {return} \ \ m' :{=}c_3/F. \end{aligned}$$
Remark 9
A part of output of \(\mathsf{Setup}(1^\lambda , n)\), \(\{ B_{0,0}, B_{0,j}, B_{i,0,l}, B_{i,j}, B'_{i,j,l}\}_{i=1,4; j=1,\ldots ,4; l= 1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}:{=}(\varvec{b}_{0} ,\ldots ,\varvec{b}_{n},\varvec{b}_{3n+1},\ldots ,\varvec{b}_{4n})\), while \({\mathbb {B}}:{=}(\varvec{b}_{0},\ldots ,\varvec{b}_{4n})\) is identified with \(\{ B_{0,0}, B_{0,j}, B_{i,0,l}, B_{i,j},\)
\(B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n }\) in Remark 8. Decryption \(\mathsf{Dec}\) can be alternatively described as:
[Correctness] Using the alternate decryption \(\mathsf{Dec}'\), \(F = e(\varvec{c},\varvec{k}) = g_T^{\zeta + \omega \delta \vec {x} \cdot \vec {v}} = g_T^{\zeta } \ \ \ \mathrm {if} \ \vec {x} \cdot \vec {v} = 0\).
Remark 10
The proposed ZIPE in this section employs a single basis, \({\mathbb {B}}\), generated by \(X \in GL(4n+1,\mathbb {F}_q)\) [or \(X \in \mathcal{L}^{+}(4, n, \mathbb {F}_q)\) of Eq. (5)], and a ciphertext can be expressed as \((\varvec{c}, g_T^{\zeta }m)\) with \(\varvec{c}= (\zeta , \, \omega \vec {x}, \, 0^{2n}, \, \eta \vec {x})_{{\mathbb {B}}}\) as shown in Remark 9. The proposed NIPE scheme in Sect. 6.3 employs two bases, \({\mathbb {B}}_0\) and \({\mathbb {B}}_1\), generated by \(X_0 \in GL(5,\mathbb {F}_q)\) and \(X_1 \in GL(4n,\mathbb {F}_q)\), and a ciphertext can be expressed as \((\varvec{c}_0, \varvec{c}_1, g_T^{\zeta }m)\) with \(\varvec{c}_0 :{=}(-\omega , \, 0, \, \zeta , \, 0, \, \eta _0)_{{\mathbb {B}}_0}\) and \(\varvec{c}_1 = ( \omega \vec {x}, \, 0^{2n}, \, \eta _1 \vec {x})_{{\mathbb {B}}_1}\). Hence, the ciphertext and secret key of the ZIPE scheme are shorter than those of the NIPE scheme (see Table 1 in Sect. 11). It is due to the difference of the decryption tricks in the ZIPE and NIPE schemes. Similarly to the fact on \(\mathcal{L}(4, n,\mathbb {F}_q)\) (for the security of the NIPE scheme) shown in Sect. 6.1, it is crucial for the security of the ZIPE scheme that \(\mathcal{L}^{+}(4, n, \mathbb {F}_q)\) is a subgroup of \(GL(4n+1, \mathbb {F}_q)\) (Lemma 3), and its security proof is made in the essentially same manner as explained in Sect. 6.1.
Theorem 3
The proposed ZIPE scheme is adaptively payload-hiding against chosen plaintext attacks under the DLIN assumption. For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_{1}\) and \(\mathcal{E}_{2}\), whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \(\mathsf{Adv}^\mathsf{ZIPE, PH}_\mathcal{A}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1}}(\lambda ) + \sum _{h=1}^{\nu } \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h}}(\lambda ) + \epsilon ,\) where \(\mathcal{E}_{2\hbox {-}h}(\cdot ) :{=}\mathcal{E}_{2}(h,\cdot )\), \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries, and \(\epsilon :{=}(11 \nu + 6)/q\).
Proof
To prove Theorem 3, we consider the following \((\nu +3)\) games. In Game 0, a part framed by a box indicates coefficients to be changed in a subsequent game. In the other games, a part framed by a box indicates coefficients that were changed in a game from the previous game.
Game 0 Original game. That is, the reply to a key query for \(\vec {v}\) is
where \(\delta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \varphi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\) and \(\vec {v} :{=}(v_1,\ldots ,v_n) \in \mathbb {F}_q^{\,n}\) with \(v_n \ne 0\). The challenge ciphertext for challenge plaintexts \((m^{(0)},m^{(1)})\) and \(\vec {x}\), \((\vec {x}, \varvec{c}_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3)\), which is identified with \((\vec {x}, \varvec{c}, c_3)\) in Remark 9, is
where \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}; \omega , \zeta , \eta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and \(\vec {x} :{=}(x_1,\ldots ,x_n) \in \mathbb {F}_q^{\,n}\) with \(x_l \ne 0\) for some \(l \in \{1,\ldots ,n-1\}\).
Game 1 Same as Game 0 except that the challenge ciphertext for challenge plaintexts \((m^{(0)},m^{(1)})\) and \(\vec {x}\) is
where \(\vec {r} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathsf{span}\langle \vec {x}, \vec {e}_n \rangle \), and all the other variables are generated as in Game 0.
\(\mathbf{Game~2}\hbox {-}{\varvec{h}} \mathbf{(} {\varvec{h}}\mathbf{=1,\ldots ,}{\varvec{\nu }}\mathbf{) }\) Game 2-0 is Game 1. Game 2-h is the same as Game 2-\((h-1)\) except that a part of the reply to the h-th key query for \(\vec {v}\), \(\varvec{k}^*\), is
where \(\vec {w} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\) and all the other variables are generated as in Game 2-\((h-1)\).
Game 3 Same as Game 2-\(\nu \) except that \(\varvec{c}\) and \(c_3\) of the challenge ciphertext are
where \(\zeta ' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) (i.e., independent from \(\zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\)), and all the other variables are generated as in Game 2-\(\nu \).
Let \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h)}(\lambda )\) (\(h=1,\ldots , \nu \)) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\) be the advantage of \(\mathcal{A}\) in Game \(0,1,2\hbox {-}h\) and 3, respectively. \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda )\) is equivalent to \(\mathsf{Adv}^\mathsf{ZIPE, PH}_\mathcal{A}(\lambda )\) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )=0\). We can evaluate the gaps between pairs of \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ),\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h)}(\lambda )\) for \(h=1,\ldots ,\nu \) using (variants of) Problems 1 and 2 as in the proof of Theorem 1. The following Lemma 13 gives a gap evaluation between \(\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}\nu \hbox {-}2)}(\lambda )\) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\), which requires a detailed proof for our ZIPE with constant-size ciphertexts (see Appendix “Proof of Lemma 13 in Sect. 8” for the proof). Combining the gap evaluations, we obtain Theorem 3. \(\square \)
Lemma 13
For any machine \(\mathcal{A}\), for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}\nu )}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )| \le 1/q. \)
9 ZIPE scheme with constant-size secret-keys
9.1 Dual orthonormal basis generator
We describe random dual orthonormal basis generator \({{\mathcal{G}^\mathsf{ZIPE, SK}_\mathsf{ob}}}\) below, which is used as a subroutine in the proposed ZIPE scheme, where \({{\mathcal{G}^\mathsf{ZIPE, CT}_\mathsf{ob}}}\) is defined in Sect. 7.1. Since the definition is employed for the scheme with \(w= 5\) in Sect. 10, we describe \({{\mathcal{G}^\mathsf{ZIPE, SK}_\mathsf{ob}}}\) for general \(w\). (We use only the cases with \(w= 4,5\)).
Remark 11
\(\{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,w; l=1,\ldots ,n}\) is identified with basis \({\mathbb {B}}^* :{=}(\varvec{b}^*_{0}, \ldots ,\)
\( \varvec{b}^*_{wn})\) dual to \({\mathbb {B}}\) as in Remark 6.
9.2 Construction and security
In the description of the scheme, we assume that input vector, \(\vec {v} :{=}(v_1, \ldots , v_n)\), has an index l (\(1 \le l \le n-1\)) with \(v_l \ne 0\), and that input vector, \(\vec {x} :{=}(x_1, \ldots , x_n)\), satisfies \(x_n \ne 0\). The plaintext space is \({\mathbb {G}}_T\).
$$\begin{aligned}&\mathsf{Setup}(1^\lambda , \ n): (\mathsf{param}_{n}, {\mathbb {B}}, \ \{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n} ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}^\mathsf{ZIPE, SK}_\mathsf{ob}}} \\&\quad (1^\lambda , 4, n), \\&\ \ \ {\widehat{\mathbb {B}}}:{=}(\varvec{b}_{0},\ldots ,\varvec{b}_{n}, \varvec{b}_{3n+1},\ldots ,\varvec{b}_{4n}), \\&\ \mathrm {return} \ \mathsf{pk} :{=}(1^\lambda , \mathsf{param}_{n}, {\widehat{\mathbb {B}}}), \mathsf{sk} :{=}\{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,3; j=1,\ldots ,4; l=1,\ldots ,n}. \\&\mathsf{KeyGen}(\mathsf{pk}, \ \mathsf{sk}, \ \vec {v}) : \ \ \ \delta , \varphi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \ \ \textstyle K^*_0 :{=}B^*_{0,0} + \sum _{l=1}^n v_l (\delta B^*_{1,0,l} + \varphi B^*_{3,0,l}), \\&\textstyle \ \ \ K^*_{1,j} :{=}\delta B^*_{1,j} + \varphi B^*_{3,j}, \ \ K^*_{2,j} :{=}B^*_{0,j} + \sum _{l=1}^n v_l (\delta B^{\prime \, *}_{1,j,l} + \varphi B^{\prime \, *}_{3,j,l}) \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \mathrm {return} \ \ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, K^*_0, \{ K^*_{1,j},K^*_{2,j} \}_{j=1,\ldots ,4}). \\&\mathsf{Enc}(\mathsf{pk}, \ m, \ \vec {x}): \omega , \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \vec {\eta } \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^{\,n}, \varvec{c}:{=}( \ \zeta , \overbrace{\ \omega \vec {x} \ }^n, \overbrace{\ 0^{n}\ }^n, \ \overbrace{\ 0^{n}\ }^n, \ \overbrace{\ \vec {\eta } \ }^n \ )_{{\mathbb {B}}}, \ \ c_3 :{=}g_T^\zeta m, \\&\ \ \ \mathrm {return} \ \ \mathsf{ct}_{\vec {x}} :{=}(\varvec{c}, c_3). \\&\mathsf{Dec}(\mathsf{pk},\ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, K^*_0, \{ K^*_{1,j},K^*_{2,j} \}_{j=1,\ldots ,4}), \ \mathsf{ct}_{\vec {x}} :{=}(\varvec{c}, c_3)) : \\&\ \ \ \text {Parse} \ \varvec{c}\ \text {as a} \ (4n+1)\text {-tuple } (C_0,\ldots ,C_{4n}) \in {\mathbb {G}}^{4n+1}, \\&\ \ \ \textstyle D_j :{=}\sum _{l=1}^{n-1} v_l C_{(j-1)n+l} \ \ \mathrm {for} \ j=1,\ldots ,4, \\&\ \ \ \textstyle F :{=}e(C_0, K_0^*) \cdot \prod _{j=1}^4 \left( e(D_j,K^*_{1,j}) \cdot e(C_{jn},K^*_{2,j}) \right) , \ \ \ \mathrm {return} \ \ m' :{=}c_3/F. \end{aligned}$$
Remark 12
A part of output of \(\mathsf{Setup}(1^\lambda , n)\), \(\{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,3; j=1,\ldots ,4; l=1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}^* :{=}(\varvec{b}^*_{0}, \ldots ,\varvec{b}^*_{n},\varvec{b}^*_{2n+1},\ldots ,\varvec{b}^*_{3n})\), while \({\mathbb {B}}^* :{=}(\varvec{b}^*_{0},\ldots ,\varvec{b}^*_{4n})\) is identified with \(\{ B^*_{0,0}, B^*_{0,j},\)
\( B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,\ldots ,4; j=1,\ldots ,4; l=1,\ldots ,n}\) in Remark 11. Decryption \(\mathsf{Dec}\) can be alternatively described as:
[Correctness] Using the alternate decryption \(\mathsf{Dec}'\), \(F = e(\varvec{c},\varvec{k}) = g_T^{\zeta + \omega \delta \vec {x} \cdot \vec {v}} = g_T^{\zeta } \ \ \ \mathrm {if} \ \vec {x} \cdot \vec {v} = 0\).
Theorem 4
The proposed ZIPE scheme is adaptively weakly-attribute-hiding against chosen plaintext attacks under the DLIN assumption. For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_{1}\) and \(\mathcal{E}_{2}\), whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \(\mathsf{Adv}^\mathsf{ZIPE, wAH}_\mathcal{A}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1}}(\lambda ) + \sum _{h=1}^{\nu } \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h}}(\lambda ) + \epsilon ,\) where \(\mathcal{E}_{2\hbox {-}h}(\cdot ) :{=}\mathcal{E}_{2}(h,\cdot )\), \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries, and \(\epsilon :{=}(11 \nu + 6)/q\).
Proof
To prove Theorem 4, we consider the following \((\nu +3)\) games. In Game 0, a part framed by a box indicates coefficients to be changed in a subsequent game. In the other games, a part framed by a box indicates coefficients that were changed in a game from the previous game.
Game 0 Original game. That is, the reply to a key query for \(\vec {v}\) is
where \(\delta , \varphi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and \(\vec {v} :{=}(v_1,\ldots ,v_n) \in \mathbb {F}_q^{\,n}\) with \(v_n \ne 0\). The challenge ciphertext for challenge plaintexts \((m^{(0)},m^{(1)})\) and \(\vec {x}\), \((\vec {x}, \varvec{c}_0, \{ C_{1,j},C_{2,j} \}_{j=1,\ldots ,4}, c_3)\), which is identified with \((\vec {x}, \varvec{c}, c_3)\) in Remark 9, is
where \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{0,1\}; \omega , \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \vec {\eta } \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\) and \(\vec {x} :{=}(x_1,\ldots ,x_n) \in \mathbb {F}_q^{\,n}\) with \(x_l \ne 0\) for some \(l \in \{1,\ldots ,n-1\}\).
Game 1 Same as Game 0 except that the challenge ciphertext for challenge plaintexts \((m^{(0)},m^{(1)})\) and \(\vec {x}\) is
where \(\vec {r} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^{\,n}\), and all the other variables are generated as in Game 0.
\(\mathbf{Game~2}\hbox {-}{\varvec{h}} \mathbf{(}{\varvec{h}}\mathbf{=1,\ldots },{\varvec{\nu }}\mathbf{)} \) Game 2-0 is Game 1. Game 2-h is the same as Game 2-\((h-1)\) except that a part of the reply to the h-th key query for \(\vec {v}\), \(\varvec{k}^*\), is
where \(\vec {w} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathsf{span}\langle \vec {v}, \vec {e}_n \rangle \) and all the other variables are generated as in Game 2-\((h-1)\).
Game 3 Same as Game 2-\(\nu \) except that \(\varvec{c}\) and \(c_3\) of the challenge ciphertext are
where \(\zeta ' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) (i.e., independent from \(\zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\)), \(\vec {x}' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\) (i.e., independent from \(\vec {x} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\)), and all the other variables are generated as in Game 2-\(\nu \).
Let \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h)}(\lambda )\) (\(h=1,\ldots , \nu \)) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\) be the advantage of \(\mathcal{A}\) in Game \(0,1,2\hbox {-}h\) and 3, respectively. \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda )\) is equivalent to \(\mathsf{Adv}^\mathsf{ZIPE, wAH}_\mathcal{A}(\lambda )\) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )=0\). We can evaluate the gaps between pairs of \(\mathsf{Adv}_\mathcal{A}^{(0)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ),\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h)}(\lambda )\) for \(h=1,\ldots ,\nu \) using (variants of) Problems 1 and 2 as in the proof of Theorem 1. The following Lemma 14 gives a gap evaluation between \(\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}\nu )}(\lambda )\) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\), which requires a detailed proof for our ZIPE with constant-size secret-keys (see Appendix “Proof of Lemma 14 in Sect. 9” for the proof). Combining the gap evaluations, we obtain Theorem 4. \(\square \)
Lemma 14
For any machine \(\mathcal{A}\), for any security parameter \(\lambda \), \( |\mathsf{Adv}_\mathcal{A}^{(2\hbox {-}\nu )}(\lambda ) - \mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )| \le 1/q. \)
10 Fully-attribute-hiding ZIPE scheme with constant-size secret-keys
By applying our technique to the fully-attribute-hiding ZIPE scheme in [27], we obtain a fully-attribute-hiding ZIPE scheme with short secret-keys.
10.1 Construction and security
In the description of the scheme, we assume that input vector, \(\vec {v} :{=}(v_1, \ldots , v_n)\), has an index l (\(1 \le l \le n-1\)) with \(v_l \ne 0\), and that input vector, \(\vec {x} :{=}(x_1, \ldots , x_n)\), satisfies \(x_n \ne 0\). The plaintext space is \({\mathbb {G}}_T\).
$$\begin{aligned}&\mathsf{Setup}(1^\lambda , \ n): (\mathsf{param}_{n}, {\mathbb {B}}, \{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i,j=1,\ldots ,5; l=1,\ldots ,n} ) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}{{\mathcal{G}^\mathsf{ZIPE, SK}_\mathsf{ob}}} \\&\quad (1^\lambda , 5, n), \\&\ \ \ {\widehat{\mathbb {B}}}:{=}(\varvec{b}_{0},\ldots ,\varvec{b}_{n}, \varvec{b}_{4n+1},\ldots ,\varvec{b}_{5n}), \\&\ \mathrm {return} \mathsf{pk} :{=}(1^\lambda , \mathsf{param}_{n}, {\widehat{\mathbb {B}}}), \mathsf{sk} :{=}\{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,4; j=1,\ldots ,5; l=1,\ldots ,n}. \\&\mathsf{KeyGen}(\mathsf{pk}, \ \mathsf{sk}, \ \vec {v}) : \ \ \ \delta , \varphi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \ \ \textstyle K^*_0 :{=}B^*_{0,0} + \sum _{l=1}^n v_l (\delta B^*_{1,0,l} + \varphi B^*_{4,0,l}), \\&\textstyle \ \ \ K^*_{1,j} :{=}\delta B^*_{1,j} + \varphi B^*_{4,j}, \ \ K^*_{2,j} :{=}B^*_{0,j} + \sum _{l=1}^n v_l (\delta B^{\prime \, *}_{1,j,l} + \varphi B^{\prime \, *}_{4,j,l}) \ \ \mathrm {for} \ j=1,\ldots ,5, \\&\ \ \ \mathrm {return} \ \ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, K^*_0, \{ K^*_{1,j},K^*_{2,j} \}_{j=1,\ldots ,5}). \\&\mathsf{Enc}(\mathsf{pk}, \ m, \ \vec {x}): \ \ \ \omega , \zeta \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q, \ \vec {\eta } \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n, \ \ \ \varvec{c}:{=}( \ \zeta , \ \overbrace{\ \omega \vec {x} \ }^n, \ \overbrace{\ 0^{2n}\ }^{2n}, \ \overbrace{\ 0^{n}\ }^n, \ \overbrace{\ \vec {\eta } \ }^n \ )_{{\mathbb {B}}}, \ \ \ \\&\quad c_3 :{=}g_T^\zeta m, \\&\ \ \ \mathrm {return} \ \ \mathsf{ct}_{\vec {x}} :{=}(\varvec{c}, c_3). \\&\mathsf{Dec}(\mathsf{pk},\ \mathsf{sk}_{\vec {v}} :{=}(\vec {v}, K^*_0, \{ K^*_{1,j},K^*_{2,j} \}_{j=1,\ldots ,5}), \ \mathsf{ct}_{\vec {x}} :{=}(\varvec{c}, c_3)) : \\&\ \ \ \text {Parse} \ \varvec{c}\ \text {as a} \ (5n+1)\text {-tuple } (C_0,\ldots ,C_{5n}) \in {\mathbb {G}}^{5n+1}, \\&\ \ \ \textstyle D_j :{=}\sum _{l=1}^{n-1} v_l C_{(j-1)n+l} \ \ \mathrm {for} \ j=1,\ldots ,5, \\&\ \ \ \textstyle F :{=}e(C_0, K_0^*) \cdot \prod _{j=1}^5 \left( e(D_j,K^*_{1,j}) \cdot e(C_{jn},K^*_{2,j}) \right) , \ \ \ \mathrm {return} \ \ m' :{=}c_3/F. \end{aligned}$$
Remark 13
A part of output of \(\mathsf{Setup}(1^\lambda , n)\), \(\{ B^*_{0,0}, B^*_{0,j}, B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,4; j=1,\ldots ,5; l=1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}^* :{=}(\varvec{b}^*_{0}, \ldots ,\varvec{b}^*_{n},\varvec{b}^*_{3n+1},\ldots ,\varvec{b}^*_{4n})\), while \({\mathbb {B}}^* :{=}(\varvec{b}^*_{0},\ldots ,\varvec{b}^*_{5n})\) is identified with \(\{ B^*_{0,0}, B^*_{0,j},\)
\( B^*_{i,0,l}, B^*_{i,j}, B^{\prime \, *}_{i,j,l} \}_{i=1,\ldots ,5; j=1,\ldots ,5; l=1,\ldots ,n}\) in Remark 11. Decryption \(\mathsf{Dec}\) can be alternatively described as:
[Correctness] Using the alternate decryption \(\mathsf{Dec}'\), \(F = e(\varvec{c},\varvec{k}) = g_T^{\zeta + \omega \delta \vec {x} \cdot \vec {v}} = g_T^{\zeta } \ \ \ \mathrm {if} \ \vec {x} \cdot \vec {v} = 0\).
Theorem 5
The proposed ZIPE scheme is adaptively fully-attribute-hiding against chosen plaintext attacks under the DLIN assumption.
For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_{0\hbox {-}1}, \mathcal{E}_{0\hbox {-}2}, \mathcal{E}_{1\hbox {-}1}, \mathcal{E}_{1\hbox {-}2\hbox {-}1}\) and \(\mathcal{E}_{1\hbox {-}2\hbox {-}2}\), whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \( \mathsf{Adv}^\mathsf{ZIPE, AH}_\mathcal{A}(\lambda ) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{0\hbox {-}1}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1\hbox {-}1}}(\lambda ) + \sum _{h=1}^{\nu } \left( \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{0\hbox {-}2\hbox {-}h}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1\hbox {-}2\hbox {-}h\hbox {-}1}}(\lambda ) \right. \left. +\mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1\hbox {-}2\hbox {-}h\hbox {-}2}}(\lambda ) \right) \)
\(+ \epsilon , \) where \(\mathcal{E}_{0\hbox {-}2\hbox {-}h}(\cdot ) :{=}\mathcal{E}_{0\hbox {-}2}(h,\cdot )\), \(\mathcal{E}_{1\hbox {-}2\hbox {-}h\hbox {-}1}(\cdot ) :{=}\mathcal{E}_{1\hbox {-}2\hbox {-}1}(h,\cdot )\), \(\mathcal{E}_{1\hbox {-}2\hbox {-}h\hbox {-}2}(\cdot ) :{=}\mathcal{E}_{1\hbox {-}2\hbox {-}2}(h,\cdot )\), \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries and \(\epsilon :{=}(29 \nu + 17)/q\).
Proof
First, we execute a preliminary game transformation from Game 0 (original security game in Definition 6) to Game 0’, which is the same as Game 0 except that flip a coin \(t \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\) before setup, and the game is aborted in the challenge step if \(t \ne s\). We define that \(\mathcal{A}\) wins with probability 1 / 2 when the game is aborted (and the advantage in Game 0’ is \(\mathsf{Pr}[ \mathcal{A} \ \mathrm {wins} \ ] - 1/2\) as well). Since t is independent from s, the game is aborted with probability 1/2. Hence, the advantage in Game 0’ is a half of that in Game 0, i.e., \(\mathsf{Adv}^\mathsf{IPE, AH, 0'}_\mathcal{A}(\lambda ) = 1/2 \cdot \mathsf{Adv}^\mathsf{IPE, AH}_\mathcal{A}(\lambda )\). Moreover, \(\Pr [\mathcal{A}\ \mathrm {wins}] = 1/2 \cdot (\Pr [\mathcal{A}\ \mathrm {wins} \ | \ t=0] + \Pr [\mathcal{A}\ \mathrm {wins} \ | \ t=1])\) in Game 0’ since t is uniformly and independently generated.
As for the conditional probability with \(t=0\), it holds that, for any adversary \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_1\) and \(\mathcal{E}_{2}\), whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), in Game 0’, \( \textstyle \Pr [ \mathcal{A} \ \mathrm {wins}\ | \ t=0] - 1/2 \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_1}(\lambda ) + \sum _{h=1}^{\nu } \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h}}(\lambda ) + \epsilon , \) where \(\mathcal{E}_{2\hbox {-}h}(\cdot ) :{=}\mathcal{E}_{2}(h,\cdot )\) and \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries and \(\epsilon :{=}(6 \nu + 5)/q\). This is obtained in the same manner as the weakly attribute-hiding security of the OT10 IPE in the full version of [25]: Since the difference between our IPE and the OT10 IPE is only the dimension of the hidden subspaces, i.e., the former has 2n and the latter has n, the weakly attribute-hiding security of the OT10 IPE implies the security with \(t=0\) of our IPE.
As for the conditional probability with \(t=1\), i.e., \(\Pr [ \mathcal{A} \ \mathrm {wins}\ | \ t=1]\), Lemma 15 holds. Therefore, \( \mathsf{Adv}^\mathsf{ZIPE, AH}_\mathcal{A}(\lambda ) = 2 \cdot \mathsf{Adv}^\mathsf{ZIPE, AH, 0'}_\mathcal{A}(\lambda ) = \Pr [\mathcal{A}\ \mathrm {wins} \ | \ t=0] + \Pr [\mathcal{A}\ \mathrm {wins} \ | \ t=1] -1 = ( \Pr [\mathcal{A}\ \mathrm {wins} \ | \ t=0] - 1/2 ) + (\Pr [\mathcal{A}\ \mathrm {wins} \ | \ t=1] - 1/2) \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{0\hbox {-}1}}(\lambda ) + \sum _{h=1}^{\nu } \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{0\hbox {-}2\hbox {-}h}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1\hbox {-}1}}(\lambda ) + \sum _{h=1}^{\nu } \left( \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1\hbox {-}2\hbox {-}h\hbox {-}1}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{1\hbox {-}2\hbox {-}h\hbox {-}2}}(\lambda ) \right) + \epsilon , \) where \(\epsilon :{=}(29 \nu + 17)/q\). \(\square \)
Lemma 15
For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_1, \mathcal{E}_{2\hbox {-}1}\) and \(\mathcal{E}_{2\hbox {-}2}\), whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), in Game 0’ (described in the proof of Theorem 5), \( \Pr [ \mathcal{A} \ \mathrm {wins}\ | \ t=1] - \frac{1}{2} \le \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_1}(\lambda ) + \sum _{h=1}^{\nu } \left( \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h\hbox {-}1}}(\lambda ) + \mathsf{Adv}^\mathsf{DLIN}_{\mathcal{E}_{2\hbox {-}h\hbox {-}2}}(\lambda ) \right) + \epsilon , \) where \(\mathcal{E}_{2\hbox {-}h\hbox {-}1}(\cdot ) :{=}\mathcal{E}_{2\hbox {-}1}(h,\cdot )\), \(\mathcal{E}_{2\hbox {-}h\hbox {-}2}(\cdot ) :{=}\mathcal{E}_{2\hbox {-}2}(h,\cdot )\), \(\nu \) is the maximum number of \(\mathcal{A}\)’s key queries and \(\epsilon :{=}(23 \nu + 12)/q\).
Proof
To prove Lemma 15, we consider the following \(4\nu +3\) games when \(t=1\). In Game 0’, a part framed by a box indicates coefficients to be changed in a subsequent game. In the other games, a part framed by a box indicates coefficients which were changed in a game from the previous game.
Game 0’
Same as Game 0 except that flip a coin \(t \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\) before setup, and the game is aborted in the challenge step if \(t \ne s\). In order to prove Lemma 15, we consider the case with \(t=1\). The reply to a key query for \(\vec {v}\) is:
where \(\delta , \varphi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\). The challenge ciphertext for challenge plaintext \(m :{=}m^{(0)} = m^{(1)}\) and vectors \((\vec {x}^{(0)},\vec {x}^{(1)})\) is:
where \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\) and \(\zeta ,\omega \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and \(\vec {\eta } \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q^n\). Here, we note that \(c_3\) is independent from bit b.
Game 1
Game 1 is the same as Game 0’ except that \(\varvec{c}_1\) of the challenge ciphertext for (challenge plaintext \(m :{=}m^{(0)} = m^{(1)}\) and) vectors \((\vec {x}^{(0)},\vec {x}^{(1)})\) is:
where \(\omega ' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 0’.
\(\mathbf{Game~2}\hbox {-}\varvec{h}\hbox {-}\mathbf{1} \mathbf{(}\varvec{h}\mathbf{=1,\ldots ,}\varvec{\nu }\mathbf{)}\)
Game 2-0-4 is Game 1. Game 2-h-1 is the same as Game 2-\((h-1)\)-4 except that \(\varvec{c}_1\) of the challenge ciphertext for (challenge plaintext \(m :{=}m^{(0)} = m^{(1)}\) and) vectors \((\vec {x}^{(0)},\vec {x}^{(1)})\) is:
where \(\omega ', \omega ''_0, \omega ''_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 2-\((h-1)\)-4.
\(\mathbf{Game~2}\hbox {-}\varvec{h}\hbox {-}\mathbf{2} \mathbf{(}\varvec{h}\mathbf{=1,\ldots },\varvec{\nu }\mathbf{)}\)
Game 2-h-2 is the same as Game 2-h-1 except that the reply to the h-th key query for \(\vec {v}\) is:
where \(\sigma ' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 2-h-1.
\(\mathbf{Game~2}\hbox {-}\varvec{h}\hbox {-}\mathbf{3} \mathbf{(}\varvec{h}\mathbf{=1,\ldots ,}\varvec{\nu }\mathbf{)}\)
Game 2-h-3 is the same as Game 2-h-2 except that \(\varvec{c}_1\) of the challenge ciphertext for (challenge plaintexts \(m :{=}m^{(0)} = m^{(1)}\) and) vectors \((\vec {x}^{(0)},\vec {x}^{(1)})\) is:
where \(\omega '_0, \omega '_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 2-h-2.
\(\mathbf{Game~2}\hbox {-}\varvec{h}\hbox {-}\mathbf{4} \mathbf{(}\varvec{h}\mathbf{=1,\ldots ,}\varvec{\nu }\mathbf{)}\)
Game 2-h-4 is the same as Game 2-h-3 except that the reply to the h-th key query for \(\vec {v}\) is:
where \(\sigma '' \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 2-h-3.
Game 3
Game 3 is the same as Game 2-\(\nu \)-4 except that \(\varvec{c}_1\) of the challenge ciphertext for (challenge plaintexts \(m :{=}m^{(0)} = m^{(1)}\) and) vectors \((\vec {x}^{(0)},\vec {x}^{(1)})\) is:
where \(\omega _0,\omega _1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\mathbb {F}_q\) and all the other variables are generated as in Game 2-\(\nu \)-4. Here, we note that \(\varvec{c}_1\) is independent from bit \(b \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\{ 0,1 \}\).
Let \(\mathsf{Adv}_\mathcal{A}^{(0')}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}1)}(\lambda ),\ldots , \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}h\hbox {-}4)}(\lambda )\) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\) be the advantage of \(\mathcal{A}\) in Game \(0',1,2\hbox {-}h\hbox {-}1,\ldots ,2\hbox {-}h\hbox {-}4\) and 3 when \(t=1\), respectively. \(\mathsf{Adv}_\mathcal{A}^{(0')}(\lambda )\) is equivalent to the left-hand side of Eq. (15) and \(\mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )=0\).
We can evaluate the gaps between pairs of neighboring games, \(\mathsf{Adv}_\mathcal{A}^{(0')}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(1)}(\lambda ), \ldots ,\)
\( \mathsf{Adv}_\mathcal{A}^{(2\hbox {-}\nu \hbox {-}4)}(\lambda ), \mathsf{Adv}_\mathcal{A}^{(3)}(\lambda )\), similarly to [27]. This completes the proof of Lemma 15. \(\square \)
11 Comparison
Table 1
Comparison with IPE schemes in [4], where \(|\mathbb {G}|\), \(|\mathbb {G}_T|\), \(|\mathbb {F}_q|\), P and M represent size of an element of \(\mathbb {G}\), that of \({\mathbb {G}}_T\), that of \(\mathbb {F}_q\), pairing operation, and scalar multiplication on \({\mathbb {G}}\), respectively
AL10 [4] ZIPE with short CT | AL10 [4] NIPE with short CT | Proposed ZIPE with short CT | Proposed NIPE with short CT | Proposed ZIPE with short SK | Proposed NIPE with short SK | Proposed fully-AH ZIPE with short SK | |
|---|---|---|---|---|---|---|---|
Security | Adaptive PH | Co-selective PH | Adaptive PH | Adaptive PH | Adaptive weakly-AH | Adaptive PH | Adaptive fully-AH |
Assump. | DLIN and DBDH | DLIN and DBDH | DLIN | DLIN | DLIN | DLIN | DLIN |
IP rel. | Zero | Non-zero | Zero | Non-zero | Zero | Non-zero | Zero |
PK size |
\((n+11)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
\((n + 11)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
\((10 n + 13)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
\((8 n + 23)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
\((10 n + 13)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
\((8 n + 23)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
\((12 n + 16)|\mathbb {G}|\) + \(|\mathbb {G}_T|\)
|
SK size |
\((n + 6) |\mathbb {G}| + (n - 1) |\mathbb {F}_q|\)
|
\((n + 6) |\mathbb {G}|\)
|
\((4 n + 1) |\mathbb {G}|\)
|
\((4 n + 5) |\mathbb {G}|\)
| 9\(|\mathbb {G}|\)
| 13\(|\mathbb {G}|\)
| 11\(|\mathbb {G}|\)
|
CT size | 9\(|\mathbb {G}| + |\mathbb {G}_T|+ |\mathbb {F}_q|\)
| 9\(|\mathbb {G}|+ |\mathbb {G}_T|\)
| 9\(|\mathbb {G}|+ |\mathbb {G}_T|\)
| 13\(|\mathbb {G}|+ |\mathbb {G}_T|\)
|
\((4 n + 1)|\mathbb {G}|+ |\mathbb {G}_T|\)
|
\((4 n + 5)|\mathbb {G}|+ |\mathbb {G}_T|\)
|
\((5 n + 1)|\mathbb {G}|+ |\mathbb {G}_T|\)
|
Dec time | 9P + nM | 9P + nM | 9P + \(4(n-1)\)M | 13P + \(4(n-1)\)M | 9P + \(4(n-1)\)M | 13P + \(4(n-1)\)M | 11P + \(5(n-1)\)M |
Table 1 compares the proposed ZIPE and NIPE schemes (ZIPE with short ciphertexts in Sect. 8, NIPE with short ciphertexts in Sect. 6, ZIPE with short secret-keys in Sect. 9, NIPE with short secret-keys in Sect. 7, and fully-attribute-hiding ZIPE with short secret-keys in Sect. 10) with the ZIPE and NIPE schemes in [4] that are secure under standard assumptions.
12 Hierarchical ZIPE scheme with constant-size ciphertexts
The proposed hierarchical ZIPE (HIPE) scheme with short ciphertexts is constructed by using two vector spaces, 5-dimensional \(\mathbb {V}_0\) and 4n-dimensional \(\mathbb {V}_1\), where hierarchical vector \((\vec {v}_1,\ldots ,\vec {v}_\ell )\) (resp. \((\vec {x}_1,\ldots ,\vec {x}_{\ell '})\)) of secret-key (resp. ciphertext) is embedded in an element in \(\mathbb {V}_1\). The delegation mechanism is based on the payload hiding HIPE scheme given in Appendix H.3 in the full version of [25].
12.1 Dual orthonormal basis generator
We describe random dual orthonormal basis generator \({{\mathcal{G}^\mathsf{HIPE, CT}_\mathsf{ob}}}\) below, which is used as a subroutine in the proposed hierarchical ZIPE scheme.
$$\begin{aligned}&\textstyle {{\mathcal{G}^\mathsf{HIPE, CT}_\mathsf{ob}}}(1^\lambda , 4, \vec {n} :{=}(d; n_1, \ldots , n_d)): \ n :{=}\sum _{t=1}^d n_t, \\&\ \ \ \mathsf{param}_\mathbb {G}:{=}(q,\mathbb {G},\mathbb {G}_T,{G},e) \mathop {\leftarrow }\limits ^{\ \mathsf{R}}\mathcal{G}_\mathsf{bpg}(1^\lambda ), \ \ \ {N}_0 :{=}5, \ {N}_1 :{=}4 n, \\&\ \ \ \mathsf{param}_{\mathbb {V}_t} :{=}(q, \mathbb {V}_t, \mathbb {G}_T, {\mathbb {A}}_t, e) :{=}{{\mathcal{G}_\mathsf{dpvs}}}(1^\lambda , {N}_t, \mathsf{param}_\mathbb {G}) \ \ \mathrm {for} \ t=0,1, \\&\ \ \ \psi \mathop {\leftarrow }\limits ^{\ \mathsf{U}}{\mathbb {F}_q^{\,\times }}, \ g_T :{=}e({G}, {G})^\psi , \ \mathsf{param}_{\vec {n}} :{=}(\vec {n}, \ \{ \mathsf{param}_{\mathbb {V}_t} \}_{t=0,1}, \ g_T), \\&\ \ \ X_0 :{=}(\chi _{0,i,j})_{i,j=1,\ldots ,5} \mathop {\leftarrow }\limits ^{\ \mathsf{U}}GL(N_0, \mathbb {F}_q), \ X_1 \mathop {\leftarrow }\limits ^{\ \mathsf{U}}\widetilde{\mathcal{L}}(4, n, \mathbb {F}_q), \ \mathrm {hereafter, \ } \\&\ \ \ \ \{ \mu _{i,j}, \mu '_{i,j,l} \}_{i,j =1,\ldots 4; l=1,\ldots ,n} \ \mathrm {denotes \ non\hbox {-}zero \ entries \ of \ } X_1 \mathrm { \ as \ in \ Eq.\,(4)}, \\&\ \ \ {\textstyle \varvec{b}_{0,i} :{=}(\chi _{0,i,1}, \ldots , \chi _{0,i,5})_{{\mathbb {A}}} = \sum _{j=1}^{5} \chi _{0,i,j} \varvec{a}_{j} \ \mathrm {for} \ i=1,\ldots ,5, \ {\mathbb {B}}_0 :{=}(\varvec{b}_{0,1},\ldots ,\varvec{b}_{0,5}), } \\&\ \ \ B_{i,j} :{=}\mu _{i,j} G, \ B'_{i,j,l} :{=}\mu '_{i,j,l} G \ \ \mathrm {for} \ i,j=1,\ldots ,4; l=1,\ldots ,n, \\&\ \ \ \mathrm {for} \ t=0,1, \ (\vartheta _{t,i,j})_{i,j=1,\ldots ,N_t} :{=}\psi \cdot (X_t^{\text {T}})^{-1}, \\&\ \ {\textstyle \varvec{b}^{*}_{t,i} :{=}(\vartheta _{t,i,1}, \ldots , \vartheta _{t,i,{N}_t})_{{\mathbb {A}}} \!=\! \sum _{j=1}^{{N}_t} \vartheta _{t,i,j} \varvec{a}_{j} \ \mathrm {for} \ i=1,\ldots ,N_t, \ {\mathbb {B}}_t^{*} :{=}(\varvec{b}^{*}_{t,1},\ldots ,\varvec{b}^{*}_{t,{N}_t}), } \\&\ \ \ \mathrm{return} \ \ (\mathsf{param}_{\vec {n}}, {\mathbb {B}}_0, {\mathbb {B}}_0^*, \{ B_{i,j}, B'_{i,j,l} \}_{i,j=1,\ldots ,4; l=1,\ldots ,n}, {\mathbb {B}}_1^* ). \end{aligned}$$
Remark 14
Let
where a blank element in the matrix denotes \(0 \in {\mathbb {G}}\). \({\mathbb {B}}_1\) is the dual orthonormal basis of \({\mathbb {B}}^*_1\), i.e., \(e(\varvec{b}_{1,i},\varvec{b}^*_{1,i}) = g_T\) and \(e(\varvec{b}_{1,i},\varvec{b}^*_{1,j}) = 1\) for \(1 \le i \ne j \le 4n\).
12.2 Construction and security
In the description of the scheme, we assume that input vector, \(\vec {x}_t :{=}(x_{t,1}, \ldots , x_{t,n_t})\), has an index \((t,l) \ne (1,1)\) with \(x_{t,l} \ne 0\), and that level-1 input vector, \(\vec {v}_1 :{=}(v_{1,1}, \ldots , v_{1,n_1})\), satisfies \(v_{1,1} \ne 0\). The plaintext space is \({\mathbb {G}}_T\).
Remark 15
A part of output of \(\mathsf{Setup}(1^\lambda , \vec {n})\), \(\{ B_{i,j}, B'_{i,j,l} \}_{i=1,4; j=1,\ldots ,4; l=1,\ldots ,n}\), can be identified with \({\widehat{\mathbb {B}}}_1 :{=}(\varvec{b}_{1,1}, \ldots ,\varvec{b}_{1,n},\varvec{b}_{1,3n+1},\ldots ,\varvec{b}_{1,4n})\) through the form of Eq. (6), while \({\mathbb {B}}_1 :{=}(\varvec{b}_{1,1},\ldots ,\varvec{b}_{1,4n})\) is identified with \(\{ B_{i,j}, \)
\(B'_{i,j,l} \}_{i,j=1,\ldots ,4; \, l=1,\ldots ,n}\) by Eq. (6). Decryption \(\mathsf{Dec}\) can be alternatively described as:
[Correctness] Using the alternate decryption \(\mathsf{Dec}'\), \( F = e(\varvec{c}_0,\varvec{k}^*_0) \cdot e(\varvec{c}_1, \varvec{k}^*_1) = g_T^{-\omega s_0 + \zeta } g_T^{\omega \sum _{t=1}^\ell s_t} \)
\(= g_T^{\zeta } \ \ \ \mathrm {if} \ \ell \le \ell ' \ \ \mathrm {and} \ \ \vec {x}_t \cdot \vec {v}_t = 0 \ \mathrm {for} \ t=1,\ldots ,\ell . \)
The definition of adaptively payload-hiding security and the advantage \(\mathsf{Adv}^\mathsf{HIPE, PH}_\mathcal{A}(\lambda )\) of adversary \(\mathcal{A}\) can be obtained through a straightforward extension of that of HIBE, e.g., [15], with replacing ID-matching by vector-orthogonality.
Theorem 6
The proposed HIPE scheme is adaptively payload-hiding against chosen plaintext attacks under the DLIN assumption.
For any machine \(\mathcal{A}\), there exist probabilistic machines \(\mathcal{E}_1\) and \(\mathcal{E}_2\), whose running times are essentially the same as that of \(\mathcal{A}\), such that for any security parameter \(\lambda \), \( \mathsf{Adv}^\mathsf{HIPE, PH}_\mathcal{A}(\lambda ) \le \mathsf{Adv}_{\mathcal{E}_1}^\mathsf{DLIN}(\lambda ) + \sum _{h=1}^\nu \mathsf{Adv}_{\mathcal{E}_{2\hbox {-}h}}^\mathsf{DLIN}(\lambda ) + \epsilon , \) where \(\mathcal{E}_{2\hbox {-}h}(\cdot ) :{=}\mathcal{E}_{2}(h,\cdot )\), \(\nu \) is the maximum number of adversary \(\mathcal{A}\)’s key queries, and \(\epsilon = (11 \nu + 6)/q\).
13 Concluding remarks
The technique with using special type matrices shown in this paper can reduce the size of ciphertexts or secret-keys of adaptively secure FE schemes in [25] from O(dn) to O(d), where d is the number of sub-universes of attributes, and n is the maximal length of attribute vectors. A key-policy attribute-based encryption (ABE) system with constant-size ciphertext [5] is selectively secure in the standard model. Therefore, it is an interesting open problem to realize an adaptively secure and constant-size ciphertext ABE scheme.
Acknowledgments
The authors would like to thank Sherman S.M. Chow for his invaluable comments and suggestions on our preliminary manuscript. We also appreciate anonymous reviewers of CANS 2011 for their valuable comments.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
