Jie Chen

Junqing Gong
email: junqing.gong@ens-lyon.fr

ABE with Tag Made Easy Concise Framework and New Instantiations in Prime-order Groups

Keywords: Attribute-based encryption, Predicate encoding, Prime-order bilinear group, Attribute-hiding, Delegation

Among all existing identity-based encryption (IBE) schemes in the bilinear group, Wat-IBE proposed by Waters [CRYPTO, 2009] and JR-IBE proposed by Jutla and Roy [AsiaCrypt, 2013] are quite special. A secret key and/or ciphertext in these two schemes consist of several group elements and an integer which is usually called tag. A series of prior work was devoted to extending them towards more advanced attribute-based encryption (ABE) including inner-product encryption (IPE), hierarchical IBE (HIBE). Recently, Kim et al. [SCN, 2016] introduced the notion of tag-based encoding and presented a generic framework for extending Wat-IBE. We may call these ABE schemes ABE with tag or tag-based ABE. Typically, a tag-based ABE construction is more efficient than its counterpart without tag. However the research on tag-based ABE severely lags-We do not know how to extend JR-IBE in a systematic way and there is no tag-based ABE for boolean span program even with Kim et al.'s generic framework.

In this work, we proposed a generic framework for tag-based ABE which is based on JR-IBE and compatible with Chen et al.'s (attributehiding) predicate encoding [EuroCrypt, 2015]. The adaptive security in the standard model relies on the k-linear assumption in the asymmetric prime-order bilinear group. This is the first framework showing how to extend JR-IBE systematically. In fact our framework and its simple extension are able to cover most concrete tag-based ABE constructions in previous literature. Furthermore, since Chen et al.'s predicate encoding supports a large number of predicates including boolean span program, we can now give the first (both key-policy and ciphertext-policy) tagbased ABE for boolean span program in the standard model. Technically our framework is based on a simplified version of JR-IBE. Both the description and its proof are quite similar to the prime-order IBE derived School of Computer Science and Software Engineering.

Introduction

An attribute-based encryption [BSW11] (ABE) is an advanced cryptographic primitive supporting fine-grained access control.4 Such a system is established by an authority (a.k.a. key generation center, KGC for short). On a predicate P : X × Y → {0, 1} (and other system parameter), the authority publishes master public key mpk. Each user will receive a secret key sk y associated with a policy y ∈ Y when he/she joins in the system. A sender can create a ciphertext ct x associated with an attribute x ∈ X . A user holding sk y can decrypt the ciphertext ct x if P(x, y) = 1 holds, otherwise he/she will infer nothing about the plaintext. This notion covers many concrete public-key encryptions such as identity-based encryption [Sha84] (IBE), fuzzy IBE [SW05], ABE for boolean span program [GPSW06] and inner-product encryption [KSW08] (IPE).

The basic security requirement is collusion-resistance. Intuitively, it is required that two (or more) users who are not authorized to decrypt a ciphertext individually can not do that by collusion either. The notion is formalized via the so-called adaptive security model [BF01] where the adversary holding mpk can get secret keys sk y1 , . . . , sk yq for y 1 , . . . , y q ∈ Y and a challenge ciphertext ct * for target x * ∈ X via key extraction queries and challenge query respectively. We emphasize that the adversary can make oracle queries in an adaptive way. Although several weaker security models [CHK03,CW14] were introduced and widely investigated, this paper will focus on the adaptive security model.

Dual System Methodology and Predicate Encoding. A recent breakthrough in this field is the dual system methodology invented by Waters [Wat09] in 2009. He obtained the first adaptively secure IBE construction with compact parameters under standard complexity assumptions in the standard model. Inspired by his novel proof technique, the community developed many ABE constructions in the next several years. More importantly, the dual system methodology finally led us to a clean and systematic understanding of ABE. In 2014, Wee [Wee14] and Attrapadung [Att14] introduced the notion of predicate encod-ing5 and proposed their respective frameworks in the composite-order bilinear group. For certain predicate, if we can construct a predicate encoding for it, their frameworks will immediately give us a full-fledged ABE scheme for the predicate. This significantly simplifies the process of designing an ABE scheme. In fact the powerful frameworks allow them to give many new concrete constructions.

As Wee pointed out in his landmark work [Wee14], the framework reflects the common structures and properties shared among a large group of dual-system ABE schemes while predicate encodings give predicate-dependent features. More concretely, investigating the IBE instance derived from a framework will show the basic construction and proof technique captured the framework, then developing and analysing various predicate encodings will tell us how to extend the IBE instance to more complex cases.

Based on pioneering work by Wee [Wee14] and Attrapadung [Att14], a series of progresses have been made to support more efficient prime-order bilinear groups, employ more advanced proof techniques and more complex predicate encodings [CGW15,AC16,Att16,AC17,AY15].

ABE with Tag. The proof technique behind all these frameworks can be traced back to the work from Lewko and Waters [LW10,LW12] and their variants. However there are two dual-system IBE schemes located beyond these frameworks: one is the first dual-system IBE by Waters [Wat09] and the other one is the IBE scheme based on quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proof by Jutla and Roy [JR13]. In this paper, we call them Wat-IBE and JR-IBE, respectively, for convenience.

Apart from several group elements as usual, a ciphertext and/or a key of Wat-IBE and JR-IBE also include an integer which is called tag. This distinguishes them from other dual-system IBE schemes. We must emphasize that the tag plays an important role in the security proof and results in a different proof technique. Therefore we believe they deserve the terminology IBE with tag or tag-based IBE. Accordingly, an ABE with a tag in the ciphertext and/or key will be called ABE with tag or tag-based ABE.

There have been several concrete tag-based ABE schemes derived from Wat-IBE or JR-IBE such as [RCS12,RS14,Ram16,RS16]. Recently, Kim et al. [KSGA16] introduced the notion of tag-based encoding and developed a new framework based on Wat-IBE [Wat09], which is the first systematic study for tag-based ABE. All these work show that a tag-based ABE typically has shorter master public key and ciphertexts/keys, especially for complex predicates. This is a desirable advantage in most application settings of ABE.

Motivation

We review previous tag-based ABE in more detail. One may notice that there is no framework based on JR-IBE and all previous extensions were obtained in a somewhat ad-hoc manner. This immediately arises our first question.

Question 1: Is it possible to propose a framework based on JR-IBE?

We note that although both Wat-IBE and JR-IBE take the tag as an important component, their proof techniques are different. That is they use the tag in their own ways in the security proof. As a matter of fact, Wat-IBE requires distinct tags on ciphertext and secret key, respectively, while a secret key in JR-IBE has no tag. To our best knowledge, there is no explicit evidence demonstrating that a framework based on Wat-IBE (like that in [KSGA16]) implies a framework based on JR-IBE.

Furthermore, we surprisingly found that there is no tag-based ABE for boolean span program even with a generic framework! In fact, Kim et al. reported that their tag-based encoding is seemingly incompatible with linear secret sharing scheme which is a crucial ingredient of ABE for boolean span program. Hence it's natural to ask the following question.

Question 2: Is there any limitation on the predicate for tag-based ABE?

To some extent, we are asking whether the tag-based proof techniques (used for Wat-IBE and JR-IBE) makes a trade-off between efficiency and expressiveness? A very recent work [KSG + 17] proposed an ABE with tag supporting boolean span program based on Wat-IBE. However the security analysis was given in the semi-adaptive model [CW14], which is much weaker than the standard adaptive security model (see [GKW16] for more discussions).

Our Contribution

In this paper, we propose a new framework for tag-based ABE. The framework is based on JR-IBE and can work with the predicate encoding defined in [CGW15]. The adaptive security in the standard model (without random oracles) relies on the k-linear assumption (k-Lin) in the prime-order bilinear group. Our framework is also compatible with attribute-hiding predicate encoding from [CGW15] and implies a family of tag-based ABE with weak attributehiding feature. Here weak attribute-hiding means that ciphertext ct x reveals no information about x against an adversary who are not authorized to decrypt ct x .

With this technical result, we are ready to answer the two questions: We compare our framework with the CGW framework by Chen et al.

[CGW15] and the KSGA framework by Kim et al. [KSGA16] in Table 1. Here we only focus on the space efficiency, i.e., the size of mpk, sk and ct. The comparison regarding the decryption time is analogous to that for the size of ct.

In general, our framework has shorter master public key and shorter ciphertexts than the CGW framework at the cost of slightly larger secret keys. We highlight that the cost we pay here is constant for specific assumption (i.e., consider k as a constant) while the improvement we gain will be proportional to n and |sE|, respectively. In fact our work can be viewed as an improvement of CGW framework using the tag-based technique underlying JR-IBE and improves a family of concrete ABE constructions in a systematic way.

Superficially, the KSGA framework is much more efficient than ours (and CGW framework as well). However, as we have mentioned, this framework is less expressive. In particular, the KSGA framework works with tag-based predicate encoding [KSGA16] which fails to support many important predicates such as boolean/arithmetic span program. That is this framework does not imply more efficient ABE for these predicates. It's also worth noting that our framework has shorter ciphertext for concrete predicate encodings with |sE| < 5, including predicate encoding for inner-product encryption with short ciphertext [CGW15]. Namely our framework also implies a more efficient IPE scheme. Actually the CGW framework also has a similar advantage but for predicate encodings with |sE| < 3.

CGW n(k 2 + k) + k k (|rE| + 1)(k + 1) 0 (|sE| + 1)(k + 1) 0 k-Lin 6n + 2 2 3 • |rE| + 3 0 3 • |sE| + 3 0 DLIN 2n + 1 1 2 • |rE| + 2 0 2 • |sE| + 2 0 SXDH KSGA n + 11 1 |rE| + 7 |rE| |sE| + 8 |sE| DLIN Ours (n + 1)k 2 + k k (|rE| + 1)(k + 1) + k 0 |sE| • k + k + 1 |sE| k-Lin 4n + 6 2 3 • |rE| + 5 0 2 • |sE| + 3 |sE| DLIN n + 2 1 2 • |rE| + 3 0 |sE| + 2 |sE| SXDH
In Table 2, we compare concrete instantiations derived from CGW, KSGA, and our framework. Here we only take inner-product encryption (IPE) and keypolicy ABE for boolean span program (KP-ABE-BSP) as examples. It is clear that our KP-ABE-BSP has the shortest master public key and ciphertexts (also fastest decryption algorithm). Under the DLIN assumption, our IPE has the shortest ciphertext but its master public key is larger than the IPE derived from KSGA framework. However if we are allowed to use stronger SXDH assumption, our IPE will have the shortest master public key.

Overview of Method: A Simplified JR-IBE

Our framework is based on JR-IBE. In Jutla and Roy's original paper [JR13], JR-IBE was derived from the QA-NIZK proof for a specific subspace language. Although it's important to describe/explain an IBE from the angle of NIZK proof, it's still a big challenge to work on it directly. Therefore the foundation of our framework is a simplified (and slightly generalized) version of JR-IBE. The simplified JR-IBE is similar to the prime-order IBE instantiated from the CGW framework [CGW15] and its proof analysis is cleaner and much easier to follow. With the benefits of these features, we are able to develop our new framework for tag-based ABE which is based on JR-IBE's proof technique [JR13] and is compatible with the predicate encoding from [CGW15]. The adaptive security relies on the k-Lin assumption, which is a generalized form of SXDH used in [JR13].

Simplified JR-IBE. We assume there is an asymmetric prime-order bilinear group 1. The parameter is the dimension of vector space for IPE while it stands for the size of universe for ABE.

(p, G 1 , G 2 , G T , e). Let g 1 ∈ G 1 , g 2 ∈ G 2 and e(g 1 , g 2 ) ∈ G T be the respec-
IPE KP-ABE-BSP |mpk| |sk| |ct| |mpk| |sk| |ct| Sec. |G1| |GT | |G2| |Zp| |G1| |Zp| |G1| |GT | |G2| |Zp| |G1| |Zp| CGW 6 + 2 2 3 + 6 0 6 0 6 + 2 2 3 + 3 0 3 + 3 0 DLIN 2 + 1 1 2 + 4 0 4 0 2 + 1 1 2 + 2 0 2 + 2 0 SXDH KSGA + 11 1 + 6 -1 9 1 - DLIN Ours 4 + 6 2 3 + 8 0 5 1 4 + 6 2 3 + 5 0 2 + 3 DLIN + 2 1 2 + 5 0 3 1 + 2 1 2 + 3 0 + 2 SXDH
tive generators, we will use the following notation: [a] s = g a s for all a ∈ Z p and s ∈ {1, 2, T }. The notation can also be naturally applied to a matrix over Z p .

Let Z p be the identity space. The JR-IBE can be re-written as

mpk : [A] 1 , [W 0 A] 1 , [W 1 A] 1 , [W A] 1 , [k A] T ct id : [As] 1 , [(W 0 + id • W 1 + τ • W ) As] 1 , [k As] T • m, τ sk id : [r] 2 , [k + (W 0 + id • W 1 )r] 2 , [Wr] 2
Here A ← Z (k+1)×k p acts as the basis, matrices W 0 , W 1 , W ← Z (k+1)×k p are common parameters, the vector k ← Z k+1 p is the master secret value, vectors s, r ← Z k p are random coins for the ciphertext and the secret key, respectively, and the tag τ is a random element in Z p .

The boxed parts involving matrix W are relevant to the tag while the remaining structure is quite similar to the IBE implied by the CGW framework. The main difference is that we do not need another basis B in sk id , which reduces the size of W, W 0 , W 1 and thus shortens mpk and ct id . In fact this structure has been used in a recent tightly secure IBE [BKP14,GDCC16], and we indeed borrow some proof technique from the tight reduction method there.

Proof Blueprint. Our proof mainly follows the tag-based proof strategy given by Jutla and Roy [JR13] which basically employs the dual system methodology [Wat09]. The first step is to transform the normal challenge ciphertext (see the real system above) into the semi-functional (SF) one:

ct SF id * : [As+ bŝ ] 1 , [(W 0 +id * •W 1 +τ •W) (As+ bŝ )] 1 , [k (As+ bŝ )] T •m, τ
where b ← Z k+1 p and ŝ ← Z p . One may prove such a transformation is not detectable by the adversary from the k-Lin assumption following [CGW15]. The next step is to convert secret keys revealed to adversary from normal form into semi-functional (SF) form defined as follows:

sk SF id : [r] 2 , [k + αa ⊥ + (W 0 + id • W 1 )r] 2 , [Wr] 2
where a ⊥ ← Z k+1 p with A a ⊥ = 0 and α ← Z p . As usual, the conversion will be done in a one-by-one manner. That is we deal with single secret key each time which arises a security loss proportional to the number of secret keys sent to the adversary. When all secret keys and the challenge ciphertext become semifunctional, it would be quite direct to decouple the message m from the challenge ciphertext which implies the adaptive security.

Tag-based Technique, Revisited. In fact what we have described still follows [CGW15] (and most dual-system proofs [Wat09]). However the proof for the indistinguishability between normal and SF secret key heavily relies on the tag as [JR13] and deviate from [CGW15].

Recall that a SF key is a normal key with additional entropy αa ⊥ . To replace a normal key with a SF key, we use the following lemma in [BKP14,GDCC16] which states that

( [r] 2 , [v r] 2 ) ≈ c ( [r] 2 , [v r + r] 2 ) given [Z] 2 , [v Z] 2 (1)
where

v, r ← Z k p , r ← Z p and Z ← Z k×k p
. Following [BKP14,GDCC16], we pick γ 0 , γ 1 ← Z p and embed the secret vector v into common parameter W 0 and W 1 as follows

W 0 = W 0 + γ 0 • a ⊥ v and W 1 = W 1 + γ 1 • a ⊥ v where W 0 , W 1 ← Z (k+1)×k p
. The lemma shown in Equation (1) will allow us to move from a normal key to the following transitional form

[r] 2 , [k + (W 0 + id • W 1 )r + (γ 0 + id • γ 1 ) • a ⊥ r ] 2 , [Wr] 2 .
(2)

However we must ensure that v will not appear in mpk and ct id , both of which consist of elements in G 1 ; otherwise, we can not apply the lemma at all since there is not element from G 1 with information on v.

It is direct to see that [W 0 A] 1 and [W 1 A] 1 in mpk reveal nothing about v from the fact that A a ⊥ = 0, but the challenge ciphertext may include v since we have

W 0 + id * • W 1 + τ • W = W 0 + id * • W 1 + τ • W + (γ 0 + id * • γ 1 )a ⊥ v
and As + bŝ ∈ Z k+1 p with high probability. Fortunately, the tag can help us to circumvent the issue: set

W = W -a ⊥ v and τ = γ 0 + id * • γ 1 , we can see that τ • W + (γ 0 + id * • γ 1 )a ⊥ v = τ • W
where there is no v anymore and the proof strategy now works well. We note that both W and τ are distributed correctly.

Then we can move from the transitional key (see Equation 2) to the SF key using the statistical argument asserting that

{ γ 0 + id * • γ 1 , γ 0 + id • γ 1 } are uniformly distributed over Z 2 p . Chen et al.'s proof [CGW15]
also involves this statistical argument. However, in Chen et al.'s proof [CGW15], both values appear "on the exponent" while γ 0 + id * • γ 1 is given out "directly" as the tag in our case.

Related Work and Discussion

Since the work by Wee [Wee14] JR-IBE has been used to construct more advanced primitives [WS16,WES17]. We note that our framework is seemingly not powerful enough to cover them. However we believe our simplified JR-IBE (and our framework as well) can shed the light on more extensions in the future.

Organization. Our paper is organized as follows. The next section will give several basic notions. Our generic framework for ABE with tag will be given in Section 3. We also prove its adaptive security in the same section. We then show the compatibility of our framework with attribute-hiding encodings in Section 4. The next section, Section 5, illustrates the new ABE constructions derived from our framework. The last section, Section 6, shows how to extend our framework to support delegation.

Preliminaries

Notation. We use s ← S to indicate that s is selected uniformly from finite set S. For a probability distribution D, notation x ← D means that x is sampled according to D. We consider λ as security parameter and a function f (λ) is negligible in λ if, for each c ∈ N, there exists λ c such that f (λ) < 1/λ c for all λ > λ c . "p.p.t." stands for "probabilistic polynomial time". For a matrix A ∈ Z k×k p with k > k , we let A be the matrix consist of the first k rows and A be the matrix with all remaining rows.

Attribute-Based Encryptions

Syntax. An attribute-based encryption (ABE) scheme for predicate P(•, •) consists of the following p.p.t. algorithms.

-Setup(1 λ , P) → (mpk, msk). The setup algorithm takes as input the security parameter λ and a description of predicate P and returns master public/secret key pair (mpk, msk). We assume that mpk contains descriptions of domains X and Y of P as well as message space M.

-Enc(mpk, x, m) → ct x . The encryption algorithm takes as input the master public key mpk, an index (attribute) x ∈ X and a message m ∈ M and outputs a ciphertext ct x .

-KeyGen(mpk, msk, y) → sk y . The key generation algorithm takes as input the master public/secret key pair (mpk, msk) and an index (policy) y ∈ Y and generates a secret key sk y .

-Dec(mpk, sk y , ct x ) → m. The decryption algorithm takes as input the master public key mpk, a secret key sk y and a ciphertext ct x with P(x, y) = 1 and outputs message m.

Correctness. For all (mpk, msk) ← Setup(1 λ , P), all x ∈ X and y ∈ Y satisfying P(x, y) = 1, and all m ∈ M, it is required that Pr Dec(mpk, sk y , ct x ) = m sk y ← KeyGen(mpk, msk, y)

ct x ← Enc(mpk, x, m) = 1.
Security. For all adversary A, define advantage function Adv abe A (λ) as follows.

Adv abe A (λ) = Pr      β = β (mpk, msk) ← Setup(1 λ , P), β ← {0, 1} (x * , m * 0 , m * 1 ) ← A KeyGen(mpk,msk,•) (mpk) ct * ← Enc(mpk, x * , m * β ) β ← A KeyGen(mpk,msk,•) (mpk, ct * )      - 1 2 .
An ABE scheme is said to be adaptively secure if Adv abe A (λ) is negligible in λ and P(x * , y) = 0 holds for each query y sent to oracle KeyGen(mpk, msk, •) for all p.p.t. adversary A. We may call x * the target attribute and each y a key extraction query.

Prime-order Bilinear Groups and Cryptographic Assumption

We assume a group generator GrpGen which takes as input security parameter 1 λ and outputs group description G = (p, G 1 , G 2 , G T , e). Here G 1 , G 2 , G T are cyclic groups of prime order p of Θ(λ) bits and e : G 1 × G 2 → G T is a nondegenerated bilinear map. We assume that descriptions of G 1 and G 2 contain respective generators g 1 and g 2 .

Let s ∈ {1, 2, T }. For A = (a ij ) ∈ Z k×k p , we define the implicit representation [EHK + 13] as

[A] s =    g a11 s • • • g a 1k s . . . . . . g a k1 s • • • g a kk s    ∈ G k×k s . Given [A] 1 ∈ G k×n 1 and [B] 2 ∈ G k×n 2 , define e([A] 1 , [B] 2 ) = [A B] T ∈ G n×n T .
We also use the following notations: given We review the matrix decisional Diffie-Hellman (MDDH) assumption in the prime-order bilinear groups as follows.

[a] s , [b] s ∈ G k s and c ∈ Z p , define [a] s • [b] s = [a + b] s ∈ G k s and [a] c s = [ca] s ∈ G k s ; (3) for ([a 1 ] s , . . . , [a n ] s ), ([b 1 ] s , . . . , [b n ] s ) ∈ (G k s ) n , we define ([a 1 ] s , . . . , [a n ] s ) • ([b 1 ] s , . . . , [b n ] s ) = ([a 1 ] s • [b 1 ] s , . . . , [a n ] s • [b n ] s ) ∈ (G k s ) n ; for a = (a 1 , . . . , a n ) ∈ Z n p and [b] s ∈ G k s , we define [b] a s = ([b] a1 s , . . . , [b] an s ) ∈ (G k s ) n . (4)
Assumption 1 (D k -MDDH, [EHK + 13]) Let s ∈ {1, 2}. For any adversary A, define the advantage function Adv D k A (λ) as follows

Adv D k A (λ) = |Pr[A(G, [A] s , [As] s ) = 1] -Pr[A(G, [A] s , [u] s ) = 1]| where G ← GrpGen(1 λ ), (A, a ⊥ ) ← D k , s ← Z k p and u ← Z k+1 p .
The assumption says that Adv D k A (λ) is negligible in λ for all p.p.t. adversary A.

Predicate Encodings

This subsection reviews the notion of predicate encoding [Wee14,CGW15] and shows some useful notations and facts.

Definition. A Z p -linear predicate encoding for P : X × Y → {0, 1} consists of five deterministic algorithms

sE : X × Z n p → Z ns p sD : X × Y × Z ns p → Z p rE : Y × Z n p → Z nr p kE : Y × Z p → Z nr p rD : X × Y × Z nr p → Z p
for some n, n s , n r ∈ N with the following features:

(linearity) For all (x, y) ∈ X ×Y, sE(x, •), rE(y, •), kE(y, •), sD(x, y, •), rD(x, y, •) are Z p -linear. A Z p -linear function L : Z n p → Z n p can be encoded as a matrix L = (l i,j ) ∈ Z n×n p such that L : (w 1 , . . . , w n ) → ( n i=1 l i1 w i , . . . , n i=1 l in w i ).
(5)

(restricted α-reconstruction) For all (x, y) ∈ X × Y such that P(x, y) = 1, all w ∈ Z n p and all α ∈ Z p , we have sD(x, y, sE(x, w)) = rD(x, y, rE(y, w)) and rD(x, y, kE(y, α)) = α.

(α-privacy) For all (x, y) ∈ X × Y such that P(x, y) = 0 and all α ∈ Z p , the following distributions are identical.

{ x, y, α, sE(x, w), kE(y, α) + rE(y, w) : w ← Z n p } and { x, y, α, sE(x, w), rE(y, w) : w ← Z n p }. We call n the parameter size and use |sE| and |rE| to denote n s and n r , respectively, which indicate the sizes of sender encodings and receiver encoding. We note that |sE| and |rE| may depend on x and y respectively. For all x ∈ X , we define the distribution sE(x) := { sE(x, w) : w ← Z n p }.

More Notations and Useful Facts. Assume s ∈ {1, 2, T }. We can naturally define a series of Z p -linear functions from L as follows:

L : (G k s ) n → (G k s ) n ([w 1 ] s , . . . , [w n ] s ) → ( n i=1 [w i ] li1 s , . . . , n i=1 [w i ] l in s ) (6)
Because they essentially share the same structure (i.e., L), we employ the same notation L. It should be clear from the context. Then we highlight three properties regarding functions L with respective to the same L as follows:

(L(•) and pairing e are commutative) For any a, b 1 , . . . , b n ∈ Z k p , we have

e([a] 1 , L([b 1 ] 2 , . . . , [b n ] 2 )) = L(e([a] 1 , [b 1 ] 2 ), . . . , e([a] 1 , [b n ] 2 )) (7) e(L([b 1 ] 1 , . . . , [b n ] 1 ), [a] 2 ) = L(e([b 1 ] 1 , [a] 2 ), . . . , e([b n ] 1 , [a] 2 )) (8)
(L(•) and [•] s are commutative) For any w 1 , . . . , w n ∈ Z p , we have

L([w 1 ] s , . . . , [w n ] s ) = [L(w 1 , . . . , w n )] s . ( 9

ABE with Tags from Predicate Encodings

Construction

Our generic tag-based ABE from predicate encodings is described below.

-Setup(1 λ , P): Let n be parameter size of predicate encoding (sE, rE, kE, sD, rD) for P. We sample

A ← D k , W 1 , • • • , W n , W ← Z (k+1)×k p , k ← Z k+1 p
and output the master public and secret key pair

mpk := { [A] 1 , [W 1 A] 1 , • • • , [W n A] 1 , [W A] 1 , [k A] T } msk := { W 1 , • • • , W n , W; k }.
-Enc(mpk, x, m): On input x ∈ X and m ∈ G T , pick s ← Z k p and τ ← sE(x). Output

ct x :=    C 0 := [As] 1 , C 1 := sE(x, [W 1 As] 1 , . . . , [W n As] 1 ) • [W As] τ 1 , C := [k As] T • m, τ    -KeyGen(mpk, msk, y): On input y ∈ Y, pick r ← r Z k p and output sk y :=    K 0 := [r] 2 , K 1 := kE(y, [k] 2 ) • rE(y, [W 1 r] 2 , . . . , [W n r] 2 ), K 2 := [Wr] 2    -Dec(mpk, sk y , ct x ): Compute K ← e(C 0 , rD(x, y, K 1 )) • e(C 0 , K 2 ) sD(x,y,τ ) /e(sD(x, y, C 1 ), K 0 )
and recover the message as m ← C/K ∈ G T .

Correctness. For all (x, y) ∈ X × Y with P(x, y) = 1, we may use the following abbreviation

sE(x, •) = sE(•), rE(y, •) = rE(•), kE(y, •) = kE(•); sD(x, y, •) = sD(•), rD(x, y, •) = rD(•)
and have

e(C 0 , rD(K 1 )) • e(C 0 , K 2 ) sD(τ ) (a) = e([As] 1 , rD(kE([k] 2 ))) • e([As] 1 , rD(rE([W 1 r] 2 , . . . , [W n r] 2 ))) • [s A Wr] sD(τ ) T (b) = rD(kE([s A k] T )) • rD(rE([s A W 1 r] T , . . . , [s A W n r] T )) • [s A Wr] sD(τ ) T (c) = [rD(kE(s A k))] T • [rD(rE(s A W 1 r, . . . , s A W n r))] T • [s A Wr] sD(τ ) T (d) = [s A k] T • [sD(sE(s A W 1 r, . . . , s A W n r))] T • [s A Wr] sD(τ ) T (e) = [s A k] T • sD(sE([s A W 1 r] T , . . . , [s A W n r] T )) • [s A Wr] sD(τ ) T (f ) = [s A k] T • e(sD(sE([W 1 As] 1 , . . . , [W n As] 1 )), [r] 2 ) • e([W As] sD(τ ) 1 , [r] 2 ) (g) = [s A k] T • e(sD(sE([W 1 As] 1 , . . . , [W n As] 1 )), [r] 2 ) • e(sD([W As] τ 1 ), [r] 2 ) (h) = [s A k] T • e(sD(sE([W 1 As] 1 , . . . , [W n As] 1 ) • [W As] τ 1 ), [r] 2 ) = [s A k] T • e(sD(C 1 ), K 0 )
which is sufficient for the correctness. We list the properties and the facts justifying each (labelled) equality in Table 3.

Security Result. We give the following main theorem stating that the above generic tag-based ABE scheme is adaptively secure under standard assumption in the standard model. The remaining of this section will be devoted to the proof of the main theorem.

Theorem 1 (Main Theorem). For any p.p.t. adversary A making at most q key extraction queries, there exists algorithms B 1 , B 2 , B 3 such that

Adv abe A (λ) ≤ Adv D k B1 (λ) + q • Adv D k B2 (λ) + q • Adv D k B3 (λ) + 2 -Ω(λ)
and max{Time(B 1 ), Time(B 2 ),

Time(B 3 )} ≈ Time(A) + q • k 2 • poly(λ, n).

Proving the Main Theorem: High-level roadmap

From a high level, the proof basically follows the common dual system methodology. We first define semi-functional distributions under the master public key (semi-functional ciphertext) A semi-functional ciphertext for target attribute x * ∈ X and challenge message pair (m * 0 , m * 1 ) ∈ M × M is defined as follows:

mpk = { [A] 1 , [W 1 A] 1 , . . . , [W n A] 1 , [W A] 1 , [k A] T }. where (A, a ⊥ ) ← D k , W 1 , . . . , W n , W ← Z (k+1)×k p , k ← Z k+1 p as follows.
[ c ] 1 , sE(x * , [ W 1 c ] 1 , . . . , [ W n c ] 1 ) • [ W c ] τ * 1 , [ k c ] T • m * β , τ *
where c ← Z k+1 p and τ * ← sE(x * ).

(semi-functional secret key) A semi-functional secret key for policy y ∈ Y is defined as follows:

[r] 2 , kE(y,

[ k + αa ⊥ ] 2 ) • rE(y, [W 1 r] 2 , . . . , [W n r] 2 ), [Wr] 2
where α ← Z p . Note that all semi-functional secret keys in the system will share the same α.

Game Sequence. Our proof employs the following game sequence.

-G 0 is the real security game defined as Section 2.1.

-G 1 is identical to G 0 except that the challenge ciphertext is semi-functional.

-G 2.i (for i ∈ [0, q]) is identical to G 1 except that the first i key extraction queries are replied with semi-functional secret keys. -G 3 is identical to G 2.q except that the challenge ciphertext is a semi-functional ciphertext for random message m * ∈ M.

Roughly speaking, we are going to prove that

G 0 lem 4 ≈ G 1 = G 2.0 sec 3.3 ≈ G 2.1 sec 3.3 ≈ • • • sec 3.3 ≈ G 2.q lem 5 = G 3 .
Here "≈" indicates that two games are computationally indistinguishable while "=" means that they are statistically indistinguishable. Let Adv i.j A (λ) be the advantage function of any p.p.t. adversary A making at most q key extraction queries in G i.j with security parameter λ.

We begin with two simple lemmas. First, it is not hard to see that G 1 and G 2.0 are actually the same and we have the following lemma.

Lemma 2 (G 1 = G 2.0 ). For any adversary A, we have Adv 1 A (λ) = Adv 2.0 A (λ). Next, observe that the challenge ciphertext in the last game G 3 is created without secret bit β ∈ {0, 1}. In other words, the challenge ciphertext reveals nothing about β. Therefore adversary has no advantage in guessing β and we have the lemma below.

Lemma 3. For any adversary A, we have Adv 3 A (λ) = 0. Following Chen et al.'s proof [CGW15], we can prove Lemma 4 showing G 0 ≈ G 1 and Lemma 5 showing G 2.q = G 3 . Due to the lack of space, we omit the proofs.

Lemma 4 (G 0 ≈ G 1 ). For any p.p.t. adversary A making at most q key extraction queries, there exists an algorithm B such that

| Adv 0 A (λ) -Adv 1 A (λ) | ≤ Adv D k B (λ) + 1/p and Time(B) ≈ Time(A) + q • k 2 • poly(λ, n).
Lemma 5 (G 2.q = G 3 ). For any adversary A, we have |Adv 2.q A (λ) -Adv 3 A (λ)| = 1/p. In order to complete the proof, we prove that G 2.i is indistinguishable with G 2.i+1 for all i ∈ [0, q -1]. The details are deferred to the next subsection.

Proving the Theorem: Filling the gap between G 2.i and G 2.i+1

This subsection proves the indistinguishability of G 2.i and G 2.i+1 . We introduce an auxiliary game sequence which is based on the proof idea from Jutla and Roy [JR13]. In particular, we need the following two auxiliary distributions.

(pesudo-normal secret key) A pseudo-normal secret key for policy y ∈ Y is defined as follows:

   [r] 2 , kE(y, [k] 2 ) • rE(y, [W 1 r] 2 , . . . , [W n r] 2 ) • [a ⊥ r] rE(y,γ1,...,γn) 2 , [Wr] 2 • [a ⊥ r] -1 2   
where r ← Z p and γ 1 , . . . , γ n ← Z p are the random coins for tag τ * in the challenge ciphertext. Recall that we compute τ * = sE(x * , (γ 1 , . . . , γ n )) for target attribute x * .

(pesudo-semi-functional secret key) A pseudo-semi-functional secret key for policy y ∈ Y is defined as follows:

[r] 2 , kE(y,

[ k + αa ⊥ ] 2 ) • rE(y, [W 1 r] 2 , . . . , [W n r] 2 ) • [a ⊥ r] rE(y,γ1,...,γn) 2 , [Wr] 2 • [a ⊥ r] -1 2
where r ∈ Z p and γ 1 , . . . , γ n ∈ Z p are defined as before and α ∈ Z p is the one used in the semi-functional secret key.

We note that the random coins γ 1 , . . . , γ n for τ * are independent of x * and thus we can pick them at the very beginning and use them to create secret keys of these two forms at any point.

Game Sub-sequence. For each i ∈ [0, q -1], we define -G 2.i.1 is identical to G 2.i except that the i + 1st key extraction query y is answered with a pseudo-normal secret key. -G 2.i.2 is identical to G 2.i.1 except that the i + 1st key extraction query y is answered with a pseudo-semi-functional secret key.

With this sub-sequence, we will prove that

G 2.i lem 6 ≈ G 2.i.1 lem 8 = G 2.i.2 lem 7 ≈ G 2.i+1 .
We first prove Lemma 6 showing that G 2.i ≈ G 2.i.1 and note that, following almost the same strategy, we can also prove that G 2.i.2 ≈ G 2.i+1 . Hence we will show the corresponding result in Lemma 7 but omit the proof.

Lemma 6 (G 2.i ≈ G 2.i.1 ). For any p.p.t. adversary A making at most q key extraction queries, there exists an algorithm B such that

| Adv 2.i A (λ) -Adv 2.i.1 A (λ) | ≤ Adv D k B (λ) and Time(B) ≈ Time(A) + q • k 2 • poly(λ, n). Proof. Given ( G, [M] 2 , [t] 2 = [Mu + ev] 2 ) where u ← Z k
p , e = (0, . . . , 0, 1) ∈ Z k+1 p and either v ← Z p or v = 0, algorithm B works as follows:

Initialize. Sample (A, a ⊥ ) ← D k , k ← Z k+1 p and β ← {0, 1}. Pick W 1 , • • • , W n , W ← Z (k+1)×k p and γ 1 , . . . , γ n ← Z p and program "hidden parameter" γ 1 , . . . , γ n into W 1 , . . . , W n , W as follows W 1 = W 1 + γ 1 V, . . . , W n = W n + γ n V, W = W -V where V = a ⊥ • (MM -1 ) ∈ Z (k+1)×k p
. One may check that all W i and W are uniformly distributed over Z (k+1)×k p as required. Due to the fact that A a ⊥ = 0, we can return the master public key as follows

mpk = { [A] 1 , [ W 1 A] 1 , . . . , [ W n A] 1 , [ W A] 1 , [k A] T }.
We note that B can not compute V and thus does not know W 1 , . . . , W n , W.

Challenge ciphertext. For target attribute x * and challenge message pair (m * 0 , m * 1 ), we sample c ← Z k+1 p , compute tag τ * = sE(x * , (γ 1 , . . . , γ n )) using the "hidden parameter" and create the challenge ciphertext as follows

{ [c] 1 , sE(x * , [ W 1 c] 1 , . . . , [ W n c] 1 ) • [ W c] τ * 1 , [k c] T • m * β , τ * } Let v = MM -1 , we show that sE(x * , [W 1 c] 1 , . . . , [W n c] 1 ) • [W c] τ * 1 = sE(x * , [ W 1 c] 1 , . . . , [ W n c] 1 ) • [ W c] τ * 1 • sE(x * , [γ 1 v a ⊥ c] 1 , . . . , [γ n v a ⊥ c] 1 ) • [-v a ⊥ c] τ * 1 from the linearity of sE(x * , •) and sE(x * , [γ 1 v a ⊥ c] 1 , . . . , [γ n v a ⊥ c] 1 ) • [-v a ⊥ c] τ * 1 (the boxed part) = sE(x * , [v a ⊥ c] (γ1,...,γn) 1 ) • [-v a ⊥ c] τ * 1 = [v a ⊥ c] sE(x * ,(γ1,...,γn)) 1 • [v a ⊥ c] -τ * 1 = 0,
where the first equality is mainly implied by Eq.(3) and Eq.( 4), and the second equality comes from the fact shown in Eq.( 10). This is sufficient to see that our simulation is perfect.

Key extraction. We consider three cases: (1) For the first i queries y, we sample r ← Z k p and implicitly set

r = Mr ∈ Z k p .
The vector r here is uniformly distributed as required and we can compute [r] 2 and simulate [Vr] 2 = [a ⊥ • (Mr )] 2 .

These suffice for creating the secret key as

[r] 2 , kE(y, [k] 2 )•rE(y, [ W 1 r] 2 •[γ 1 Vr] 2 , . . . , [ W n r] 2 •[γ n Vr] 2 ), [ Wr] 2 •[-Vr] 2
because k, W 1 , . . . , W n , W and γ 1 , . . . , γ n are all known to B. (2) For the i + 1st query y, we implicitly set

r = Mu = t ∈ Z k p .
The vector r is distributed properly and [r] 2 = [ t ] 2 can be simulated. Then we may produce the secret key as follows

[ t ] 2 , kE(y, [k] 2 ) • rE(y, [ W 1 t ] 2 • [ γ 1 a ⊥ t ] 2 , . . . , [ W n t ] 2 • [ γ n a ⊥ t ] 2 ), [ Wt ] 2 • [ -a ⊥ t ] 2 .
(3) For the remaining q -i -1 queries, we may work just as in the first case except that we employ k + αa ⊥ in the place of k.

Finalize. Output 1 when β = β and 0 otherwise.

Observe that, in the reply to the i + 1st key extraction query, we have

a ⊥ t = a ⊥ (Mu + v) = a ⊥ (MM -1 )(Mu) + a ⊥ v = Vt + a ⊥ v.
Therefore we have

kE(y, [k] 2 ) • rE(y, [ W 1 t ] 2 • [ γ 1 a ⊥ t ] 2 , . . . , [ W n t ] 2 • [ γ n a ⊥ t ] 2 ) = kE(y, [k] 2 ) • rE(y, [ W 1 r ] 2 • [ γ 1 a ⊥ v ] 2 , . . . , [ W n r ] 2 • [ γ n a ⊥ v ] 2 ) = kE(y, [k] 2 ) • rE(y, [ W 1 r ] 2 , . . . , [ W n r ] 2 ) • rE(y, [ γ 1 a ⊥ v ] 2 , . . . , [ γ n a ⊥ v ] 2 ) = kE(y, [k] 2 ) • rE(y, [ W 1 r ] 2 , . . . , [ W n r ] 2 ) • rE(y, [ a ⊥ v ] (γ1,...,γn) 2 ) = kE(y, [k] 2 ) • rE(y, [ W 1 r ] 2 , . . . , [ W n r ] 2 ) • [ a ⊥ v ] sE(y,γ1,...,γn) 2 [ Wt ] 2 • [ -a ⊥ t ] 2 = [ Wr ] 2 • [ -a ⊥ v ] 2 = [ Wr ] 2 • [ a ⊥ v ] -1 2
It is now clear that the simulation is identical to G 2.i when v = 0; and if v is a random element in Z p , the simulation is identical to G 2.i.1 where r = v.

Lemma 7 (G 2.i.2 ≈ G 2.i+1 ). For any p.p.t. adversary A making at most q key extraction queries, there exists an algorithm B such that

| Adv 2.i.2 A (λ) -Adv 2.i+1 A (λ) | ≤ Adv D k B (λ)
and Time(B) ≈ Time(A)

+ q • k 2 • poly(λ, n).
Proof. The proof is similar to that for Lemma 6.

We complete the proof by proving Lemma 8 which states that G 2.i.1 and G 2.i.2 are statistically indistinguishable. This is derived from the α-privacy of predicate encodings.

Lemma 8 (G 2.i.1 = G 2.i.2 ). For any adversary A, we have

Adv 2.i.1 A (λ) = Adv 2.i.2 A (λ).
Proof. We prove the lemma for any fixed

-(A, a ⊥ ) ← D k , W 1 , . . . , W n , W ← Z (k+1)×k p , k ← Z k+1 p , β ← {0, 1}; -random coin c ← Z k+1 p for semi-functional challenge ciphertext ct * ;
α ← Z p , random coin r ← Z k p for each key extraction query and the extra random coin r ← Z p for the i + 1st one.

Let sk (b) y be the reply to the i + 1st key extraction query y in G 2.i.b (b = 1, 2) and ct * is the challenge ciphertext for target attribute x * . It is sufficient to show

{ (sk (1) y , ct * ) } = { (sk (2) y , ct * ) }
where the probability space is defined by γ 1 , . . . , γ n ← Z p . In fact, we can further reduce to the claim that , sE(x * , γ 1 , . . . , γ n ) }.

{ kE(y, [αa ⊥ ] 2 ) • [a ⊥ r]
which is statistically close to the second one by the α-privacy of predicate encoding. This readily proves the lemma.

4 Tag-based ABE with Weak Attribute-hiding Property

This section shows that our framework (presented in Section 3) is compatible with the attribute-hiding predicate encoding [CGW15]. This means that our framework can derive a series of attribute-hiding ABE with tag.

Preliminaries

Definition. We may call an ABE with (weak) attribute-hiding the predicate encryption (PE for short). A PE scheme is also defined by four p.p.t algorithms Setup, KeyGen, Enc, Dec as in Section 2, but the security is defined in a slightly different way. For all adversary A, define the advantage function Adv pe A (λ) as

Adv pe A (λ) = Pr      β = β (mpk, msk) ← Setup(1 λ , P), β ← {0, 1} (x * 0 , x * 1 , m * 0 , m * 1 ) ← A KeyGen(mpk,msk,•) (mpk) ct * ← Enc(mpk, x * β , m * β ) β ← A KeyGen(mpk,msk,•) (mpk, ct * )      - 1 2 .
A PE scheme is said to be adaptively secure and weakly attribute-hiding if Adv pe A (λ) is negligible in λ and P(x * 0 , y) = P(x * 1 , y) = 0 holds for each query y sent to oracle KeyGen(mpk, msk, •) for all p.p.t. adversary A.

Attribute-hiding Predicate Encoding.

A Z p -linear predicate encoding (sE, rE, kE, sD, rD) for P : X × Y → {0, 1} is attribute-hiding [CGW15] if it has the following two additional properties:

(x-oblivious α-reconstruction) sD(x, y, •) and rD(x, y, •) are independent of x.

(attribute-hiding) For all (x, y) ∈ X × Y such that P(x, y) = 0 , the following distributions are identical.

x, y, sE(x, w), rE(y, w) : w ← Z n p and x, y, r : r ← Z |sE|+|rE| p .

Construction and Security Analysis

Assuming an attribute-hiding predicate encoding, we can construct a predicate encryption with tag as in Section 3.1. Technically we prove the following theorem stating that the generic tag-based PE scheme is adaptively secure and weakly attribute-hiding under standard assumption in the standard model.

Theorem 2 (Weak AH). For any p.p.t. adversary A making at most q key extraction queries, there exists algorithms B 1 , B 2 , B 3 such that

Adv pe A (λ) ≤ Adv D k B1 (λ) + q • Adv D k B2 (λ) + q • Adv D k B3 (λ) + 2 -Ω(λ)
and max{Time(B 1 ), Time(B 2 ),

Time(B 3 )} ≈ Time(A) + q • k 2 • poly(λ, n).
Proof Overview. We prove the theorem using almost the same game sequence as described in Section 3.2 and Section 3.3. We just describe the differences between them. Firstly, the challenge ciphertext will be generated for identity x * β . Secondly, we need to re-define pseudo-semi-functional secret keys and semifunctional secret keys as follows.

(pesudo-semi-functional secret key) A pseudo-semi-functional secret key for policy y ∈ Y is defined as follows:

         [r] 2 , kE(y, [k + αa ⊥ ] 2 ) • rE(y, [W 1 r + a ⊥ û1 ] 2 , . . . , [W n r + a ⊥ ûn ] 2 ) •[a ⊥ r] rE(y,γ1,...,γn) 2 , [Wr] 2 • [a ⊥ r] -1 2         
where r ∈ Z p , γ 1 , . . . , γ n ∈ Z p , α ∈ Z p are defined as before and û1 , . . . , ûn ← Z p are fresh for each pseudo-semi-functional secret key.

(semi-functional secret key) A semi-functional secret key for policy y ∈ Y is defined as follows:

[r] 2 , kE(y, [k + αa ⊥ ] 2 ) • rE(y, [W 1 r + a ⊥ û1 ] 2 , . . . , [W n r + a ⊥ ûn ] 2 ), [Wr] 2
where α ∈ Z p are defined as before and û1 , . . . , ûn ← Z p are fresh for each semi-functional secret key.

Finally, we add an additional game G 4 shown below. Its preceding game G 3 (the final game in the previous game sequence) is restated so as to emphasize the difference between them.

-G 3 is identical to G 2.q except that the challenge ciphertext is a semi-functional ciphertext for attribute x * β and random message m * ∈ M . -G 4 is identical to G 3 except that the challenge ciphertext is a semi-functional ciphertext for random attribute x * ∈ X and random message m * ∈ M.

With the extended game sequence, we will prove that

G 0 ≈ G 1 = G 2.0 ≈ G 2.1 ≈ • • • ≈ G 2.q = G 3 = G 4 .
where "G 2.i ≈ G 2.i+1 " for all i ∈ [0, q] will be proved using the game sub-sequence

G 2.i ≈ G 2.i.1 = G 2.i.2 ≈ G 2.i+1 .
Because of the similarity of game sequences, most lemmas we have presented in Section 3.2 and Section 3.3 still hold and can be proved in the same way. Due to the lack of space, we omit them. The proofs of "G 3 = G 4 " and "G 2.i.1 = G 2.i.2 " (the boxed parts) mainly follow [CGW15] and our proof in previous section. Finally, we point out the fact: The challenge ciphertext in G 3 still leaks information of β ∈ {0, 1} via x * β , but such a dependence is removed in G 4 . Therefore Adv 4

A (λ) = 0 for any A. We use M i to denote the ith row of M. For an input x = (x 1 , . . . , x n ) ∈ {0, 1} n , we say

x satisfies (M, ρ) ⇐⇒ 1 ∈ span(M x ) where 1 = (1, 0, . . . , 0) ∈ Z 1× p and M x = { M j : x ρ(j) = 1 }. In this case one can efficiently find coefficients ω 1 , . . . , ω ∈ Z p such that j : x ρ(j)=1 ω j M j = 1.

Here we will assume n = and ρ is an identity map following [CGW15].

Key-policy Construction

The corresponding predicate is defined as P(x, M) = 1 ⇐⇒ x satisfies M where x ∈ X = {0, 1} and M ∈ Y = Z × p . Our concrete KP-ABE scheme is described below:

-Setup(1 λ , 1 ): Sample The partial ordering is the prefix relation, that is y ≤ y iff y is a prefix of y.

Syntax and Definition

An ABE scheme for a delegatable predicate P consists of algorithms Setup, KeyGen, Enc, Dec as defined in Section 2.1 and a delegation algorithm Del.

-Del(mpk, sk y , y) → sk y . The delegation algorithm takes as input the master public key mpk, a secret key sk y for y ∈ Y and index (policy) y ∈ Y with y ≤ y , and generates a secret key sk y for y.

We require that the delegation algorithm is path-oblivious which means secret keys generated by KeyGen and Del have the same distribution, that is {(sk y , sk y ) : sk y ← KeyGen(mpk, msk, y ), sk y ← KeyGen(mpk, msk, y)} = {(sk y , sk y ) : sk y ← KeyGen(mpk, msk, y ), sk y ← Del(mpk, sk y , y)} for all y, y ∈ Y satisfying y ≤ y . The assumption is natural and allows us to continue working with the security model described in Section 2.1; otherwise one should turn to the model described in [SW08] where an adversary can decide how to create secret keys-using KeyGen or Del.

Predicate Encoding Supporting Delegation

A predicate encoding for delegatable predicate P is composed of five algorithms sE, sD, rE, kE, rD satisfying all requirements described in Section 2. since Del will not be involved. Therefore we can prove the adaptive security of our ABE scheme as in Section 3.2 and Section 3.3. In fact what we need to show here is how to simulate these extra entries in mpk in our previous proofs.

To prove Lemma 4, Lemma 5, Lemma 8, the simulator knows W 1 , . . . , W n and W. It can sample matrix Z ← Z k×k p and simulate the extra entries directly. For Lemma 6 and Lemma 7, we recall that the simulator received ( G, [M] 2 , [t] 2 ) and implicitly define

W 1 = W 1 + γ 1 V, . . . , W n = W n + γ n V, W = W -V
where W 1 , . . . , W n , W ← Z (k+1)×k p , γ 1 , . . . , γ n ← Z p and V = a ⊥ • (MM -1 ).

As we have mentioned, the simulator can not calculate V and does not know W 1 , . . . , W n , W. However it can still simulate the extra entries as follows: Sample Z ← Z k×k p and define Z = M Z.

Since M is full-rank with high probability, matrix Z is distributed correctly and we have

W i Z = W i M Z + γ i a ⊥ M Z for all i ∈ [n] and WZ = WM Z -a ⊥ M Z.
That means we can simulate all extra entries from [M] 2 . This is sufficient to finish our proof.

Let

  D k be a matrix distribution sampling matrix A ∈ Z (k+1)×k p along with a non-zero vector a ⊥ ∈ Z k+1 p satisfying A a ⊥ = 0. We need the following lemma with respect to D k . Lemma 1 (Basic Lemma, [GDCC16,GHKW16]). With probability 1-1/p over (A, a ⊥ ) ← D k and b ← Z k+1 p , it holds that b / ∈ span(A) and b a ⊥ = 0.

  ) (L(•) and "exponentiation" are commutative) For any w ∈ Z n p and [a] As an example, we show the predicate encoding for equality predicate as below. This is the simplest encoding and extracted from classical.(encoding for equality [LW10]) Let X = Y = Z p and P(x, y) = 1 iff x = y.Let n = 2 and w 1 , w 2 ← Z p . Define sE(x, (w 1 , w 2 )) := w 1 + xw 2 sD(x, y, c) := c rE(y, (w 1 , w 2 )) := w 1 + yw 2 kE(y, α) := α rD(x, y, k) := k Here we have |sE| = |rE| = 1.

5

  New Tag-based ABE In this section we will exhibit two tag-based ABE for boolean span program derived from our generic tag-based ABE and two concrete encodings in [CGW15]. Boolean Span Program. Assume n ∈ N. Let [n] be the attribute universe. A span program over [n] is defined by (M, ρ) where M ∈ Z × p and ρ : [ ] → [n].

A

  ← D k , W 1 , . . . , W , U 2 , . . . , U , W ← Z (k+1)×k p , k ← Z k+1 p and output mpk := { [A] 1 , [W 1 A] 1 , • • • , [W A] 1 , [W A] 1 , [k A] T } msk := { W 1 , . . . , W , U 2 , . . . , U , W; k }One of classical delegatable predicates is the predicate for HIBE: Let ∈ N and X = Y = Z ≤ p . The predicate is P(x, y) = 1 ⇐⇒ y is a prefix of x.

  3 and an extra algorithm dE : Y × Y × Z nr p → Z n r p with the following features: (1) for all w ← Z n p , α ← Z p and y, y ∈ Y with y ≤ y , it holds that dE(y, y , kE(y , α) + rE(y , w)) = kE(y, α) + rE(y, w) and (2) dE(y, y , •) is Z p -linear. A predicate encoding for HIBE from Boneh-Boyen-Goh's HIBE with constant-size ciphertext [BBG05] is as follows: (encoding for HIBE [BBG05]) Let w ← Z 1×( +1) p , x = (x 1 , . . . , x x ) and y = (y 1 , . . . , y y ) for x , y ≤ . Define sE(x, w) := w (1, x, 0) sD(x, y, c) := c rE(y, w) := w 1 y I rD(x, y, k) := k (1, x y +1 , . . . , x x , 0) kE(y, α) := (α, 0)

  Ramanna et al. [RCS12] simplified Wat-IBE (with stronger assumptions) and extended it to build hierarchical IBE (HIBE) and broadcast encryption. Ramanna and Sarkar [RS14] described two HIBE constructions derived from JR-IBE. Then two IPE schemes were proposed by Ramanna [Ram16]. Although both of them were constructed from JR-IBE, the first one borrows some techniques from Wat-IBE. The recent work [RS16] by Ramanna and Sarkar provided us with two identity-based broadcast encryption schemes, both of which comes from JR-IBE. Kim et al.'s tag-based encoding and generic framework [KSGA16] allow them to present several new IPE, (doubly) spatial encryption with various features.

Table 1 .

 1 Comparison among CGW [CGW15], KSGA [KSGA16], and our framework in terms of space efficiency. All of them work with asymmetric bilinear group (p, G1, G2, GT , e). In the table, |G1|, |G2| and |GT | represent the element sizes of three groups, respectively. Parameter n is the number of common parameter of the predicate encoding, |sE| and |rE| are the respective size of sender and receiver encodings.

	|mpk| |G1|	|GT |	|sk| |G2|	|Zp|	|ct| |G1|	|Zp|	Sec.

Table 2 .

 2 Comparison among CGW [CGW15], KSGA [KSGA16], and ours framework in terms of concrete instantiations. In the table, |G1|, |G2| and |GT | have the same meanings as Table

  and Attrapadung [Att14], predicate/pair encodings and corresponding generic frameworks have been extended and improved via various methods [CGW15,AC16,Att16,AC17,ABS17]. Before that, there were many early-age ABE from pairing such as IBE [BF01,BB04b,BB04a,Wat05,Gen06], fuzzy IBE [SW05], inner-product encryption [KSW08,OT12], and ABE for boolean formula [GPSW06,OSW07,BSW07,OT10,LOS + 10,Wat11,LW12]. Most of them has been covered by generic frameworks. Attrapadung et al. [AHY15] even gave a generic framework for tightly secure IBE based on broadcast encodings and reached a series of interesting constructions. However IBE schemes with exponent-inverse structure [Gen06,Wee16,CGW17] are out of the scope of current predicate encodings, and we still have no framework supporting fully attribute-hiding feature [OT12].

Table 3 .

 3 Properties and Facts for Correctness.

	Eq.	Properties	Facts
	(a) Composition of two linear functions	Both e([As]1, •) and rD(x, y, •) are linear
	are linear.		functions.
	(b) Linear functions and pairings are	Both rD(x, y, kE(y, •)) and rD(x, y, rE(y, •))
	commutative. (cf. Eq.(7))	are Zp-valued linear functions.
	(c) Linear functions and [•]s are commu-	Both rD(x, y, kE(y, •)) and rD(x, y, rE(y, •))
	tative. (cf. Eq.(9))	are Zp-valued linear functions.
			s A k, s A W1r, . . . , s A Wnr ∈ Zp.
	(d) Restricted α-reconstruction.	s A k, s A W1r, . . . , s A Wnr ∈ Zp.
	(e) Linear functions and [•]s are commu-	sD(x, y, sE(x, •)) is a Zp-valued linear func-
	tative. (cf. Eq.(9))	tion.
			s A k, s A W1r, . . . , s A Wnr ∈ Zp.
	(f) Linear functions and pairings are	sD(x, y, sE(x, •)) is a Zp-valued linear func-
	commutative. (cf. Eq.(8))	tion.
	(g) Linear functions and "exponentia-

tions" are commutative. (cf. Eq.(10)) sD(x, y, •) is a Zp-valued linear function. (h) Composition of two linear functions are linear. Both e(•, [r]2) and sD(x, y, •) are linear functions.

The terminology introduced byBoneh et al. [BSW11] is functional encryption. However the notion we will consider here is restricted. Therefore we adopt a moderate terminology, i.e., attribute-based encryption. We note that the attribute-based encryption in our paper is more general than that introduced by Goyal et al. [GPSW06] which is named ABE for boolean formula/span program.

Attrapadung [Att14] actually introduced another terminology pair encoding. Although predicate encoding and pair encoding serve the same methodology, Attrapadung's framework is based on more advanced proof technique originated from [LW12].

Acknowledgement. We want to thank Benoît Libert, Somindu C. Ramanna and Hoeteck Wee for their helpful discussion, and thank Jiangtao Li for his proofreading at early stage. We also thank all anonymous reviewers of ASIACRYPT 2017 for their valuable comments.

Supported by the National Natural Science Foundation of China (Nos. 61472142, 61632012) and the Science and Technology Commission of Shanghai Municipality (No. 14YF1404200). Homepage: http://www.jchen.top Partially supported by the French ANR ALAMBIC project (ANR-16-CE39-0006). from Chen et al.'s framework. This not only allows us to work with Chen

-Enc(mpk, x, m): On input x ∈ {0, 1} and m ∈ G T , pick s ← Z k p and w 1 , . . . , w ← Z p . Output

. . .

Recover the message as m ← C/K ∈ G T .

Ciphertext-policy Construction

The corresponding predicate is defined as

where M ∈ X = Z × p and x ∈ Y = {0, 1} . Our concrete CP-ABE scheme is described below:

Using concrete encodings in [CGW15], we can derive more tag-based ABE instantiations. With our framework, we can also reproduce several previous concrete tag-based ABE schemes (such as those in [Ram16,RS16]) with simple proofs under the k-Lin assumption. In fact we just need to extract respective concrete encodings from them and apply our framework.

How to Support Predicate Encoding with Delegation

Our framework shown in Section 3 and extended in Section 4 cannot cover the HIBE schemes proposed by Ramanna and Sarkar [RS14]. This section further develops the framework and predicate encoding to accommodate the delegation mechanism in HIBE system.

We first recall a notion from [CGW15]. A predicate P : X × Y → {0, 1} is delegatable if there exists a partial ordering ≤ on Y such that (y ≤ y ) ∧ P(x, y) = 1 =⇒ P(x, y ) = 1 for all x ∈ X .

As shown in [KSGA16], the encoding is linear and satisfies α-restriction and αprivacy. Besides that, for y = (y 1 , . . . , y y ) and y = (y 1 , . . . , y y ) with y ≤ y , we also define dE(y, y , k ) = k 1 y y +1 . . . y y I .

It's straightforward to show that dE meets two requirements.

Generic Construction and Security Analysis

A direct way to support delegation in our framework in Section 3.1 is to apply dE to K 1 . However this delegation algorithm is not path-oblivious. Following [RS14], we publish W 1 , . . . , W n , W in the master public key mpk in a proper form which makes it possible to publicly re-randomize any secret key.

Construction. Our tag-based ABE supporting delegation is as follows. We highlight all terms we add for delegation in the dashboxes.

-Setup(1 λ , P): Let n be the parameter size of predicate encoding supporting delegation (sE, rE, kE, rE, rD, dE ) for P. Sample

and output the master public and secret key pair

-Del(mpk, sk y , y): Let sk y = { K 0 , K 1 , K 2 }. Sample r ← Z k p and compute a re-randomizer

The remaining algorithms KeyGen, Enc and Dec are defined as in Section 3.1. The algorithm Del is path-oblivious: if we let r be the random coin for sk y , the random coin in sk y will be r = r + Z r which is independent of r thanks to r.

Security. Observe that the only difference in the security game here is that the mpk sent to the adversary also includes


Anastasiia Tsukanova
email: anastasiia.tsukanova@inria.fr

Benjamin Elie
email: benjamin.elie@inria.fr

Yves Laprie
email: yves.laprie@loria.fr

Articulatory Speech Synthesis from Static Context-Aware Articulatory Targets

Keywords: articulatory synthesis, coarticulation, articulatory gestures

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Articulatory speech synthesis is a method of synthesizing speech by managing the vocal tract shape on the level of the speech organs, which is an advantage over the state-of-the-art methods that do not usually incorporate any articulatory information. The vocal tract can be modeled with geometric [START_REF] Öhman | Coarticulation in VCV utterances: spectrographic measurements[END_REF][START_REF] Birkholz | Construction and control of a three-dimensional vocal tract model[END_REF][START_REF] Story | Phrase-level speech simulation with an airway modulation model of speech production[END_REF], biomechanical [START_REF] Lloyd | ArtiSynth: a fast interactive biomechanical modeling toolkit combining multibody and finite element simulation[END_REF][START_REF] Anderson | A Comprehensive 3D Biomechanically-Driven Vocal Tract Model Including Inverse Dynamics for Speech Research[END_REF] and statistical [START_REF] Maeda | Compensatory articulation during speech: evidence from the analysis and synthesis of vocal-tract shapes using an articulatory model[END_REF][START_REF] Howard | Modeling the development of pronunciation in infant speech acquisition[END_REF]) models. The advantage of statistical models is that they use very few parameters, speeding up the computation time. Their disadvantage is that they follow the data a priori without any guidance and do not have access to the knowledge of what is realistic or physically possible. Because of this, to produce correct configurations, they need to be finely tuned.

Previous work performed by [START_REF] Tsukanova | A Coarticulation Model for Articulatory Speech Synthesis[END_REF] explored the potential in using quite little, and yet sufficient, static magnetic resonance imaging (MRI) data and implemented one of the few existing attempts at creating a full-fledged speech synthesizer that would be capable of reproducing the vast diversity of speech phenomena. This work is its follow-up, with improvements in the statistical articulatory model (better fitting of the articulators), articulation strategies (more fine-grained timing control over separate articulators rather than their ensemble) and acoustic simulation (operating the vocal folds by their relative opening rather than by the pressure and voicing controls, and more work on the production of fricatives and trills).

Building an articulatory speech synthesis system

The system is basically made up of three components: the database with the "building blocks" for articulating utterances, the joint control algorithm for the vocal tract and the glottal source, and acoustic simulation. The primary concern of this work are the first two components.

Dataset

The dataset construction and manipulation were inspired by the work of [START_REF] Birkholz | Modeling consonant-vowel coarticulation for articulatory speech synthesis[END_REF]. We used static MRI data, 97 images of the midsagittal section, capturing articulation without phonation: the speaker was instructed to show the position that he would have to attain to produce a particular sound. For vowels, that is the position when the vowel would be at its clearest if the subject were phonating. For consonant-vowel (CV) syllables, that is the blocked configuration of the vocal tract, as if the subject were about to start pronouncing it. The assumption is that such articulation shows the anticipatory coarticulation effects of the vowel V on the consonant C preceding it. There were 13 vowels, 72 CV syllables and 2 semi-vowels in the final dataset. This covers all main phonemes of the French language, but not in all contexts. After manually annotating the captures as shown in Fig. 1 we applied a principal-component-analysis (PCA)-based model on the articulator contours [START_REF] Laprie | Construction and evaluation of an articulatory model of the vocal tract[END_REF][START_REF] Laprie | Geometric articulatory model adapted to the production of consonants[END_REF][START_REF] Laprie | 2D articulatory velum modeling applied to copy synthesis of sentences containing nasal phonemes[END_REF]. Within that model, the jaw is represented by 3 parameters, the tongue by 12, the lips by 3, the velum by 5, the larynx by 3 and the epiglottis by 3, in total forming a vector from R 29 (see Fig. 2 for major parameter contributions to the articulator shape). Since the model uses PCA, the zero configuration should correspond to the central position as identified in the dataset, and small changes in the parameter space within a certain neighborhood of zero should correspond to small changes (in terms of distance and shape, not in terms of the resulting acoustics) in the curves. However, there is inter-articulator correlation taken into account as well as various boundary conditions imposed, so the model's behavior is not entirely linear. This non-linear behavior is especially evident in the lips because their shape defines where the vocal tract should end, and while a change may be minor in the articulatory parameter space, it can result in cutting off the vocal tract at quite different positions.

Expanding the dataset

Since the collected French phonemic dataset was limited, we needed to expand it to cover other contexts as well. We used the notion of the cardinal vowels-/a/, /i/ and /u/,-assuming that /a/, /i/ and /u/ represent the most extreme places of vowel articulation, and since then any other vowel articulation can be expanded as a combination of its /a/, /i/ and /u/ "components". Having captured the C+/a/, C+/i/ and C+/u/ context for all consonants C and all non-cardinal vowels V on their own, we were able to estimate the missing C+V samples:

• We projected the vowel V articulatory vector (from R 29 ) onto the convex hull of the /a/, /i/ and /u/ vectors. • Assuming that the linear relationship between the C+V vector and the C+/a/, C+/i/ and C+/u/ vectors is the same as the one between V and /a/, /i/ and /u/, we estimated C+V from C+/a/, C+/i/ and C+/u/ using the coefficients from the projection of V onto the convex hull of /a/, /i/ and /u/.

We also estimated the pure C configuration as the average of C+/a/, C+/i/ and C+/u/.

Finally, we assumed that the voiced and unvoiced consonants did not have any differences in the articulation.

Strategies for transitioning between the articulatory targets

The dataset provided static images capturing idealistic, possibly over-articulated, targets for consonants anticipating particular vowels, whereas the goal was to be also able to deal with consonant clusters and consonants that would not anticipate any vowel at all-for example, due to their ultimate position in a rhythmic phrase. This is why we imposed several restrictions on the anticipatory effect:

• Temporal: no coarticulatory effect if the anticipated phoneme is more than 200 ms ahead; • Spatial: if there is any movement scheduled between the anticipated vowel, the phoneme in question negates the effect. For example, consider such sequence as /lka/: after /l/, the tongue needs to move backward to produce /k/ before coming back forward for /a/. In this situation, our algorithm does not allow the /l/ to anticipate the coming /a/; • Categorical: it is not possible to anticipate a vowel more than 5 phonemes ahead, and this restriction becomes stricter if it applies across syllable boundaries.

For vowels, there is also a model of target undershoot.

Having established the articulatory targets, the question is how to transition between them. We have tested out three strategies for interpolation between the target vectors:

• Linear: the interpolation between the target vectors is linear; • Cosine; • Complex: transitions vary by the articulators. The critical ones reach for their target position faster than the others, while those articulators whose contribution to the resulting sound intelligibility is not as large move slower. Besides, the articulators composed of heavier tissues (such as the tongue back) move slower than the light and highly mobile ones (such as the lips).

Obtaining the sound

Each vocal tract position was encoded in an area function. They were obtained by the algorithm of [START_REF] Heinz | On the relations between lateral cineradiographs, area functions and acoustic spectra of speech[END_REF] with coefficients adapted by Shinji Maeda and Yves Laprie.

Considering the presence of central and lateral phonemes in the French language and conflicting evidence in the literature [START_REF] Soquet | Mid-sagittal cut to area function tranformations: Direct measurements of mid-sagittal distance and area with MRI[END_REF] and McGowan, Jackson, and Berger (2012)), though, it is quite probable that these coefficients need to be changed dynamically.

We used an acoustic simulation system implemented by Elie and Laprie (2016b) to obtain sound from the area functions and supplementary control files: glottal opening and pitch control.

Glottal opening was modeled by using external lighting and sensing photo-glottography (ePGG) measurements [START_REF] Honda | Glottal-opening and airflow pattern during production of voiceless fricatives: a new noninvasive instrumentation[END_REF]). Within the model, glottis is at its most closed position when producing vowels, nasals and the liquid sound /l/, and momentarily reaches its most open one when producing voiceless fricatives and stops. Voiced fricatives and stops also create peaks in glottal opening, but not as high.

There was no need to model voicing (high-frequency oscillations of low amplitude superimposed onto the glottal opening waves) since the vocal folds operated by the glottal chink model (Elie and Laprie 2016b; Elie and Laprie 2016a) are selfoscillating.

Evaluation

Each step in the system was evaluated on its own, and afterwards the synthesis results were evaluated visually, acoustically and perceptually.

The articulatory model and the trajectories

One peculiarity of the dataset and therefore of the model was the fact that it used only the sagittal section of the speaker's vocal tract. While full three-dimensional models can capture the full geometry of the vocal tract with such phenomena as lateral phonemes (e.g. /l/), two-dimensional models get the benefit of faster computation time and overall simplicity, but irreversibly lose the spatial information.

In general, the articulatory model captured vocal tract positions correctly or with no critical errors, and some adjustments could be necessary only at the points of constriction, since on its own the model did not impose much control over them. This is a disadvantage brought by the nature of the articulatory model: choosing to operate at the level of articulators rather than the resulting vocal tract geometry.

As for the movements, for now we can say that they were reasonable and the coarticulation-affected targets guided the articulators to the positions necessary to produce a particular utterance. One key point here is the timing strategy. Rulebased timing strategy seems to be very rigid for the dynamic nature of speech; it would be more natural to follow speech production processes in humans and to guide the synthesis with the elicited sound or the speaker's expectation-based on their experience-on what this sound will be. We plan to evaluate the transitions with new dynamic MRI data.

Glottal opening control

The algorithm for the glottis opening successfully allowed to distinguish between vowels and consonants. Distinguishing between voiced and voiceless consonants, though, stays a point for improvement, as well as well-coordinated control over the glottis and the vocal tract.

The synthesized sound

Vowels and stops were the most identifiable and correct, although sometimes some minor adjustments in the original data were necessary to obtain formants close to the reference values. When compared to human speech, the formant transitions within the suggested strategies sometimes occurred too fast and sometimes too slowly; again, this highlights the utmost importance of realistic timing strategies. Fig. 3 shows an example of the synthesis when it is not guided by real timing: /aSa/ as produced by the system and as uttered by a human. The highfrequency contributions in vowels, not appearing in the human sample, are due to the acoustic simulation. The noise of /S/ is at the correct frequencies, but with a bit different energy dis-tribution, probably because of differences in articulation or in the area functions. There are also differences in phoneme duration: the synthesized /S/ is shorter, and both instances of /a/ are longer. It does not mean that the synthesized version is wrong; one human sample does not have to be the only correct way to say this. Nevertheless it could lead a synthesis result to sound unnatural. Figure 3: An example of synthesis of /aSa/ (above) and its utterance by a human (below).

Conclusion

Regarding speech as a process of transitioning between contextaware targets is an interesting approach that can be connected with the mental processes of speech production: to allow the others to perceive the necessary acoustic cue, the speaker needs to come close enough to the associated articulatory goal. The important difference between a real speaker and the algorithm is the fact that the algorithm solves a static problem, laid out in full; it needs to hit particular targets in a given order. As for humans, we solve a dynamic problem, and coarticulation is not something we put in its definition; rather, coarticulation is our means to make the problem of reaching too many targets in a too short period of time solvable.

The statistically derived articulatory model encodes complicated shapes of the articulators in only 29 parameters, sometimes struggling at the constrictions because of the inherentand intentional-lack of control over the resulting geometry of the vocal tract.

Those shapes of the articulators change in time according to the produced trajectories of the vocal tract, and those are phonetically sound. Whether there are any important differences between the produced transitions and the ones in real speech, needs to be verified with actual dynamic data.

After the aspect of how the articulators move we need to consider when. The timing strategies, currently rule-based, apparently need to be extracted from dynamic data, and we can use the approaches by Elie et al. (2016) for that.

A closer, intertwined interaction with the acoustic simulation unit-such as guidance on how to navigate between the area functions at the level of separate acoustic tubes and im-proved control over the glottal opening-could improve the results for consonants.

Figure 1 :

 1 Figure 1: An example of dataset image annotation (/a/).

Figure 2 :

 2 Figure 2: The PCA-based articulatory model: curve change directions encoded in the first three factors of each articulator (the jaw, the tongue, the lips, the epiglottis, the larynx).

Acknowledgments

The data collection for this work benefited from the support of the project ArtSpeech of ANR (Agence Nationale de la Recherche), France.