Fully-Anonymous Functional Proxy-Re-Encryption Yutaka Kawai and Katsuyuki Takashima Mitsubishi Electric, 5-1-1 Ofuna, Kamakura, Kanagawa 247-8501, Japan, [email protected], [email protected] October 11, 2013 Abstract. Inthispaper,weintroduceageneralnotionoffunctionalproxy-re-encryption(F-PRE),where awideclassoffunctionalencryption(FE)iscombinedwithproxy-re-encryption(PRE)mechanism.The PREencryptionsystemshouldrevealminimalinformationtoaproxy,inparticular,hidingparametersof re-encryptionkeysandoforiginalciphertextswhichhemanipulateishighlydesirable.Wefirstformulate such a fully-anonymous security notion of F-PRE including usual payload-hiding properties. We then propose the first fully-anonymous inner-product PRE (IP-PRE) scheme, whose security is proven under the DLIN assumption and the existence of a strongly unforgeable one-time signature scheme in the standardmodel.Also,weproposethefirstciphertext-policyF-PREschemewiththeaccessstructuresof Okamoto-Takashima (CRYPTO 2010), which also has an anonymity property for re-encryption keys as well as payload-hiding for original and re-encrypted ciphertexts. The security is proven under the same assumptions as the above IP-PRE scheme in the standard model. For these results, we develop novel blind delegation and subspace insulation for re-enc key basis techniques on the dual system encryption (DSE) paradigm and the dual pairing vector spaces (DPVS) approach. These techniques seem difficult to be realized by a composite-order bilinear group DSE approach. 1 1 Introduction 1.1 Background The notions of inner-product encryption (IPE) and attribute-based encryption (ABE) introduced by Katz, Sahai and Waters [13] and Sahai and Waters [31] constitute an advanced class of encryption, functional encryption (FE), and provide more flexible and fine-grained functionalities in sharing and distributing sensitive data than traditional symmetric and public-key encryption as well as identity- based encryption (IBE). In FE, there is a relation R(v,x), that determines whether a secret key associated with a parameter v can decrypt a ciphertext encrypted under another parameter x. The parametersforIPEareexpressedasvectors⃗x(forencryption)and⃗v (forasecretkey),whereR(⃗v,⃗x) holds, i.e., a secret key with ⃗v can decrypt a ciphertext with ⃗x, iff ⃗v·⃗x = 0. (Here, ⃗v·⃗x denotes the standard inner-product.) In ABE systems, either one of the parameters for encryption and secret key is a set of attributes, and the other is an access policy (structure) or (monotone) span program over a universe of attributes, e.g., a secret key for a user is associated with an access policy and a ciphertext is associated with a set of attributes, where a secret key can decrypt a ciphertext, iff the attribute set satisfies the policy. For some applications for FE, the parameters for encryption are required to be hidden from ciphertexts. To capture the security requirement, Katz, Sahai and Waters [13] introduced attribute- hiding (based on the same notion for hidden vector encryption (HVE) by Boneh and Waters [6]), a security notion for FE that is stronger than the basic security requirement, payload-hiding. Roughly speaking, attribute-hiding requires that a ciphertext conceal the associated parameter as well as the plaintext, while payload-hiding only requires that a ciphertext conceal the plaintext. Informally, in the(fully)attribute-hiding,thesecrecyofchallengeattributex(0),x(1) isensuredagainstanadversary having a secret key with v such that R(v,x(0)) = R(v,x(1)) holds (even if R(v,x(b)) = 1), i.e., the adversary cannot guess bit b if the compatibility condition R(v,x(0)) = R(v,x(1)) for the challenge holds. (It is a maximal requirement since if the challenge is incompatible for some key query, an adversary easily guess the challenge bit.) Inner-products for IPE represent a fairly wide class of relations including equality tests as the simplest case, disjunctions or conjunctions of equality tests, and, more generally, CNF or DNF formulas. We note, however, that inner-product relations are less expressive than a class of relations (on span programs) for ABE, while existing ABE schemes for such a wider class of relations are not attribute-hiding but only payload-hiding. Among the existing IPE schemes, only the OT12 IPE scheme [29] achieves the full (adaptive) security and fully attribute- hiding simultaneously. As for ABE, Lewko et.al. and Okamoto-Takashima ABE schemes [14,27] are fully secure in the standard model. Proxy-re-encryption(PRE)isaninterestingextensionoftraditionalpublickeyencryption(PKE). In addition to the normal operations of PKE, with a dedicated re-encryption key (generated by an original receiver A), a proxy can turn ciphertexts originally destined for user A (called original ciphertexts) into those for user B. A remarkable property of PRE is that the proxy carrying out the transform is totally ignorant of the plaintext. PRE was first formalized by Blaze et al. [4] and has received much attention in recent years. There are many models as well as implementations; refer to [4,2,8,20,33,19,9,34,35,12,23,22,11,17] for some examples. Extending FE with PRE, i.e., functional PRE (F-PRE), improves various aspects of existing FE. Forexample,whenAlicecontactsalocalgovernmentontaxandsocialsecurity,shesubmitsencrypted information to a man to contact (say, Bob) since she has no knowledge on the inner structure of the government,whichisusuallyaconfidentialmatter.Bobisgivenare-encryptionkeyfromhismanager, and then re-encrypts the encrypted message on tax to an appropriate department X, and that on social security to another department Y, while Bob learns nothing on the contents for the privacy of 2 Table 1. Comparison of our schemes with existing Ciphertext-Policy (CP)-AB-PRE schemes [19,22,18], where q, d, jUj,jΓj,ℓ(resp.ℓ′)andnrepresentthenumberofkeyqueries,thenumberofsub-universesofattributes,themaximum sizeofasub-universe,thenumberofattributesforthesecretkey,thenumberofrowsinaccessmatrixfortheoriginal ciphertext (resp.re-enc key or re-enc ciphertext) and the dimension for attribute vectors, respectively. STdM, ROM, CTDH, ADBDH, DBDH, BDHE, and sUF stand for standard model, random oracle model, complex triple Diffie- Hellman problem, augment decisional bilinear Diffie-Hellman problem, the decisional bilinear Diffie-Hellman problem, and the bilinear Diffie-Hellman exponent problem, strongly unforgeable, respectively. (PK, SK, RK, OCT and RCT stand for public key, secret key, re-encryption key, original ciphertext, re-encrypted ciphertext, respectively.) LCLS09 [19] LHC10 [22] LFWS13 [18]a Proposed Primitive CP-AB-PRE CP-AB-PRE CP-AB-PRE IP-PREb CP-AB-PRE Security selective selective selective adaptive adaptive model in STdM in STdM in ROM in STdM in STdM (large-universe) (large-universe) Access non-monotonic non-monotonic monotonic inner-product non-monotonic structures AND gates AND gates span programs relations span programs CTDH & DLIN & DLIN & Assumptuion ADBDH DBDH q-parallel BDHE sUF sig. sUF sig. Anonymity (cid:2) (cid:2) (cid:2) ✓ ✓ against Proxy PK/SK/ O(d)/O(d)/ O(djUj)/O(d)/ O(1)/O(jΓj)/ O(n)/O(n)/ O(d)/O(jΓj)/ RK sizec O(d) O(d) O(jΓj+ℓ′) O(n2) O(d+ℓ′) OCT/RCT sizec O(d)/O(d) O(1)/O(1) O(ℓ)/O(ℓ+ℓ′) O(n)/O(n2) O(ℓ)/O(d+ℓ+ℓ′) a The large-universe CP-AB-PRE obtained from small-universe one in [17] has similar features as that of [18]. b An efficient version of our fully-anonymous IP-PRE scheme in Section 4.2 by applying the sparse matrix technique given in [28] c The number of group elements is given with a common assumption in the ABE/IPE application that the description of the attribute or policy is not considered a part of SK/RK/OCT/RCT. Alice. (By using our fully anonymous F-PRE, Bob need not know even the destinations, X or Y.) Such re-encryption by attributes also deals with personnel changes flexibly: When the department X (or some of the members) is changed to Y, Bob re-encrypts an encrypted message originally for X to that destined to Y. As the examples show, F-PRE realizes convenient private communication even among organizations with unknown or changeable inner structures. Previously, various combinations of PRE and special classes of FE exist, that is, ID-based PRE (IB-PRE) [12,23,11], broadcast encryption based PRE [10,38], attribute-based PRE (AB-PRE) [19, 24,22,17,18]. While the notion of AB-PRE covers the existing F-PRE schemes above, the previous AB-PRE schemes [19,22,17,18] only achieve a weak security, that is, security in the selective model (Table 1). Also, access structures which can be treated in the previous AB-PRE [19,24,22] are just conjunctive (AND) formulas, not disjunction (OR) or negation (NOT). Thus, these previous F-PRE schemes are insufficient from the view point of functionality or security, or both. In recent applications, usually, the data is outsourced to an outside remote server. Then, since we do not trust on the server manager, or proxy, any more, another important requirement for PRE is anonymity for a re-encryption key:As wellas an encrypted message, source and target parameters of ′ a re-encryption key, i.e., v and x of rkv,x′, should be concealed from the proxy. The security property ensures that we can securely outsource the re-encryption task to the proxy. Surprisingly, many previous PRE schemes (even of traditional PKE-based) has no anonymity for a re-encryption key. The first anonymous (PKE-based) PRE scheme was proposed by Ateniese et al.[1], however, the security is only proven in a weak security model, where only a restricted adversary is considered. While the weak point was removed in a subsequent work by Shao et al.[36], 3 Table 2. Comparison of anonymity properties (“Anonimity” and “Unlinkability”) between our schemes and existing several anonymous (F-)PRE schemes [1,11,36,32,21]. STdM, ROM, OCT, RCT, RK and AH-RK stand for standard model, random oracle model, original ciphertext, re-encrypted ciphertext, re-encryption key and attribute-hiding for re-encryption keys, respectively. ABH09 [1] SLWL12 [36] EMO11 [11] Shao12 [32] Proposed Primitive (PK-)PRE IB-PRE IP-PRE CP-AB-PRE Security model in STdM in ROM in ROM in STdM Anonimity for partial ✓ ✓ab ✓a ✓ ✓ ✓ OCT/RCT/RK (only for AH-RK) Unlinkability for partial ✓ partial ✓ ✓ ✓ ✓ ✓ RCT/RK (only for RK) (only for RK) a An original ciphertext has an anonymity in the sense that it cannot be linked to the used public key. b The anonymity for RK is only proven in a weak security model, where an adversary cannot query with the same parameter twice to the re-encryption key oracle. the security of their scheme is proven only in the random oracle model. Moreover, anonymous F- PRE schemes were proposed in [11,32], however, they are less expressive ID-based PRE and the security is claimed just in the random oracle model. No such kinds of anonymous (including key- private)expressive inner-product(IP-)PREexists.Namely,existinganonymousF-PREconstructions are quite insufficient. See Table 2 for the comparison on anonymous F-PRE. An anonymous F-PRE scheme should have usual anonymous FE security requirements, that is, payload-hidingand(fully-)attribute-hiding securityfororiginalandre-encryptedciphertexts.And,as ′ mentioned, parameters (v,x), which we call predicate and attribute, respectively, in a re-encryption key rkv,x′ should be also concealed. The secrecy should be kept against a powerful adversary who can access a combination of decryption key, re-encryption key, and re-encryption queries. For example, even using the two types of keys, an original ciphertext should not reveal additional information on message or attributes. We will give a reasonable security definition including the above basic requirements (in Section 3) and call it fully-anonymity. Ourfirsttargetisanadaptively secureandfully anonymousIP-PREscheme(Table2).Amongthe aboverequirements,(full)attribute-hidingpropertyforanoriginalciphertextisthemostchallenging since an adversary can apply queried decryption keys, re-encryption keys, and re-encryption oracle to the target ciphertext. Even if we use the dual system encryption (DSE) by Waters [37] and its extension in [29], the main difficulty resides in how to change a (normal) re-encryption key queried with(⃗v,⃗x′)toasemi-functionalre-encryptionkey,before seeing the challenge (⃗x(0),⃗x(1)),i.e.,without knowing whether R(⃗v,⃗x(0)) = R(⃗v,⃗x(1)) holds or not. We will explain it below: The previous fully attribute-hidingIPEsecuritygameallowsanon-matchingkeyquery,anditrequiresthatadecryption key query ⃗v is compatible with the challenge (⃗x(0),⃗x(1)), i.e., R(⃗v,⃗x(0)) = R(⃗v,⃗x(1)). (The case that R(⃗v,⃗x(0)) = R(⃗v,⃗x(1)) = 0 is a non-matching one.) While this condition for the challenge and decryption key queries is common for the previous FE systems, a (fully-anonymous) F-PRE scheme must also deal with a more complicated condition, i.e., R(⃗v,⃗x(0))·R(⃗v′,⃗x′) = R(⃗v,⃗x(1))·R(⃗v′,⃗x′) (1) ′ ′ for any re-encryption key query (⃗v,⃗x ) and decryption key query ⃗v . It reflects one attack strategy of the adversary, where he (or she) tries to convert the challenge ciphertext to a re-encrypted one by a queried re-encryption key rk⃗v,⃗x′ and then decrypt it by a queried decryption key sk⃗v′. We consider ′ ′ ′ ′ some fixed re-encryption key query (⃗v,⃗x ) below. If R(⃗v ,⃗x ) = 1 for some decryption key query ⃗v , 4 Eq.(1)isequivalenttoR(⃗v,⃗x(0)) = R(⃗v,⃗x(1)).However,ifR(⃗v′,⃗x′) = 0foranydecryptionkeyquery ⃗v′, Eq.(1) holds unconditionally even in the incompatible case, i.e., R(⃗v,⃗x(0)) ̸= R(⃗v,⃗x(1)). At a first glance, it looks hard to treat with both the cases simultaneously, since the form of semi-functional re-encryption key may be different depending on whether R(⃗v,⃗x(0)) = R(⃗v,⃗x(1)) or not, and the simulator does not know the fact when the re-encryption key query occurs before the challenge. Another technically challenging target in this paper is to prove the security under the decisional linear (DLIN) assumption (on prime order pairing groups) in the standard model. 1.2 Our Results 1. This paper introduces a new notion of functional proxy-re-encryption (F-PRE). The system should reveal minimal information to a proxy, in particular, hiding parameters in re-encryption keys and in original ciphertexts which he manipulates is highly desirable. We first formulate such a fully-anonymous notion of F-PRE, which includes usual payload-hiding properties. It can be consideredasanaturalextensionoffully-attribute-hidingFE.Thenotionconsistsofthefollowing security requirements, which are informally described, and more formally defined by the games against an adversary with access to decryption, re-encrypted key, and re-encryption queries (see ′ Section 3 for the formal definitions). Here, parameters x,x and v are called attributes and a predicate, respectively. Attribute-Hiding Security for Original Ciphertexts: An original ciphertext for plaintext m and attribute x releases no information regarding (m,x) against a user not in possession of a matching decryption key sk with R(v,x) = 1, or a matching key pair of a re-encryption v ′ ′ key and a decryption key (rkv,x′,skv′) with R(v,x) = 1 and R(v ,x) = 1. It also releases no information regarding x against a user in possession of a matching decryption key sk except v ′ ′ thatR(v,x) = 1oramatchingkeypair(rkv,x′,skv′)exceptthatR(v,x) = 1andR(v ,x) = 1. Predicate- and Attribute-Hiding Security for Re-encrypted Ciphertexts: Are-encrypted ciphertextforplaintextm(andoriginalattributex)andre-encryptionkeyrkv,x′ withattribute ′ ′ x releasesnoinformationregarding(m,x,v;x)againstausernotinpossessionofamatching ′ ′ decryption key skv′ for x, and no information regarding x against a user in possession of a ′ ′ matching decryption key skv′ except that R(v ,x) = 1. Predicate- and Attribute-Hiding Security for Re-encryption Keys: Are-encryptionkey ′ ′ for predicate and attribute (v,x) releases no information regarding (v,x) against a user not ′ ′ in possession of a matching key for x, and no information regarding x against a user in ′ ′ possession of a matching decryption key skv′ except that R(v ,x) = 1. Unlinkability of Re-encryption Keys: A re-encryption key generated from a decryption key cannot be linked to the decryption key by any means (unconditional unlinkability). Unlinkability of Re-encrypted Ciphertexts: A re-encrypted ciphertext generated from a re-encryption key and an original ciphertext cannot be linked to the re-encryption key or the original ciphertext by any efficient adversary (computational unlinkability). Full Anonymity: We say that an F-PRE scheme is fully-anonymous if it satisfies the above three hiding requirements given in three adaptive security games, and two unlinkability re- quirements. 2. Thispaperproposesthefirstfully-anonymousinner-productproxy-re-encryption(IP-PRE)scheme, whose security is proven under the DLIN assumption and the existence of a strongly unforgeable one-time signature scheme in the standard model (Tables 1 and 2, Theorem 1). The IP-PRE scheme uses an underlying fully attribute-hiding IPE scheme, which was proposed in [29]. It shows a new significant application of fully attribute-hiding property except for searchable en- cryption. For achieving the security properties, we use two key techniques, blind delegation and hidden subspace insulation for (extended) dual system encryption. 5 re-enc key generation ( encryption by with ) blind delegation & CHK transformed re-randomization (re-)encryption by with re-randomized Fig.1. Basic Conversions among secret key skv, re-encryption key rkv,x′, original ciphertext octx and re-encrypted ciphertext rctx′ in a high-level description 3. We also propose the first ciphertext-policy (CP-)F-PRE scheme with the access structure class givenbyOkamoto-Takashima[27],whichincludesnon-monotonespanprogramaccessstructures. The construction is based on our IP-PRE schemes. The scheme is proven to be payload-hiding of originalandre-encryptedciphertexts,attribute-hidingofre-encryptionkeys,andunlinkableunder thesameassumptionsasthoseofourIP-PREschemes(Tables1and2).Here,hidingattributesof re-encryption keys is an important requirement for anonymous re-encryption outsourcing. Refer to Appendix E. 1.3 Key Techniques AswementionedinSection1.1,inourfully-anonymousF-PRE,whileadecryptionkeyqueryvshould satisfy a simple compatibility condition (R(v,x(0)) = R(v,x(1))) with the challenge, a re-encryption ′ key query (v,x) need satisfy a complicated condition in Eq.(1), which includes an incompatible case (R(v,x(0)) ̸= R(v,x(1))). All the previous DSE proofs (including the fully-attribute-hiding one [29]) use the compatibility condition as an essential logical ingredient. Hence, we need to develop an extended DSE technique which allows the incompatible case for achieving adaptively secure and fully-anonymous F-PRE. CHK Transform and Blind Delegation: As a first attempt, to conceal sk (including v) from a v malicious proxy, we encrypt it as (EncW1(skv),FEncx′(W1)) in a re-encryption key rkv,x′, where Enc is an ordinary (symmetric) encryption scheme with secret W , and FEnc is a functional encryption 1 ′ ′ scheme with parameter x. Then, if an adversary has no matching key for x, he has no information of sk nor v. v If these components are also embedded into a re-encrypted ciphertext rctx′ without modification, ′ a user with a matching key for x obtains the original sk . It is not desirable for (F-)PRE, therefore, v modified forms of EncW1(skv) (and FEncx′(W1))) should be embedded into a re-encrypted ciphertext rctx′. For achieving an appropriate modification, we use two ingredients, the Canetti-Halevi-Katz (CHK) transformation [7] and blind delegation (see Figure 1). The CHK transformation converts a ciphertextctx toctx∧verk,whereverkisaverificationkeyofaone-timesignaturescheme,andx∧verk is the conjunction of x (for relation R) and verk (for identity matching). An original ciphertext in our F-PRE schemes consists of octx := (ctx∧verk,verk,S) with S is a signature of ctx∧verk by a corresponding signature generation key. Then, a decryptor of oct first verifies if S is valid under x verk, and if so, correctly decrypts ctx∧verk with a decryption key. By this mechanism, an adversary cannot modify the challenge ciphertext meaningfully. Using verk in input, a re-encryptor modifies 6 (or delegates) skv to skv∧verk, which is specialized to ctx∧verk in the input original ciphertext. Since ctx∧verk cannotbemodifiedtoanothermeaningfulone,modifiedskv∧verk isonlyeffectivetoctx∧verk. Here,wehaveatechnicalchallenge:There-encryptorshouldmodifyEncW1(skv)toEncW1(skv∧verk) without decrypting Enc (sk ), i.e., in an encrypted form. For achieving it, in our schemes, we will W1 v f f include EncW1(pk) in a re-encryption key rkv,x′, where pk is a part of the public key. Namely, rkv,x′ f essentially consists of (EncW1(skv),FEncx′(W1),EncW1(pk)), and in re-encryption, a re-encryptor del- f egates EncW1(skv) to EncW1(skv∧verk) using EncW1(pk) in a blind manner. Hence, we call such a new technique blind delegation. We develop it based on the dual pairing vector spaces (DPVS) framework [26,27,29]. (See REnc algorithms in Sections 4.1 and 4.2.) Moreover, in order not to allow a matching key holder for x to decrypt a re-encrypted ciphertext rctx′ (with x′ ̸= x), ctx∧verk in an input original ciphertext is encrypted with another secret W2 in re- encryption. Hence, the re-encrypted ciphertext rctx′ essentially consists of (EncW2(ctx∧verk),FEncx′( W2),EncW1(skv∧verk),FEncx′(W1)), where FEncx′(W1) is re-randomized for an unlinkability require- ′ ment (Figure 1). A decryptor with a matching key for x first obtains W and W and calculates 1 2 Dec(skv∧verk, ctx∧verk) by using usual decryption. Information-Theoretical Insulation of a Subspace for Re-Enc Key Basis: For formal security proof, we use a novel technique (subspace insulation for re-enc key basis) for realizing DSE with allowing an incompatible re-encryption key query. In an original DSE security game [37,27], each queried decryption key is changed to semi-functional, one by one. In our F-PRE, we also change eachqueriedre-encryptionkeytosemi-functional,onebyone.Sinceasimulator(challenger)doesnot know whether the query is compatible or incompatible to the challenge before seeing the challenge query, the semi-functional form should not depend on the compatibility type. Namely, we need to give two (or more) different and consistent simulations for the same semi-functional re-encryption ′ key for (v,x) with the following requirements: ′ – If some matching decryption key for x is queried, the adversary obtains the secret W for the 1 re-encryption key. The challenger must simulate a semi-functional form of a decryption key sk , v which can be decrypted from Enc (sk ) by using W . W1 v 1 ′ – If no matching decryption keys for x are queried, the adversary has no W for the re-encryption 1 key. The challenger must simulate Enc (sk ) which is consistent with the above semi-functional W1 v form of sk . For the simulation, we use an insulated subspace since W is hidden for the adversary. v 1 To achieve the above simulations, we realize a nice trick based on the DPVS framework. That is, we can create a (hidden) subspace of a re-enc key basis D∗ := B∗·W , which is information-theoretically 1 1 insulated from the master key bases (B,B∗). We elaborately combine this trick for the second type of re-encryption key queries, and a similar game change as in the original (and extended) DSE in [27, 29] for the first type key queries based on a pairwise independent argument. For the details of the technique, refer to Appendix D.1 and Figure 2. DPVS Framework: Both techniques, i.e., blind delegation and subspace insulation for re-enc key ∗ basis, are built on the DPVS framework, where a ciphertext c and a secret key k are encoded on a x v random basis B := (b ) and its dual B∗ := (b∗), respectively. For blind delegation, a random matrix i i W in FN×N transforms k∗ and b∗(∈ pfk) to k∗rk := k∗W and d∗ := b∗W (∈ Enc (pfk)) in a re- 1 q v i v v 1 i i 1 W1 encryptionkey,then,REncdelegatesk∗rk tok∗rk byusingd∗ insteadofb∗.Forthedelegation,not v v∧verk i i allbasisvectors d∗ (inD∗)are includedinthe re-encryptionkey,hence,an insulated hiddensubspace i from a subbasis of D∗ := (d∗) is used for proving adaptive security against an adversary, and the i basis changing technique is crucial for our constructions. In composite-order DSE schemes, a hidden subspace (subgroup) is given by the order-q subgroup in order-pqr subgroup (with p,q,r primes), for example. Therefore, while the DPVS approach is suitable for the above subspace insulation, the composite-order bilinear group approach seems to be difficult to realize them. 7 1.4 Notations When A is a random variable or distribution, y ←R A denotes that y is randomly selected from A according to its distribution. When A is a set, y ←U A denotes that y is uniformly selected from A. We denote the finite field of order q by F , and F \ {0} by F×. A vector symbol denotes a q q q vector representation over F , e.g.,⃗x denotes (x ,...,x ) ∈ Fn. For two vectors⃗x = (x ,...,x ) and q ∑1 n q 1 n ⃗v = (v ,...,v ),⃗x·⃗v denotestheinner-product n x v .Thevector⃗0isabusedasthezerovectorin 1 n i=1 i i Fn for any n. XT denotes the transpose of matrix X. A bold face letter denotes an element of vector q space V, e.g., x ∈ V. When b ∈ V (i = 1,...,n), span⟨b ,...,b ⟩ ⊆ V (resp. span⟨⃗x ,...,⃗x ⟩) i 1 n 1 n denotes the subspace generated by b ,...,b (resp. ⃗x ,...,⃗x ). For bases B := (b ,...,b ) and 1∑ n 1 n ∑ 1 N B∗ := (b∗1,...,b∗N), (x1,...,xN)B := Ni=1xibi and (y1,...,yN)B∗ := Ni=1yib∗i. ⃗ej denotes the zj}−|1{ zn}−|j{ canonical basis vector (0···0,1,0···0) ∈ Fn. GL(n,F ) denotes the general linear group of degree q q n over F . q 2 Dual Pairing Vector Spaces (DPVS) De(cid:12)nition 1. “Symmetric bilinear pairing groups” (q,G,G ,G,e) are a tuple of a prime q, cyclic T additive group G and multiplicative group G of order q, G ̸= 0 ∈ G, and a polynomial-time com- T putable nondegenerate bilinear pairing e : G×G → G i.e., e(sG,tG) = e(G,G)st and e(G,G) ̸= 1. T Let G be an algorithm that takes input 1λ and outputs a description of bilinear pairing groups bpg (q,G,G , G,e) with security parameter λ. T In this paper, we concentrate on the symmetric version of dual pairing vector spaces [25,26]. constructed by using symmetric bilinear pairing groups given in Definition 1. For the asymmetric version of DPVS, (q,V,V∗,G ,A,A∗,e), see Appendix A.2 in the full version of [27]. T De(cid:12)nition 2. “Dual pairing vector spaces (DPVS)” (q,V,G ,A,e) by a direct product of symmetric T z }N| { pairing groups (q,G,G ,G,e) are a tuple of prime q, N-dimensional vector space V := G×···×G T z i}−|1 { over F , cyclic group G of order q, canonical basis A := (a ,...,a ) of V, where a := (0,...,0,G, q T 1 N i z N}−|i { ∏ 0,...,0), and pairing e : V×V → G . The pairing is defined by e(x,y) := N e(G ,H ) ∈ G where T i=1 i i T x := (G ,..., G ) ∈ V and y := (H ,...,H ) ∈ V. This is nondegenerate bilinear i.e., e(sx,ty) = 1 N 1 N e(x,y)st and if e(x,y) = 1 for all y ∈ V, then x =⃗0. For all i and j, e(ai,aj) = e(G,G)δi,j where δ = 1 if i = j, and 0 otherwise, and e(G,G) ̸= 1 ∈ G . DPVS generation algorithm G takes i,j T dpvs input 1λ (λ ∈ N) and N ∈ N, and outputs a description of param′ := (q,V,G ,A,e) with security V T parameter λ and N-dimensional V. It can be constructed by using G . bpg For matrix W := (w ) ∈ FN×N and element g := (G ,...,G ) in N-dimensional V, ∑ i,j i,j=1∑,...,N q ∑ ∑1 N gW denotes ( N G w ,..., N G w ) = ( N w G ,..., N w G ) by a natural mul- i=1 i i,1 i=1 i i,N i=1 i,1 i i=1 i,N i tiplication of a N-dim.row vector and a N × N matrix. Thus it holds an associative law like (gW)W−1 = g(WW−1) = g. 3 Functional Proxy-Re-Encryption In this section, we define a notion of functional proxy-re-encryption, F-PRE, and its security. An attribute and a predicate are expressed as x and v, respectively. We denote R(v,x) = 1 that a 8 relation holds for v and x. Informally speaking, F-PRE is functional encryption with re-encryption mechanism, that is, an FE scheme with additional algorithms, re-encryption key generation (RKG) and re-encryption (REnc). RKG algorithm, which takes as input a decryption key of FE sk and an v ′ ′ attribute x, generates a re-encryption key rkv,x′ which is associated with v and x. A proxy who is given a re-encryption key rkv,x′ and an original ciphertext with x, can computes a re-encrypted ′ ciphertext with attribute x from a ciphertext with x using REnc algorithm if R(v,x) = 1. De(cid:12)nition 3 (Functional Proxy-Re-Encryption: F-PRE). A functional proxy-re-encryption scheme consists of the following seven algorithms. Setup: takes as input a security parameter 1λ and a format parameter Λ. It outputs public key pk and (master) secret key sk. KG: takes as input the public key pk, the (master) secret key sk, and a predicate v. It outputs a corresponding decryption key sk . v Enc: takes as input the public key pk, an attribute x, and a plaintext m in some associated plaintext space. It outputs an original ciphertext oct . x ′ RKG: takes as input the public key pk, a decryption key sk , and an attribute x. It outputs a re- v encryption key rkv,x′. REnc: takes as input the public key pk, a re-encryption key rkv,x′, and an original ciphertext octx. It outputs a re-encrypted ciphertext rctx′. Dec : takes as input the public key pk, a decryption key sk , and an original ciphertext oct . It oct v x outputs either a plaintext m or the distinguished symbol ⊥. Decrct: takes as input the public key pk, a decryption key skv′, and a re-encrypted ciphertext rctx′. It outputs either a plaintext m or the distinguished symbol ⊥. The correctness for an F-PRE scheme is defined as: 1. Foranyplaintextm,any(pk,sk) ←R Setup(1λ),anyvandx,anydecryptionkeysk ←R KG(pk,sk,v), v andanyoriginalciphertextoct ←R Enc(pk,x,m),wehavem =Dec (pk,sk ,oct )ifR(v,x) = 1. x oct v x Otherwise, it holds with negligible probability. 2. Foranyplaintextm,any(pk,sk) ←R Setup(1λ),anyv,v′,x,x′,anydecryptionkeysk ←R KG(pk,sk,v), v any re-encryption key rkv,x′ ←R RKG(pk,skv,x′), any original ciphertext octx ←R Enc(pk,x, m), and re-encrypted ciphertext rctx′ ←R REnc(pk,rkv,x′,octx), we have m = Decrct(pk, skv′,rctx′) if ′ ′ R(v,x) = 1 and R(v ,x) = 1. Otherwise, it holds with negligible probability. De(cid:12)nition 4. We introduce a useful (multiplicative) notation “•” for describing our security defi- nitions (Definitions 5–7) concisely. For any variable X, { X if R(v,x) = 1, X •R(v,x) := ⊥ if R(v,x) = 0. Let m•R(v,x)•R(v′,x′) mean (m•R(v,x))•R(v′,x′). Then, the results of items 1 and 2 in the above correctness are rephrased as m•R(v,x) = Dec (pk,sk ,oct ) and m•R(v,x)•R(v′,x′) = oct v x Decrct(pk, skv′,rctx′), respectively. Next, we define four security properties of F-PRE. De(cid:12)nition 5 (Attribute-Hiding for Original Ciphertexts (AH-OC)). The model for defin- ing the (adaptively) attribute-hiding security for original ciphertexts of F-PRE against adversary A (under chosen plaintext attacks) is given by the following game: 9 Setup. The challenger runs the setup algorithm (pk,sk) ←R Setup(1λ), and it gives the security parameter λ and the public key pk to the adversary A. Phase 1. The adversary A is allowed to adaptively issue a polynomial number of queries as follows. Decryption key query. For a decryption key query v, the challenger gives sk ←R KG(pk,sk,v) v to A. ′ Re-encryption key query. For a re-encryption key query (v,x), the challenger computes rkv,x′ ←R RKG(pk,skv,x′) where skv ←R KG(pk,sk,v). It gives rkv,x′ to A. ′ Re-encryption query. For a re-encryption query (v,x,octx), the challenger computes rkv,x′ ←R RKG(pk,skv,x′) where skv ←R KG(pk,sk,v) and rctx′ ←R REnc(pk,rkv,x′,octx). It gives rctx′ to A. Challenge. For a challenge query (m(0),m(1),x(0),x(1)) subjected to the following restrictions: ′ – Any decryption key query v and any re-encryption key query (v ,x ) for ℓ = 1,...,ν satisfy ℓ ℓ 2 m(0)•R(v,x(0)) = m(1)•R(v,x(1)) and m(0)•R(v ,x(0))•R(v,x′) = m(1)•R(v ,x(1))•R(v,x′). ℓ ℓ ℓ ℓ The challenger flips a random bit b ←U {0,1} and gives oct ←R Enc(pk,x(b),m(b)) to A. x(b) Phase 2. The adversary A may continue to issue decryption key queries, re-encryption key queries and re-encryption queries, subjected to the restriction in challenge phase and the following addi- tional restriction for re-encryption queries. ′ Re-encryption query. For a re-encryption query (v ,x ,oct ) for t = 1,...,ν , subject to the t t t 3 following restrictions: – m(0)•R(v ,x(0))•R(v′,x′) = m(1)•R(v ,x(1))•R(v′,x′) for any decryption key query for t t t t ′ v if oct = oct t x(b) TIthgeivcehsalrlcetnxg′etrocoAm.putesrkvt,x′t ←R RKG(pk,KG(pk,sk,vt),x′t)andrctx′t ←R REnc(pk,rkvt,x′t,octt). Guess. A outputstits guess b′ ∈ {0,1} for b and wins the game if b = b′. We define the advantage of A as AdvAH-OC(λ) := Pr[b = b′]− 1. An F-PRE scheme is attribute- A 2 hiding for original ciphertexts if all polynomial time adversaries have at most negligible advantage in the above game. For each run of the game, we define three types of variables s ,s ,s (ℓ = m rk,ℓ renc,t 1,...,ν ,t = 1,...,ν ) as follows: 2 3 – For challenge plaintexts m(0) and m(1), s := 0 if m(0) ̸= m(1) and s := 1, otherwise. m m – For the ℓ-th re-encryption key query (v ,x′) and challenge (m(0),x(0)) and (m(1),x(1)), ℓ ℓ s := 0 if m(0)•R(v ,x(0)) ̸= m(1)•R(v ,x(1)) and s := 1 otherwise. rk,ℓ ℓ ℓ rk,ℓ – For the t-th re-encryption query (v ,x′,oct ) and challenge (m(0),x(0)) and (m(1),x(1)), t t t s := 0 if oct = oct ∧ m(0)•R(v ,x(0)) ̸= m(1)•R(v ,x(1)), renc,t t x(b) t t s := 1 if oct = oct ∧ m(0)•R(v ,x(0)) = m(1)•R(v ,x(1)), and s := 2 if oct ̸= oct renc,t t x(b) t t renc,t t x(b) The above variables, s ,s ,s , are used for defining cases in the proof of Theorem 2 in Ap- m rk,ℓ renc,t pendix D.3. De(cid:12)nition 6 (Predicate- and Attribute-Hiding for Re-Encrypted Ciphertexts (PAH- RC)).Themodelfordefiningthe(adaptively)predicate-andattribute-hidingsecurityforre-encrypted ciphertexts of F-PRE against adversary A (under chosen plaintext attacks) is given by the following game: Setup, Phase 1. They are defined as the same as those in Definition 5, respectively. Challenge. For a challenge query (m(0),m(1),x(0),x(1),v(0),v(1),x′(0),x′(1)) subjected to the follow- ing restrictions: