arXiv CS open access

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

2026 · arxiv_cs

arXiv CS · Papers · 2026

cryptography cybersecurity privacy security

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model Tightly Secure in Multi-User, Multi-Challenge Settings Sayantan Mukherjee

arXiv:2608.29191v1 [cs.CR] 29 Aug 2026

Department of Computer Science and Engineering, Indian Institute of Technology, Jammu csayantan.mukherjee@gmail.com

Abstract. Searchable Encryption (SE) allows users to perform a keyword search over encrypted documents. In Eurocrypt’04, Boneh et al. introduced Public-key Encryption with Keyword Search (PEKS). Broadcast Encryption with Keyword Search (BEKS) is a natural progression that allows for some amount of access control. However, PEKS and BEKS suffer from keyword-guessing attacks (KGA). In the case of KGA, an adversary guesses the keyword encoded in a trapdoor by creating a ciphertext on a sequence of keywords of its choice and testing them against the trapdoor. In ACISP’21, Liu et al. introduced a variant of BEKS called Broadcast Authenticated Encryption with Keyword Search (BAEKS) as a generalization of Public-Key Authenticated Encryption with Keyword Search (PAEKS) in troduced in Information Sciences in 2017. This was followed with a number works on BAEKS and PAEKS. However, no known work considered the functionality requirement in its most realistic setting. We propose a new security definition of BAEKS in the multi-user (with adaptive corruptions) and multichallenge (both in terms of ciphertext and trapdoor in an interleaved manner) settings. We also study the question of the unforgeability of BAEKS. In fact, our strong hiding requirement already implies a significant amount of unforgeability. We then propose a new BAEKS construction in the bilinear pairing groups. We prove this scheme achieves adaptive tight full-hiding security under (almost) standard MDDH assumptions. Restricting our BAEKS construction for a single receiver also gives an efficient and tightly secure PAEKS construction. We further run experiments to implement and evaluate our scheme.

Introduction

PEKS [10] is an well known primitive to solve the problem of searching over encrypted data. In a PEKS, Test(Tr, Ct) outputs 1 if the ciphertext-attribute y (encoded in ciphertext Ct by SrchEnc) matches the key-attribute x (encoded in trapdoor Tr by TrapGen) where SrchEnc is a publicly evaluation function and TrapGen uses the master secret key msk. This line of work [12,1,11,5,14,38] has produced several PEKS of different security levels and functionalities. Keyword guessing attacks [13,53] capture the question if a trapdoor hides encoded key-attribute (in this case the keyword). Being public key encryptions, however, all the above PEKS schemes were vulnerable to keyword guessing attacks as an adversary can create a ciphertext (using SrchEnc) and run Test on the challenge trapdoor to comprehend the keyword encoded in the trapdoor. There have been many efforts to introduce various query, advanced security requirements, efficiency improvements and expansions. In the literature, two prominent directions to overcome key guessing attacks are: – Restrict searching capability: This line of work studied designated-tester PEKS [6,26,24]. Here, Test uses the tester’s secret key. – Restrict encryption capability: This line of work studied public key authenticated encryption with keyword search (PAEKS) [30,20,44,17,41,21,33,51]. Here, SrchEnc uses the sender’s secret key. Over the years, PAEKS got much attention [30,20,46,45,17,41,21,33,52,19,36]. PAEKS allows a sender S to compute a searchable ciphertext on ω for a receiver R using both sender’s secret key skS and the receiver’s

public key pkR . To check if a searchable ciphertext on w is from a sender E intended for a receiver F, the receiver creates a trapdoor that is computed using the sender’s public key pkE and the receiver’s secret key skF . Given a ciphertext and a trapdoor, any public entity runs Test to find if S = E, ω = w and R = F. In ACISP 2021, Liu et al. [39] extended this primitive towards supporting multiple receivers. In particular, they introduced the notion of broadcast authenticated encryption with keyword search (BAEKS) to allow a sender to encrypt a keyword for a set of authorized receivers.1 This is followed up with a statistically consistent BAEKS construction by Mukherjee [42] and a generic construction of computationally consistent BAEKS proposed by Emura [22]. Both the works defined different versions of consistency notions and argued security in the standard model. However, none of these works considered security in the multi-challenge settings which is more realistic for an authenticated encryption typically deployed for a set of users. In case of BAEKS (or PAEKS), the encryption uses both secret and public keys, multi-challenge security of BAEKS (or the simpler variant PAEKS) does not necessarily follow from their single-challenge variant. Moreover, the security models should also ensure that they withstand multi-challenge queries made in an interleaved manner. As far we could find, there are no works on BAEKS (or for that matter PAEKS) with sufficient formalism. In this work we have considered large-universe setting where number of users |U| could be exponential in the security parameter λ. Thus the security reduction advantage is upper bounded by |U |·ϵ for some negligible ϵ does not give an effective solution. Moreover, in a multi-user, multi-challenge security, security reductions often suffer from a nontrivial multiplicative security loss J which is in the order of number of queries adversary has made. As an example, both the most prominent BAEKS [42,22] (and PAEKS [45,17,41,21,33,52,19,36]) suffer from a multiplicative loss of Θ(|QCt | + |QTr |) where QCt (and QTr ) is the number of ciphertext oracle queries (resp. trapdoor oracle queries). As [7,28] has argued, we should always aim for tight security where security reductions does not suffer from such a loss. This motivates us to explore tight security of BAEKS (and thereby of PAEKS) in the multi-user, multi-challenge setting. Remark 1. On a closer look, both [42,22] developed BAEKS using PAEKS although [42] did not mention it explicitly. Thus, in both [42,22] size of BAEKS ciphertext = O(|R|)× size of PAEKS ciphertext where R is the set of authorized receivers. This is indeed in line with state-of-the-art anonymous Broadcast encryption schemes [37,35] where anonymity was attained at the cost of ciphertext size linearly dependent on O(|R|). 1.1

Motivation

As a motivation for BAEKS functionality, let us consider an hospital where a doctor encrypts patient’s health record with with regards to hospital’s public key. Using PEKS [10], hospital could allow other doctor’s to search for keywords on this health record by providing them trapdoors. Inquisitive insurance agents, too nosy about patient’s record, can mount key-guessing attack on the trapdoors. To avoid this, a hospital can decide using PAEKS where encryption using hospital’s public key and the encrypting doctor’s secret key. Consider a generalization of this scenario, where a doctor wishes to share this record with different doctors from other hospitals. This is where BAEKS turns out to be an important primitive towards solution of this problem. 1.2

Related Works

Pan and Li [45] introduced multi-ciphertext indistinguishability (MCI) and multi-trapdoor indistinguishability (MTI) and proposed a PAEKS secure in the random oracle model.2 Cheng and Meng [16] showed [45] to be insecure and proposed a PAEKS [17] under LWE assumption. Liu et al. [40] introduced an informal argument of consistency in PAEKS and proposed a new generic construction along with a lattice-based instantiation. Emura [21] argued the generic construction of [40] is not practical, formally introduced computational consistency in PAEKS and proposed a generic construction and proved it to be IND-CKA and 1

Obviously PAEKS is a BAEKS where the underlying authorized set is singleton. This work focuses on BAEKS and the results rightaway applies to PAEKS. See Remark 1 for comments on BAEKS and PAEKS relationship. 2 A discussion of these security notions is given in Section 3.3.

IND-IKGA secure.2 Emura also mentioned MTI security to be an open problem. This was followed with [34] who proposed PAEKS with updatability. Cheng et al. [19] proposed a new PAEKS construction under random-oracle and followed it up with [18] a server aided version for better efficiency. Recently Li and Boyen [36] proposed a generic construction of PAEKS. Despite being so many works in this field, the security definition is not yet standardadized [19, Table 1]. Moreover, the notion of consistency is an core objective of a searchable encryption [1] which a number of PAEKS constructions did not consider. Given the current status of PAEKS constructions available, we now take a look at existing BAEKS constructions to identify research gaps. Mukherjee [42] introduced a statistical consistency definition for BAEKS. They also improved the adaptive security notions of [39] towards reality and proposed a standard model construction attaining the new stronger security notions. They also proposed a novel technique to argue statistical consistency of their construction. Emura [22] introduced a computational consistency definition for BAEKS extending the computational consistency definition of [21,23]. Their security model allows user corruptions3 which was not allowed in [42]. However, they didn’t consider sender anonymity unlike [42]. They then proposed a BAEKS construction from generic PAEKS construction of [21]. They then claim consistency and security of this construction due to consistency and security of the underlying PAEKS [21]. Our critical analysis of the consistency proof of [21] (and thereby [22]) brings up several questions rendering the proof inconclusive. We present an analysis of the consistency proof of PAEKS [21] (and thereby BAEKS [22]) in Section 3.4. In PKC2024, Ling et al. [38] proposed two PEKS constructions in the multi-user, multi-challenge setting. They proposed two PEKS constructions in the composite order bilinear groups and utilized Dual system technique [49] to give a tight security proof. Since these constructions are PEKS constructions, they are susceptible to the dreaded keyword guessing attacks [13,53]. In fact, our analysis of proofs of both the constructions brings up several questions rendering the proofs of [38] incomplete. We present an analysis of the security proof of PEKS in [38] in Section A. Schemes [42]

Consistency statistical

CT-Security Trap-Security Corruption Tightness Confidentility Confidentility No No S&R anonymity E&F anonymity [22] computational? Confidentility Confidentility Adaptive No R anonymity F anonymity This paper statistical f ull-cpa (see Section 3.2.1) Adaptive Yes

Fig. 1 Comparison between standard model BAEKS schemes. S and E anonymity stands for sender anonymity in ciphertext (Ct) and trapdoor (Tr) respectively. R and F anonymity stands for receiver anonymity in Ct and Tr respectively. Confidentiality in CT-Security and Trap-Security respectively denotes hiding the keywords in Ct and Tr respectively. In Section 1.2, we justify that the proof of computational consistency is not complete in [22] and therefore mark it as computational?.

And therefore, the following question arises naturally: Can we obtain a multi-user BAEKS (and thereby a PAEKS) scheme in the prime order groups that is tightly secure in multi-user, multi-challenge setting under adaptive corruptions? 1.3

Our Contribution

We propose a novel definition of f ull-cpa security for the BAEKS primitive, which improved upon the security definitions of existing PAEKS [45,17,41,21,33,52,19,36] and BAEKS [42,22]. Looking ahead, the f ull-cpa security notion allows adversary to challenge on ciphertext and challenge on trapdoors in an interleaved manner while allowing adaptive corruptions. We emphasize that, our f ull-cpa security notion hides the keyword, the (honest) sender information, and the (honest) receiver(s) information in both the trapdoor and 3

Corruption of users are pretty common in a real network scenario. Corruptions of users during a security game done via adversary receiving secret key of users it selected and therefore captures stronger security.

the ciphertext simultaneously in presense of adaptive corruptions of users in the system. We also propose two unforgeability security notions (i) ct-cma and (ii) trap-cma to capture the requirement that none but the authentic user would be able to create a ciphertext or a trapdoor in this system. We then show that, f ull-cpa security already ensures both types of unforgeabilities. Then we give a new statistically-consistent construction of broadcast authenticated encryption with keyword search scheme called baeks and argue its statistical consistency. Finally, we argue tight-f ull-cpa security in the standard model under standard matrix diffie-hellman-based assumptions. We also have implemented and evaluated the construction. 1.4

Technical Overview

In a BAEKS scheme, as introduced above informally, a ciphertext Ct ← SrchEnc(skS , ω, pkR ) is generated wrt a sender S, a keyword ω and some (at most ℓ) receivers R 4 and a trapdoor Tr ← TrapGen(pp, pkE , w, skF ) is generated wrt a sender E, a keyword w and a receiver F. Mukherjee [42] represented Sender and Receiver information as (common) variables (WS and WR respectively) mimicking dual system encryption [15] and encoded ω as the Boneh-Boyen Hash wrt the common variables. In particular, for the above scenario-example, [42] produces ciphertext-encodings as {(WS ω + WR )}R∈R and trapdoor encoding as (WE w + WF ). Observe that, if E = S, w = ω and F ∈ R, there will be a match inbetween the encodings in terms of membership (i.e. (WE w + WF ) ∈ {(WS ω + WR )}R∈R ). On the other hand, if one of the above equalities or membership (i.e. (E, w, F) ∈ / {(S, ω, R)}R∈R ) does not hold, the encodings are independent (even against an unbounded adversary) which is a crucial part of the proof of [42]. It is easy to see that, the independence breaks down if more than two encoding instances are considered. Therefore, Mukherjee’s BAEKS construction does not seem useful for tight security in multi-users, multi-challenge settings. Following footstep of [42], we set our goal to find an ciphertext-trapdoor encoding that allows tight security argument. Intuitively, we would like to replace the Boneh-Boyen Hash encoding of [42] with this encoding that allows tight security argument. We, start taking a look at existing tightly secure IBE [8,29], HIBE [31,32] constructions. All these works randomize multiple encodings simultaneously due to underlying (randomized) Naor-Reingold PRF structure [43]. However, all these schemes depend on a trusted third party (KGC) having a master secret key. To get a secret key, each user has to request KGC with their identity. In BAEKS, each user should be able to choose their own public-private key pairs. Moreover, every user could be a sender in certain communication and a receiver in others. To give a brief overview of all these tightly secure (H)IBEs, built on (randomized) Naor-Reingold PRF structure, define master secret keys {Wj,b }(j,b)∈[m]×{0,1} where m is bit-length of identity. Ciphertext and P key-encoding with respect to any identity id ∈ {0, 1}m , is Wj,idj . Following this, we could let each j∈[m]

user j have two keys (i) {Uj,b }(j,b)∈[m]×{0,1} for being a sender and (ii) {Vj,b }(j,b)∈[m]×{0,1} for being a α receiver. A Pciphertext-trapdoor encoding for keyword τ ∈ {0, 1} from the sender S to a receiver R would then be (US,τj + VR,τj ). We could follow the blueprint of all those tightly secure (H)IBEs and inject j∈[α] P P random functions ( US,τj + RFS (τ )) + ( VR,τj + RFR (τ )) via a hybrid argument to all the ciphertext j∈[α]

j∈[α]

and trapdoor encodings simultaneously. Finally, we could aim to replace RFS (τ ) + RFR (τ ) with random choices. Recall that, this argument requires {RFS (τ ) + RFR (τ )}(S,R)∈S×R is independent and therefore utlize an information theoretic step. It is fairly easy to verify that this information theoretic step cannot be utlized in BAEKS (or PAEKS) as {RFS (τ ) + RFR (τ )}(S,R)∈S×R for |S|, |R| > 2 are not independent. We cannot directly apply techniques from all these tightly secure (H)IBEs such as [32]. Pu We modify the representations of users. In our construction, we denote j th user as (i) i=1 Ui,ji for Pu let each keyword 1}α be encoded being Pαa sender (ii) i=1 Vi,ji for being a receiver. We alsoP Pα ω ∈ {0,P u u by i=1 Ki,ωi . Thus, a tuple (S, ω, R) would be encoded as i=1 Ui,Si + i=1 Ki,ωi + i=1 i,Ri . This PV u representation allows us to inject randomness into the trapdoor and ciphertexts such that i=1 Ui,Si + Pα Pu K + V + RF(S||ω||R). HIBE construction of [31,32] intutivelly uses similar structure except i,ω i,R i i i=1 i=1 4

For PAEKS, |R| = 1.

we need to address different parties taking part is defining different variables. In particular, in our case U is chosen by the sender, V is chosen by the receiver and K is chosen by the trusted third party. This makes a bit more P u the situtation Pα P u complicated. A ciphertext on (S, ω, R) is computed as (ct0 = As, ct1 = (Pi=1 Ui,Si + Pi=1 Ki,ωi + Pi=1 Vi,Ri )As). A trapdoor is computed as (k0 , k1 ) where (k0 = Br, k1 = u u α ⊤ ⊤ ( i=1 U⊤ i,Si + i=1 Vi,Ri )Br). i=1 Ki,ωi + To withstand such a situtation, we focus on the non-triviality condition of the f ull-cpa-security Section 3.2.1 (or the Core-Lemma Figure 7 which reciprocates the f ull-cpa security model). In particular, we make use of the restriction that A will not query skU for those users on which ciphertext and trapdoor queries are made (informally, U ∈ {R[0] ∪ R[1] ∪ {S[0] , S[1] , R[0] , R[1] }}). Looking ahead, we essentially manage to inject a random function RF(U||τ ||U′ ) to all the ciphertext and trapdoor encodings of (U, τ, U′ ) without affecting the secret keys queried. We give a complete proof in Section 5. We now discuss adaptive corruption queries informally. This discussion requires us to informally introduce the nh public and system. The public parameters i secret keysoof every users as well as the public parameters ofthe ⊤ ⊤ 5 th are Kι,b A , [Kι,b B]2 ι∈[α] , and each j user has secret key skj = Uj A 1 , [Vj B]2 and has public 1 b∈{0,1} n o key pkj = [Uj B]2 , Vj⊤ A 1 . Corruption queries on user j leak their secret keys U⊤ A , [V B] and j j 2 1 n ⊤ o remember that, the public keys [Uj B]1 , Vj A 2 are already available to everybody. We already know that, projections U⊤ j A 1 and [Uj B]1 allow to retain some of the entropy of Uj [15,4]. On top of this, our Core-Lemma-based proof utilizes the fact that A will not query skU for those users on which challenge ciphertext and challenge trapdoor queries are made and therefore, we can insert additional randomness in Uj and Vj required for the proof but is not visible to the adversary. 1.5

Organization of the paper

In Section 2, we discuss some basic notations and descriptions of mathematical tools. We define broadcast authenticated encryption with keyword search and its security in Section 3. In Section 4, we propose a new construction baeks along with a security proof. In Section 5, we argue that the core-lemma is secure. Section 6 provides our experimental evaluations of our construction. Finally, we conclude the paper in Section 7.

Mathematical Tools and Preliminaries

Notations. For a, b ∈ N such that a ≤ b, we often use [a, b] to denote {a, . . . , b} and write [b] := [1, b]. For a set D, we write x ←- D to denote x is sampled uniformly at random from D. The abbreviation ppt stands for probabilistic polynomial time. The small-case bold letters s denote a column vector, and large-case bold ∗ letters S = sij to denote a matrix of appropriate size. ∀i, j ∈ I denotes for all distinct i and (i,j)∈I×J

j from I. We use _ as the don’t care symbol. For τ ∈ {0, 1}L , τ|i denotes i-bit sub-string τ1 || . . . ||τi and τ|i ||_|| . . . ||_ denotes L bit string τ1 || . . . ||τi ||_|| . . . ||_ having last L − i bits containing don’t care symbol _. We use A ⊔ B to denote disjoint union. 2.1

Mathematical Tools and Hardness Assumptions

2.1.1 Bilinear Pairing. Let G1 , G2 , GT are groups of order p which is a large prime number. We consider an efficiently computable and non-degenerate bilinear pairing e : G1 × G2 → GT where ∀g1 ∈ G1 , g2 ∈ G2 , e(g1a , g2b ) = e(g1 , g2 )ab for any a, b ∈ Zp . We use type-3 bilinear pairing in this work where G1 and G2 have no known isomorphism. We define ABSGen as the group generator that generates the type-3 bilinear pairing description. Precisely, G = (p, G1 , G2 , GT , g1 , g2 , e) ←- ABSGen(1λ ) such that G1 , G2 , GT are cyclic groups of 5

[A]1 = g1A and [B]2 = g2B where g1 , g2 are generators of prime order bilinear groups G1 and G2 respectively.

prime order p where G1 = ⟨g1 ⟩, G2 = ⟨g2 ⟩ and GT = ⟨gT ⟩ s.t. gT = e(g1 , g2 ). We denote gsa by [a]s [25] for any a ∈ Zp and s ∈ {1, 2, T}. For A = (aij ) ∈ Zℓ×k p , for s ∈ {1, 2, T} we denote  a11 a  gs . . . gs 1k   . [A]s =  ... . . . ...  ∈ Gℓ×k s aℓk aℓ1 gs . . . gs

Definition 1. Let ℓ, k ∈ N, such that ℓ > k. We call Dℓ,k a matrix distribution if it outputs a matrix D ∈ Zℓ×k of full rank k in polynomial time (w.l.o.g. we assume the first k rows of D ← Dℓ,k form an p invertible matrix). We write Dk = Dk+1,k . Definition 2. Let ℓ, k ∈ N, such that ℓ > k. We denote by Uℓ,k the uniform distribution over all full-rank ℓ × k matrices over Zp . We write Uk = Uk+1,k . 2.1.2

Matrix Diffie-Hellman Assumption. For all adversary A, its advantage against the matrix Diffie-

Hellman problem is defined as U

-MDDH

ℓ,k AdvA,G s

(λ) = | Pr[A([U]s , [Ux]s ) = 1] − Pr[A([U]s , [z]s ) = 1]| U

-MDDH

ℓ,k is where s ∈ {1, 2}, U ← Uℓ,k , x ←- Zkp and z ←- Zℓp . The Uℓ,k -MDDH assumption states that AdvA,G s neg(λ) for all ppt adversary A. m-fold Uℓ,k -MDDH problem contains m independent instances of Uℓ,k -MDDH problem. Due to Random Self-Reducibility [25], we know that

m-U

AdvA,Gsℓ,k 2.1.3

-MDDH

k -MDDH (λ) ≤ (ℓ − k) · AdvU (λ) + A,Gs

1 . p−1

Lateral Matrix Diffie-Hellman Assumption. For all adversary A, its advantage against the lateral

matrix Diffie-Hellman problem is defined as lat-U

AdvA,Gsℓ,k

-MDDH

(λ) = | Pr[A([U]s , [Ux]s , [U]3−s ) = 1] − Pr[A([U]s , [z]s , [U]3−s ) = 1]| lat-U

-MDDH

is neg(λ) where U ← Uℓ,k , x ←- Zkp and z ←- Zℓp . The lat-Uℓ,k -MDDH assumption states that AdvA,G ℓ,k for all ppt adversary A. We can define m-fold lat-Uℓ,k -MDDH problem contains m independent instances of lat-Uℓ,k -MDDH problem. 2.1.4

Bilateral Matrix Diffie-Hellman Assumption. For all adversary A, its advantage against the bilat-

eral matrix Diffie-Hellman problem is defined as bil-U

AdvA,G ℓ,k

-MDDH

(λ) = | Pr[A([U]1 , [Ux]1 , [U]2 , [Ux]2 ) = 1] − Pr[A([U]1 , [z]1 , [U]2 , [z]2 ) = 1]| bil-U

-MDDH

where U ← Uℓ,k , x ←- Zkp and z ←- Zℓp . The bil-Uℓ,k -MDDH assumption states that AdvA,G ℓ,k is negligible in λ for all ppt adversary A. We can define m-fold bil-Uℓ,k -MDDH problem contains m independent instances of bil-Uℓ,k -MDDH problem. Over the years, bil-Uℓ,k -MDDH assumption has become pretty standard [2,50]. Fact. We state a few results next. (F1) Uk -MDDH ⇔ Uℓ,k -MDDH for ℓ > k. (See [27, Lemma 1]) (F2) bil-Uk -MDDH ≤ lat-Uk -MDDH ≤ Uk -MDDH m-X-U -MDDH X-U -MDDH 1 (λ) + p−1 (F3) AdvA,G ℓ,k (λ) ≤ (ℓ − k) · AdvA,G k for X ∈ {lat, bil}. (Due to random self-reducibility [25, Lemma 1])

(F4) bil-Uk -MDDH, lat-Uk -MDDH are hard for k > 1 6

Broadcast Authenticated Encryption with Keyword Search

A BAEKS scheme baeks is defined by a tuple of five ppt algorithms (Setup, KeyGen, SrchEnc, TrapGen, Test) as following. 3.1

Definition

– Setup(1λ , u, α): It takes the security parameter 1λ , u = poly(λ) to define a userspace U = {0, 1} u and α = poly(λ) to define a keyword space KW = {0, 1}α and publishes params pp. We assume pp implicitly defines a ciphertext space CT and a trapdoor space T too. – KeyGen(pp): It takes the public parameter pp as input, and outputs public-private key pair (pk, sk). It keeps sk secret and publishes pk. – SrchEnc(pp, skS , ω, pkR ): It takes pp, a sender secret key skS , a keyword ω and public-keys pkR = {pkR1 , . . . , pkRℓ } of a set of receivers R = {R1 , . . . , Rℓ }. It outputs a ciphertext Ct ∈ CT . – TrapGen(pp, pkE , w, skF ): It takes pp, a sender public key pkE , a keyword w and a receiver secret key skF . It outputs a trapdoor Tr ∈ T . – Test(pp, Tr, Ct): It takes Tr and Ct as input, and outputs 0/1. From now on, we drop explicit mention of pp in each algorithm description and assume all the above algorithms use pp implicitly. Correctness. For any security parameter 1λ , any sender S ∈ U, any receiver set R ⊂ U such that pkR = (pkU )U∈R , any keyword ω ∈ KW if F ∈ R, Pr[Test(TrapGen(pkS , ω, skF ), SrchEnc(skS , ω, pkR )) = 1] = 1 − neg(λ) where the probability is taken over pp ← Setup(1λ , α, u) and (skU , pkU ) ← KeyGen(pp) for all the users U ∈ R ⊔ {S}. Informally speaking, if (E = S) ∧ (w = ω) ∧ (F ∈ R), we say the key-attributes (E, w, F) match the ciphertext-attributes (S, ω, R). If Test(Tr, Ct) → 1, we say the trapdoor Tr matches the ciphertext Ct. pp ← Setup(1λ , α, u) (pki , ski ) ← KeyGen(pp, i) for i ∈ R0 ∪ R1 ∪ {S0 , S1 , R0 , R1 } (ω0 , ω1 , i, j) ← A (pkt )t∈R0 ∪R1 ∪{S0 ,S1 ,R0 ,R1 } s.t. ω0 , ω1 ∈ KW ∧ distinct i, j ∈ {0, 1} ∧ ((Si , ωi , Ri ) does not match (Sj , ωj , Rj )) Ct ← SrchEnc(skSi , ωi , pkRi ) Tr ← TrapGen(pkSj , ωj , skRj ) If Test(Tr, Ct) = 1, Output 1. Otherwise, Output 0.

Fig. 2 Consistency

Consistency. For a BAEKS scheme baeks = (Setup, KeyGen, SrchEnc, TrapGen, Test), the consistency experiment is presented in Figure 2. This definition of consistency of BAEKS is borrowed from [42]. 3.2

Security

Confidentiality of Ciphertexts and Trapdoors. A BAEKS scheme baeks satisfies full hiding security (f ull-cpa) if for all security parameter λ, for all ppt adversary A, there exists a negligible function neg(·) ull-cpa such that the advantage of AdvfA,baeks (λ) ≤ neg(λ) for where A is given access to following oracles with a natural restriction that (E[b] , w[b] , R[b] ) does not match (S[b] , ω [b] , R[b] ) for b ∈ {0, 1} (i.e. QCt ∩ QTr = ∅) and A has not queried skU for U ∈ {R[0] ∪ R[1] ∪ 3.2.1

 ull-cpa AdvfA,baeks (λ) = Pr  b′ = b:

 pp ← Setup(1λ , α, u), − 1 b ←- {0, 1}, QCt , QTr , Qsk ← ∅, 2 ′ OCt (b,·,·),OTr (b,·,·),Osk (·),Opk (·) b ←A (pp)

Fig. 3 Full Hiding Security of BAEKS (and thereby of PAEKS) {S[0] , S[1] , R[0] , R[1] }} (i.e. ∀ (u, _, _) ∈ Qsk , (pku , _, _), (_, _, pku ) ∈ / QTr ∪QCt ). Moreover, we put the restriction that OTr (and Osk ) queries will have no repetition. Note that, we do not put any such restriction on OCt queries. – OCt is an oracle that on input (b, (pkS[0] , ω [0] , pkR[0] ), (pkS[1] , ω [1] , pkR[1] )) outputs SrchEnc(pp, skS[b] , ω [b] , pkR[b] ). For b ∈ {0, 1}, QCt is updated with {(pkS[b] , ω [b] , pkR )}R∈R[b] . A makes |QCt | many OCt queries. – OTr is an oracle that on input (b, (pkE[0] , w[0] , pkF[0] ), (pkE[1] , w[1] , pkF[1] )) outputs TrapGen(pp, pkE[b] , w[b] , skF[b] ). For b ∈ {0, 1}, QTr is updated with {(pkE[b] , w[b] , pkF[b] )}. A makes |QTr | many OTr queries. – Opk is an oracle that on new j outputs pkj consistently where (skj , pkj ) ← KeyGen(pp, j) after storing (j, skj , pkj ) in Qpk . A makes |Qpk | many Opk queries. – Osk is an oracle that on new j outputs (skj , pkj ) consistently which it retrieve from Opk (j) after storing (j, skj , pkj ) in Qsk . A makes |Qsk | many Osk queries. We assume before making a OTr or a OCt query involving user j, A will query Opk (j). In this work, we also explore the question of integrity of Ciphertexts and Trapdoors and further show that f ull-cpa already implies such integrity. We defer this discussion to Section B.1. 3.3

Differences in Security Defintions

Next we discuss different security notions of BAEKS (and PAEKS) that have been defined over the years. 3.3.1

Privacy of Ciphertexts and Trapdoors. Cheng and Meng [17] introduced Fully CI Security and

Fully TI Security. Fully CI Security. The challenger C setup the keys for the target sender (S) and target receiver (R) at the initialization phase of the system. A receives corresponding public keys. Then A is allowed to query for ciphertext oracle (OCt ) and trapdoor oracle (OTr ) in an interleaved manner. A makes ciphertext query on (pkS , ω, pkF ) to get Ct and makes trapdoor query on (pkE , ω, pkR ) to get Tr. In the challenge phase, A chooses ω0 and ω1 with the restriction that (pkS , ω0 , _), (pkS , ω1 , _) ∈ / QTr . A gets a challenge ciphertext Ct ← SrchEnc(skS , ω b, pkR ). A can make further oracle queries subject to the restriction. Finally A guesses b′ ∈ {0, 1} and wins if b′ = b. Fully TI Security. The challenger C setup the keys for the target sender (S) and target receiver (R) at the initialization phase of the system. A receives corresponding public keys. Then A is allowed to query for ciphertext oracle (OCt ) and trapdoor oracle (OTr ) in an interleaved manner. A makes ciphertext query on (pkS , ω, pkF ) to get Ct and makes trapdoor query on (pkE , ω, pkR ) to get Tr. In the challenge phase, A chooses ω0 and ω1 with the restriction that (_, ω0 , pkR ), (_, ω1 , pkR ) ∈ / QCt . A gets a challenge trapdoor Tr ← TrapGen(pkS , ω b, skR ). A can make further oracle queries subject to the restriction. Finally A guesses b′ ∈ {0, 1} and wins if b′ = b. They have further defined MCI/MTI-security respectively where in the challenge phase, A chooses two sequences of keywords (ω0,i )i∈I and (ω1,i )i∈I non-adaptively. Moreover, their definitions support multiple users but considers only CT-confidentiality and Trap-confidentiality i.e. hiding of keyword(s). Interestingly, Cheng and Meng [17] do not provide a security proof for CI-Security ⇒ MCI-Security and TI-Security ⇒ MTI-Security. They claim to have followed [47] which also do not provide a proof for this claim. Observe that neither of MCI and MTI security allows multiple challenges on target sender only, that too in a non-adaptive manner. Emura [21,23] in his works on PAEKS, resorted to IND-CKA and IND-IKGA Security. 8

IND-CKA Security. The security notion is fairly similar to fully CI-security except that the challenger simulates multiple senders (of C’s choice) and the adversary A gets public keys of all such senders. Similar to CI-security, the target receiver (R) is fixed at the start. A can adaptively choose two keywords ω0 and ω1 and a target sender from the list provided by C. A can make ciphertext and trapdoor query on fixed target receiver R. IND-IKGA Security. The security notion is exactly same as IND-CKA except that the challenge is a trapdoor. Emura [21,23] claimed that IND-CKA also implies MCI-security due to [47] and IND-IKGA in the form they considered do not imply MTI-security directly. The IND-CKA security of [22], in addition to the IND-CKA security of [21,23], also include hiding the receiver identity and allow user corruptions. The IND-IKGA security of [22] is exactly same as the IND-CKA security of [22] except that the challenge is a trapdoor. Mukherjee [42] proposed ct-cpa and trap-cpa which are quite similar to IND-CKA and IND-IKGA of Emura [22] except that both the notions additionally capture sender anonymity but do not consider user corruptions. Full-Hiding Security (f ull-cpa). In this work, we introduce f ull-cpa security that allows interleaved challenge queries to ciphertext, trapdoor and secret key oracles. Recall that both SrchEnc and TrapGen use secret keys and therefore the security captures multi-ciphertext and multi-trapdoor security simultaneously. Moreover, this security model considers keyword hiding along with sender and receiver anonymities in both the ciphertext and in the trapdoors simultaneously. This indeed matches the security definition of [48] therefore achieves the most coveted security. This concludes our claim of stronger security model and we next describe the problem in the reduction essential in the proof of consistency of Emura’s BAEKS [22] and Emura’s PAEKS [21]. Following that, we describe the system model we consider here for BAEKS. 3.4

Analysis of Consistency of Emura’s PAEKS

Emura [21] introduced a notion for computational consistency for PAEKS. We reproduce the definition in Figure 4 and informally describe their proof technique. Expconsist paeks,A (λ,): (pkR , skR ) ← KeyGenR (1λ ) (pkS[0] , skS[0] ) ← KeyGenS[0] (pkR ) (pkS[1] , skS[1] ) ← KeyGenS[1] (pkR ) (ω, w, i, j) ← A(pkR , pkS[0] , pkS[1] ) s.t. ω, w ∈ KW ∧ distinct i, j ∈ {0, 1} ∧ ((ω, i) ̸= (w, j)) Ct ← SrchEnc(skS[i] , ω, pkR ) Tr ← TrapGen(pkS[j] , w, skR ) If Test(Tr, Ct) = 1, Output 1 or 0 Otherwise.

Fig. 4 Computational Consistency of [21]

Emura [21] called a PAEKS scheme paeks is computationally consistent if Pr[Expconsist paeks,A (λ, =)1] ≤ neg(λ) for all ppt adversary A. This definition, informally speaking, captures the situation that no ppt adversary can produce two unmatching keywords (i.e. (ω, S[i]) ̸= (w, S[j]) for distinct i, j ∈ {0, 1}) but the corrsponding Ct and Tr matches. First we notice that some important situations are missing in the definition. In particular, the adversary does not choose the sender or the receivers. Moreover, it considered same receiver in both SrchEnc and Tr thereby restricting the model. However, these are only some observations about the consistency definition in [21] and are not the biggest issue in their consistency proof. Next we describe the proof technique informally. 9

Firstly, Emura [21] proposed a generic construction of PAEKS from a PKE, a Hash-Proof system and a PEKS. Their idea was to reduce the computational consistency of PAEKS to the computational consistency of underlying PEKS. To argue computational consistency of the construction generically, Emura proposed a hybrid argument. The argument starts from G0 which basically is the real security game. In G1 , the projective hash function in SrchEnc is replaced by hash function of SPHF. In G2 , they modified key-pair computation of S[i]. In G3 , they sampled the sender public key in SrchEnc from outside the language. Then, in G4 , they again modified key-pair computation of S[i]. Then, in G5 , they again modified key-pair computation of S[j]. In G6 , they sampled the sender public key in TrapGen from outside the language. In G7 and in G8 , they replace the PRF with a random function in SrchEnc and TrapGen respectively. Finally in G9 , they reduce the consistency of PAEKS to the consistency of underlying PEKS. We note down some of the problems with the above argument: 1. The reductions are not formally proven. We take an example where G0 and G1 are proven indistinguishable. Note that, they state that | Pr[X0 ] − Pr[X1 ]| is negligible due to the correctness of WI-SPHF. However, this is not formally argued via forming reductions. 2. In fact, none of the reductions are argued properly. Typically provable security argues that, if a given adversary breaks a particular security notion, we can define a reduction that breaks another security notions. Except G1 ≈ G2 and G7 ≈ G8 , reduction arguments are missing despite being stated. 3. We look at the reduction that claims to have proven G1 ≈ G2 . To properly understand the given reduction, we look at their security model reproduced in Figure 4. Observe that, the adversary in this security model is considered successful if it produces (ω, w, i, j) for (ω, S[i]) ̸= (w, S[j]) but Ct matches Tr where Ct ← SrchEnc(skS[i] , ω, pkR ) and Tr ← TrapGen(pkS[j] , w, skR ). Thus, to argue G1 ≈ G2 , the reduction B should run A to get such (ω, w, i, j). Now, the paper claims that the reduction will modify pkS[i] keeping corresponding skS[i] unchanged. In particular, till G1 , pkS[i] was an encryption of 0 and in G2 , they make it an encryption of 1. The issue as we understand is pkS[i] is used in both SrchEnc and in Tr and does not really behave differently based on the value that is encrypted. To summarise, once A produces the adversarial challenge (ω, w, i, j) according to Figure 4, it is not really clear how the reduction B is going to use this challenge tuple (ω, w, i, j) to break IND-CPA of the encryption scheme. 4. The bigger issue we think is with the reduction to argue G8 ≈ G9 . While arguing this indistinguishability, when A outputs (ω, w, i, j), B randomly chooses der-ω, der-w ←- KS and sends (der-ω, der-w) to the challenger. The rest of the argument works on der-ω, der-w. In this reduction we think A is not utilized at all. In particular, B could anyway sample der-ω, der-w ←- KS without any input from A and complete the game with the challenger. This as a result shows that B can always distinguish between G8 and G9 . This, in our opinion, contradicts with the notion of polynomial reduction that is used to relate hardness/security of two problems/protocols. Recently, an expanded version of this paper was published [23]. Although this version gives sufficient details on the proof of security, we unfortunately were not able to find any additional details over [21] on the proof of consistency. Therefore, observations we have made above still persists in our opinion. 3.5

System Model

The system model we consider in this work is similar to that of [42]. To set a system up where the user space U = {0, 1} u for u = poly(λ) and keyword space KW = {0, 1}α for α = poly(λ), the system administrator runs Setup to generate public parameter pp and then can go offline. Any user U ∈ U can generate its own public-private key pairs (pkU , skU ) taking pp into account, to join the system. The requirement from a BAEKS scheme is that a user could encrypt a keyword for a (set) of user(s) such that any privileged user would be able to search. To compute a searchable ciphertext of a keyword ω for a set of users (called receiver-set R = {R1 , . . . , Rℓ }), a user (called sender S) first gathers the receivers’ public keys pkR = {pkR1 , . . . , pkRℓ }. The sender S then encrypts a keyword ω to Ct running SrchEnc on its own secret key skS and on the set of privileged receivers pkR . The sender S stores Ct in the cloud. Any user R can compute a trapdoor Tr using TrapGen for a keyword w of interest with its own secret key skR and a sender’s public key pkE , and 10

send Tr to the cloud server as a search query. The cloud server can run Test on Tr and Ct to check match without knowing neither the sender’s identity nor the receiver’s identity. A document will be returned if all the followings hold: the underlying keywords are the same (ω = w), the trapdoor Tr is for querying the content from the sender S (i.e. S = E) rather than other senders, and the receiver R is one of the target receivers (i.e. R ∈ R) of the searchable ciphertext Ct.

Tight Broadcast Authenticated Encryption with Keyword Search

Setup(1λ , α, u)

SrchEnc(pp, skS , ω, pkR = (pkR1 , . . . , pkR ))

1: G = (p, G1 , G2 , GT , g1 , g2 , e) ←- ABSGen(1λ ) 2: A ←- U2k,k , B ←- U3k,k 3: For (ι, b) ∈ [α] × {0, 1} :

ℓ

1: s ←- Zkp , τ ←- Γ ([ℓ]) 2: Ct = (([ctȷ,0 ]1 , [ctȷ,1 ]1 )ȷ∈[ℓ] ) s.t.

Qι,b , Nι,b ←- Z(k)×(3k) p Qι,b 4: Kι,b = N ι,b 5: pp = ([A]1 , [A]2 , [B]1 , [B]2 ,

ctȷ,0 = Asȷ P ⊤ ⊤ ctȷ,1 = ( K⊤ ι,ωι + US + VR ι∈[α]

b∈{0,1}

KeyGen(pp, j)

1: r ←- Zkp 2: Tr = ([k0 ]2 , [k1 ]2 ) s.t.

k0 = BrP k1 = ( Kι,wι + UE + VF )Br

1: Wj , Yj ←- Z(k)×(3k) p 2: For (ι, b) ∈ [2u] × {0, 1}: Jj,ι,b ←- Z(k)×(3k) p P2u Pu ,Z = J 3: Xj = i=1 J i=u+1 j,i,j i j j,i,ji Wj and Vj = Xj h i ⊤ 5: skj = Uj A , [Vj B]2 1h i 6: pkj = [Uj B]2 , Vj⊤ A

)Asȷ

TrapGen(pp, pkE , w, skF ) nh i o K⊤ , [Kι,b B]2 ι∈[α] ) ι,b A

4: Set Uj =

τ (ȷ)

ι∈[α]

Test(Tr, Ct)

1: Let Ct = (([ctȷ,0 ]1 , [ctȷ,1 ]1 )ȷ∈[ℓ] ) 2: Let Tr = ([k0 ]2 , [k1 ]2 ) 3: Output 1 if ∃ȷ ∈ [ℓ] s.t.

Yj Zj

4: Output 0 otherwise

e([ctȷ,0 ]1 , [k1 ]2 ) = e([ctȷ,1 ]1 , [k0 ]2 )

Fig. 5 Our BAEKS Construction: baeks

4.1

Our Construction

We give baeks in Figure 5. This construction assumes a trusted third party running a one-time Setup. As per the system model described in Section 3.5, any user j can run KeyGen(j) to generate its key pair. Our construction is proven correct and satistically consistent next.

4.1.1

Correctness. Suppose, E = S, w = ω and F ∈ R for

– Ct = ([ct1,0 ]1 , [ct1,1 ]1 , . . . , [ctℓ,0 ]1 , [ctℓ,1 ]1 ) ← SrchEnc(pp, skS , ω, pkR ) – Tr = ([k0 ]2 , [k1 ]2 ) ← TrapGen(pp, pkE , w, skF ), 11





A = e([ctȷ,0 ]1 , [k1 ]2 ) = e([Asȷ ]1 , (

Kι,wι + UE + VF )Br )

ι∈[α]





= e((

⊤ ⊤  , [Br] ) K⊤ ι,wι + UE + VF )Asȷ 2

ι∈[α]





B = e([ctȷ,1 ]1 , [k0 ]2 ) = e((

⊤ ⊤  K⊤ ι,ωι + US + VRτ (ȷ) )Asȷ

ι∈[α]

, [Br]2 )



 A  ⊤ ⊤ = r B ( B

⊤ ⊤ ⊤ ⊤ ⊤  (K⊤ ι,wι − Kι,ωι ) + US − UE + VRτ (ȷ) − VF )Asȷ

ι∈[α]

Since, E = S, w = ω and F ∈ R (∃j ∈ [ℓ], F = Rτ (j) ), Pr[A = B] = 1.

Consistency. Informally describing Figure 2, we need to show that for distinct i, j ∈ {0, 1}, if S[j] ̸= S[i] or if ω [j] ̸= ω [i] or if R[j] ∈ / R[i] for adversarially chosen keywords ω [j] , ω [i] ∈ KW, a trapdoor Trj ← [j] TrapGen(pkS[j] , ω , skR[j] ) matches a ciphertext Cti ← SrchEnc(skS[i] , ω [i] , pkR[i] ) with only negligible probability. We emphasize that this holds even against statistical adversary that is given public keys of the senders and the receivers. nh i o Proof Sketch. Observe that adversary A gets params pp = ([A]1 , [A]2 , [B]1 , [B]2 , K⊤ , [Kι,b B]2 ι∈[α] ). ι,b A 1 b∈{0,1} A also gets the public keys for (pkt )t∈R[0] ∪R[1] ∪{S[0] ,S[1] ,R[0] ,R[1] } . It therefore has access to pkt = ([Ut B]2 , Vt⊤ A 1 ) where Ut , Vt ∈ Z2k×3k are defined as per Figure 5 by the experiment for all t ∈ R[0] ∪R[1] ∪{S[0] , S[1] , R[0] , R[1] }. p We show that, given all these information, there is enough entropy in the corresponding secret keys (skt )t∈R[0] ∪R[1] ∪{S[0] ,S[1] ,R[0] , to show that the best A can do is to guess despite A being an unbounded adversary. 4.1.2

To formulate our argument, we first check KeyGen where Ut and Vt are sampled in a particular way (k)×(3k) are all sampled uniformly at random for ι ∈ [u] and for an input t. Observe that, Wt , Yt , Jt,ι,b ∈ Zp (2k)×(3k) are distributed uniformly at random. b ∈ {0, 1}. Therefore, Ut , Vt ∈ Zp e ι,b + e et + u We sample Kι,b = K kι,b T for all ι ∈ [α] and b ∈ {0, 1}. We further sample Ut = U et T and 2k×3k [0] [1] [0] [1] [0] [1] e t + vet T for U e t, V e t , T ←- Z et Vt = V , u e , v e ←Z for all t ∈ R ∪ R ∪ {S , S , R , R }. Since, U t t p p [0] [1] [0] [1] [0] [1] e and Vt are uniformly random, Ut and Vt are uniformly random for all t ∈ R ∪ R ∪ {S , S , R , R }. Thus, for all t ∈ R[0] ∪R[1] ∪{S[0] , S[1] , R[0] , R[1] }, pkt are properly distributed and do not leak any information [j] [j] about the corresponding u et , vet . We sample r ←- Zkp . The trapdoor Trj = (k0 , k1 ) is then, [j]

k0 = [Br]2  X [j] k1 = ( K ι∈[α]

 [j] f[j] TBr for k f = 1 [j] + US[j] + VR[j] )Br + k1

ι,ωι

e k

ι∈[α]

eS[j] + v eR[j] [j] + u ι,ωι

[i] [i] [i] [i] On the other hand, Cti = ((ctȷ,0 , ctȷ,1 )ȷ∈[ℓ] ) for R[i] = {R1 , . . . , Rℓ }, a random permutation τ : [ℓ] → [ℓ] and sȷ ←- Zkp such that, [i]

ctȷ,0 = [Asȷ ]1   X [i] ⊤ ⊤ ⊤ [i] ⊤ [i]  ctȷ,1 = ( K [i] + US[i] + V [i] )Asȷ + cg T Asȷ  for cg = ȷ,1 ȷ,1 ι∈[α]

ι,ωι

τ (ȷ)

l ∈ [ℓ] and σℓ+1 = ke1

[j]

P e kι,ω[j] + u eS[j] + veR[j] .

ι∈[α]

We now focus at the boxed part of the above equations. Let σl = cf ȷ,1 ι

[i]

e k

eS[i] + v e [i] [i] + u ι,ωι R τ (ȷ)

P e kι,ω[i] + u eS[i] + veR[i]

ι∈[α]

τ (ȷ)

for all

Case-1 Consider the case S[j] ̸= S[i] . Notice that, u eS[j] and u eS[i] are sampled uniformly at random, σℓ+1 is ∗

independent to all {σl }l∈[ℓ] . Moreover, ∀a, b ∈ [ℓ], veR[i]

τ (a)

and veR[i]

are sampled uniformly at random, σa

τ (b)

is independent to all σb . Therefore, σ1 , . . . , σℓ+1 are independent and uniformly random. [j] [i] Case-2 Consider the case (S = S[j] = S[i] ) ∧ (ω [j] ̸= ω [i] ). Since, ω [j] ̸= ω [j] , ∃d ∈ [α] s.t. ωd ̸= ωd . Notice kd,ω[i] are sampled uniformly at random, σℓ+1 is independent to all {σl }l∈[ℓ] . Moreover, that, e kd,ω[j] and e d

∗

∀a, b ∈ [ℓ], veR[i]

τ (a)

and veR[i]

are sampled uniformly at random, σa is independent to all σb . Therefore,

τ (b)

σ1 , . . . , σℓ+1 are independent and uniformly random. Case-3 Consider the case (S = S[j] = S[i] ) ∧ (ω = ω [j] = ω [i] ) ∧ (R[j] ∈ / R[i] ). Since, R[j] ∈ / R[i] , ∀d ∈ [ℓ], [i] [j] R ̸= Rτ (d) .   P e eS k [i] + u ι,ωι  ι∈[α]   v e [i] 1 1 0 ··· 0 0     R σ1   τ (1) 1 0 1 · · · 0 0    v e [i]   σ2     R    . . . . . .  τ (2)   .  = . . . .. . . ×  . .   . . .  .  . .   1 0 0 · · · 1 0  .   . σℓ+1   1 0 0 ··· 0 1   | {z } v e [i]  | {z }  R τ (ℓ) (ℓ+1)×1 (ℓ+1)×(ℓ+2) v eR[j] | {z } 



(ℓ+2)×1

The above relation between σ1 , . . . , σℓ+1 is represented as a system of the linear equation where the linear transformation has rank (ℓ + 1). Since, e kι,b[i] , u eS are all chosen uniformly at random ι ∈ [α] and P e P e b ∈ {0, 1}. Thus, kι,ω[i] + u eS is also distributed unformly at random. Observe that, kι,ω[i] + u eS , ι∈[α]

ι∈[α]

veR[i] , . . . , veR[i] , veR[j] are independent and uniformly random, σ1 , . . . , σℓ+1 are too independent and τ (1)

τ (ℓ)

uniformly random. In other words, σ1 , . . . , σℓ+1 are completely uncorelated and as a result Cti and Trj considered in the consistency game does not match except with negligible probability.

4.2

Security

Next, we argue that our construction baeks is adaptively f ull-cpa secure. Theorem 1. If the lat-Uk -MDDH Assumption holds in G, then baeks is a f ull-cpa-secure BAEKS scheme. Precisely, for any ppt adversary A that breaks baeks in the f ull-cpa model making at most q challenge trapdoor queries, at most Q challenge encryption requests and at most Q̃ key requests, there exists ppt algorithms B1 , B2 such that, |Q |ℓ-lat-U2k,k -MDDH

ull-cpa AdvfA,baeks (λ) ≤ AdvB,GCt1

(λ) + AdvCore B,G (λ) 4 |Q |-lat-U3k,k -MDDH + AdvB,GTr2 (λ) + p−1

k -MDDH ≤ kAdvlat-U (λ) + AdvCore B,G (λ) B,G1 4 k -MDDH + 2kAdvlat-U (due to F3) (λ) + B,G2 p−1

We use devise a hybrid argument to argue the f ull-cpa security of baeks. We define G0 , G1 , . . . , G6 in Figure 6 to argue the coveted f ull-cpa security. We describe the games and provide the security argument ull-cpa next. Thus, AdvfA,baeks (λ) above is also tight. 13

Init(1λ , α, u) // G3 -G6

1: G = (p, G1 , G2 , GT , g1 , g2 , e) ←- ABSGen(1λ ) 2: A ←- U2k,k s.t. A ∈ Zk×k is invertible p 3: B ←- U3k,k 4: For (ι, b) ∈ [α] × {0, 1} :

OSEnc(skS , ω, pkR ) //G1 , G2 , G3 , G4 , G5 , G6

1: Let pkR = (pkR1 , . . . , pkRℓ ) 2: τ ←- Γ ([ℓ]) 3: Ct = (([ctȷ,0 ]1 , [ctȷ,1 ]1 )ȷ∈[ℓ] ) s.t.

Qι,b , Nι,b ←- Z(k)×(3k) p Qι,b Kι,b = Nι,b

ctȷ,0 = Asȷ for sȷ ←- Zk p ctȷ,0 ←- Z2k p

3k×k K⊤ ι,b A ←- Zp

Kι,b B =

−⊤

//G4 -G6

⊤ ⊤ ((K⊤ ι,b A) B − A Nι,b B)

K⊤ ι,b A

ctȷ,1 = (

Nι,b B

5: pp = ([A]1 , [A]2 , [B]1 , [B] , nh2

k ct ȷ,0 ←- Zk p , hȷ,0 ←- Zp , ct ȷ,0 = hȷ,0 + AA

ι∈[α]

i 1

−1

ct ȷ,0

, hS,ω,Rτ (ȷ) ←- Z3k p

, [Kι,b B]2

o ι∈[α] b∈{0,1}

)

⊤ ⊤ K⊤ ι,ωι + US + VR

τ (ȷ)

⊤ ⊤ K⊤ ι,ωι + US + VR

)AA

⊤ ⊤ K⊤ ι,ωι + US + VR

)AA

ctȷ,1 = (

ι∈[α]

ctȷ,1 = (

ι∈[α]

)ctȷ,0

τ (ȷ)

−1

ct ȷ,0 + (

P ι∈[α]

−1

⊤ ⊤ N⊤ ι,ωι + XS + ZR

ct ȷ,0 + hS,ω,Rτ (ȷ)

OKgen(j) // G3 -G6

1: Wj , Yj ←- Z(k)×(3k) p 2: For (ι, b) ∈ [2u] × {0, 1}:

//G0 -G2

Jj,ι,b ←- Z(k)×(3k) p P2u Pu , Zj = J 3: Xj = i=1 J i=u+1 j,i,ji j,i,ji Yj j , Vj = 4: Uj = W Zj Xj

//G0 -G2 //G0 -G2 //G0 -G2

Uj B =

−⊤

//G4 -G6

⊤ ⊤ ((U⊤ j A) B − A Xj B)

Xj B −⊤

((Vj⊤ A)⊤ B − A⊤ Zj B) Zj B h i 5: skj = ( U⊤ A , [V B] j j 2 ) 1h i 6: pkj = ( [Uj B]2 , Vj⊤ A )

Vj B =

OTgen(pkE , w, skF ) //G1 , G2 , G3 , G4 , G5

1: r ←- Zkp 2: Tr = ([k0 ]2 , [k1 ]2 ) where k0 = Br

⊤ 3k×k U⊤ j A, Vj A ←- Zp

ctȷ,1 ←- Z3k p

k0 ←- Z3k , tE,w,F ←- Zk p p P k1 = ( Kι,wι + UE + VF )k0 ι∈[α]   P ( Qι,wι + WE + YF )k0 k1   ι∈[α] = = P ( Nι,wι + XE + ZF )k0  k1 ι∈[α]

  −⊤ ⊤ P −⊤ ⊤ A A ( Kι,wι + UE + VF )k0 − A A k1 k1   ι∈[α] P k1 = =  k1 ( Nι,wι + XE + ZF )k0 ι∈[α]

  −⊤ ⊤ P −⊤ ⊤ A A ( Kι,wι + UE + VF )k0 − A A k1 k1   k1 = = ι∈[α] k1 tE,w,F

Finalize(b ∈ {0, 1})

1: Return b ∧ (QTr ∩ QCt = ∅) ∧ (∀ (u, _, _) ∈ Qsk , (pku , _, _), (_, _, pku ) ∈ / QTr ∪ QCt )

k1 ←- Z2k p

Fig. 6 Hybrids for the transition from G1 to G6 .

τ (ȷ)

)hȷ,0

4.3

Full Security Argument

Proof. We argue the proof of Theorem 1 via a hybrid argument. We sequence the games first and follow it by lemmas that acts as a reduction to so-called Core Lemma Section 5. – G0 : The real situation. – G1 : For ȷ ∈ [ℓ], use ctȷ,0 to compute ctȷ,1 and k0 to compute k1 . – G2 : Sample ctȷ,0 for ȷ ∈ [ℓ] and k0 uniformly at random. – G3 : Replace usage of Qι,b , Wj and Yj , by (Qι,b , Nι,b ), (Uj , Xj ) and (Vj , Zj ) respectively. ⊤ ⊤ – G4 : Sample Q⊤ ι,b A, Uj A and Vj A uniformly at random. – G5 : We remove effect of Nι,b , Xj and Zj in both OSEnc and OTgen responses. – G6 : {ct1,1 , . . . , ctℓ,1 } and k1 are all random quantities of appropriate dimensions.

4.4

Lemmas for Full Security of BAEKS

Lemma 5. (G4 to G5 ) For any ppt adversary A in the f ull-cpa security model, there exists an ppt adversary B such that |AdvGA4 (λ) − AdvGA5 (λ)| ≤ AdvCore B,G (λ). Lemma 6. (G5 to G6 ) For any adversary A, AdvGA5 (λ) = AdvGA6 (λ). 4.5

Proof of Lemmas for Full Security of BAEKS

Proof of Lemma 1. This is a syntactic change and therefore AdvGA0 (λ) = AdvGA1 (λ). Proof of Lemma 2. To argue this indistinguishability, we introduce an intermediate game G1.5 which is exactly same as G1 except that ctȷ,0 are sampled from Z2k p for all ȷ ∈ [ℓ] for all challenge queries. We then argue that, G1 and G1.5 are computationally indistinguishable under |QCt |ℓ-fold lat-U2k,k -MDDH assumption. The same argument can also be applied to show G1.5 and G2 are computationally indistinguishable under |QTr |-fold lat-U3k,k -MDDH assumption. B that takes |QCt |ℓ-fold lat-U2k,k -MDDH instance ([D]1 , [D]2 , [f1 ]1 , . . . , Wenext construct the reduction and simulates pp using ([D]1 , [D]2 , [B]1 , [B]2 ). It uses f(c−1)ℓ+1 to fcℓ f|QCt |ℓ 1 ). It samples B ←- Z3k×k p to simulate cth challenge ct1,1 to ctℓ,1 . Rest of the simulation is done exactly the same as in G1 . Thus, |Q |ℓ-lat-U2k,k -MDDH 1 . |AdvGA1 (λ) − AdvGA1.5 (λ)| ≤ AdvB,GCt1 (λ) + p−1 |Q |-lat-U3k,k -MDDH

Similarly, we could argue that, |AdvGA1.5 (λ) − AdvGA2 (λ)| ≤ AdvB,GTr2

1 . (λ) + p−1

⊤ ⊤ Proof of Lemma 3. G3 does not use Qι,b , Wj and Yj anymore. In particular, by K⊤ j,ι,b A = Qj,ι,b A+Nj,ι,b A, ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ U⊤ j A = Wj A + Xj A and Vj A = Yj A + Zj A, we get Qj,ι,b = (Kj,ι,b A − Nj,ι,b A)A

−1

, Wj⊤ =

⊤ (U⊤ j A − Xj A)A

−1

and Yj⊤ = (Vj⊤ A − Z⊤ j A)A ⊤

⊤

k 1 = k0 (

−1

. We substitute Qι,b , Wj and Yj in all OTr responses:

⊤

Qι,wι + WE + YF )

ι∈[α] ⊤

= k0

−1

⊤

(Kι,wι A − Nι,wι A)A

⊤

+ k0 (UE A − XE A)A

−1

⊤

+ k0 VF AA

−1

ι∈[α] ⊤

−1

⊤

− k0 ZF AA X X −1 ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ Nι,wι A + XE A + ZF A)A = k0 ( Kι,wι A + UE A + VF A) − k0 ( ι∈[α]

ι∈[α] ⊤

= k0 (

⊤

Kι,wι + UE + VF )A − k0 (

⊤

Kι,wι + UE + VF )A − k0 (

⊤

−1

⊤

−1

Nι,wι + XE + ZF )AA

ι∈[α]

= k0 (

⊤

Nι,wι + XE + ZF )AA

ι∈[α]

= k0 (

⊤

Kι,wι + UE + VF )A − k 1 AA

−1

ι∈[α]

As for the distribution of OCt responses, it is easy to see that ctȷ,0 are uniformly random, as in G2 . We substitute Qι,b , Wj and Yj in all OCt responses:

ct ȷ,0 −1 ct ȷ,0 for ct ȷ,0 = hȷ,0 + AA ct ȷ,0 X X −1 ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ctȷ,1 = ( Kι,ωι + US + VR )AA ct ȷ,0 + ( Nι,ωι + XS + ZR ctȷ,0 =

τ (ȷ)

ι∈[α]

(Qι,ωι A + Nι,ωι A) + WS A + XS A + VR

⊤

τ (ȷ)

A + ZR

τ (ȷ)

⊤

A)A

)hȷ,0

−1

ct ȷ,0

ι∈[α]

⊤

Nι,ωι + XS + ZR

τ (ȷ)

)(ct ȷ,0 − AA

−1

ct ȷ,0 )

ι∈[α]

⊤

Qι,ωι +WS +VR

)AA

−1

τ (ȷ)

ι∈[α]

⊤

Nι,ωι + XS + ZR

τ (ȷ)

⊤

Qι,ωι + WS + VR

τ (ȷ)

)ct ȷ,0 + (

⊤

τ (ȷ)

⊤

Nι,ωι + XS + ZR

τ (ȷ)

−1

⊤

)AA

ct ȷ,0

τ (ȷ)

)ct ȷ,0

ι∈[α]

X ⊤ ⊤ ⊤ ⊤ ⊤ Qι,ωι ∥ Nι,ωι + WS ∥ XS + YR

ι∈[α]

⊤

Nι,ωι + XS + ZR

ι∈[α]

ct ȷ,0

ι∈[α]

)AA

τ (ȷ)

)ct ȷ,0 − (

ι∈[α]

−1

Nι,ωι + XS +ZR

ι∈[α]

+( =(

⊤

ct ȷ,0 + (

Qι,ωι Nι,ωι ⊤

⊤

WS XS

⊤

Kι,ωι + US + VR

⊤

τ (ȷ)

YRτ (ȷ) ZRτ (ȷ)

⊤

∥ ZR

τ (ȷ)

ct ) ct ȷ,0 ȷ,0

!⊤ )ctȷ,0

)ctȷ,0

ι∈[α]

1 . This is a syntactic change provided A is invertible and therefore |AdvGA2 (λ) − AdvGA3 (λ)| ≤ p−1 ⊤ ⊤ 3k×k Proof of Lemma 4. We sample K⊤ . Then we compute Kι,b B, Uj B and Vj B folι,b A, Uj A, Vj A ←- Zp ⊤ ⊤ lowing G3 . Since G3 sampled Kι,b , Jj,i,ji , Wj , Yj uniformly at random, K⊤ ι,b A, Uj A, Vj A were also uniformly random quantities. This is therefore a conceptual change provided A is invertible and therefore 1 |AdvGA3 (λ) = AdvGA4 (λ)| ≤ p−1 .

Proof of Lemma 5. This lemma is proved assuming ExpCore B (λ, b) is tightly secure for all ppt adversary which we have proved in the next section. Given a ppt adversary A that distinguishes G4 and G5 , we construct Core Core a reduction B that distinguishes ExpCore B (λ, 0) from ExpB (λ, 1). Let C be the ExpB (λ, b) challenger who sampled b ←- {0, 1} uniformly at random at the start of the game. – C gives out params to B. 16

• B samples d ←- {0, 1}. • B samples A ←- U2k,k . 3k×k • B samples K⊤ for all (ι, b) ∈ [α] × {0, 1}. ι,b A ←- Zp h i • B defines pp = ([A]1 , [A]2 , K⊤ A , params). ι,b 1 • B gives pp to A. – When A makes Osk queries on a new j: • B first makes a OKey query on j. • B then makes a OCor query on j. • C responds with dj = [Xj B]2 , [Zj B]2 . ⊤ 3k×k • B samples U⊤ . j A, Vj A ←- Zp • B computes Uj B =

−⊤

⊤ ⊤ ((U⊤ j A) B − A Xj B) Xj B

and Vj B =

−⊤

((Vj⊤ A)⊤ B − A⊤ Zj B) Zj B

• B maintains a list Qsk of (j, skj , pkjh ). i h i • It returns (skj , pkj ) to A where skj = U⊤ , [Vj B]2 and pkj = [Uj B]2 , Vj⊤ A . j A 1 1 – When A makes Opk queries on a new j: • B first makes a OKey query on j. • C responds with (j, [Xj B]2 ). ⊤ 3k×k • B samples U⊤ . j A, Vj A ←- Zp −⊤ ⊤ ⊤ ⊤ A ((U j A) B − A Xj B) . • B computes Uj B =

i Xj B

• B sends pkj = [Uj B]2 , Vj⊤ A back to A. 1 – When A makes OTr queries on new ((pkE[0] , w[0] , pkF[0] ), (pkE[1] , w[1] , pkF[1] )): • B finds E[d] and F[d] from Qpk it maintained. • B makes a QT query on (E[d] , w[d] , F[d] ). k • C replies with T = (t0 , t1 ) ∈ G3k 2 × G2 . • B uses T to compute Tr = (k0 , k1 ) where it sets k0 = t0 and   −⊤ P −⊤ ⊤ ⊤ ⊤ ⊤ A ( K⊤ A t1 ι,wι A + UE A + VF A) t0 − A  k1 =  ι∈[α] t1

• B forwards Tr to A as the challenge. – When A makes OCt queries on new ((pkS[0] , ω [0] , pkR[0] ), (pkS[1] , ω [1] , pkR[1] )): • B finds S[d] and R[d] = {R1 , . . . , Rℓ } from Qpk it maintained. • B makes a QC query on (S[d] , ω [d] , R[d] ). ℓ • C replies with C = ((cȷ,0 , cȷ,1 )ȷ∈[ℓ] ) ∈ (Gk1 × G3k 1 ) • B uses C to compute Ct = ((ctȷ,0 , ctȷ,1 )ȷ∈[ℓ] ) where it sets ctȷ,0 = " (

P ι∈[α]

⊤ ⊤ K⊤ ι,wι A + UE A + VF A)A

−1

cȷ,0 ct −1 cȷ,0 cȷ,0 + AA ct

and ctȷ,1 =

# cȷ,0 ct

+ cȷ,1

cȷ,0 ←- Zk for ct p

• B forwards Ct to A as the challenge. – A finally outputs d′ ∈ {0, 1}. Observe that when A makes Osk query on any arbitrary j, B queries OKey and OCor to get dj . B then uses dj = ( [Xj,ι,b B]2 , [Zj,ι,b B]2 ι∈[L] ), to compute pkj and skj . Thus, A receives the keys of j. b∈{0,1}

Observe that when A makes Opk query on any arbitrary j, B queries OKey on j. Notice that, B gets ⊤ 3k×k (j, [Xj B]2 ) in this case and cannot compute pkj and skj completely. B samples U⊤ j A, Vj A ←- Zp uniformly at random, and use it simulate pkj response to A. If b = 0, A gets properly simulated challenges for both Tr and Ct. A can guess d in this case with probability 1/2 + |AdvGA4 (λ) − AdvGA5 (λ)|. If b = 1, A gets simulated random challenges for both Tr and Ct. A can guess d in this case with probability 1/2. Thus, |AdvGA4 (λ) − AdvGA5 (λ)| ≤ AdvCore B,G (λ). The restrictions in f ull-cpa security and the Core-Lemma Figure 7 are same and therefore translate naturally. k Proof of Lemma 6. Recall that, QCt ∩ QTr = ∅. Since hS,ω,Rτ (ȷ) ←- Z3k p and tE,w,F ←- Zp are sampled afresh, these make ctȷ,1 and k1 uniformly random and independent.

Core Lemma

We now present the core lemma in terms of an experiment in Figure 7 that forms the basis in the proofs of our BAEKS construction. Informally speaking, the core lemma experiment checks if A has guessed the experiment’s choice b′ right after making polynomial many queries to OKey, OCor, OTag, OChal oracles in an interleaved manner subject to the condition that same queries are not made on OTag and OChal oracles and only users, that are not a part of any OTag or OChal queries, can be corrupted. Observe that, these restrictions match with the restrictions of f ull-cpa security and are only natural restrictions. Interestingly, OKey outputs [Xj B]2 , a part of the secret key. However, we note that the indistinguishability Pargument u still goes through. Intuitively, the primary reason for that would be for every user j, Xj = i=1 Jj,i,ji , a summation of random quantity. Thus, even after the projection [Xj B]2 is published, Xj keeps sufficient entropy that can be utilized to inject randomness into OTag and OChal responses. This small observation has allowed us to prove the Core Lemma and subsequently use Core Lemma to prove Lemma 5. For any adversary A, the advantage is defined as Core Core AdvCore A,G (λ) = | Pr[ExpA (λ, 0) = 1] − ExpA (λ, 1) = 1|

OCor(j ∈ U ) ExpCore A (λ, b)

1: QCr = QCr ⊔ {(j, dj )} from QK 2: Return dj

1: G ←- ABSGen(1λ ) 2: B ←- U3k,k 3: For (ι, b) ∈ [α] × {0, 1} : Nι,b ←- Z(k)×(3k) p 4: params = ([B]1 , [B]2 , [Nι,b B]2 ι∈[α] )

OTag(E, w, F)

1: QT = QT ⊔ {(E, w, F)} 2: T = ([t0 ]2 , [t1 ]2 ) where

b∈{0,1} ′

OKey(·),OTag(·,·,·),OChal(·,·,·)

5: b ← A (params) ? 6: Return (b = b′ ) ∧ (QT ∩ QC = ∅)

′ k t0 ←- Z3k p , t ←- Zp P ′ t1 = (1 − b)( α ι=1 Nι,wι + XE + ZF )t0 + b · t 3: Return T

∧ (∀ (u, _) ∈ QCr , (u, _, _), (_, _, u) ∈ / QT ∪QC ) OKey(j ∈ U )

OChal(S, ω, R)

1: For (ι, b) ∈ [2u] × {0, 1}: Jj,ι,b ←- Z(k)×(3k) p P2u Pu 2: Xj = i=1 Jj,i,ji , Zj = i=u+1 Jj,i,ji 3: dj = ( [Xj B]2 , [Zj B]2 ) 4: QK = QK ⊔ {(j, dj )} 5: Return (j, [Xj B]2 )

1: Let R = {R1 , . . . , Rℓ } 2: QC = QC ∪ {(S, ω, Rȷ )ȷ∈[ℓ] } and τ ←- Γ ([ℓ]) 3: C = (([cȷ,0 ]1 , [cȷ,1 ]1 )ȷ∈[ℓ] ) s.t. ′ 3k cȷ,0 ←- Zk p , c ←- Zp P ⊤ ⊤ ⊤ cȷ,1 = (1 − b)( α ι=1 Nι,ωι + XS + ZR

τ (ȷ)

)cȷ,0 +b · c′

4: Return C

Fig. 7 Experiment for the Core Lemma.

Theorem 2 (Core Lemma). Consider the experiments ExpCore b,A (λ,) be defined as Figure 7 where A is given access to OKgen, OCor, OTag and OChal oracles for polynomial number of queries (i.e. |QK |, |QT |, |QC | = poly(λ)). We claim that under the U3k,k -MDDH assumption for G1 and U3k,k -MDDH assumption for G2 , Core AdvCore A,G (λ) = neg(λ) for all ppt adversary. For all ppt adversary A having advantage AdvA,G (λ), there exists 18

ppt adversaries B, B1 , B2 , B3 s.t. |Q |-U

T 3k,k AdvCore A,G (λ) ≤ 2(2u + α)AdvB1 ,G2

-MDDH

(λ)

k|Q |-U -MDDH + 2(2u + α)AdvB2 ,GC 1 2k,k (λ) k|Q |-U

+ (2u + α)AdvB3 ,GC 1 3k,k +

-MDDH

(λ)

(2u + α)(4k + 3|QC | + 6) (2u + α)k + p−1 p

k -MDDH ≤ 4(2u + α)kAdvU (λ) B,G2 k -MDDH + 4(2u + α)kAdvU (λ) B,G1

(2u + α)(4k + 3|QC | + 6) p−1 (2u + α)k + (due to F3) p +

Core We use devise a hybrid argument to argue the indistinguishability of ExpCore A (λ, 0) and ExpA (λ, 1). We define H1 , H2,0,1 , . . . , H2,α−1,5 , H2,α,1 , H3,α,1 , . . . , H3,α+u−1,5 , H3,α+u,1 , H4,α+u,1 , . . . , H4,α+2u−1,5 , H4,α+2u,5 , H5 and H6 in Figure 8, Figure 9 and Figure 10 to argue the said indistinguishability. We describe the games next and provide the security argument in ?? due to space limitation.

5.1

Overview of the Proof of Core-Lemma

Core Proof. We use devise a hybrid argument to argue the indistinguishability of ExpCore A (λ, 0) and ExpA (λ, 1). We define H1 , H2,0,1 , . . . , H2,α−1,5 , H2,α,1 , H3,α,1 , . . . , H3,α+u−1,5 , H3,α+u,1 , H4,α+u,1 , . . . , H4,α+2u−1,5 , , H4,α+2u,5 , H5 and H6 in Figure 8, Figure 9 and Figure 10 to argue the said indistinguishability. In Section 5.2, we give the lemmas needed to prove these indistinguishabilities.

– H1 : Same as ExpCore A (λ, 0). – H2,i,1 : Injected randomness via RFi : {0, 1}i → Zk×2k defined on-the-fly. p – H2,i,2 : Sample each t0 based on concerned ωi+1 ∈ {0, 1}. – H2,i,3 : Express RFi : {0, 1}i → Zk×2k in the span (B∗0 ||B∗1 ) in terms of ZFi , OFi : {0, 1}i → Zk×k defined p p on-the-fly. – H2,i,4 : Inject randomness in ZFi : {0, 1}i → Zk×k to define ZFi+1 : {0, 1}i+1 → Zk×k based on concerned p p ωi+1 ∈ {0, 1}. based on concerned to define OFi+1 : {0, 1}i+1 → Zk×k – H2,i,5 : Inject randomness in OFi : {0, 1}i → Zk×k p p ωi+1 ∈ {0, 1}. – H3,α+i,1 : Injected randomness via RFα+i : {0, 1}α+i → Zk×2k defined on-the-fly. p – H3,α+i,2 : Sample each t0 based on concerned Si+1 ∈ {0, 1}. – H3,α+i,3 : Express RFα+i : {0, 1}α+i → Zk×2k in the span (B∗0 ||B∗1 ) in terms of ZFα+i , OFα+i : {0, 1}α+i → p k×k Zp defined on-the-fly. – H3,α+i,4 : Inject randomness in ZFα+i : {0, 1}α+i → Zk×k to define ZFα+i+1 : {0, 1}α+i+1 → Zk×k p p depending on Si+1 ∈ {0, 1}. – H3,α+i,5 : Inject randomness in OFα+i : {0, 1}α+i → Zk×k to define OFα+i+1 : {0, 1}α+i+1 → Zk×k p p depending on Si+1 ∈ {0, 1}. – H4,α+u+i,1 : Injected randomness via RFα+u+i : {0, 1}α+u+i → Zk×2k defined on-the-fly. p – H4,α+u+i,2 : Sample each t0 based on concerned Ri+1 ∈ {0, 1}. – H4,α+u+i,3 : Express RFα+u+i : {0, 1}α+u+i → Zk×2k in the span (B∗0 ||B∗1 ) in terms of ZFα+u+i , OFα+u+i : p {0, 1}i → Zk×k defined on-the-fly. p – H4,α+u+i,4 : Inject randomness in ZFα+u+i : {0, 1}α+u+i → Zk×k to define ZFα+u+i+1 : {0, 1}α+u+i+1 → p k×k Zp depending on Ri+1 ∈ {0, 1}. 19

– H4,α+u+i,5 : Inject randomness in OFα+u+i : {0, 1}α+u+i → Zk×k to define OFα+u+i+1 : {0, 1}α+u+i+1 → p k×k Zp depending on Ri+1 ∈ {0, 1}. – H5 : All t1 are sampled uniformly at random. – H6 : Same as ExpCore A (λ, 1).

5.2

Lemmas for Core-Lemma H

2,0,1 1 Lemma 7. (H1 to H2,0,1 ) For any adversary A, AdvH (λ). A (λ) = AdvA

Lemma 8. (H2,i,1 to H2,i,2 ) For any ppt adversary A in the f ull-cpa security model, there exists a ppt |Q |-U -MDDH H H adversary B such that |AdvA2,i,1 (λ) − AdvA2,i,2 (λ)| ≤ 2AdvB,GT 2 3k,k (λ) + 2×2k p−1 . H

Lemma 12. (H2,α,1 to H3,α,1 ) For any adversary A, AdvA2,α,1 (λ) = AdvA3,α,1 (λ). Lemma 13. (H3,α+i,1 to H3,α+i,2 ) For any ppt adversary A in the f ull-cpa security model, there exists a |Q |-U -MDDH H H (λ) + 2×2k ppt adversary B such that |AdvA3,α+i,1 (λ) − AdvA3,α+i,2 (λ)| ≤ 2AdvB,GT 2 3k,k p−1 . H

Lemma 17. (H3,α+u,1 to H4,α+u,1 ) For any adversary A, AdvA3,α+u,1 (λ) = AdvA4,α+u,1 (λ). Lemma 18. (H4,α+u+i,1 to H4,α+u+i,2 ) For any ppt adversary A in the f ull-cpa security model, there exists |Q |-U -MDDH H H (λ) + 2×2k a ppt adversary B such that |AdvA4,α+u+i,1 (λ) − AdvA4,α+u+i,2 (λ)| ≤ 2AdvB,GT 2 3k,k p−1 . H

5 Lemma 22. (H4,L,1 to H5 ) For any adversary A, AdvA4,L,1 (λ) = AdvH A (λ)

H1 , H2,i,1 , H2,i,2 , H2,i,3 , H2,i,4 , H2,i,5 λ

Init(1 )

1: G ←- ABSGen(1λ ) 2: B, B0 , B1 ,

OKey(j)

∗ B∗ 0 , B1

1: For (ι, b) ∈ [2u] × {0, 1}: Jj,ι,b ←- Z(k)×(3k) p Pu P2u 2: Xj = i=1 Jj,i,ji , Zj = i=u+1 Jj,i,ji 3: dj = ( [Xj B]2 , [Zj B]2 ) 4: QK = QK ⊔ {(j, dj )} 5: Return (j, [Xj B]2 )

←- U3k,k s.t.

− (B, B0 , B1 ) generates Z3k p ∗ ⊥ − (B∗ 0 , B1 ) generates B ⊤ ∗ ⊤ ∗ ⊤ ∗ − B B0 = O, B1 B0 = O, B⊤ B∗ 1 = O, B0 B1 = O 3: For (ι, b) ∈ [α] × {0, 1} : Nι,b ←- Z(k)×(3k) p 4: params = ([B]1 , [B]2 , [Nι,b B]2 ι∈[α] )

OTag(E, w, F)

b∈{0,1}

1: QT = QT ⊔ {(E, w, F)} 2: T = ([t0 ]2 , [t1 ]2 ) where

OChal(S, ω, R)

t0 ←- Z3k p

1: Let R = {R1 , . . . , Rℓ } 2: τ ←- Γ ([ℓ]) 3: QC = QC ∪ {(S, ω, Ri )i∈[ℓ] } 4: C = (([cȷ,0 ]1 , [cȷ,1 ]1 )ȷ∈[ℓ] ) s.t.

t0 = Br + Bwi+1 rwi+1 for r, rwi+1 ←- Zk p P t1 = ( Nι,wι + XE + ZF )t0

cj,0 ←- Zk p P ⊤ ⊤ cj,1 = ( N⊤ ι,ωι + XS + ZR

τ (j)

ι∈[α]

ι∈[α] ⊤

+(RFi (w|i ))B⊥ t0

)cj,0

⊤ ⊤ +((ZFi (w|i )(B∗ + OFi (w|i )(B∗ 0) 1 ) ))t0

+B⊥ (RFi (ω|i )⊤ )cj,0

⊤ ⊤ +(ZFi+1 (w|i+1 )(B∗ + OFi (w|i )(B∗ 0) 1 ) )t0

⊤ ⊤ +(B∗ + B∗ 0 ZFi (ω|i ) 1 OFi (ω|i ) )cj,0

⊤ ⊤ +(ZFi+1 (w|i+1 )(B∗ + OFi+1 (w|i+1 )(B∗ 0) 1 ) )t0

⊤ ⊤ +(B∗ + B∗ 0 ZFi+1 (ω|i+1 ) 1 OFi (ω|i ) )cj,0

3: Return T

⊤ ⊤ +(B∗ + B∗ 0 ZFi+1 (ω|i+1 ) 1 OFi+1 (ω|i+1 ) )cj,0

Finalize(b ∈ {0, 1})

5: Return C

1: Return b ∧ (QT ∩ QC = ∅) ∧ (∀ (u, _) ∈ QCr , (u, _, _), (_, _, u) ∈ / QT ∪QC )

OCor(j)

1: QCr = QCr ⊔ {(j, dj )} from QK 2: Return dj

Fig. 8 Hybrids for the transition from H1 to H2,α−1,5 .

5.3

Proof of Lemmas for Core-Lemma ⊤

′ Proof of Lemma 7. Suppose we replace Nι,b by Nι,b + RF0 (ω|0 )B⊥ for b ∈ {0, 1}. Observe that, pp stays ′ the same. For all (S′ , ω ′ , R′ ) ∈ QT ⊔ QC , we have RF0 (ω|0 ) = RF0 (ϵ) and Nι,b is identically distributed to

Nι,b + RF0 (ϵ)B⊥

⊤

for b ∈ {0, 1}.

Proof of Lemma 8. To argue this indistinguishability, we introduce an intermediate game H2,i,1.5 where t0 is sampled from span(B||B0 ) if wi+1 = 0 and is sampled from Z3k p if wi+1 = 1. We then argue that, H2,i,1 and H2,i,1.5 are computationally indistinguishable under |QT |-fold U3k,k -MDDH assumption. The same argument can also be applied to show H2,i,1.5 and H2,i,2 are computationally indistinguishable. To argue the indistinguishability of H2,i,1 and H2,i,1.5 , we devise an ppt algorithm B next. Let B receive |QT |-fold U3k,k -MDDH instance ([D]2 , [f1 ]2 , . . . , f|QT | 2 ). (k)×(3k)

Setup. B samples B, B1 ←- Z3k×k and B⊥ ←- Z3k×2k s.t. B⊤ B⊥ = O. B also chooses Nι,b ←- Zp for p p all (ι, b) ∈ [α] × {0, 1} uniformly at random. (k)×(3k) OKey. On every query on j, B samples Jι,b ←- Zp for all (ι, b) ∈ [2u] × {0, 1} uniformly at random Pu P2u sets Xj = i=1 Ji,ji and Zj = i=u+1 Ji,ji for all (ι, b) ∈ [2u] × {0, 1}. B defines random functions RFi (w|i ) ∈ Zk×2k on the fly. It updates (j, dj ) in QK and returns j. p OCor. On every query on j, B executes OKey(j) to retrieve dj if (j, _) ∈ / QK . It finally returns dj and updates (j, dj ) in QCr . 21

H3,α+i,1 , H3,α+i,2 , H3,α+i,3 , H3,α+i,4 , H3,α+i,5 λ

Init(1 )

1: G ←- ABSGen(1λ ) 2: B, B0 , B1 ,

∗ B∗ 0 , B1

OKey(j)

1: For (ι, b) ∈ [α] × {0, 1}: Jj,ι,b ←- Z(k)×(3k) . p Pu P2u 2: Xj = i=1 Jj,i,ji , Zj = i=u+1 Jj,i,ji 3: dj = [Xj B]2 , [Zj B]2 4: QK = QK ⊔ {(j, dj )} 5: Return (j, [Xj B]2 )

←- U3k,k s.t.

OTag(E, w, F)

b∈{0,1}

1: QT = QT ⊔ {(E, w, F)} 2: T = ([t0 ]2 , [t1 ]2 ) where

OChal(S, ω, R)

t0 ←- Z3k p

1: Let R = {R1 , . . . , Rℓ } 2: τ ←- Γ ([ℓ]) 3: QC = QC ∪ {(S, ω, Rȷ )ȷ∈[ℓ] } 4: C = (([cȷ,0 ]1 , [cȷ,1 ]1 )ȷ∈[ℓ] ) s.t.

t0 = Br + BEi+1 rEi+1 for r, rEi+1 ←- Zk p P Nι,wι + XE + ZF )t0 t1 = ( ι∈[α]

cj,0 ←- Zk p P ⊤ ⊤ cj,1 = ( N⊤ ι,ωι + XS + ZR ι∈[α]

τ (j)

⊤

+(RFα+i (w ∥ E|i ))B⊥ t0

)cj,0

⊤ ⊤ +((ZFα+i (w ∥ E|i )(B∗ + OFα+i (w ∥ E|i )(B∗ 0) 1 ) ))t0

+B⊥ (RFα+i (ω ∥ S|i )⊤ )cj,0

⊤ ⊤ +(ZFα+i+1 (w ∥ E|i+1 )(B∗ + OFα+i (w ∥ E|i )(B∗ 0) 1 ) )t0

⊤ ⊤ +(B∗ + B∗ 0 ZFα+i (ω ∥ S|i ) 1 OFα+i (ω ∥ S|i ) )cj,0

⊤ ⊤ +(ZFα+i+1 (w ∥ E|i+1 )(B∗ + OFα+i+1 (w ∥ E|i+1 )(B∗ 0) 1 ) )t0

⊤ ⊤ +(B∗ + B∗ 0 ZFα+i+1 (ω ∥ S|i+1 ) 1 OFα+i (ω ∥ S|i ) )cj,0

3: Return T

⊤ ⊤ +(B∗ + B∗ 0 ZFα+i+1 (ω ∥ S|i+1 ) 1 OFα+i+1 (ω ∥ S|i+1 ) )cj,0

Finalize(b ∈ {0, 1})

5: Return C

1: Return b ∧ (QT ∩ QC = ∅) ∧ (∀ (u, _) ∈ QCr , (u, _, _), (_, _, u) ∈ / QT ∪QC )

OCor(j)

1: QCr = QCr ⊔ {(j, dj )} from QK 2: Return dj

Fig. 9 Hybrids for the transition from H3,α,1 to H3,α+u−1,5 .

OChal. Follows the description in Figure 8. OTag. For any j th query j ∈ [|QT |], B simulates t0 as following: ( t0 =

Br + fj z

for r ←- Zkp if wi+1 = 0 for z ←- Z3k p if wi+1 = 1

Since the challenger chose D ←- Z3k×k and B chose B, B1 ←- Z3k×k uniformly at random, (B||D||B1 ) is a fullp p H

|Q |-U

2,i,1 rank matrix with overwhelming probability 1− k+k (λ)−AdvA2,i,1.5 (λ)| ≤ AdvB,GT 2 3k,k p−1 . Thus, |AdvA

-MDDH

(λ)+

|Q |-U -MDDH H2,i,1.5 H 2×k (λ) − AdvA2,i,2 (λ)| ≤ AdvB,GT 2 3k,k (λ) + 2×k p−1 . A similar argument shows that |AdvA p−1 .

Proof of Lemma 9. We show that, these two games are statistically indistinguishable. In H2,i,2 , we rewrite RFi (ω|i′ ) as following: ′ RFi (ω|i )B⊥

⊤

′ ′ = ZFi (ω|i )B∗0 + OFi (ω|i )B∗1 ,

for all (S′ , ω ′ , R′ ) ∈ QT ⊔ QC where ZFi , OFi : {0, 1}i → Zk×k are independent random functions. Since, p ⊤

are independent (B∗0 ||B∗1 ) generates B⊥ with overwhelming probability 1− kp , and ZFi , OFi : {0, 1}i → Zk×k p random functions, RFi : {0, 1}i → Zk×2k are random functions as well. p Proof of Lemma 10. To argue the indistinguishability of H2,i,3 and H2,i,4 , we define 22

H4,α+u+i,1 , H4,α+u+i,2 , H4,α+u+i,3 , H4,α+u+i,4 , H4,α+u+i,5

, H5 ,

Init(1λ )

1: G ←- ABSGen(1λ ) 2: B, B0 , B1 ,

∗ B∗ 0 , B1

OKey(j) ←- U3k,k s.t.

1: For (ι, b) ∈ [α] × {0, 1}: Jj,ι,b ←- Z(k)×(3k) p Pu P2u 2: Xj = i=1 Jj,i,ji , Zj = i=u+1 Jj,i,ji 3: dj = ( [Xj B]2 , [Zj B]2 ι∈[α] )

− (B, B0 , B1 ) generates Z3k p ∗ ⊥ − (B∗ 0 , B1 ) generates B ⊤ ∗ ⊤ ∗ ⊤ ∗ − B ⊤ B∗ 0 = O, B1 B0 = O, B B1 = O, B0 B1 = O 3: For (ι, b) ∈ [α] × {0, 1} : Nι,b ←- Z(k)×(3k) p 4: params = ([B]1 , [B]2 , [Nι,b B]2 ι∈[α] )

b∈{0,1}

4: QK = QK ⊔ {(j, dj )} 5: Return (j, [Xj B]2 ) OTag(E, w, F)

b∈{0,1}

1: QT = QT ⊔ {(E, w, F)} 2: T = ([t0 ]2 , [t1 ]2 ) where

OChal(S, ω, R)

1: Let R = {R1 , . . . , Rℓ } 2: τ ←- Γ ([ℓ]) 3: QC = QC ∪ {(S, ω, Ri )i∈[ℓ] } 4: C = (([cȷ,0 ]1 , [cȷ,1 ]1 )ȷ∈[ℓ] ) s.t.

t0 ←- Z3k p

cj,0 ←- Zk p P ⊤ ⊤ cj,1 = ( N⊤ ι,ωι + XS + ZR

τ (j)

ι∈[α]

t0 = Br + BFi+1 rFi+1 for r, rFi+1 ←- Zk p P t1 = ( Nι,wι + XE + ZF )t0 ι∈[α]

)cj,0

⊤

+(RFα+u+i (w ∥ E ∥ F|i ))B⊥ t0

+B⊥ (RFα+u+i (ω ∥ S ∥ Rτ (j) |i )⊤ )cj,0

⊤ ⊤ +((ZFα+u+i (w ∥ E ∥ F|i )(B∗ + OFi (F|i )(B∗ 0) 1 ) ))t0

⊤ ⊤ +(B∗ + B∗ 0 ZFα+u+i (ω ∥ S ∥ Rτ (j) |i ) 1 OFα+u+i (ω ∥ S ∥ Rτ (j) |i ) )cj,0

⊤ ∗ ⊤ +(ZFα+u+i+1 (w ∥ E ∥ F|i+1 )(B∗ 0 ) +OFα+u+i (w ∥ E ∥ F|i )(B1 ) )t0

⊤ ⊤ +(B∗ + B∗ 0 ZFα+u+i+1 (ω ∥ S ∥ Rτ (j) |i+1 ) 1 OFα+u+i (ω ∥ S ∥ Rτ (j) |i ) )cj,0

⊤ +(ZFα+u+i+1 (w ∥ E ∥ F|i+1 )(B∗ 0 ) t0 ⊤ +OFα+u+i+1 (w ∥ E ∥ F|i+1 )(B∗ 1 ) )t0

⊤ +(B∗ 0 ZFα+u+i+1 (ω ∥ S ∥ Rτ (j) |i+1 ) cj,0

t1 ←- Zk p

⊤ +B∗ 1 OFα+u+i+1 (ω ∥ S ∥ Rτ (j) |i+1 ) )cj,0

3: Return T cj,1 ←- Z3k p

Finalize(b ∈ {0, 1})

5: Return C

1: Return b ∧ (QT ∩ QC = ∅) ∧ (∀ (u, _) ∈ QCr , (u, _, _), (_, _, u) ∈ / QT ∪QC )

OCor(j)

1: QCr = QCr ⊔ {(j, dj )} from QK 2: Return dj

Fig. 10 Hybrids for the transition from H4,α+u,1 to H6 .

( ′ ZFi+1 (ω|i+1 )=

′ ZFi (ω|i ) ′ f i (ω ′ ) ZFi (ω|i ) + ZF |i

′ if ωi+1 =0 , ′ if ωi+1 = 1

f i : {0, 1}i → Zk×k are independent random functions. for all (S′ , ω ′ , R′ ) ∈ QT ⊔ QC where ZF p We devise the reduction B next in Figure 11. B receives k|QC |-fold U2k,k -MDDH instance ([D]1 , [f1 ]1 , . . . , fk|QC | 1 ). It is easy to verify that, the OTag responses are same in both H2,i,3 and H2,i,4 . We analyze OChal responses is invertible which happens with overwhelming for the two games next. First we assume that D ∈ Zk×k p DK c 1 probability 1 − p−1 . Observe that Fc = where Rc is either Ok or uniformly random in Zk×k . p DKc + Rc 1 We assume that F c is invertible which happens with overwhelming probability 1 − p−1 . Thus, cȷ,0 = F c c′ȷ,0 are uniformly random quantities as both F c and c′ȷ,0 are uniformly random. Now we analyze cȷ,1 for all ȷ ∈ [ℓ] for all the challenge queries. 1. For ωi+1 = 0, the OChal responses are same in both H2,i,3 and H2,i,4 . 23

2. For ωi+1 = 1, cȷ,1 = (

b⊤ + Z b⊤ b⊤ + X N S R ι,ωι

∗

τ (j)

⊤

)cȷ,0 + B0 ZFi (ω|i ) cȷ,0

ι∈[α] ⊤

∗

′

+ B1 OFi (ω|i ) cȷ,0 + B0 F c cȷ,0 =(

b⊤ + Z b⊤ b⊤ + X N S R ι,ωι

∗

τ (j)

⊤

)cȷ,0 + B0 ZFi (ω|i ) cȷ,0

ι∈[α] ∗

⊤

−1

∗

′

∗

′

+ B1 OFi (ω|i ) cȷ,0 + B0 DD F c cȷ,0 + B0 Rc cȷ,0 X b⊤ b⊤ b⊤ + Z b⊤ + X )cȷ,0 + N cȷ,0 N i+1,ω R S ι,ωι

i+1

τ (j)

ι∈[α]\{i+1} ∗

+ B0 DD

−1

⊤

∗

cȷ,0 + (B0 ZFi (ω|i )

∗

⊤

∗

⊤

+ B1 OFi (ω|i ) )cȷ,0

∗ ′ + B0 Rc cȷ,0

⊤

Nι,ωι + XS + ZR

τ (j)

)cȷ,0 + B0 ZFi (ω|i ) cȷ,0

ι∈[α] ∗

−1

+ (B0 Rc F c

⊤

∗

+ B1 OFi (ω|i ) )cȷ,0

f i (ω|i ) = Rc F −1 and If Rc = Ok , B simulates H2,i,3 and if Rc is uniformly random, we implicitly set ZF c k|Q |-U2k,k -MDDH

simulate H2,i,4 . Thus, |AdvA2,i,3 (λ) − AdvA2,i,4 (λ)| ≤ AdvB,GC1

C |+2 (λ) + |Qp−1 .

Init(1λ ) OTag(E, w, F)

1: G ←- ABSGen(1λ ) 2: From k|QC |-fold U2k,k -MDDH instance,

1: QT = QT ⊔ {(E, w, F)} 2: T = ([t0 ]2 , [t1 ]2 ) where

define Fc = (f(c−1)k+1 || . . . ||fck ) ∈ Z2k×k p for c ∈ [|QC |] ∗ ∗ 3: B,B0 , B1 , B0 , B1 ←- U3k,k s.t. − (B, B0 , B1 ) generates Z3k p ∗ ⊥ − (B∗ 0 , B1 ) generates B ⊤ ∗ − B ⊤ B∗ 0 = O, B1 B0 = O ⊤ ∗ − B ⊤ B∗ 1 = O, B0 B1 = O b ι,b ←- Z(k)×(3k) 4: For (ι, b) ∈ [α] × {0, 1} : Nι,b = N p −⊤ ⊤ ⊤ b D (B∗ // Implicit: Ni+1,b = N 0) i+1,b + D 5: params = ([B]1 , [B]2 , [Nι,b B]2 ι∈[α] )

t0 = Br + Bwi+1 rwi+1 for r, rwi+1 ←- Zk p P ⊤ ⊤ + OFi (w|i )(B∗ t1 = ( Nι,wι + XE + ZF )t0 +((ZFi+1 (w|i+1 )(B∗ 0) 1 ) ))t0 ι∈[α]

P b bE + Z b F )t0 +((ZFi (w|i )(B∗ )⊤ + OFi (w|i )(B∗ )⊤ ))t0 Nι,wι + X 0 1 ι∈[α]

3: Return T OChal(S, ω, R)

1: Let R = {R1 , . . . , Rℓ } 2: τ ←- Γ ([ℓ]) 3: QC = QC ∪ {(S, ω, Rȷ )ȷ∈[ℓ] } 4: For all (S, Rτ (ȷ) ) ∈ {S} × R :

b∈{0,1}

OKey(j)

1: For (ι, b) ∈ [2u] × {0, 1}: Jj,ι,b ←- Z(k)×(3k) p b j = P2u b j = P u Jj,i,j , Z 2: X i=u+1 Jj,i,ji i=1 i b j , Zj = Z bj 3: Xj = X 4: dj = [Xj B]2 , [Zj B]2 5: QK = QK ⊔ {(j, dj )} 6: Return (j, [Xj B]2 )

5: If ωi+1 = 1: cȷ,1 = cȷ,1 + B∗0 F c c′ȷ,0 6: Return C = (([cȷ,0 ]1 , [cȷ,1 ]1 )ȷ∈[ℓ] )

OCor(j)

Finalize(b ∈ {0, 1})

1: QCr = QCr ⊔ {(j, dj )} from QK 2: Return dj

1: Return b ∧ (QT ∩ QC = ∅)∧ (∀(u, _) ∈ QCr , (u, _, _), (_, _, u) ∈ / QT ∪QC )

Let (S, ω|i ||_|| · · · ||_, Rτ (ȷ) ) be the cth entry of QC cȷ,0 = F c c′ȷ,0 for c′ȷ,0 ←- Zk p P b⊤ b⊤ + Z b⊤ cȷ,1 = ( N +X )cȷ,0 +((B∗ ZFi (ω|i )⊤ + B∗ OFi (ω|i )⊤ ))cȷ,0 ι∈[α]

ι,ωι

Rτ (ȷ)

Fig. 11 The reduction B in the proof of Lemma 10.

Proof of Lemma 11. To argue indistinguishability of H2,i,4 and H2,i,5 following the proof of Lemma 10. Here, we define ( ′ OFi+1 (ω|i+1 )=

′ OFi (ω|i ) ′ f i (ω ′ ) OFi (ω|i ) + OF |i

′ if ωi+1 =1 , ′ if ωi+1 = 0

f i : {0, 1}i → Zk×k are independent random functions. Rest of the for all (S′ , ω ′ , R′ ) ∈ QT ⊔ QC where OF p proof is same as proving indistinguishability of H2,i,3 and H2,i,4 with the roles of 0 and 1 swapped. Thus, k|Q |-U -MDDH H H C |+2 (λ) + |Qp−1 |AdvA2,i,4 (λ) − AdvA2,i,5 (λ)| ≤ AdvB,GC1 2k,k .

Proof of Lemma 12. Note that, we define H3,α,1 = H2,α,1 as a stepping stone to inject randomness into RFα (ω ′ ). Looking ahead, the goal is going to define RFα+i depending on the (α+i)-length bit string ω ′ ∥ S′|i and P P utlize Ei+1 to define t0 for any tag query on (E, _, _). Observe that, ( Nι,ωι′ + XS + ZRτ (j) ) = Nι,ωι′ + ι∈[α]

ι∈[α]

P2u Pu JS′ ,ι,S′ι + ι=u+1 JR′ ,ι,R′ι . Thus, to attain the goal mentioned above, we modify ι=1 JS′ ,ι,S′ι + RFα (ω ′ ) ι=1P u into ι=1 JS′ ,ι,S′ι + RFα+u(ω ′ ∥ S′ ) iteratively via H3,α,1 , . . . , H3,α+u,1 . Pu

Proof of Lemma 13. This proof is same as the proof of proof of Lemma 8 except that RFα+i takes a (α+i)-bit string an input ω ′ ∥ S′|i . Proof of Lemma 14. This proof is same as the proof of proof of Lemma 9 except that ZFα+i , OFα+i both take a (α + i)-bit string an input ω ′ ∥ S′|i . Proof of Lemma 15. This proof is same as the proof of proof of Lemma 10 except that ZFα+i+1 takes a (α + i + 1)-bit string an input ω ′ ∥ S′|i+1 and OFα+i takes a (α + i)-bit string an input ω ′ ∥ S′|i . Proof of Lemma 16. This proof is same as the proof of proof of Lemma 11 except that ZFα+i+1 , OFα+i+1 both take a (α + i + 1)-bit string an input ω ′ ∥ S′|i+1 . Proof of Lemma 17. Note that, we define H4,α+u,1 = H3,α+u,1 as a stepping stone to inject randomness into RFα+u(ω ′ ∥ S′ ). Looking ahead, the goal is going to define RFα+u+i depending on the (α + u + i)-length bit string ω ′ ∥ S′ ∥ R′|i and utlize Fi+1 to define t0 for any tag query on (_, _, F). As we already observed, P P Pu P2u ( Nι,ωι′ + XS + ZRτ (j) ) = Nι,ωι′ + ι=1 JS′ ,ι,S′ι + ι=u+1 JR′ ,ι,R′ι . Thus, to attain the goal mentioned ι∈[α]

ι∈[α]

P2u P2u above, we modify ι=u+1 JR′ ,ι,R′ι + RFα+u(ω ′ ∥ S′ ) into ι=u+1 JR′ ,ι,R′ι + RFα+2u(ω ′ ∥ S′ ∥ R′ ) iteratively via H4,α+u,1 , . . . , H4,α+2u,1 . Proof of Lemma 18. This proof is same as the proof of proof of Lemma 13 except that RFα+u+i takes a (α + u + i)-bit string an input ω ′ ∥ S′ ∥ R′|i . Proof of Lemma 19. This proof is same as the proof of proof of Lemma 14 except that ZFα+u+i , OFα+u+i both take a (α + u + i)-bit string an input ω ′ ∥ S′ ∥ R′|i . Proof of Lemma 20. This proof is same as the proof of proof of Lemma 15 except that ZFα+u+i+1 takes a (α + u + i + 1)-bit string an input ω ′ ∥ S′ ∥ R′|i+1 and OFα+u+i takes a (α + u + i)-bit string an input ω ′ ∥ S′ ∥ R′|i . Proof of Lemma 21. This proof is same as the proof of proof of Lemma 16 except that ZFα+u+i+1 , OFα+u+i+1 both take a (α + u + i + 1)-bit string an input ω ′ ∥ S′ ∥ R′|i+1 . Proof of Lemma 22. Firstly, in H4,L,5 , ω ′ ∥ S′ ∥ R′|L = ω ′ ∥ S′ ∥ R′ for (ω ′ , S′ , R′ ) ∈ {0, 1}L . Since QT ∩ QC = ∅, (S′ , ω ′ , R′ ) ∈ QT are not repeated anywhere else. Moreover, as per our restriction, OTag queries are distinct. Therefore, uniformly random RF(ω ′ ∥ S′ ∥ R′ ) ∈ Zk×2k is never repeated. This makes t1 for all (S′ , ω ′ , R′ ) ∈ QT p H4,L,5 uniformly random elements. Thus, Adv (λ) = AdvH5 (λ). 25

Proof of Lemma 23. We devise the reduction B next in Figure 12. B receives k|QC |-fold U3k,k -MDDH instance ([D]1 , [f1 ]1 , . . . , fk|QC | 1 ). OTag responses in both H5 and H6 are sampled uniformly at random. We analyze OChal responses for the is invertible which happens with overwhelming probability two games next. First we assume that D ∈ Zk×k p DK c 1 1 − p−1 where Rc is either O2k×k or uniformly random in Z2k×k . We . Observe that Fc = p DKc + Rc 1 assume that F c is invertible which happens with overwhelming probability 1 − p−1 . Thus, cȷ,0 = F c c′ȷ,0 are uniformly random quantities as both F c and c′ȷ,0 are uniformly random. Now we analyze cȷ,1 for all ȷ ∈ [ℓ] for all the challenge queries. cȷ,1 = (

b⊤ + X b⊤ + Z b⊤ N ι,ωι S R

⊥

τ (ȷ)

⊤

)cȷ,0 + B RFα+2u (ω ∥ S ∥ Rτ (ȷ) ) cȷ,0

ι∈[α] ′

⊥

+ B F c cȷ,0 X b⊤ + X b⊤ + Z b⊤ =( N ι,ωι

Rτ (ȷ) )cȷ,0 + B

⊥

⊤

RFα+2u (ω ∥ S ∥ Rτ (ȷ) ) cȷ,0

ι∈[α] ⊥

−1

′

⊥

′

+ B DD F c cȷ,0 + B Rc cȷ,0 X b⊤ + X b⊤ + Z b⊤ b⊤ N )cȷ,0 + (N =( ι,ωι

1,ω1 + B

Rτ (ȷ)

⊥

−1

)cȷ,0

ι∈[α]\{1} ⊥

⊤

⊥

−1

+ B RFα+2u (ω ∥ S ∥ Rτ (ȷ) ) cȷ,0 + B Rc F c cȷ,0 X ⊤ ⊤ ⊤ ⊥ ⊤ =( Nι,ωι + XS + ZR )cȷ,0 + B RFα+2u (ω ∥ S ∥ Rτ (ȷ) ) cȷ,0 τ (ȷ)

ι∈[α] ⊥

−1

+ B Rc F c cȷ,0

Init(1λ )

1: G ←- ABSGen(1λ ) 2: From k|QC |-fold U3k,k -MDDH instance,

OTag(E, w, F)

define Fc = (f(c−1)k+1 || . . . ||fck ) ∈ Z3k×k p for c ∈ [|QC |] ⊥ 3k×2k ⊥⊤ 3: B ←- U3k,k , B ←- Zp s.t. B B=O b ι,b ←- Z(k)×(3k) 4: For (ι, b) ∈ [α] × {0, 1} : Nι,b = N p

b 1,b + D−⊤ D⊤ (B∗ )⊤ Implicit: N1,b = N 0 5: params = ([B]1 , [B]2 , [Nι,b B]2 ι∈[α] ). b∈{0,1}

OKey(j)

1: For (ι, b) ∈ [α] × {0, 1}: J[j, ι, b] ←- Z(k)×(3k) p P2u ⊤ b ⊤ = P u J⊤ b⊤ 2: X j i=1 j,i,ji , Zj = i=u+1 Jj,i,ji b j , Zj = Z bj 3: Xj = X 4: dj = ( [Xj,ι,b B]2 , [Zj,ι,b B]2 ι∈[L] ) b∈{0,1}

5: QK = QK ⊔ {(j, dj )} 6: Return (j, [Xj B]2 ) OCor(j)

1: QCr = QCr ⊔ {(j, dj )} from QK 2: Return dj

1: QT = QT ⊔ {(E, w, F)} k 2: T = ([t0 ]2 , [t1 ]2 ) where t0 ←- Z3k p , t1 ←- Zp . 3: Return T OChal(S, ω, R)

1: Let R = {R1 , . . . , Rℓ } 2: τ ←- Γ ([ℓ]) 3: QC = QC ∪ {(S, ω, Rȷ )ȷ∈[ℓ] } 4: For all (S, Rτ (ȷ) ) ∈ {S} × R : Let (S, ω, Rτ (ȷ) ) be the cth entry of QC cȷ,0 = F c c′ȷ,0 for c′ȷ,0 ←- Zk p P b⊤ b⊤ + Z b⊤ cȷ,1 = ( N +X )cȷ,0 +B⊥ RFα+2u (ω ∥ S ∥ Rτ (ȷ) )⊤ cȷ,0 + B⊥ F c′ ι∈[α]

ι,ωι

Rτ (ȷ)

5: Return C = (([cȷ,0 ]1 , [cȷ,1 ]1 )ȷ∈[ℓ] ) Finalize(b ∈ {0, 1})

1: Return b ∧ (QT ∩ QC = ∅)∧ (∀(u, _) ∈ QCr , (u, _, _), (_, _, u) ∈ / QT ∪QC )

Fig. 12 The reduction B in the proof of Lemma 23.

c ȷ,0

Experimental Results

We implement baeks (Figure 5) in python 3.6.9 using the Charm 0.50 framework [3]. We use MNT224 curve for pairings as it is a Type-III curve in PBC and existing works [2] also use this for their implementation. Interestingly, [2] introduced the bil-Uk -MDDH assumption and we prove our construction secure under lat-Uk -MDDH assumption which is hard under bil-Uk -MDDH assumption. We have run our experiments on Virtualbox VM running Ubuntu 18.04 where the VM is allocated one processor and 4GB RAM (fixed by the Virtualbox Setting). Figure 13 then lists the number of various operations in G1 , G2 and GT for Setup, KeyGen, SrchEnc, TrapGen and Test. Note that, Setup is run only once by a trusted third party at the starting of the system, KeyGen is run by each user independently only once when they join. SrchEnc and TrapGen are respectively ciphertext generation and trapdoor generation algorithms which will be run by the users over and over. Test is another algorithm, that is run by the cloud server many times. It is only natural to aim for making SrchEnc, TrapGen and Test simple and efficient. Observe that, all the computations does not involve u and only Setup and SrchEnc computation varies with α = poly(λ) linearly. As k denotes security level (predecided), all other algorithms are extremely efficient. In our baeks, Test executes 2ℓ-many bilinear pairings to test a match between a ciphertext and a trapdoor, in the worst case. Setting ℓ = 1,we get a paeks, where Test executes only 2 bilinear pairings to test a match between a ciphertext and a trapdoor. G1 G2 GT Mul Exp Mul Exp Mul Pairing 2 2 2 Setup 6αk (2k − 1) (5 + 12αk)k 4αk (3k − 1) (5 + 12αk)k KeyGen 6k2 (2k − 1) 12k3 4k2 (3k − 1) 12k3 SrchEnc (3αk + 11k − 5)kℓ 5k2 ℓ TrapGen (2αk + 9k − 5)k 5k2 Test (5k − 2)ℓ 5kℓ 2

Fig. 13 Number of various operations in G1 , G2 and GT for Setup, KeyGen, SrchEnc, TrapGen and Test of baeks. Here, k denotes the security level (k > 1), |KW| = 2α , |U| = 2 u and receiver set size is upper-bounded by ℓ. To see computation cost of our PAEKS, one can set ℓ = 1.

Note that, lat-Uk -MDDH for security level k = 1 is an easy problem, and therefore we consider k = 2 in all our experiments. In our experiments, we consider U to be a list of numbers where we denote an arbitrary user as i ∈ U = {1, 2, . . . , 100}. Note that, each user runs KeyGen on their own, independently than the rest of the users. Therefore, in the experiment it is reasonable to fix a list of users U. We also consider different values of ℓ i.e. different sizes of receiver sets such as {1, 5, 10, 50, 100} Note that, for ℓ = 1, BAEKS becomes PAEKS. We also have considered different u from {128, 512} and different α from {128, 512}. Therefore, as a subproduct of this work, we also achieve a tightly secure PAEKS in the multi-users, multi-challenge settings with adaptive corruptions. We only present a small description of our performance in Figure 14. The PAEKS is already extremely comparably efficient with existing works and provide tight security. Our simple proof-of-concept BAEKS code running on virtualbox shows practicality of our protocol. Making tournament-wise parallel multiplication of group elements running on multiple cores will certainly make our protocol much more efficient.

Conclusion

This paper revamps existing BAEKS security models of [42,22] to consider ciphertext and trapdoor security from the lens of sender, receiver, and keyword privacy. We further propose a consistency definition for BAEKS. Following this, we propose a new statistically consistent construction of BAEKS which we prove to be secure in the standard model. More precisely, our novel BAEKS construction achieves adaptive f ull-cpa 27

α = 128 α = 512 u = 128 u = 512 u = 128 u = 512 S K S T T S K S T T S K S T T S K S T T E E R R E E E R R E E E R R E E E R R E T Y C A S T Y C A S T Y C A S T Y C A S U G H P T U G H P T U G H P T U G H P T P E E G P E E G P E E G P E E G N N E N N E N N E N N E C N C N C N C N 1 80.38 0.77 0.14 0.02 0.05 82.41 1.11 0.15 0.026 0.05 307.34 0.72 0.21 0.046 0.05 82.41 1.11 0.15 0.026 0.05 5 79.84 0.76 0.14 0.08 0.25 81.67 1.16 0.16 0.09 0.26 308.58 0.71 0.20 0.11 0.23 308.67 1.07 0.21 0.10 0.24 ℓ 10 79.56 0.76 0.14 0.16 0.48 87.84 1.13 0.14 0.18 0.36 289.22 0.75 0.21 0.18 0.33 307.25 1.05 0.20 0.19 0.46 50 80.58 0.75 0.14 0.82 2.44 81.48 1.14 0.14 0.81 2.48 318.98 0.73 0.20 0.81 2.38 307.40 1.07 0.21 0.82 2.34 100 47.89 0.43 0.08 1.08 2.46 47.75 0.63 0.08 1.09 2.45 237.31 0.43 0.12 1.09 2.47 207.47 0.63 0.12 1.1 2.43

Fig. 14 Average time (in seconds) taken by various algorithms of baeks (Section 4.1) for receiver set of size ℓ. For ℓ = 1, we present performance of our PAEKS.

security (in terms of both ciphertext and trapdoor) under the standard assumption (lateral) Matrix DiffieHellman (lat-Uk -MDDH). In terms of the ciphertext and key size, our scheme is a little less efficient than [42] but we achieve tight f ull-cpa security and can withstand adversary corrupting a few users. For future work, one might aim for a new construction that achieves more robust security in the presence of malicious adversaries making their own key pairs.

References 1. Abdalla, M., Bellare, M., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone-Lee, J., Neven, G., Paillier, P., Shi, H.: Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. Journal of Cryptology 21(3), 350–391 (Jul 2008). https://doi.org/10.1007/s00145-007-9006-6 2. Agrawal, S., Chase, M.: FAME: Fast attribute-based message encryption. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017. pp. 665–682. ACM Press (Oct / Nov 2017). https://doi.org/10. 1145/3133956.3134014 3. Akinyele, J.A., Garman, C., Miers, I., Pagano, M.W., Rushanan, M., Green, M., Rubin, A.D.: Charm: a framework for rapidly prototyping cryptosystems. vol. 3, pp. 111–128 (Jun 2013). https://doi.org/10.1007/ s13389-013-0057-3, https://doi.org/10.1007/s13389-013-0057-3 4. Attrapadung, N.: Dual system encryption framework in prime-order groups via computational pair encodings. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 591–623. Springer, Berlin, Heidelberg (Dec 2016). https://doi.org/10.1007/978-3-662-53890-6_20 5. Attrapadung, N., Furukawa, J., Imai, H.: Forward-secure and searchable broadcast encryption with short ciphertexts and private keys. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 161–177. Springer, Berlin, Heidelberg (Dec 2006). https://doi.org/10.1007/11935230_11 6. Baek, J., Safavi-Naini, R., Susilo, W.: Public key encryption with keyword search revisited. In: Computational Science and Its Applications – ICCSA 2008. LNTCS, vol. 5072, pp. 1249–1259. Springer Berlin Heidelberg, Berlin, Heidelberg (2008) 7. Bellare, M., Rogaway, P.: The exact security of digital signatures: How to sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT’96. LNCS, vol. 1070, pp. 399–416. Springer, Berlin, Heidelberg (May 1996). https: //doi.org/10.1007/3-540-68339-9_34 8. Blazy, O., Kiltz, E., Pan, J.: (Hierarchical) identity-based encryption from affine message authentication. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 408–425. Springer, Berlin, Heidelberg (Aug 2014). https://doi.org/10.1007/978-3-662-44371-2_23 9. Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443–459. Springer, Berlin, Heidelberg (Aug 2004). https://doi.org/ 10.1007/978-3-540-28628-8_27 10. Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Berlin, Heidelberg (May 2004). https://doi.org/10.1007/978-3-540-24676-3_30 11. Boneh, D., Gentry, C., Waters, B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 258–275. Springer, Berlin, Heidelberg (Aug 2005). https://doi.org/10.1007/11535218_16 12. Boneh, D., Waters, B.: Conjunctive, subset, and range queries on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535–554. Springer, Berlin, Heidelberg (Feb 2007). https://doi.org/10.1007/ 978-3-540-70936-7_29 13. Byun, J.W., Rhee, H.S., Park, H.A., Lee, D.H.: Off-line keyword guessing attacks on recent keyword search schemes over encrypted data. In: Jonker, W., Petković, M. (eds.) Secure Data Management. LNISA, vol. 4165, pp. 75–83. Springer Berlin Heidelberg, Berlin, Heidelberg (2006) 14. Chatterjee, S., Mukherjee, S.: Keyword search meets membership testing: Adaptive security from SXDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 21–43. Springer, Cham (Dec 2018). https://doi.org/10.1007/978-3-030-05378-9_2 15. Chen, J., Gay, R., Wee, H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 595–624. Springer, Berlin, Heidelberg (Apr 2015). https://doi.org/10.1007/978-3-662-46803-6_20 16. Cheng, L., Meng, F.: Security analysis of pan et al.’s “public-key authenticated encryption with keyword search achieving both multi-ciphertext and multi-trapdoor indistinguishability”. Journal of Systems Architecture 119, 102248 (2021). https://doi.org/https://doi.org/10.1016/j.sysarc.2021.102248, https://www. sciencedirect.com/science/article/pii/S1383762121001703 17. Cheng, L., Meng, F.: Public key authenticated encryption with keyword search from LWE. In: Atluri, V., Di Pietro, R., Jensen, C.D., Meng, W. (eds.) ESORICS 2022, Part I. LNCS, vol. 13554, pp. 303–324. Springer, Cham (Sep 2022). https://doi.org/10.1007/978-3-031-17140-6_15 18. Cheng, L., Meng, F.: Server-aided public key authenticated searchable encryption with constant ciphertext and constant trapdoor. IEEE Transactions on Information Forensics and Security 19, 1388–1400 (2024). https: //doi.org/10.1109/TIFS.2023.3336160

19. Cheng, L., Qin, J., Feng, F., Meng, F.: Security-enhanced public-key authenticated searchable encryption. Information Sciences 647, 119454 (2023). https://doi.org/https://doi.org/10.1016/j.ins.2023.119454, https://www.sciencedirect.com/science/article/pii/S0020025523010393 20. Chi, T., Qin, B., Zheng, D.: An efficient searchable public-key authenticated encryption for cloud-assisted medical internet of things. Wireless Communications and Mobile Computing 2020, 8816172 (Jul 2020). https://doi. org/10.1155/2020/8816172, https://doi.org/10.1155/2020/8816172 21. Emura, K.: Generic construction of public-key authenticated encryption with keyword search revisited: Stronger security and efficient construction (retrieved on 25.05.2024). In: ASIA Public-Key Cryptography Workshop. p. 39–49. APKC ’22, Association for Computing Machinery, New York, NY, USA (2022). https://doi.org/10. 1145/3494105.3526237 22. Emura, K.: Generic construction of fully anonymous broadcast authenticated encryption with keyword search with adaptive corruptions (retrieved on 24.05.2024). IET Information Security 2023(1) (nov 2023). https:// doi.org/10.1049/2023/9922828, https://doi.org/10.1049/2023/9922828 23. Emura, K.: Generic construction of public-key authenticated encryption with keyword search revisited. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 107(3), 260–274 (2024) 24. Emura, K., Miyaji, A., Rahman, M.S., Omote, K.: Generic constructions of secure-channel free searchable encryption with adaptive security. Security and Communication Network 8(8), 1547–1560 (may 2015). https: //doi.org/10.1002/sec.1103, https://doi.org/10.1002/sec.1103 25. Escala, A., Herold, G., Kiltz, E., Ràfols, C., Villar, J.L.: An algebraic framework for Diffie-Hellman assumptions. Journal of Cryptology 30(1), 242–288 (Jan 2017). https://doi.org/10.1007/s00145-015-9220-6 26. Fang, L., Susilo, W., Ge, C., Wang, J.: A secure channel free public key encryption with keyword search scheme without random oracle. In: Cryptology and Network Security. LNSC, vol. 5888, pp. 248–258. Springer Berlin Heidelberg, Berlin, Heidelberg (2009) 27. Gay, R., Hofheinz, D., Kiltz, E., Wee, H.: Tightly CCA-secure encryption without pairings. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 1–27. Springer, Berlin, Heidelberg (May 2016). https://doi.org/10.1007/978-3-662-49890-3_1 28. Hofheinz, D., Jager, T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 590–607. Springer, Berlin, Heidelberg (Aug 2012). https://doi. org/10.1007/978-3-642-32009-5_35 29. Hofheinz, D., Jia, D., Pan, J.: Identity-based encryption tightly secure under chosen-ciphertext attacks. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 190–220. Springer, Cham (Dec 2018). https://doi.org/10.1007/978-3-030-03329-3_7 30. Huang, Q., Li, H.: An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks. Information Sciences 403-404, 1–14 (2017). https://doi.org/https://doi.org/10.1016/j.ins.2017. 03.038, https://www.sciencedirect.com/science/article/pii/S0020025516321090 31. Langrehr, R., Pan, J.: Tightly secure hierarchical identity-based encryption. In: Lin, D., Sako, K. (eds.) PKC 2019, Part I. LNCS, vol. 11442, pp. 436–465. Springer, Cham (Apr 2019). https://doi.org/10.1007/ 978-3-030-17253-4_15 32. Langrehr, R., Pan, J.: Hierarchical identity-based encryption with tight multi-challenge security. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part I. LNCS, vol. 12110, pp. 153–183. Springer, Cham (May 2020). https://doi.org/10.1007/978-3-030-45374-9_6 33. Li, H., Huang, Q., Huang, J., Susilo, W.: Public-key authenticated encryption with keyword search supporting constant trapdoor generation and fast search. IEEE Transactions on Information Forensics and Security 18, 396–410 (2023). https://doi.org/10.1109/TIFS.2022.3224308 34. Li, H., Huang, Q., Huang, J., Susilo, W.: Public-key authenticated encryption with keyword search supporting constant trapdoor generation and fast search. IEEE Transactions on Information Forensics and Security 18, 396–410 (2023), https://api.semanticscholar.org/CorpusID:253913825 35. Li, J., Gong, J.: Improved anonymous broadcast encryptions - tight security and shorter ciphertext. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 497–515. Springer, Cham (Jul 2018). https: //doi.org/10.1007/978-3-319-93387-0_26 36. Li, Q., Boyen, X.: Public-key authenticated encryption with keyword search made easy. CiC 1(2), 16 (2024). https://doi.org/10.62056/a63z11zn4 37. Libert, B., Paterson, K.G., Quaglia, E.A.: Anonymous broadcast encryption: Adaptive security and efficient constructions in the standard model. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 206–224. Springer, Berlin, Heidelberg (May 2012). https://doi.org/10.1007/978-3-642-30057-8_13 38. Ling, Y., Zhang, K., Chen, J., Huang, Q., Qian, H.: Public-key encryption with keyword search in multi-user, multi-challenge setting under adaptive corruptions. In: Tang, Q., Teague, V. (eds.) PKC 2024, Part II. LNCS, vol. 14604, pp. 105–126. Springer, Cham (Apr 2024). https://doi.org/10.1007/978-3-031-57728-4_4

39. Liu, X., He, K., Yang, G., Susilo, W., Tonien, J., Huang, Q.: Broadcast authenticated encryption with keyword search. In: Baek, J., Ruj, S. (eds.) ACISP 21. LNCS, vol. 13083, pp. 193–213. Springer, Cham (Dec 2021). https://doi.org/10.1007/978-3-030-90567-5_10 40. Liu, Z.Y., Tseng, Y.F., Tso, R., Mambo, M., Chen, Y.C.: Public-key authenticated encryption with keyword search: Cryptanalysis, enhanced security, and quantum-resistant instantiation. In: Suga, Y., Sakurai, K., Ding, X., Sako, K. (eds.) ASIACCS 22. pp. 423–436. ACM Press (May / Jun 2022). https://doi.org/10.1145/ 3488932.3497760 41. Lu, Y., Li, J.: Lightweight public key authenticated encryption with keyword search against adaptively-chosentargets adversaries for mobile devices. IEEE Transactions on Mobile Computing 21(12), 4397–4409 (2022). https: //doi.org/10.1109/TMC.2021.3077508 42. Mukherjee, S.: Statistically consistent broadcast authenticated encryption with keyword search - adaptive security from standard assumptions. In: Simpson, L., Baee, M.A.R. (eds.) ACISP 23. LNCS, vol. 13915, pp. 523–552. Springer, Cham (Jul 2023). https://doi.org/10.1007/978-3-031-35486-1_23 43. Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS. pp. 458–467. IEEE Computer Society Press (Oct 1997). https://doi.org/10.1109/SFCS.1997.646134 44. Pan, X., Li, F.: Public-key authenticated encryption with keyword search achieving both multi-ciphertext and multi-trapdoor indistinguishability. Journal of Systems Architecture 115, 102075 (2021). https://doi.org/ https://doi.org/10.1016/j.sysarc.2021.102075, https://www.sciencedirect.com/science/article/pii/ S1383762121000643 45. Pan, X., Li, F.: Public-key authenticated encryption with keyword search achieving both multi-ciphertext and multi-trapdoor indistinguishability. Journal of Systems Architecture 115, 102075 (2021). https://doi.org/ https://doi.org/10.1016/j.sysarc.2021.102075, https://www.sciencedirect.com/science/article/pii/ S1383762121000643 46. Qin, B., Chen, Y., Huang, Q., Liu, X., Zheng, D.: Public-key authenticated encryption with keyword search revisited: Security model and constructions. Information Sciences 516, 515–528 (2020). https://doi.org/https://doi.org/10.1016/j.ins.2019.12.063, https://www.sciencedirect.com/ science/article/pii/S0020025519311752 47. Qin, B., Cui, H., Zheng, X., Zheng, D.: Improved security model for public-key authenticated encryption with keyword search. In: Huang, Q., Yu, Y. (eds.) ProvSec 2021. LNCS, vol. 13059, pp. 19–38. Springer, Cham (Nov 2021). https://doi.org/10.1007/978-3-030-90402-9_2 48. Shen, E., Shi, E., Waters, B.: Predicate privacy in encryption systems. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 457–473. Springer, Berlin, Heidelberg (Mar 2009). https://doi.org/10.1007/ 978-3-642-00457-5_27 49. Waters, B.: Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619–636. Springer, Berlin, Heidelberg (Aug 2009). https://doi. org/10.1007/978-3-642-03356-8_36 50. Wee, H.: Functional encryption for quadratic functions from k-lin, revisited. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part I. LNCS, vol. 12550, pp. 210–228. Springer, Cham (Nov 2020). https://doi.org/10.1007/ 978-3-030-64375-1_8 51. Yao, L., Weng, J., Yang, A., Liang, X., Wu, Z., Jiang, Z., Hou, L.: Scalable cca-secure public-key authenticated encryption with keyword search from ideal lattices in cloud computing. Information Sciences 624, 777– 795 (2023). https://doi.org/https://doi.org/10.1016/j.ins.2022.12.035, https://www.sciencedirect. com/science/article/pii/S0020025522015304 52. Yao, L., Weng, J., Yang, A., Liang, X., Wu, Z., Jiang, Z., Hou, L.: Scalable cca-secure public-key authenticated encryption with keyword search from ideal lattices in cloud computing. Information Sciences 624, 777– 795 (2023). https://doi.org/https://doi.org/10.1016/j.ins.2022.12.035, https://www.sciencedirect. com/science/article/pii/S0020025522015304 53. Yau, W.C., Heng, S.H., Goi, B.M.: Off-line keyword guessing attacks on recent public key encryption with keyword search schemes. In: Rong, C., Jaatun, M.G., Sandnes, F.E., Yang, L.T., Ma, J. (eds.) Autonomic and Trusted Computing. LNPSE, vol. 5060, pp. 100–105. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)

Comments on Security Proof of Ling et al.’s PEKS

Ling et al. [38] proposed two multi-user PEKS constructions. We informally recall important parts of their constructions next. 31

1. Construction-I: Params. pp = (G, g1 ∈ GN , h1 ∈ HN ) where G = (N = p1 p2 , GN , HN , GT , e) where order(g1 ) = order(h1 ) = p1 Key-Pair. pkj = (g1x , g1y , e(g1 , h1 )α ), skj = (x, y, α) ←- Z3N . (xω+y)r

Ciphertext. U = g1r , V = g1 , W = δ · e(g1 , h1 )αr , δ for r ←- ZN , δ ←- GT . α+s(xw+y) s Trapdoor. A = h1 , B = h1 for s ←- ZN . ?

Test. e(U,B) e(V,A) · δ = W . 2. Construction-II: Params. pp = (G, g1 ∈ GN , h1 ∈ HN ) where G = (N = p1 p2 , GN , HN , GT , e) where order(g1 ) = order(h1 ) = p1 Key-Pair. pkj = (g1x , e(g1 , h1 )α ), skj = (x, α) ←- Z3N . Ciphertext. Trapdoor.

(x+ω)r

V = g1

α x+w

A = h1

, W = δ · e(g1 , h1 )αr , δ for r ←- ZN , δ ←- GT .

Test. e(V, A) · δ = W . Ling et al. [38] claimed both these schemes are PEKS in the multi-user, multi-ciphertext setting and have provided two proofs. Both the proofs define three types of ciphertexts – (i) type-0, (ii) type-1 and (iii) type-2. Both the proofs are three steps where, – G0 ≈ G1 : First, they replace g1r (in type-0 ciphertext) with g1r g2r̂ (and make the ciphertexts type-1) by means of subgroup decision assumption. – G1 ≈ G2 : Then, they use DDH on G2 to inject randomness in V (and make the ciphertexts type-2). Random self-reducibility of DDH allows them to modify all challenge V . (xω+y)r ẑ – G2 is information-theoretic secure: Finally, they argue that type-2 ciphertext V = g1 g2 in the G2 space has sufficient entropy to hide all the hashes involving different keywords ω. Our Observations. Both these constructions use well-known structures Boneh-Boyen hash where the first Construction uses the affine hash, whereas the second construction uses exponent inversion-based hash [9]. To the best of our knowledge, none of these hashes are known to be tightly secure for multi-challenge setting. A critical analysis of the proof shows that, the final step where [38] has claimed to have sufficient entropy does not really hold. To see this, let us assume a simpler situation where an adversary has received a challenge ciphertext on ω b ∈ {ω0 , ω1 }. Consider the adversary makes a trapdoor query on w ̸= ω. Since the trapdoor responses are normal (without any G2 ) component, pairing A (of trapdoor) with V removes entropy due to G2 . One can easily check the effect of the following two pairings e(V, A) where V is type-0 and e(V, A) when V is a type-2 ciphertext. Therefore, G2 is not information theoretically secure. Therefore, the proofs are incomplete. Moreover, [38] did not argue consistency which is a definitive characteristic of PEKS.

Differences in Security Notions

B.1

Unforgeability of Ciphertexts and Trapdoors.

A BAEKS scheme baeks satisfies ciphertext unforgeability ct-cma if for all ppt adversary A, the advantage of A is Advct-cma A,baeks (λ) = neg(λ) where A’s advantage is defined in Figure 15 provided A is given access to following oracles: – OCt is an oracle that on input (pkS , ω, pkR ) outputs Encrypt(pp, skS , ω, pkR ). It maintains a list QCt of (pkS , ω, pkR ) for all R ∈ R queried. – OTr is an oracle that on input (pkE , w, pkF ) outputs TrapGen(pp, pkE , w, skF ). – Osk is an oracle that on input j outputs (skj , pkj ) ← KeyGen(pp, j) after storing (j, skj , pkj ) in Qsk . – Opk is an oracle that on input j outputs pkj where (skj , pkj ) ← KeyGen(pp, j). 32



Advct-cma A,baeks (λ) =

 λ ∗ pp ← Setup(1 , ℓ), Qsk , QCt ← ∅ Test(Tr, Ct ) = 1   ∗ ∗ ∗ O (·,·,·),OTr (·,·,·),Osk (·),Opk (·) / Qsk Pr  (pkS∗ , ω , pkR∗ , Ct ) ← A Ct (pp)   ∧ (S , _, _) ∈  ∗ ∗ ∗ ∗ ∧ (pkS∗ , ω , pkR∗ ) ∈ / QCt ∃R ∈ R s.t.Tr ← TrapGen(pkS∗ , ω , skR∗ ) 

Test(Tr∗ , Ct) = 1 Advtrap-cma (λ) = Pr  A,baeks  ∧ (F∗ , _, _) ∈ /Q

pp ← Setup(1 ), Qsk ← ∅ ∗

∗

(pkE∗ , ω̃ , pkF∗ , Tr ) ← A

OCt (·,·,·),OTr (·,·,·),Osk (·),Opk (·)

∗

  (pp)  

Ct ← SrchEnc(skE∗ , ω̃ , pkF∗ )

Fig. 15 Unforgeability of Ciphertexts and Trapdoors

A BAEKS scheme baeks satisfies trapdoor unforgeability trap-cma if for all ppt adversary A, the advantage of A is Advtrap-cma A,baeks (λ) = neg(λ) which is defined in Figure 15 provided A is given access to following oracles: – OCt is an oracle that on input (pkS , ω, pkR ) outputs Encrypt(pp, skS , ω, pkR ). It maintains a list QCt of (pkS , ω, pkR ) for all R ∈ R queried. – OTr is an oracle that on input (pkE , w, pkF ) outputs TrapGen(pp, pkE , w, skF ). – Osk is an oracle that on input j outputs (skj , pkj ) ← KeyGen(pp, j) after storing (j, skj , pkj ) in Qsk . – Opk is an oracle that on input j outputs pkj where (skj , pkj ) ← KeyGen(pp, j). Now we argue that if a BAEKS scheme is f ull-cpa secure, then it is both ct-cma and trap-cma secure. We argue this in two steps. First we show that, given a ppt adversary that breaks ct-cma of a BAEKS construction, we can construct another ppt adversary that breaks f ull-cpa of the BAEKS construction. Consider C is the f ull-cpa challenger and A the ct-cma adversary. – Setup: C gives out pp that B forwards to A. – Query Phase-: When A makes oracle queries on OCt or OTr or Osk , B forwards it to the corresponding oracles modeled by C. B forwards the responses to A. Note that, B forwards A’s query on OCt or OTr by putting them on both the sides of the challenge tuple. B maintains a list QCt which memorizes (pkS , ω, pkR ) for all R ∈ R when A makes OCt queries on (pkS , ω, pkR ). – Forge: At some point of time, A produces a forgery (pkS∗ , ω ∗ , pkR∗ , Ct∗ ) s.t. ∃R∗ ∈ R∗ for which Test(TrapGen(pkS∗ , ω ∗ , skR∗ ), Ct∗ ) = 1 subject to the restriction (pkS∗ , ω ∗ , pkR∗ ) is not in QCt and no secret key query has been made on S∗ . 1. B makes a OTr query on ((pkS∗ , ω ∗ , pkR∗ ), (pkE , ω ∗ , pkR∗ )) where E ̸= S∗ s.t. (pkE , ω ∗ , pkR∗ ) is not in QCt . 2. C responds with Tr∗b for its choice of b ∈ {L, R} (symbolic of "Left" and "Right"). 3. B runs Test(Tr∗ , Ct∗ ). If it is 1, B outputs its guess b′ = L; otherwise outputs b′ = R. As (pkS∗ , ω ∗ , pkR∗ ), (pkE , ω ∗ , pkR∗ ) ∈ / QCt , B is allowed to make the challenge OTr query. If Tr∗b encoded ∗ (pkS∗ , ω , pkR∗ ), the correctness of BAEKS ensures Test outputs 1 and B correctly guesses L. If Tr∗b encoded (pkE , ω ∗ , pkR∗ ), the consistency of BAEKS will ensure Test outputs 0 (and B correctly guesses R) except with negligible probability. It is easy to see that f ull-cpa security of a BAEKS scheme would also ensure trap-cma security of the BAEKS scheme following a reduction very similar to the above.

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

Analyze & explore related research in Conceptio

Related documents