Michel Abdalla
email: michel.abdalla@ens.fr

Junqing Gong
email: jqgong@sei.ecnu.edu.cn

Hoeteck Wee
email: wee@di.ens.fr

Functional Encryption for Attribute-Weighted Sums from k-Lin

Keywords: §1. Introduction, 1 §2. Technical Overview, 6 §3. Preliminaries, 10 §4. Definitions and Tools, 11 §5. Π Unbounded-Slot Scheme, 21 §8

We present functional encryption schemes for attribute-weighted sums, where encryption takes as input N attribute-value pairs (x i , z i ) where x i is public and z i is private; secret keys are associated with arithmetic branching programs f , and decryption returns the weighted sum N i =1 f (x i )z i while leaking no additional information about the z i 's. Our main construction achieves (1) compact public parameters and key sizes that are independent of N and the secret key can decrypt a ciphertext for any a-priori unbounded N ;

(2) short ciphertexts that grow with N and the size of z i but not x i ;

(3) simulation-based security against unbounded collusions; (4) relies on the standard k-linear assumption in prime-order bilinear groups.

Introduction

In this work, we consider the problem of computing aggregate statistics on encrypted databases. Consider a database of N attribute-value pairs (x i , z i ) i =1,..., N , where x i is a public attribute of user i (e.g. demographic data), and z i is private sensitive data associated with user i (e.g. salary, medical condition, loans, college admissions outcome). Given a function f , we want to privately compute weighted sums over the z i 's corresponding to

N i =1 f (x i )z i
We refer to this quantity as an attribute-weighted sum. An important special case is when f is a boolean predicate, so that the attribute-weighted sum

N i =1 f (x i )z i = i : f (x i )=1 z i
(1) corresponds to the average z i over all users whose attribute x i satisfies the predicate f . Concrete examples include average salaries of minority groups holding a particular job title (z i = salary) and approval ratings of an election candidate amongst specific demographic groups in a particular state (z i = rating). Similarly, if z i is boolean, then the attributeweighted sum becomes i :z i =1 f (x i ). This could capture for instance the number of and average age of smokers with lung cancer (z i = lung cancer).

This work. We study functional encryption (FE) schemes for attribute-weighted sums [START_REF] Sahai | Fuzzy identity-based encryption[END_REF][START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF][START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF][START_REF] Gorbunov | Predicate encryption for circuits from LWE[END_REF], for a more general setting where the attribute-value pairs and the output of f are vectors. That is, we would like to encrypt N attributevalue pairs (x i , z i ) i =1,...,N to produce a ciphertext ct, and generate secret keys sk f so that decrypting ct with sk f returns the attribute-weighted sum i f (x i ) z i while leaking no additional information about the individual z i 's. We want to support rich and expressive functions f , such as boolean formula and simple arithmetic computation. In addition, we want simulation-based security against collusions, so that an adversary holding secret keys for different functions learns nothing about the z i 's beyond the attribute-weighted sums for all of these functions. As articulated [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF],

simulation-based security is the right notion for functional encryption applied to real-world data.

In many databases, it is often the case that the size of each attribute-value pair (x i , z i ) is small and a-priori bounded, whereas the number of slots N is large and a-priori unbounded. This motivates the notion of an unbounded-slot FE scheme for attribute-weighted sums, where a secret key sk f can decrypt encrypted databases with an arbitrary number of slots. Indeed, handling arbitrary-sized inputs is also the motivation behind studying ABE and FE schemes for DFA and NFA [START_REF] Waters | Functional encryption for regular languages[END_REF][START_REF] Agrawal | Attribute based encryption (and more) for nondeterministic finite automata from LWE[END_REF]. In an unbounded-slot FE, key generation and the size of sk f depends only on f and not N . This provides stronger flexibility than standard ABE and FE (even in the so-called unbounded setting [START_REF] Lewko | Unbounded HIBE and attribute-based encryption[END_REF][START_REF] Brakerski | Circuit-ABE from LWE: Unbounded attributes and semi-adaptive security[END_REF][START_REF] Goyal | Semi-adaptive security and bundling functionalities made generic and easy[END_REF]21]), where each sk f only works for a fixed N . In practice, this means that we can reuse the same set-up and secret keys across multiple databases without an a-priori upper bound on the database size N .

Our Results

We present an unbounded-slot functional encryption scheme for attribute-weighted sums for the class of functions f captured by arithmetic branching programs (ABP), a powerful model of computation that captures both boolean formula and branching programs with only a linear blow-up in size. Our construction achieves:

(1) compact public parameters and key sizes that are independent of N ;

(2) short ciphertexts that grow with N and the size of z i but not x i ;

(3) selective 4 , simulation-based security against unbounded collusions; (4) relies on the standard k-linear assumption in prime-order bilinear groups.

As with all prior FE schemes that rely on DDH and bilinear groups [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF][START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF][START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF][START_REF] Lin | Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs[END_REF][START_REF] Baltico | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF][START_REF] Jain | How to leverage hardness of constant-degree expanding polynomials overa R to build i O[END_REF][START_REF] Jain | Simplifying constructions and assumptions for i O[END_REF][START_REF] Chen | Practical attribute based inner product functional encryption from simple assumptions[END_REF], efficient decryption requires that the output of the computation N i =1 f (x i ) z i lies in a polynomial-size domain. We also show how to extend our unbounded-slot scheme to a setting where the database is distributed across multiple clients that do not completely trust one another [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF], assuming some simple non-interactive MPC set-up amongst the clients that does not depend on the database and does not require interaction with the key authority.

Prior works. While we regard the unbounded-slot setting as the key conceptual and technical novelty of this work, we note that FE for attribute-weighted sums for N = 1 already captures many functionalities considered in the literature, e.g. (i) FE for inner product [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF][START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF] where f outputs a fixed vector, (ii) attribute-based encryption (ABE) by taking z to be the payload, (iii) attribute-based inner-product FE [START_REF] Chen | Practical attribute based inner product functional encryption from simple assumptions[END_REF][START_REF] Abdalla | Inner-product functional encryption with fine-grained access control[END_REF], where ciphertexts are associated with a public x and a private z, and keys with a boolean formula g and a vector y, and decryption returns z y iff g (x) = 1, by taking f (x) := y • g (x), which can be computed using an ABP.

On the other hand, none of these three classes captures the special case of attribute-weighted sums in [START_REF] Abdalla | From single-input to multi-client inner-product functional encryption[END_REF]. We show a comparison in Fig 1 . The more recent works in [START_REF] Jain | How to leverage hardness of constant-degree expanding polynomials overa R to build i O[END_REF][START_REF] Jain | Simplifying constructions and assumptions for i O[END_REF] do capture a larger class supporting quadratic instead of linear functions over z, 5 but in a weaker secret-key setting, which is nonetheless sufficient for the application to obfuscation. Finally, none of these works consider the unbounded-slot setting.

Our construction

We present a high-level overview of our unbounded-slot FE scheme for attribute-weighted sums. We start with a oneslot scheme that only handles N = 1, and then "bootstrap" to the unbounded-slot setting. The main technical novelty of this work lies in the bootstrapping, which is what we would focus on in this section.

A one-slot scheme. In a one-slot FE scheme, we want to encrypt (x, z) and generate secret keys sk f for computing f (x) z, while leaking no additional information about z. We adopt the framework of Wee's [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] (which in turn builds on [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF][START_REF] Waters | Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions[END_REF][START_REF] Wee | Dual system encryption via predicate encodings[END_REF][START_REF] Ishai | Partial garbling schemes and their applications[END_REF]) that builds a FE scheme for a closely related functionality f (x) z ? = 0; the construction also achieves selective, simulation-based security under the k-Lin assumption in prime-order bilinear groups. We achieve a smaller ciphertext, and an algebraically more concise and precise description. Our simulator also embeds the output of the ideal functionality f (x) z into the simulated sk f . This is in some sense inherent for two reasons: (i) the ciphertext has a fixed size and cannot accommodate an a-priori unbounded number of key queries [START_REF] Agrawal | Functional encryption: New perspectives and lower bounds[END_REF], (ii) in the selective setting, we do not know f or f (x) z while simulating the ciphertext.

The unbounded-slot scheme. A very natural approach is to use the one-slot scheme to compute

f (x i ) z i , i = 1, 2, . . . , N (2)
by providing N independent encryptions ct x i ,z i of (x i , z i ). The secret key is exactly that for the one-slot scheme and therefore independent of N , and decryption proceeds by decrypting each of the N one-slot ciphertexts, and then computing their sum. The only problem with this approach is that it is insecure since decryption leaks the intermediate summands.

First idea. To avoid this leakage, we would computationally mask the summands using DDH tuples, by using the one-slot scheme to compute [ f (x i ) z i + w i r ], i = 1, 2, . . . , N

where the w i 's are sampled during encryption subject to the constraint N i =1 w i = 0; r is fresh per secret key; and - [•] denotes "in the exponent" of a bilinear group.

Multiplying the partial decryptions yields [ i f (x i ) z i ], and we need to perform a brute-force discrete log to recover the answer. Indeed, we can modify the one-slot scheme to support the functionality in [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF], where the one-slot encryption takes as input (x i , z i w i ) (where w i is also private) to produce a ciphertext ct x i ,z i w i , and with secret keys sk f ,r associated with ( f , r ). Henceforth, we describe the proof strategy for a single secret key query for simplicity, but everything we describe extends quite readily to an unbounded number of key queries.

The intuition is that the partial decryptions now yield

( Dec(sk f ,r , ct x 1 ,z 1 w 1 ), Dec(sk f ,r , ct x 2 ,z 2 w 2 ), . . . , Dec(sk f ,r , ct x N ,z N w N ) ) = ( [ f (x 1 ) z 1 + w 1 r ], [ f (x 2 ) z 2 + w 2 r ], . . . , [ f (x N ) z N + w N r ] ), DDH ≈ c ( [ f (x 1 ) z 1 + w 1 ], [ f (x 2 ) z 2 + w 2 ], . . . , [ f (x N ) z N + w N ] ), w i = 0 ≈ s ( [ i f (x i ) z i + w 1 ], [w 2 ], . . . , [w N ] ),
As with the one-slot scheme, we need to embed these N partial descriptions into sk f ,r in the proof of security. Translating this intuition into a proof would then require embedding ≈ N units of statistical entropy into the simulated sk f ,r in the final game; this means that the size of sk f ,r would grow with N , which we want to avoid!

= ( [ f (x 1 ) z 1 + w 1 r ], [ f (x 2 ) z 2 + w 2 r ], [ f (x 3 ) z 3 + w 3 r ] ) DDH ≈ c ( [ f (x 1 ) z 1 + f (x 2 ) z 2 + w 1 r ], [w 2 r ], [ f (x 3 ) z 3 + w 3 r ] ) DDH ≈ c ( [ f (x 1 ) z 1 + f (x 2 ) z 2 + f (x 3 ) z 3 + w 1 r ], [w 2 r ], [w 3 r ] ) (4)
where the first DDH ≈ c uses pseudorandomness of ([w 2 r ], [r ]) and the second uses that of ([w 3 r ], [r ]).

Next, we need to design the ciphertext and key distributions for the unbounded-slot scheme so that partial decryption yields the quantities in [START_REF] Abdalla | Inner-product functional encryption with fine-grained access control[END_REF]. We begin by defining the final simulated ciphertext-key pair as follows:

(ct * x 1 , ct x 2 ,0 w 2 , . . . , ct x N ,0 w N ), sk * f ,r (5)
where

-(ct * x 1 , sk * f ,r
) are obtained using the simulator for the one-slot scheme so that

Dec(sk * f ,r , ct * x 1 ) = [w 1 r + i f (x i ) z i ] That is, we embed [w 1 r + i f (x i ) z i ] into the simulated sk * f ,r ; -ct x i ,0 w i , i > 1 are generated as normal encryptions of (x i , 0 w i ) (instead of normal encryptions of (x i , z i w i )) so that Dec(sk * f ,r , ct x i ,0 w i ) = Dec(sk f ,r , ct x i ,0 w i ) = [w i r ], i > 1
Here, we use fact that simulated secret keys behave like normal secret keys when used to decrypt normal ciphertexts.

This distribution can be computed given just i f (x i ) z i and matches exactly what we need in the final game in (4).

Third idea. Now, consider the following attempt to interpolate between the normal distributions and the simulated distributions for the case N = 2:

( ct x 1 ,z 1 w 1 , ct x 2 ,z 2 w 2 , sk f ,r ) ≈ c ( ct * x 1 , ct x 2 ,z 2 w 2 , sk * f ,r ), Dec(sk * f ,r , ct * x 1 ) = [ f (x 1 ) z 1 + w 1 r ] ≈ c ( ct * x 1 , ???, sk * f ,r ), ≈ c ( ct * x 1 , ct x 2 ,0 w 2 , sk * f ,r ), Dec(sk * f ,r , ct * x 1 ) = [ f (x 1 ) z 1 + f (x 2 ) z 2 + w 1 r ]
where the first row is the real distribution, the last row is the simulated distribution in [START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF], and the first ≈ c follows from simulation-based security of the one-slot scheme. A natural idea is to replace "???" with a simulated ciphertext ct *

x 2 but this is problematic for two reasons: first, we cannot switch between a normal and simulated ciphertext in the presence of a simulated key, and second, the simulator can only generate a single simulated ciphertext.

Luckily, we can overcome both difficulties by modifying the unbounded-slot FE scheme to use two independent copies of the one-slot scheme as follows:

setup generates two one-slot master public-secret key pairs (mpk 1 , msk 1 ), (mpk 2 , msk 2 ); -to encrypt (x i , z i ) i =1,...,N , we generate ct x 1 ,z 1 w 1 w.r.t mpk 1 and the remaining ct x i ,z i w i , i = 2, . . . , N w.r.t. mpk 2 ; -the secret key contains two one-slot secret keys sk f ,r,1 , sk f ,r,2 generated for ( f , r ) but using msk 1 , msk 2 respectively.

Scheme

Enc KeyGen

Function Security |ct|

OT12, KSW08 [START_REF] Okamoto | Adaptively attribute-hiding (hierarchical) inner product encryption[END_REF][START_REF] Okamoto | Efficient (hierarchical) inner-product encryption tightly reduced from the decisional linear assumption[END_REF][START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF]] z y z y That would in fact be our final construction, where the asymmetry of encryption with respect to the first slot reflects the asymmetry of the simulated ciphertext in [START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF]. Note that the first issue goes away because we can switch between a normal and simulated ciphertext w.r.t. mpk 2 in the presence of a simulated secret key w.r.t. mpk 1 ; the second goes away because the two simulated ciphertext correspond to mpk 1 and mpk 2 respectively. We defer the remaining details to the technical overview in Section 2 and the formal scheme in Section 7.

? = 0 AD-IND O(|z|) ALS16, ABDP15 [3,8] z y z y AD-IND O(|z|) W17 [43] x, z f ABP z f (x) ? = 0 SA-SIM O(|x| + |z|) DOT18 [21] x, z f ABP z f (x) ? = 0 AD-SIM O(|x| + |z|) ACGU20, CZY19 [4,19] x, z y, f NC1 f (x) • z y AD-IND O(|x| + |z|) ACGU20 [4] z 1 , z 2 y 1 , y 2 z 1 y 1 if z 2 y 2 = 0 AD-IND O(|z 1 | + |z 2 |) This work ( §5) x, z f ABP z f (x) SA-SIM O(|z|)
The multi-client setting. Now, consider a setting where the database (x i , z i ) i =1,...,N are distributed across multiple clients that do not completely trust one another [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Chotard | Decentralized multi-client functional encryption for inner product[END_REF]; in practice, the clients could correspond to hospitals holding medical records for different patients, or colleges holding admissions data. It suffices to just consider the setting with N clients where client i holds (x i , z i ). Note that to produce the ciphertext in our unbounded-slot FE scheme, it suffices for the N clients to each hold a random private w i (per database) subject to the constraint w i = 0, which is simple to generate via a non-interactive MPC protocol where each client sends out additive shares of 0 [START_REF] Ben-Or | Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract)[END_REF]. Moreover, generating the w i 's can take place in an offline, pre-processing phase before knowing the database, and does not require interacting with the key generation authority. Moreover, our unbounded-slot FE scheme also achieves a meaningful notion of security, namely that if some subset S of clients collude and additionally learn some sk f , they will not learn anything about the remaining z i 's apart from i ∉S f (x i ) z i (that is, the attribute-weighted sum as applied to the honest clients' inputs); security is simulation-based and also extends to the many-key setting. In order to achieve this, we require a slight modification to the scheme to break the asymmetry with respect to the first slot: to encrypt (x i , z i ), client i samples random z i , w i and publishes a one-slot encryption of (x i , z i w i ) under mpk 1 and another of (x i , z -z i w i -w i ) under mpk 2 . This readily gives us a multi-client unbounded-slot FE for attribute-weighted sums;

we refer the reader to Section 8 for more details of the definition, construction and proof.

Discussion

Additional related works. As noted earlier in the introduction, our unbounded-slot notion is closely related to uniform models of computation with unbounded input lengths, such as ABE and FE for DFA and NFA [START_REF] Waters | Functional encryption for regular languages[END_REF][START_REF] Gong | ABE for DFA from k-lin[END_REF][START_REF] Agrawal | Attribute based encryption (and more) for nondeterministic finite automata from LWE[END_REF][START_REF] Agrawal | Attribute based encryption for deterministic finite automata from DLIN[END_REF]. At a very high level, our construction may be viewed as following the paradigm in [START_REF] Agrawal | Attribute based encryption (and more) for nondeterministic finite automata from LWE[END_REF][START_REF] Agrawal | Attribute based encryption for deterministic finite automata from DLIN[END_REF] for building ABE/FE for uniform models of computation by "stitching" together ABE/FE for the smaller step functions; in our setting, the linear relation between the step functions and the overall computation makes "stitching" much simpler. The way we use two copies of the one-slot scheme is also analogous to the "two-slot, interweaving dual system encryption" argument used in the previous ABE for DFA from k-Lin in [START_REF] Gong | ABE for DFA from k-lin[END_REF], except our implementation is simpler and more modular.

On selective vs adaptive security. We believe that selective, simulation-based security already constitutes a meaningful notion of security for many of the applications we have in mind. For instance, in medical studies, medical records and patient conditions (the x i , z i 's) will not depend -not in the short run, at least-adaptively on the correlations (the functions f 's) that researchers would like to investigate. Nonetheless, we do agree that extending our results to achieve adaptive security is an important research direction. Concretely, -Can we show that the one-slot scheme achieves simulation-based, adaptive security in the generic group model, as has been shown for a large class of selectively secure ABEs [START_REF] Ambrona | Attribute-based encryption in the generic group model: Automated proofs and new constructions[END_REF]?

-Can we construct an adaptively secure unbounded-slot FE for arithmetic branching programs with compact ciphertexts without the one-use restriction from k-Lin? We conjecture that our transformation from one-slot to unbounded-slot preserves adaptive security. Solving the one-slot problem would require first adapting the techniques for adaptive simulation-based security in [21,[START_REF] Agrawal | Adaptive simulation security for inner product functional encryption[END_REF], and more recent advances in [START_REF] Kowalczyk | Compact adaptively secure ABE for NC 1 from k-lin[END_REF] to avoid the one-use restriction.

Open problems. We conclude with two other open problems. One is whether we can construct (one-slot) FE for attribute-weighted sums from LWE, simultaneously generalizing prior ABE and IPFE schemes from LWE [START_REF] Gorbunov | Attribute-based encryption for circuits[END_REF][START_REF] Boneh | Fully keyhomomorphic encryption, arithmetic circuit ABE and compact garbled circuits[END_REF][START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF]; an affirmative solution would likely also avoid the polynomial-size domain limitation. Another is to achieve stronger notions of security for the multi-client setting where the w i 's could be reused across multiple databases.

Organization. We provide a more detailed technical overview in Section 2. We present preliminaries, definitions and tools in Sections 3 and 4. We present our one-slot scheme and an extension in Sections 5 and 6, and the unboundedslot scheme and the multi-client extension in Sections 7 and 8.

Technical Overview

We proceed with a more technical overview of our construction, building on the overview given in Section 1.2, and giving more details on the one-slot scheme. We summarize the parameters of the one-slot and unbounded-slot scheme in Fig 2.

One-slot scheme

Notation. We will make extensive use of tensor products. For instance, we will write the linear function

x 1 U 1 + x 2 U 2 as (U 1 U 2 ) x 1 I x 2 I = (U 1 U 2 ) x 1 x 2 ⊗ I
This allows us to concisely and precisely capture "compilers" where we substitute scalars with matrices, as well as the underlying linear relations, which may refer to left or right multiplication, and act on scalars or matrices.

Partial garbling.

Recall the starting point for ABE for ABP as an "arithmetic secret-sharing scheme" that on input an ABP f : Z n p → Z p and a secret z ∈ Z p , outputs m affine functions 1 , . . . , m : Z n p → Z p such that for all x ∈ Z n p :

-(correctness) given 1 (x), . . . , m (x) along with f , x, we can recover z if f (x) = 0.

-(privacy) given 1 (x), . . . , m (x) along with f , x, we learn nothing about z if f (x) = 0.

In particular, the coefficients of the functions 1 , . . . , m depends linearly on the randomness used in secret sharing.

Partial garbling generalizes the above as follows: on input an ABP f : Z n p → Z n p , outputs m + 1 affine functions 0 , 1 , . . . , m such that for all x ∈ Z n p , z ∈ Z n p :

-(correctness) given 0 (z), 1 (x), . . . , m (x) along with f , x, we can recover f (x) z.

-(privacy) given 0 (z), 1 (x), . . . , m (x) along with f , x, we learn nothing about z apart from f (x) z.

Henceforth, we will use t (L 1 (x ⊗ I m ) + L 0 ) ∈ Z m p to denote the m linear functions 1 (x), . . . , m (x), 6 where t ← Z m+n -1 p corresponds to the randomness used in the secret sharing; L 1 ∈ Z (m+n -1)×mn p , L 0 ∈ Z (m+n -1)×m p depends only on the function f , and m is linear in the size of the ABP f . Basic scheme. We rely on an asymmetric bilinear group (G 1 , G 2 , G T , e) of prime order p where e : [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF]. Our starting point is the following scheme 7 :

G 1 ×G 2 → G T . We use [•] 1 , [•] 2 , [•] T to denote component-wise exponentiations in respective groups G 1 , G 2 , G T
mpk = [w] 1 , [u] 1 , [v] 1 and msk = w, u, v (6) ct x,z = [s] 1 , [z + sw] 1 , [s(u x + v)] 1 ∈ G n +2 1 sk f = [t + w] 2 , [t L 1 + u (I n ⊗ r )] 2 , [t L 0 + vr ] 2 , [r] 2 where w ← Z n p , u ← Z n p , v ← Z p , t ← Z m+n -1 p , r ← Z m p
Decryption uses the fact that

t (L 1 (x ⊗ I m ) + L 0 ) = (t L 1 + u (I n ⊗ r )) • (x ⊗ I m ) + (t L 0 + vr ) -(u x + v) • r (7)
which in turn uses (I n ⊗ r ) • (x ⊗ I m ) = x • r . Using the pairing and the above relation, we can recover

[z -st] T , [st (L 1 (x ⊗ I m ) + L 0 )] T
We can then apply reconstruction "in the exponent" to recover [ f (x) z] T and thus f (x) z via brute-force DLOG.

Security in the secret-key setting. The scheme as written already achieves simulation-based selective security in the secret-key, many-key setting (that is, against an adversary that does not see mpk); this holds under the DDH assumption in G 2 . We sketch how we can simulate (ct x,z , sk f ) given x, f , f (x) z; the proof extends readily to the many-key setting. The idea is to program w = z + sw, ṽ = s(u x + v) 6 As an example with n = 2, m = 3, we have

a
⊗ I 3 + (b 1 , b 2 , b 3 )
In addition, using [START_REF] Agrawal | Adaptive simulation security for inner product functional encryption[END_REF], we can rewrite (ct x,z , sk f ) as

ct x,z = [s] 1 , [ w] 1 , [ ṽ] 1 ∈ G n +2 1 sk f = [t + s -1 ( w -z)] 2 , [ û ] 2 , [t (L 1 (x ⊗ I m ) + L 0 ) -û • (x ⊗ I m ) + s -1 ṽr ] 2 , [r] 2
where û := t L 1 + u (I n ⊗ r ). Under the DDH assumption in G 2 , we know that 8[u (

I n ⊗ r )] 2 , [r ] 2 , u ← Z n p , r ← Z m p is pseudorandom, which means that [ û ] 2 , [r ] 2 is pseudorandom.
We can therefore simulate (ct x,z , sk f ) as follows: on input µ = f (x) z, 1. run the simulator for partial garbling on input f , x, µ to obtain (p 1 , p 2 ); 2. sample s ← Z p , w ← Z n p , ṽ ← Z p , û ← Z mn p ; 3. output

ct x,z = [s] 1 , [ w] 1 , [ ṽ] 1 ∈ G n +2 1 sk f = [-p 1 + s -1 w] 2 , [ û ] 2 , [p 2 -û • (x ⊗ I m ) + s -1 ṽr ] 2 , [r] 2
Looking ahead, we note that the above analysis extends to the k-Lin assumption, at the cost of blowing up the width of u, v, r by a factor of k. In the analysis, we use the fact that under k-Lin over G 2 , ([u (

I n ⊗ R)] 2 , [R] 2 ) is pseudo- random where u ← Z kn p , R ← Z k×m p .
The compiler. To obtain a public-key scheme secure under the k-Lin assumption, we perform the following substitutions to [START_REF] Agrawal | Functional encryption: New perspectives and lower bounds[END_REF], following [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF][START_REF] Chen | Improved dual system ABE in prime-order groups via predicate encodings[END_REF]:

s → s A ∈ Z 1×(k+1) p w → W ∈ Z (k+1)×n p u → U ∈ Z (k+1)×kn p v → V ∈ Z (k+1)×k p t → T ∈ Z (k+1)×(m+n -1) p r → R ∈ Z k×m p
That is, we blow up the height of w , u , v, t by a factor of k + 1, and the width of u , v, r by a factor of k. The proof of security follows the high-level strategy in [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF]:

-We first switch [s A ] 1 in the ciphertext with a random [c ] 1 .
-We decompose sk f into two parts, A sk f , c sk f , corresponding to component-wise multiplication by A , c respectively, using the fact that (A|c) forms a full-rank basis.

-We simulate A sk f using (mpk, f ), and simulate the ciphertext and c sk f as in the secret-key setting we just described.

We refer the reader to Section 6 to see how the construction can be extended to handle the "extended" functionality in (3); an overview is given at the beginning of that section.

Unbounded-slot scheme

We refer the reader to Section 1.2 for a high-level overview of the unbounded-slot scheme, and proceed directly to describe the construction and the security proof. The construction. We run two copies of the one-slot scheme, which we denote by

(Enc b , KeyGen b ) = (Enc(mpk b , •), KeyGen(msk b , •)), b = 1, 2
We denote the corresponding simulators by (Enc * b , KeyGen * b ). Informally, we have

(Enc b (x, z w), KeyGen b ( f , [r ] 2 )) ≈ c (Enc * b (x), KeyGen * b (( f , [r ] 2 ), [ f (x) z + wr ] 2 ))
Then, Enc,KeyGen in the unbounded-slot scheme are given by

Enc((x i , z i ) i ) = Enc 1 (x 1 , z 1 -i ∈[2,N ] w i ), Enc 2 (x 2 , z 2 w 2 ), • • • , Enc 2 (x N , z N w N ) KeyGen(f ) = KeyGen 1 ( f , [r ] 2 ), KeyGen 2 ( f , [r ] 2 ), [r ] 2
The final simulator is given by:

Enc * ((x i ) i ) = Enc * 1 (x 1 ), Enc 2 (x 2 , 0 w 2 ), • • • , Enc 2 (x N , 0 w N ) KeyGen * ( f , µ) = KeyGen * 1 (( f , [r ] 2 ), [µ -i ∈[2,N ] w i r ] 2 ), KeyGen 2 ( f , [r ] 2 )
As a sanity check, observe that decrypting Enc * ((

x i ) i ) using KeyGen * ( f , i f (x i ) z i ) returns i f (x i ) z i .
Proof overview. For simplicity, we focus on the setting N = 3 with one secret key query in ≈ c , we use simulation-based semi-adaptive security of (Enc 1 , KeyGen 1 ) and (Enc 2 , KeyGen 2 ), respectively.

In the setting for general N and Q secret key queries, -we will invoke simulation-based security of (Enc 1 , KeyGen 1 ) once, and that of (Enc 2 , KeyGen 2 ) for 2(N -1) times, while using the fact that both of these schemes are also secure against Q secret key queries;

-in DDH ≈ c , we will rely on pseudorandomness of {[w i r j ] 2 , [r j ] 2 )} j ∈[Q] for i ∈ [2, N ].

Preliminaries

Notations. We denote by s ← S the fact that s is picked uniformly at random from a finite set S. We use ≈ s to denote two distributions being statistically indistinguishable, and ≈ c to denote two distributions being computationally indistinguishable. We use lower case boldface to denote column vectors and upper case boldcase to denote matrices.

We use e i to denote the i 'th elementary column vector (with 1 at the i 'th position and 0 elsewhere, and the total length of the vector specified by the context). For any positive integer N , we use [N ] to denote {1, 2, . . . , N } and [2, N ] to denote {2, . . . , N }. The tensor product (Kronecker product) for matrices A = (a i , j ) ∈ Z ×m , B ∈ Z n×p is defined as

A ⊗ B =     a 1,1 B, . . . , a 1,m B . . . , . . . , . . . a ,1 B, . . . , a ,m B     ∈ Z n×mp . ( 8
)
Arithmetic Branching Programs. A branching program is defined by a directed acyclic graph (V, E ), two special vertices v 0 , v 1 ∈ V and a labeling function φ. An arithmetic branching program (ABP), where p is a prime, computes a function f : Z n p → Z p . Here, φ assigns to each edge in E an affine function in some input variable or a constant, and f (x) is the sum over all v 0 -v 1 paths of the product of all the values along the path. We refer to |V | + |E | as the size of f . The definition extends in a coordinate-wise manner to functions f :

Z n p → Z n p . Henceforth, we use F ABP,n,n to denote the class of ABP f : Z n p → Z n p .
We note that there is a linear-time algorithm that converts any boolean formula, boolean branching program or arithmetic formula to an arithmetic branching program with a constant blow-up in the representation size. Thus, ABPs can be viewed as a stronger computational model than all of the above. Recall also that branching programs and boolean formulas correspond to the complexity classes LOGSPACE and NC1 respectively.

Prime-order Bilinear Groups

A generator G takes as input a security parameter 1 λ and outputs a description G := (p, G 1 , G 2 , G T , e), where p is a prime of Θ(λ) bits, G 1 , G 2 and G T are cyclic groups of order p, and e : G 1 × G 2 → G T is a non-degenerate bilinear map. We require that the group operations in G 1 , G 2 , G T and the bilinear map e are computable in deterministic polynomial time in λ. Let g 1 ∈ G 1 , g 2 ∈ G 2 and g T = e(g 1 , g 2 ) ∈ G T be the respective generators. We employ the implicit representation of group elements: for a matrix M over Z p , we define

[M] 1 := g M 1 , [M] 2 := g M 2 , [M] T := g M T , where exponentiation is carried out component-wise. Also, given [A] 1 , [B] 2 , we let e([A] 1 , [B] 2 ) = [AB] T .
We recall the matrix Diffie-Hellman (MDDH) assumption on G 1 [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF]:

Assumption 1 (MDDH d k, Assumption) Let k, , d ∈ N.
We say that the MDDH d k, assumption holds if for all PPT adversaries A, the following advantage function is negligible in λ.

Adv MDDH d k, A (λ) := Pr[A(G, [M] 1 , [MS] 1 ) = 1] -Pr[A(G, [M] 1 , [U] 1 ) = 1]
where

G := (p, G 1 , G 2 , G T , e) ← G(1 λ ), M ← Z ×k p , S ← Z k×d p and U ← Z ×d p .
The MDDH assumption on G 2 can be defined in an analogous way. Escala et al. [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF] showed that

k-Lin ⇒ MDDH 1 k,k+1 ⇒ MDDH d k, ∀ k, d ≥ 1, > k
with a tight security reduction. (In the setting where ≤ k, the MDDH d k, assumption holds unconditionally.) We state the following lemma implied by MDDH 1 k,Q .

Lemma 1. For all Q ∈ N and µ 1 , . . . , µ Q ∈ Z p , we have

[-w r j ] 2 , [ µ j + w r j ] 2 , [r j ] 2 j ∈[Q] ≈ c [ µ j -w r j ] 2 , [w r j ] 2 , [r j ] 2 j ∈[Q]
where w, r j ← Z k p for all j ∈ [Q]. Concretely, the distinguishing advantage is bounded by

2 • Adv MDDH 1 k,Q B (λ). Proof. This follows from MDDH 1 k,Q assumption stating that {[w r j ] 2 , [r j ]} j ≈ {[ r j ] 2 , [r j ] 2 } j with r j ← Z p for all j ∈ [Q] and change of variables: r j → r j -µ j or all j ∈ [Q].

Definitions and Tools

In this section, we formalize functional encryption for attribute-weighted sums, using the framework of partiallyhiding functional encryption [START_REF] Gorbunov | Predicate encryption for circuits from LWE[END_REF][START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF][START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF].

FE for Attribute-Weighted Sums

Syntax. An unbounded-slot FE for attribute-weighted sums consists of four algorithms:

Setup(1 λ , 1 n , 1 n ) :
The setup algorithm gets as input the security parameter 1 λ and function parameters 1 n , 1 n . It outputs the master public key mpk and the master secret key msk.

Enc(mpk,(x i , z i ) i ∈[N ] ) :
The encryption algorithm gets as input mpk and message

(x i , z i ) i ∈[N ] ∈ (Z n p × Z n p ) . It outputs a ciphertext ct (x i ,z i ) with (x i ) being public.
KeyGen(msk, f ) : The key generation algorithm gets as input msk and a function f ∈ F ABP,n,n . It outputs a secret key sk f with f being public.

Dec((sk f , f ), (ct (x i ,z i ) , (x i ) i ∈[N ]
)) : The decryption algorithm gets as input sk f and ct (x i ,z i ) along with f and (x i ) i ∈ [N ] . It outputs a value in Z p .

Correctness. For all (x i ,

z i ) i ∈[N ] ∈ (Z n p × Z n p ) and f ∈ F ABP,n,n , we require Pr     Dec((ct (x i ,z i ) , (x i ) i ∈[N ] ), (sk f , f )) = i ∈[N ] f (x i ) z i : (mpk, msk) ← Setup(1 λ , 1 n , 1 n ) sk f ← KeyGen(msk, f ) ct (x i ,z i ) ← Enc(mpk,(x i , z i ) i ∈[N ] )     = 1.
Remark 1 (Relaxation of correctness.). Our scheme only achieves a relaxation of correctness where the decryption algorithm takes an additional bound 1 B (and runs in time polynomial in B ) and

outputs i ∈[N ] f (x i ) z i if the value is bounded by B .
This limitation is also present in prior works on (IP)FE from DDH and bilinear groups [START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF][START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF][START_REF] Abdalla | Multi-input inner-product functional encryption from pairings[END_REF][START_REF] Lin | Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs[END_REF][START_REF] Baltico | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF], due to the reliance on brute-force discrete log to recover the answer "from the exponent". We stress that the relaxation only refers to functionality and does not affect security.

Security definition. We consider semi-adaptive [START_REF] Chen | Semi-adaptive attribute-based encryption and improved delegation for Boolean formula[END_REF] (strengthening of selective), simulation-based security, which stipulates that there exists a randomized simulator (Setup * , Enc * , KeyGen * ) such that for every efficient stateful adversary A,

         1 N ← A(1 λ ); (mpk, msk) ← Setup(1 λ , 1 n , 1 n ); (x * i , z * i ) i ∈[N ] ← A(mpk); ct * ← Enc(mpk,(x * i , z * i ) i ∈[N ] ); output A KeyGen(msk,•) (mpk, ct * )          ≈ c          1 N ← A(1 λ ); (mpk, msk * ) ← Setup * (1 λ , 1 n , 1 n , 1 N ); (x * i , z * i ) i ∈[N ] ← A(mpk); ct * ← Enc * (msk * , (x * i ) i ∈[N ] ); output A KeyGen * (msk * ,(x * i ) i ∈[N ] ,•,•) (mpk, ct * )         
such that whenever A makes a query f to KeyGen, the simulator KeyGen * gets f along with

i ∈[N ] f (x * i ) z * i . We use Adv FE
A (λ) to denote the advantage in distinguishing the real and ideal games.

One-slot scheme. A one-slot scheme is the same thing, except we always have N = 1 for both correctness and security.

Partial Garbling Scheme

The partial garbling scheme [START_REF] Ishai | Partial garbling schemes and their applications[END_REF][START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] for f (x) z with f ∈ F ABP,n,n is a randomized algorithm that on input f outputs an affine function in x, z of the form:

p f ,x,z = z -t , t (L 1 (x ⊗ I m ) + L 0 )
where

L 0 ∈ Z (m+n -1)×mn p , L 1 ∈ Z (m+n -1)×m p depends only on f ; t ← Z m+n -1 p
is the random coin and t consists of the last n entries in t, such that given (p f ,x,z , f , x), we can recover f (x) z, while learning nothing else about z.

Lemma 2 (partial garbling [30,43]

). There exists four efficient algorithms (lgen, pgb, rec,pgb * ) with the following properties:

-(syntax) on input f ∈ F ABP,n,n , lgen( f ) outputs L 0 ∈ Z (m+n -1)×mn p , L 1 ∈ Z (m+n -1)×m p
, and

pgb(f , x, z; t) = z -t , t (L 1 (x ⊗ I m ) + L 0 ) pgb * ( f , x, µ; t) = -t , t (L 1 (x ⊗ I m ) + L 0 ) + µ • e 1
where t ∈ Z m+n -1 p and t consists of the last n entries in t and m are linear in the size of f .

-(reconstruction) rec(f , x) outputs d f ,x ∈ Z n +m p such that for all f , x, z, t, p f ,x,z d f ,x = f (x) z
where p f ,x,z = pgb(f , x, z; t).

-(privacy) for all f , x, z,

pgb( f , x, z; t) ≈ s pgb * ( f , x, f (x) z; t)
where the randomness is over t ← Z m+n -1 p .

Extension. We will also rely on an extra property of the above construction to handle shifts by δ ∈ Z p , namely that, given

p f ,x,z, δ = z -t , t (L 1 (x ⊗ I m ) + L 0 ) + δ • e 1
together with ( f , x), we can recover f (x) z + δ, while learning nothing else about z, δ. That is, for all f , x, z and δ ∈ Z p :

-(reconstruction) (pgb( f , x, z; t) + (0, δ • e 1 ))d f ,x = f (x) z + δ -(privacy) pgb(f , x, z; t) + (0, δ • e 1 ) ≈ s pgb * ( f , x, f (x) z + δ ; t)
where the randomness is over t ← Z m+n -1 p .

See Section A for more detail about Lemma 2 and the extension.

Π one : One-Slot Scheme

In this section, we present our one-slot FE scheme for attribute-weighted sums. This scheme achieves simulationbased semi-adaptive security under k-Linear assumptions.

Construction

Our one-slot FE scheme Π one in prime-order bilinear group is described as follows.

-

Setup(1 λ , 1 n , 1 n ): Run G = (p, G 1 , G 2 , G T , e) ← G(1 λ ). Sample A ← Z (k+1)×k p and W ← Z (k+1)×n p , U ← Z (k+1)×kn p , V ← Z (k+1)×k p and output mpk = G, [A ] 1 , [A W] 1 , [A U] 1 , [A V] 1 and msk = W, U, V .
-Enc(mpk,(x,z)): Sample s ← Z k p and output

ct x,z = [s A ] 1 , [z + s A W] 1 , [s A U(x ⊗ I k ) + s A V] 1 and x.
-

KeyGen(msk, f ): Run (L 1 , L 0 ) ← lgen(f ) where L 1 ∈ Z (m+n -1)×mn p , L 0 ∈ Z (m+n -1)×m p (cf. Section 4.2). Sample T ← Z (k+1)×(m+n -1)
p and R ← Z k×m p and output

sk f = [T + W] 2 , [TL 1 + U(I n ⊗ R)] 2 , [TL 0 + VR] 2 , [R] 2 and f
where T refers to the matrix composed of the right most n columns of T.

-Dec((sk f , f ), (ct x,z , x)): On input key:

sk f = [K 1 ] 2 , [K 2 ] 2 , [K 3 ] 2 , [R]
2 and f and ciphertext:

ct x,z = [c 0 ] 1 , [c 1 ] 1 , [c 2 ]
1 and x the decryption works as follows:

1. compute [p 1 ] T = e([c 1 ] 1 , [I n ] 2 ) • e([c 0 ] 1 , [-K 1 ] 2 ) (9) 2. compute [p 2 ] T = e([c 0 ] 1 , [K 2 (x ⊗ I m ) + K 3 ] 2 ) • e([-c 2 ] 1 , [R] 2 ) (10) 3. run d f ,x ← rec(f , x) (cf. Section 4.2), compute [D] T = [(p 1 , p 2 )d f ,x ] T ( 11
)
and use brute-force discrete log to recover D as the output.

Correctness. For ct x,z and sk f , we have

p 1 = z -s A T (12)
p 2 = s A TL 1 (x ⊗ I m ) + s A TL 0 ( 13
) (p 1 , p 2 )d f ,x = f (x) z (14)
Here [START_REF] Boneh | Fully keyhomomorphic encryption, arithmetic circuit ABE and compact garbled circuits[END_REF] follows from the fact that

(p 1 , p 2 ) = pgb(f , x, z; (s A T) ) and d f ,x = rec(f , x)
and reconstruction of the partial garbling in [START_REF] Agrawal | Attribute based encryption (and more) for nondeterministic finite automata from LWE[END_REF]; the remaining two equalities follow from:

(12) z -s A T = (z + s A W) • I n -s A • (T + W) (13) s A TL 1 (x ⊗ I m ) + s A TL 0 = s A • (TL 1 + U(I n ⊗ R))(x ⊗ I m ) + (TL 0 + VR) -s A U(x ⊗ I k ) + s A V • R
in which we use the equality (

I n ⊗ R)(x ⊗ I m ) = (x ⊗ I k )R.
This readily proves the correctness.

Remark 2 (Comparison with W17 [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF]). The ciphertext in [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] contains a term of the form

[x ⊗ s A V + s A U] 1 ∈ G kn 1 in the place of [s A U(x ⊗ I k ) + s A V] 1 ∈ G k 1 where U ← Z (k+1)×kn p , V ← Z (k+1)×k p
. The secret key sizes in both our schemes and that in [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] are O(mn + n ). In our scheme, the multiplicative factor of n comes at the cost of a smaller ciphertext. In [START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF], the multiplicative factor of n comes from a locality requirement that each column of L 1 (x ⊗ I m ) + L 0 depends on a single entry of x, which can be achieved generically at the cost of a blow-up of n. We remove the locality requirement in our scheme.

Security. We have the following theorem with the proof shown in the subsequent subsection.

Theorem 1. Our one-slot scheme Π one for attribute-weighted sums described in this section achieves simulation-based semi-adaptive security under the MDDH assumption in G 1 and in G 2 .

Simulator

We start by describing the simulator.

-Setup * (1 λ , 1 n , 1 n ): Run G = (p, G 1 , G 2 , G T , e) ← G(1 λ ). Sample A ← Z (k+1)×k p and W ← Z (k+1)×n p , U ← Z (k+1)×kn p , V ← Z (k+1)×k p c ← Z k+1 p w ← Z n p , v ← Z k p and output mpk = G, [A ] 1 , [A W] 1 , [A U] 1 , [A V]
sk * f = C ⊥ • sk * f [1] + a ⊥ • sk * f [2], [R] 2 and f ( 15
)
where

sk * f [1] = [A T + A W] 2 , [A TL 1 + A U(I n ⊗ R)] 2 , [A TL 0 + A VR] 2 sk * f [2] = [-(p * 1 ) + w ] 2 , [ û ] 2 , [(p * 2 ) -û (x * ⊗ I m ) + v R] 2
Here T refers to the matrix composed of the right most n columns of T. That is,

sk * f =     [C ⊥ (A T + A W) +a ⊥ (-(p * 1 ) + w )] 2 , [C ⊥ (A TL 1 + A U(I n ⊗ R)) +a ⊥ ( û )] 2 , [R] 2 [C ⊥ (A TL 0 + A VR) +a ⊥ (p * 2 ) -û (x * ⊗ I m ) + v R ] 2    
Remark 3 (decryption checks). As a sanity check, we check that an adversary cannot use the decryption algorithm to distinguish between the real and simulated output.

Observe that when we decrypt the simulated ciphertext ct 2 ) ) ← pgb * ( f , x * , f (x * ) z * ). Similarly, when we decrypt a normal ciphertext ct x,z ← Enc(mpk,(x,z)) corresponding to any (x, z) with a simulated secret key, the sk * f [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] part cancels out and leaves just the sk * f [START_REF] Abdalla | From single-input to multi-client inner-product functional encryption[END_REF] part since

A C ⊥ = I, A a ⊥ = 0.
We end up with (p 1 , p 2 )d f ,x = f (x) z where (p 1 , p 2 ) = pgb( f , x, z; (s A T) ) as in the real Dec algorithm.

Proof

With our simulator, we prove the following theorem which implies Theorem 1.

Theorem 2. For all A, there exist B 1 and B 2 with Time(B 1 ), Time(B 2 ) ≈ Time(A) such that

Adv Π one A (λ) ≤ Adv MDDH 1 k,k+1 B 1 (λ) + Adv MDDH n k,mQ B 2 (λ) + 1/p
where n is length of public input x * in the challenge, m is the parameter depending on size of function f and Q is the number of key queries.

Note that this yields a tight security reduction to the k-Lin assumption. Before we proceed to describe the game sequence and proof, we state the following lemma we will use.

Lemma 3 (statistical lemma). For any full-rank

(A|c) ∈ Z (k+1)×k p × Z k+1 p , we have A W, c W : W ← Z (k+1)×k p ≡ A W, w : W ← Z (k+1)×k p , w ← Z k p .
Game sequence. We use (x * , z * ) to denote the semi-adaptive challenge and for notational simplicity, assume that all key queries f j share the same parameter m. We prove Theorem 2 via a series of games.

Game 0 : Real game.

Game 1 : Identical to Game 0 except that ct * for (x * , z * ) is given by

ct * = [ c ] 1 , [(z * ) + c W] 1 , [ c U(x * ⊗ I k ) + c V] 1
where c ← Z k+1 p . We claim that Game 0 ≈ c Game 1 . This follows from MDDH 1 k,k+1 assumption:

[A ] 1 , [s A ] 1 ≈ c [A ] 1 , [c ] 1 .
In the reduction, we sample W, U, V honestly and use them to simulate mpk and KeyGen(msk,•) along with [A ] 1 ; the challenge ciphertext ct * is generated using the challenge term given above. See Lemma 4 for details.

Game 2 : Identical to Game 1 except that the j -th query f j to KeyGen(msk,•) is answered by

sk f j = C ⊥ • sk f j [1] + a ⊥ • sk f j [2], [R j ] 2 with sk f j [1] = [A T j + A W] 2 , [A T j L 1, j + A U(I n ⊗ R j )] 2 , [A T j L 0, j + A VR j ] 2 sk f j [2] = [c T j + c W] 2 , [c T j L 1, j + c U(I n ⊗ R j )] 2 , [c T j L 0, j + c VR j ] 2
where (L 1, j , L 0, j ) ← lgen(f j ),

T j ← Z (k+1)×(m+n -1) p , R j ← Z k×m p
, c is the randomness in ct * and C ⊥ , a ⊥ are defined such that (A|c) (C ⊥ |a ⊥ ) = I k+1 (cf. Setup * in Section 5.2). By basic linear algebra, we have Game 1 = Game 2 .

Game 3 : Identical to Game 2 except that we replace Setup,Enc with Setup * , Enc * where ct * is given by

ct * = [c ] 1 , [ w ] 1 , [ v ] 1
and replace KeyGen(msk,•) with KeyGen * 3 (msk * , •), which works as KeyGen(msk,•) in Game 2 except that, for the j -th query f j , we compute

sk f j [2] = [ t j -(z * ) + w ] 2 , [ t j L 1, j + ũ (I n ⊗ R j )] 2 , [ t j L 0, j -ũ (I n ⊗ R j )(x * ⊗ I m ) + v R j ] 2
where w, ṽ are given in msk * (output by Setup * ) and ũ ← Z kn p , t j ← Z m+n -1 p , R j ← Z k×m p . We claim that Game 2 ≈ s Game 3 . This follows from the following statement: for any full-rank (A|c), we have (A U,c U,A W,c W,A V,c V, A T j , c T j )

≡ (A U, ũ , A W, w -(z * ) , A V, ṽ -ũ (x * ⊗ I k ) , A T j , t j )
which is implied by Lemma 3. See Lemma 5 for details.

Game 4 : Identical to Game 3 except that we replace KeyGen * 3 with KeyGen * 4 which works as KeyGen *

sk f j [2] = [ t j -(z * ) + w ] 2 , [ t j L 1, j + û j ] 2 , [ t j L 0, j -û j (x * ⊗ I m ) + v R j ] 2
where ûj ← Z nm p and R j ← Z k×m p . We claim that Game 3 ≈ c Game 4 . This follows from MDDH n k,mQ assumption which tells us that

[ u (I n ⊗ R j )] 2 , [R j ] 2 j ∈[Q] ≈ c [ û j ] 2 , [R j ] 2 j ∈[Q]
where Q is the number of key queries. See Lemma 6 for details.

Game 5 : Identical to Game 4 except that we replace KeyGen * 4 with KeyGen * ; this is the ideal game. We claim that Game 4 ≈ s Game 5 . This follows from the privacy of partial garbling scheme in Section 4.2. See Lemma 7 for details.

We use Adv xx

A (λ) to denote the advantage of adversary A in Game xx .

Lemmas

We prove the following lemmas showing the indistinguishability of adjacent games listed above. This completes the proof of Theorem 2.

Lemma 4 (Game 0 ≈ c Game 1 ). For all A, there exists B 1 with Time(B 1 ) ≈ Time(A) such that

|Adv 1 A (λ) -Adv 0 A (λ)| ≤ Adv MDDH 1 k,k+1 B 1 (λ).
Proof. Recall that we replace s A with c ← Z 1×(k+1) p in ct * in Game 1 . We prove the lemma from MDDH 1 k,k+1 assumption:

[A ] 1 , [s A ] 1 ≈ c [A ] 1 , [c ] 1 where s ← Z k p and c ← Z k+1 p . On input [A ] 1 , [c ] 1 where c = s A or c ← Z 1×(k+1)
p , the algorithm B 1 samples msk = (W, U, V) and proceeds as follows:

simulate mpk using msk and [A ] 1 ;

on input the semi-adaptive challenge (x * , z * ), output the challenge ciphertext

ct * = [c ] 1 , [(z * ) + c W] 1 , [c U(x * ⊗ I k ) + c V] 1
using [c] 1 and msk; -we answer all key queries honestly using msk.

Observe that, when c = s A , the simulation is identical to Game 0 ; when c ← Z 1×(k+1) p , the simulation is identical to Game 1 . This proves the lemma.

Lemma 5 (Game 2 ≈ c Game 3 ). For all A, we have

Adv 3 A (λ) ≈ Adv 2 A (λ).
Proof (of Lemma 5). Recall that the difference between the two games lies in ct * and sk f j [2]: instead of computing

ct * = [c ] 1 , [(z * ) + c W] 1 , [c U(x * ⊗ I k ) + c V] 1 sk f j [2] = [c T j + c W] 2 , [ c T j L 1, j + c U (I n ⊗ R j )] 2 , [ c T j L 0, j + c VR j ] 2 in Game 2 , we compute ct * = [c ] 1 , [ w ] 1 , [ v ] 1 sk f j [2] = [ t j -(z * ) + w ] 2 , [ t j L 1, j + ũ (I n ⊗ R j )] 2 , [ t j L 0, j -ũ (I n ⊗ R j )(x * ⊗ I m ) + v R j ] 2 in Game 3 .
This follows readily from the following statement, which in turn follows from Lemma 3: for all x * , z * ,

(A U, c U , A W, c W , A V, c V , A T j , c T j ) ≡ (A U, ũ , A W, w -(z * ) , A V, ṽ -ũ (x * ⊗ I k ) , A T j , t j )
where U, W, V, w, ṽ are sampled as in Setup * and ũ ← Z kn p , T j ← Z (k+1)×(m+n -1) p , tj ← Z m+n -1 p . We clarify that in the semi-adaptive security game, (x * , z * ) are chosen after seeing A U, A W, A V. Since the two distributions are identically distributed, the distinguishing advantage remains 0 even for adaptive choices of x * , z * via a random guessing argument.

Finally, note that A U, A W, A V, A T j are used to simulate mpk, sk f j [1], whereas the boxed/gray terms are used to simulate sk f j [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF]. This readily proves the lemma. Lemma 6 (Game 3 ≈ c Game 4 ). For all A, there exists B 2 with Time(B 2 ) ≈ Time(A) such that

|Adv 4 A (λ) -Adv 3 A (λ)| ≤ Adv MDDH n k,mQ B 2 (λ)
where n is length of public input x in the challenge, m is the maximum size of function f and Q is the number of key queries.

Proof. Recall that the differences between the two games is that we replace ũ (I n ⊗ R j ) with û j in sk f j [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] for all j ∈ [Q]. We prove the lemma from MDDH n k,mQ assumption which implies that

[ ũ (I n ⊗ R j )] 2 , [R j ] 2 j ∈[Q] ≈ c [ û j ] 2 , [R j ] 2 j ∈[Q] ( 16
)
where ũ ← Z kn p , R j ← Z k×m p , ûj ← Z nm p . To see that MDDH n k,mQ implies (16), we write ũ = ( ũ 1 , . . . , ũ n ) ∈ (Z 1×k p ) n and û j = ( û j ,1 , . . . , ũ j ,n )

∈ (Z 1×m p ) n , ∀ j ∈ [Q]
and restate [START_REF] Brakerski | Circuit-ABE from LWE: Unbounded attributes and semi-adaptive security[END_REF] as follows:

[MS] 2 , [M] 2 ≈ c [U] 2 , [M] 2
where

S = ( ũ1 | • • • | ũn ) ← Z k×n p , M =      R 1 . . . R Q      ← Z mQ×k p , U =      û1,1 • • • û1,n . . . . . . ûQ,1 • • • ûQ,n      ← Z mQ×n p
, this is exactly that MDDH n k,mQ assumption states. We proceed to prove the lemma from [START_REF] Brakerski | Circuit-ABE from LWE: Unbounded attributes and semi-adaptive security[END_REF]. On input [t j ] 2 , [R j ] 2 j ∈[Q] where t j = ũ (I n ⊗ R j ) or t j = û j , the algorithm B works as follows:

Setup. Run Setup * honestly with output [START_REF] Abdalla | From single-input to multi-client inner-product functional encryption[END_REF] and msk * = W, U, V, w, ṽ, c, C ⊥ , A, a ⊥ and return mpk to A. Challenge. On the semi-adaptive challenge (x * , z * ), output Enc * (msk * , x * ). Key queries. On input the j -th key query f j , we sample T j ← Z (k+1)×(m+n -1) p , tj ← Z m+n -1 p and want to return sk f j combined from the components below via [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF]:

mpk = G, [A ] 1 , [A W] 1 , [A U] 1 , [A V]
sk f j [1] = [A T j + A W] 2 , [A T j L 1, j + A U(I n ⊗ R j )] 2 , [A T j L 0, j + A VR j ] 2 sk f j [2] = [ t j -(z * ) + w ] 2 , [ t j L 1, j + t j ] 2 , [ t j L 0, j -t j (x * ⊗ I m ) + ṽ R j ] 2
where

t j =    ũ (I n ⊗ R j ) , KeyGen * 3 û j , KeyGen * 4
Here sk f j [START_REF] Abdalla | From single-input to multi-client inner-product functional encryption[END_REF] can be simulated using msk * and [R j ] 2 given out in the input; sk f j [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF] can be simulated using msk * , [R j ] 2 and the challenge term [t j ] 2 in the input.

Observe that when t j = ũ (I n ⊗ R j ) , we simulate KeyGen * 3 during Key queries and the simulation is identical to Game 3 ; -when t j = û j , we simulate KeyGen * 4 during Key queries and the simulation is identical to Game 4 .

This proves the lemma.

Lemma 7 (Game 4 ≈ s Game 5 ). For all A, we have Adv 5 A (λ) ≈ Adv 4

A (λ).

Proof. Recall that the difference between the two games lies in sk f j [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF]: instead of computing

sk f j [2] = [ t j -(z * ) + w ] 2 , [ t j L 1, j + û j ] 2 , [ t j L 0, j -û (x * ⊗ I m ) + ṽ R] 2
in KeyGen * 4 (i.e., Game 4 ), we compute

sk f j [2] = [ t j + w ] 2 , [ û j ] 2 , [ t j (L 1, j (x * ⊗ I m ) + L 0, j ) + e 1 • f j (x * ) z * -û j (x * ⊗ I m ) + ṽ R] 2
in KeyGen * (i.e., Game 5 ). By change of variable û j → û j -t j L 1, j for all j ∈ [Q] in Game 4 , we can rewrite in the form:

sk f j [2] = [-p j ,1 + w ] 2 , [ û j ] 2 , [p j ,2 -û j (x * ⊗ I m ) + ṽ R] 2 where (p j ,1 , p j ,2 ) ←    pgb(f j , x * , z * ; tj ) in Game 4 pgb * ( f j , x * , f j (x * ) z * ; tj ) in Game 5
Then the lemma immediately follows from the privacy of underlying partial garbling scheme which means pgb(f j , x * , z * ) ≈ s pgb * ( f j , x * , f j (x * ) z * ).

Π ext : Extending Π one

In this section, we extend our one-slot FE scheme Π one in Section 5 to handle the randomization offsets w r. The scheme achieves simulation-based semi-adaptive security under k-Linear assumption.

Extension. The extended scheme is the same as a one-slot FE for attribute-weighted sums, except we replace functionality ((x, z), f

) → f (x) z with ((x, z w), ( f , [r] 2 )) → [ f (x) z + w r] T
where w, r ∈ Z k p . That is, we make the following modifications:

-Enc takes z w instead of z as the second input; -KeyGen,KeyGen * takes ( f , [r] 2 ) instead of f as input;

-in correctness, decryption computes [ f (x) z + w r] T instead of f (x) z;
in the security definition, A produces (x * , z * w * ) instead of (x * , z * ), and

KeyGen * gets [ f (x * ) z * +(w * ) r] 2 instead of f (x * ) z * .
In particular, correctness states that:

Dec(Enc(mpk,(x,z w)), KeyGen(msk,(f , [r] 2 ))) = [ f (x) z + w r] T
Construction overview. To obtain a scheme with the extension, the idea -following the IPFE in [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF]-is to augment the previous construction Π one with [A W 0 ] 1 in mpk, [w + s A W 0 ] 1 in the ciphertext, and [W 0 r] 2 in the secret key.

During decryption, we will additionally compute

e([w + s A W 0 ] 1 , [r] 2 ) • e([s A ] 1 , [W 0 r] 2 ) -1 = [w r] T
This works for correctness, but violates security since the decryptor learns both [ f (x) z] T and [w r] T instead of just the sum. To avoid this leakage while preserving correctness, we will carefully embed W 0 r into the secret key for Π one , while relying on the extension of the garbling scheme for handling shifts to argue both correctness and security, cf.

Section 4.2.

Our scheme

Scheme. Our extended one-slot FE scheme Π ext in prime-order bilinear group is described as follows. The boxes indicate the changes from the scheme in Section 5.1.

-

Setup(1 λ , 1 n , 1 n ): Run G = (p, G 1 , G 2 , G T , e) ← G(1 λ ). Sample A ← Z (k+1)×k p and W ← Z (k+1)×n p , W 0 ← Z (k+1)×k p , U ← Z (k+1)×kn p , V ← Z (k+1)×k p and output mpk = G, [A ] 1 , [A W] 1 , [A U] 1 , [A V] 1 , [A W 0 ] 1 and msk = W, U, V, W 0 .
-Enc(mpk,(x,z w)): Sample s ← Z k p and output

ct x,z,w = [s A ] 1 , [z + s A W] 1 , [s A U(x ⊗ I k ) + s A V] 1 , [w + s A W 0 ]
sk f ,r = [T + W] 2 , [TL 1 + U(I n ⊗ R)] 2 , [TL 0 -W 0 r • e 1 + VR] 2 , [R] 2 and ( f , [r] 2 )
where T refers to the matrix composed of the right most n columns of T.

-Dec((sk f ,r , ( f , [r] 2 )), (ct x,z w , x)): On input key:

sk f ,r = [K 1 ] 2 , [K 2 ] 2 , [K 3 ] 2 , [R] 2 and ( f , [r] 2 )
and ciphertext:

ct x,z w = [c 0 ] 1 , [c 1 ] 1 , [c 2 ] 1 , [c 3 ] 1

and x

the decryption works as follows:

1. compute

[p 1 ] T = e([c 1 ] 1 , [I n ] 2 ) • e([c 0 ] 1 , [-K 1 ] 2 ) (17) 2. compute [p 2 ] T = e([c 0 ] 1 , [K 2 (x ⊗ I m ) + K 3 ] 2 ) • e([-c 2 ] 1 , [R] 2 ) • e([c 3 ] 1 , [r • e 1 ] 2 ) (18) 3. run d f ,x ← rec( f , x) (see Section 4.2), output [D] T = [(p 1 , p 2 )d f ,x ] T ( 19
)
Simulator. The simulator for Π ext is as follows. The boxes indicate the changes from the simulator for Π one in Section 5.2.

-Setup * (1 λ , 1 n , 1 n ): Run G = (p, G 1 , G 2 , G T , e) ← G(1 λ ). Sample A ← Z (k+1)×k p and W ← Z (k+1)×n p , W 0 ← Z (k+1)×k p , U ← Z (k+1)×kn p , V ← Z (k+1)×k p c ← Z k+1 p w ← Z n p , w 0 ← Z k p , v ← Z k p and output mpk = G, [A ] 1 , [A W] 1 , [A W 0 ] 1 , [A U] 1 , [A V] 1 msk * = W, W 0 , U, V, w, w 0 , v, c, C ⊥ , A, a ⊥
where (A|c) (C ⊥ |a ⊥ ) = I k+1 . Here we assume that (A|c) has full rank, which happens with probability 1 -1/p.

-Enc * (msk * , x * ): Output ct * = [c ] 1 , [ w ] 1 , [ v ] 1 , [ w 0 ] 1 and x * . -KeyGen * (msk * , x * , ( f , [r] 2 ), [µ] 2 ): Run (L 1 , L 0 ) ← lgen(f ) and ([(p * 1 ) ] 2 , [(p * 2 ) ] 2 ) ← pgb * ( f , x * , [µ] 2 ).
Here, we use the fact that pgb * ( f , x * , •) is an affine function. Sample û ← Z nm p , T ← Z (k+1)×(m+n -1) p and R ← Z k×m p and output

sk * f ,r = C ⊥ • sk * f ,r [1] + a ⊥ • sk * f ,r [2], [R] 2 and ( f , [r] 2 ) ( 20
)
where

sk * f ,r [1] = [A T + A W] 2 , [A TL 1 + A U(I n ⊗ R)] 2 , [A TL 0 -A W 0 r • e 1 + A VR] 2 sk * f ,r [2] = [-(p * 1 ) + w ] 2 , [ û ] 2 , [(p * 2 ) -û (x * ⊗ I m ) -w 0 r • e 1 + v R] 2
Here T refers to the matrix composed of the right most n columns of T. That is,

sk * f ,r =     [C ⊥ (A T + A W) +a ⊥ (-(p * 1 ) + w )] 2 , [C ⊥ (A TL 1 + A U(I n ⊗ R)) +a ⊥ ( û )] 2 , [R] 2 [C ⊥ (A TL 0 -A W 0 r • e 1 + A VR) +a ⊥ (p * 2 ) -û (x * ⊗ I m ) -w 0 r • e 1 + v R ] 2     -KeyGen(msk, f ): Pick r ← Z k p , compute sk f ,1 ← KeyGen ext (msk 1 , ( f , [r] 2 )); sk f ,2 ← KeyGen ext (msk 2 , ( f , [r] 2 ))
and output

sk f = (sk f ,1 , sk f ,2 , [r] 2 ) and f . -Dec((sk f , f ), (ct (x i ,z i ) , (x i ) i ∈[N ]
)): Parse ciphertext and key as

sk f = (sk f ,1 , sk f ,2 , [r] 2 ) and ct (x i ,z i ) = (ct 1 , . . . , ct N ).
We proceed as follows:

1. Compute

[D 1 ] T ← Dec ext (sk f ,1 , ( f , [r] 2 )), (ct 1 , x 1 ) ; (21)
2. For all i ∈ [2, N ], compute

[D i ] T ← Dec ext (sk f ,2 , ( f , [r] 2 )), (ct i , x i ) ; (22) 3. Compute [D] T = [D 1 ] T • • • [D N ] T ( 23
)
and output D via brute-force discrete log.

Correctness. For ct (x i ,z i ) with randomness w 2 , . . . , w N and sk f with randomness r, we have

D 1 = f (x 1 ) z 1 -i ∈[2,N ] w i r (24)
D i = f (x i ) z i + w i r, ∀i ∈ [2, N ] (25)
D = i ∈[N ] f (x i ) z i ( 26
)
Here ( 24) and ( 25) follow from the correctness of Π ext and the last ( 26) is implied by ( 24) and ( 25). This readily proves the correctness.

Security. We have the following theorem with the proof shown in the subsequent subsection.

Theorem 3. Assume that extended one-slot scheme Π ext achieves simulation-based semi-adaptive security, our unboundedslot FE scheme Π ubd described in this section achieves simulation-based semi-adaptive security under the k-Linear assumption in G 2 .

Simulator

Let (Setup * ext , Enc * ext , KeyGen * ext ) be the simulator for Π ext , we start by describing the simulator for Π ubd . As written, the adversary needs to commit to the length N in advance; this is merely an artifact of our formalization of simulationbased security, and can be avoided by having Enc * pass auxiliary information to KeyGen * .

-Setup * (1 λ , 1 n , 1 n , 1 N ): Sample w 2 , . . . , w N ← Z k p , run (mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ); (mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n )
and output mpk = (mpk 1 , mpk 2 ) and msk * = (msk * 1 , msk 2 , w 2 , . . . , w N ).

-Enc * (msk * , (x * i ) i ∈[N ] ): Compute ct * 1 ← Enc * ext (msk * 1 , x * 1 ) and ct i ← Enc ext (mpk 2 , (x * i , 0 w i )), ∀i ∈ [2, N ]
and output

ct * = (ct * 1 , ct 2 , . . . , ct N ) and (x * i ) i ∈[N ] .
-KeyGen * (msk * , (

x * i ) i ∈[N ] , f , µ ∈ Z p ): Pick r ← Z k p , compute sk * f ,1 ← KeyGen * ext (msk * 1 , x * 1 , ( f , [r] 2 ), [µ -i ∈[2,N ] w i r] 2 ) sk f ,2 ← KeyGen ext (msk 2 , ( f , [r] 2 ))
and output

sk * f = (sk * f ,1 , sk f ,2 , [r]
2 ) and f .

Proof

With our simulator, we prove the following theorem which implies Theorem 3.

Theorem 4.

For all A, there exist B 1 and B 2 with Time(B 1 ), Time(B 2 ) ≈ Time(A) such that

Adv Π ubd A (λ) ≤ (2N -1) • Adv Π ext B 1 (λ) + (N -1) • Adv MDDH 1 k,Q B 2 (λ)
where Q is the number of key queries and N is number of slots.

Game sequence. We use (x * 1 , z * 1 , . . . , x * N , z * N ) to denote the semi-adaptive challenge and prove Theorem 4 via the following game sequence summarized in Fig 4 , where

Game 0 ≈ c Game 1 = Game 2.0 ≈ c Game 2.1 ≈ c Game 2.2 ≈ c Game 2.3 . . . = Game N .0 ≈ c Game N .1 ≈ c Game N .2 ≈ c Game N .3
Game 0 : Real game.

Game 1 : Identical to Game 0 except for the boxed terms below:

we generate mpk = (mpk 1 , mpk 2 ) and msk = ( msk * 1 , msk 2 ) where

(mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ) ; (mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n ) -the challenge ciphertext for (x * 1 , z * 1 , . . . , x * N , z * N ) is ct * = ( ct * 1 , ct 2 , . . . , ct N ) where ct * 1 ← Enc * ext (msk * 1 , x * 1 ) ; ct i ← Enc ext (mpk 2 , (x * i , z * i w i )), ∀i ∈ [2, N ]
the key for the j -th query f j is sk

f j = ( sk * f j ,1 , sk f j ,2 , [r j ] 2 )
where

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ f j (x * 1 ) z * 1 -i ∈[2,N ] w i r j ] 2 sk f j ,2 ← KeyGen ext (msk 2 , ( f j , [r j ] 2 ));
where w 2 , . . . , w N ← Z k p and r j ← Z k p for all j ∈ [Q]. We claim that Game 0 ≈ c Game 1 . This follows from the simulationbased semi-adaptive security of Π ext . See Lemma 8 for more details.

Game η.0 for η ∈ [2, N ]: Identical to Game 1 except for the boxed terms below:

-the challenge ciphertext for (x * 1 , z * 1 , . . . , x * N , z * N ) is ct * = (ct * 1 , ct 2 , . . . , ct N ) where ct * 1 ← Enc * ext (msk * 1 , x * 1 ); ct i ←    Enc ext (mpk 2 , (x * i , 0 w i )) i ∈ [2, η -1] Enc ext (mpk 2 , (x * i , z * i w i )) i ∈ [η, N ]
the key for the j -th query f j is sk

f j = (sk * f j ,1 , sk f j ,2 , [r j ] 2 )
where

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ i ∈[η-1] f j (x * i ) z * i -i ∈[2,N ] w i r j ] 2 sk f j ,2 ← KeyGen ext (msk 2 , ( f j , [r j ] 2 ));
where w 2 , . . . ,

w N ← Z k p and r j ← Z k p for all j ∈ [Q].
Game η.1 for η ∈ [2, N ]: Identical to Game η.0 except for the boxed terms below:

we generate mpk = (mpk 1 , mpk 2 ) and msk = (msk * 1 , msk *

2 ) where

(mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ); (mpk 2 , msk * 2 ) ← Setup * ext (1 λ , 1 n , 1 n ) -the challenge ciphertext for (x * 1 , z * 1 , . . . , x * N , z * N ) is ct * = (ct * 1 , ct 2 , . . . , ct η-1 , ct * η , ct η+1 , . . . , ct N ) where ct * 1 ← Enc * ext (msk * 1 , x * 1 )
and

         ct i ← Enc ext (mpk 2 , (x * i , 0 w i )) i ∈ [2, η -1] ct * η ← Enc * ext (msk * 2 , x * η ) i = η ct i ← Enc ext (mpk 2 , (x * i , z * i w i )) i ∈ [η + 1, N ]
the key for the j -th query f j is sk

f j = (sk * f j ,1 , sk * f j ,2 , [r j ] 2 )
where

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ i ∈[η-1] f j (x * i ) z * i -i ∈[2,N ] w i r j ] 2 sk * f j ,2 ← KeyGen * ext (msk * 2 , x * η , ( f j , [r j ] 2 ), [ f j (x * η ) z * η + w η r j ] 2 )
where w 2 , . . . , w N ← Z k p and r j ← Z k p for all j ∈ [Q]. We claim that Game η.0 ≈ c Game η.1 . This follows from the simulation-based semi-adaptive security of Π ext . See Lemma 9 for more details.

Game η.2 for η ∈ [2, N ]: Identical to Game η.1 except for the boxed terms below:

the key for the j -th query f j is sk

f j = (sk * f j ,1 , sk * f j ,2 , [r j ] 2 )
where

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ i ∈[η] f j (x * i ) z * i -i ∈[2,N ] w i r j ] 2 sk * f j ,2 ← KeyGen * ext (msk * 2 , x * η , ( f j , [r j ] 2 ), [ w η r j ] 2 )
where w 2 , . . . , w N ← Z k p and r j ← Z k p for all j ∈ [Q]. We claim that Game η.1 ≈ c Game η.2 . This follows from Lemma 1 w.r.t. w η and

f j (x * η ) z * η which is implied by MDDH 1 k,Q assumption: for all f j , x * η , z * η , sk * f j ,1 [-w η r j ] 2 , sk * f j ,2 [ f j (x * η ) z * η + w η r j ] 2 , [r j ] 2 j ∈[Q] ≈ c [ f j (x * η ) z * η -w η r j ] 2 , [w η r j ] 2 , [r j ] 2 j ∈[Q] (27)
where w η , r j ← Z k p for all j ∈ [Q]. See Lemma 10 for more details.

Game η.3 for η ∈ [2, N ]: Identical to Game η.2 except for the boxed terms below:

we generate mpk = (mpk 1 , mpk 2 ) and msk = (msk * 1 , msk 2 ) where

(mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ); (mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n ) -the challenge ciphertext for (x * 1 , z * 1 , . . . , x * N , z * N ) is ct * = (ct * 1 , ct 2 , . . . , ct η-1 , ct η , ct η+1 , . . . , ct N ) where ct * 1 ← Enc * ext (msk * 1 , x * 1 )
and

         ct i ← Enc ext (mpk 2 , (x * i , 0 w i )) i ∈ [2, η -1] ct i ← Enc ext (mpk 2 , (x * η , 0 w η )) i = η ct i ← Enc ext (mpk 2 , (x * i , z * i w i )) i ∈ [η + 1, N ]
the key for the j -th query f j is sk

f j = (sk * f j ,1 , sk f j ,2 , [r j ] 2 )
where

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ i ∈[η] f j (x * i ) z * i -i ∈[2,N ] w i r j ] 2 sk f j ,2 ← KeyGen ext (msk 2 , ( f j , [r j ] 2 ))
where w 2 , . . . , w N ← Z k p and r j ← Z k p for all j ∈ [Q]. We claim that Game η.2 ≈ c Game η.3 . This follows from the simulation-based semi-adaptive security of Π ext with the fact f j (x * η ) 0+w η r = w η r. See Lemma 11 for more details.

Here we have Game

Lemmas

We prove the following lemmas showing the indistinguishability of adjacent games listed above. This completes the proof of Theorem 4.

Lemma 8 (Game 0 ≈ c Game 1 ). For all A, there exists B 1 with Time(B 1 ) ≈ Time(A) such that

|Adv 1 A (λ) -Adv 0 A (λ)| ≤ Adv Π ext B 1 (λ).
Proof. Recall that the difference lies in msk 1 , ct 1 and sk f j ,1 :

in Game 0 , we compute them by (Setup ext , Enc ext , KeyGen ext ) ; -in Game 1 , we compute them by (Setup * ext , Enc * ext , KeyGen * ext ) .

The lemma follows from the simulation-based semi-adaptive security of Π ext , cf. Section 4. The algorithm B 1 works as follows:

Initialize. Get mpk from the challenger, run

(mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n )
and return ( mpk,mpk 2 ) to A.

Challenge. On the challenge message

(x * 1 , z * 1 , . . . , x * N , z * N ) from A, pick w 2 , . . . , w N ← Z k p , submit (x * 1 , z * 1 -i ∈[2,N ] w i )
to the challenger and get ct.

Run ct i ← Enc ext (mpk 2 , (x * i , z * i w i )), ∀i ∈ [2, N ]
and return ct * = ( ct,ct 2 , . . . , ct N ) to A.

Key queries. On input the j -th key query f j , sample r j ← Z k p , and compute

sk f j ,2 ← KeyGen ext (msk 2 , ( f j , [r j ] 2 )).
Send a key query ( f j , [r j ] 2 ) to the challenger and get back sk j . Output sk when ( mpk, msk) = (mpk 1 , msk 1 )

f j = ( sk j , sk f j ,2 , [r j ] 2 ). Game ct * sk f Remark ct 1 ct i , 1 < i < η ct η ct i , η < i ≤ N sk f ,1 sk f ,2 0 real: x * 1 , z * 1 -w i real: x * i , z * i w i real: real: Real game 1 sim : x * 1 real: x * i , z * i w i sim : [ f (x * 1 ) z * 1 -w i r] 2 real: Π ext η.0 sim: x * 1 real: x * i , 0 w i real: x * η , z * η w η real: x * i , z * i w i sim: [ i <η f (x * i ) z * i -w i r] 2 real: η.1 sim: x * 1 real: x * i , 0 w i sim : x * η real: x * i , z * i w i sim: [ i <η f (x * i ) z * i -w i r] 2 sim : [ f (x * η ) z * η + w η r] 2 Π ext η.2 sim: x * 1 real: x * i , 0 w i sim: x * η real: x * i , z * i w i sim: [ i ≤η f (x * i ) z * i -w i r] 2 sim: [w η r] 2 MDDH η.3 sim: x * 1 real: x * i , 0 w i real : x * η , 0 w η real: x * i , z * i w i sim: [ i ≤η f (x * i ) z * i -w i r] 2 real : Π ext N .3 sim: x * 1 real: x * i , 0 w i sim: [ i ∈[N ] f (x * i ) z * i -w i r]
← Setup ext (1 λ , 1 n , 1 n ) and ct ← Enc ext (mpk 1 , (x * 1 , z * 1 -i ∈[2,N ] w i )) sk j ← KeyGen ext (msk 1 , ( f j , [r j ] 2 )) , ∀ j ∈ [Q]
the simulation is identical to Game 0 ; -when ( mpk, msk)

= (mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ) and ct ← Enc * ext (msk * 1 , x * 1 )
sk j ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ f j (x * 1 ) z * 1 -i ∈[2,N ] w i r j ] 2 , ∀ j ∈ [Q]
the simulation is identical to Game 1 .

This readily proves the lemma.

Lemma 9 (Game η.0 ≈ c Game η.1 ). For all A and all η ∈ [2, N ], there exists B 1 with Time(B 1 ) ≈ Time(A) such that

|Adv η.1 A (λ) -Adv η.0 A (λ)| ≤ Adv Π ext B 1 (λ).
Proof. Recall that the difference lies in msk 2 , ct η and sk f j ,1 :

in Game η.0 , we compute them by (Setup ext , Enc ext , KeyGen ext ) ;

in Game η.1 , we compute them by (Setup * ext , Enc * ext , KeyGen * ext ) .

The lemma follows from the simulation-based semi-adaptive security of Π ext , cf. Section 4. The algorithm B 1 works as follows:

Initialize. Get mpk from the challenger, run

(mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n )
and return (mpk 1 , mpk) to A.

Challenge. On input the challenge message

(x * 1 , z * 1 , . . . , x * N , z * N ) from A, pick w 2 , . . . , w N ← Z k p , submit (x * η , z * η w η ) to the challenger and get back ct. Compute ct * 1 ← Enc * ext (msk * 1 , x * 1 ); ct i ←          Enc ext (mpk 2 , (x * i , 0 w i )) i ∈ [2, η -1] ct i = η Enc ext (mpk 2 , (x * i , z * i w i )) i ∈ [η + 1, N ]
and output ct * = (ct * 1 , ct 2 , . . . , ct N ).

Key queries. On input the j -th key queries f j , sample r j ← Z k p and compute

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ i ∈[η-1] f j (x * i ) z * i -i ∈[2,N ] w i r j ] 2 .
Send a key query ( f j , [r j ] 2 ) to the challenger and get back sk j . Output sk f j = (sk * f j ,1 , sk j , [r j ] 2 ).

Analysis. Observe that, -when ( mpk, msk) = (mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n ) and

ct ← Enc ext (mpk 2 , (x * η , z * η w η )) , sk j ← KeyGen ext (msk 2 , ( f j , [r j ] 2 )) , ∀ j ∈ [Q]
the simulation is identical to Game η.0 ; -when ( mpk, msk)

= (mpk 2 , msk * 2 ) ← Setup * ext (1 λ , 1 n , 1 n ) and ct ← Enc * ext (msk * 2 , x * η ) , sk j ← KeyGen * ext (msk * 2 , x * η , ( f j , [r j ] 2 ), [ f j (x * η ) z * η + w η r j ] 2 ) , ∀ j ∈ [Q]
the simulation is identical to Game η.1 .

This readily proves the lemma.

A (λ) -Adv η.1 A (λ)| ≤ 2 • Adv MDDH 1 k,Q B 2 (λ)
where Q is the number of key queries.

Proof. Recall that the difference lies in sk * f j ,1 and sk * f j ,2 . We prove the lemma using Lemma 1 w.r.t. w η and f j (x * η ) z * η .

On input

([t j ,1 ] 2 , [t j ,2 ] 2 , [r j ] 2 ), the reduction B 2 sample w i ← Z k p for i ∈ [2, N ] \ {η} and run (mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ); (mpk 2 , msk * 2 ) ← Setup * ext (1 λ , 1 n , 1 n );
this allows us to simulate mpk and create challenge ciphertext. Here we crucially use the fact that we do not need w η when generating the ciphertext. For the j -th key queries f j , we compute

sk * f j ,1 ← KeyGen * ext msk * 1 , x * 1 , ( f j , [r j ] 2 ), [ i ∈[η-1] f j (x * i ) z * i -i ∈[2,N ]\{η} w i r j + t j ,1 ] 2 sk * f j ,2 ← KeyGen * ext (msk * 2 , x * η , ( f j , [r j ] 2 ), [t j ,2 ] 2 )
using the term in the input and output sk f j = (sk * f j ,1 , sk * f j ,2 , [r j ] 2 ). This proves the lemma.

Lemma 11 (Game η.2 ≈ c Game η.3 ). For all A and all η ∈ [2, N ], there exists B 1 with Time(B 1 ) ≈ Time(A) such that

|Adv η.3 A (λ) -Adv η.2 A (λ)| ≤ Adv Π ext B 1 (λ).
Proof. The proof is analogous to that for Lemma 9 with the following modifications: B 1 submits (x * η , 0 w η ) to the challenger during Challenge, so that

-when ( mpk, msk) = (mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n ) and ct ← Enc ext (mpk 2 , (x * η , 0 w η )) , sk j ← KeyGen ext (msk 2 , ( f j , [r j ] 2 )) , ∀ j ∈ [Q] the simulation is identical to Game η.3 ; -when ( mpk, msk) = (mpk 2 , msk * 2 ) ← Setup * ext (1 λ , 1 n , 1 n ) and ct ← Enc * ext (msk * 2 , x * η ) , sk j ← KeyGen * ext (msk * 2 , x * η , ( f j , [r j ] 2 ), [w η r j ] 2 ) , ∀ j ∈ [Q]
the simulation is identical to Game η.2 .

Π mcl : Multi-Client Scheme

In this section, we introduce the notion of multi-client unbounded-slot FE for attribute-weighted sums and provide a generic scheme Π mcl based on Π ext as in Π ubd . We refer the reader to Section 1.2 for a quick introduction.

Overview. For simplicity, we consider one client per slot, though the definition and the construction extend readily to the setting where there are fewer clients than slots, where the complexity of the one-time secret key generation grows only with the number of clients and not the number of slots.

Comparison with prior works. We proceed to comparisons with the notion of multi-client FE in prior works [START_REF] Goldwasser | Multi-input functional encryption[END_REF][START_REF] Abdalla | From single-input to multi-client inner-product functional encryption[END_REF][START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF]:

-Each client in our scheme does not have any long-term secret key for encryption from the authority; they merely see a mpk from the authority.

-Instead, a group of clients generate a set of one-time secret keys by themselves for each encryption; the distribution is independent of the databases and does not require interaction with the authority. We consider only static corruption of clients that leak the one-time key. -The one-time secret keys also rule out mix-and-match attacks amongst the ciphertexts, which limit the power of the adversary.

Overview of the construction. Roughly speaking, we would like to show that the unbounded-slot FE scheme Π ubd in the previous section satisfies the following property: for all S [N ], we can simulate mpk,ct,sk f , (w i ) i ∈S

given i ∉S f (x i ) z i .
That is, the leakage on (z i ) i ∉S is bounded by the attribute-weighted sums computed over these entries in the database. Turns out this is indeed true if 1 ∉ S so that w 1 remains hidden, via a straight-forward adaptation of the previous proof. To avoid this restriction on S, we need to modify the scheme to break the asymmetry of the construction w.r.t. the first slot.

Definition

A multi-client unbounded-slot FE for attribute-weighted sums is the same as an unbounded-slot FE for the same function class with the following changes:

-OTSKGen takes input 1 λ , 1 N and outputs (otsk i ) i ∈ [N ] .

-Enc takes input mpk,(x,z) and an additional input otsk.

-Dec takes input (sk f , f ) and (ct i , x i ) i ∈ [N ] .

Both correctness and security can be adapted from those for unbounded-slot FE, see below.

Correctness. For all N , (x i , z i ) i ∈ [N ] and for all f ∈ F ABP,n,n , we require

Pr        Dec((sk f , f ), (ct i , x i ) i ∈[N ] ) = N i =1 f (x i ) z i : (mpk, msk) ← Setup(1 λ , 1 n , 1 n ) (otsk i ) i ∈[N ] ← OTSKGen(1 λ , 1 N ) sk f ← KeyGen(msk, f ) ct i ← Enc(mpk,otsk i , (x i , z i )), i ∈ [N ]        = 1.
Security definition. We consider semi-adaptive, simulation-based security, which stipulates that there exists a randomized simulator (Setup * , OTSKGen * , Enc * , KeyGen * ) such that for every efficient stateful adversary A,

            (1 N , S) ← A(1 λ ); (mpk, msk) ← Setup(1 λ , 1 n , 1 n ); (x * i , z * i ) i ∉S ← A(mpk); (otsk i ) i ∈[N ] ← OTSKGen(1 λ , 1 N ); ct * i ← Enc(mpk,otsk i , (x * i , z * i )), i ∉ S; output A KeyGen(msk,•) ((otsk i ) i ∈S , (ct * i ) i ∉S )             ≈ c             (1 N , S) ← A(1 λ ); (mpk, msk * ) ← Setup * (1 λ , 1 n , 1 n , 1 N , S); (x * i , z * i ) i ∉S ← A(mpk); (otsk i ) i ∈S ← OTSKGen * (msk * ); (ct * i ) i ∉S ← Enc * (msk * , (x * i ) i ∉S ); output A KeyGen * (msk * ,(x * i ) i ∉S ,•,•) ((otsk i ) i ∈S , (ct * i ) i ∉S )            
such that whenever A makes a query f to KeyGen, the simulator KeyGen * gets f along with i ∉S f (x * i ) z * i . We use

Adv MCFE

A

(λ) to denote the advantage in distinguishing the real and ideal games.

Construction

Scheme. Assume Π ext = (Setup ext , Enc ext , KeyGen ext , Dec ext ) be the extended one-slot scheme in Section 6. Our multi-client unbounded-slot FE Π mcl is similar to Π ubd in Section 7:

-Setup,KeyGen as in Π ubd .

-OTSKGen(1 λ , 1 N ): Sample w i ← Z k p for all i ∈ [N ] subject to the constraint i ∈ [N ] w i = 0 and output

(otsk i = w i ) i ∈[N ] .
-Enc(mpk,otsk,(x,z)): Parse otsk = w. Sample z ← Z n p , w ← Z k p and compute

ct 1 ← Enc ext (mpk 1 , (x, z w )) ct 2 ← Enc ext (mpk 2 , (x, z -z w -w ))
and output ct = (ct 1 , ct 2 ) and x.

-Dec((sk f , f ), (ct i , x i ) i ∈ [N ] ): Parse ciphertext and key as

sk f = (sk f ,1 , sk f ,2 , [r] 2 ) and ct i = (ct i ,1 , ct i ,2 ), ∀i ∈ [N ].
We proceed as follows:

1. For all i ∈ [N ], compute

[D i ,1 ] T ← Dec ext (sk f ,1 , ( f , [r] 2 )), (ct i ,1 , x i ) ; [D i ,2 ] T ← Dec ext (sk f ,2 , ( f , [r] 2 )), (ct i ,2 , x i ) ; 2. Compute [D] T = i ∈[N ] ([D i ,1 ] T • [D i ,2 ] T )
and output D via brute-force discrete log.

Correctness. Correctness uses

i ∈[N ] f (x i ) z i = i ∈[N ] D i ,1 f (x i ) z i + (w i ) r + D i ,2 f (x i ) (z i -z i ) + (w i -w i )r
which in turn uses w i = 0.

Security. We prove the following theorem.

Theorem 5. Assume that extended one-slot scheme Π ext achieves simulation-based semi-adaptive security, our multiclient unbounded-slot FE scheme Π mcl described in this section achieves simulation-based semi-adaptive security under the k-Linear assumption in G 2 .

Both simulator and proof are analogous to those of Π ubd in Section 7 with a high-level idea as follows. WLOG, assume S = [N ] for some N < N . We can rewrite ct 1 = (ct 1,1 , ct 1,2 ) as Enc ext (mpk 1 , (x * by relying on the entropy in z 1 , w 1 . For notational simplicity, for the rest of the overview, we assume w i = 0 and z i = 0 for all i ∈ S; the general case follows readily. That is, we only rely on the entropy in the (z i , w i )'s to rewrite ct 1 = (ct 1,1 , ct 1,2 ).

We now have:

ct * i = (ct * i ,1 , ct * i ,2 ) = Enc ext (mpk 1 , (x * 1 , z * 1 w 1 )), Enc ext (mpk 2 , (x * 1 , 0 0)) i = 1 Enc ext (mpk 1 , (x * i , 0 0)), Enc ext (mpk 2 , (x * i , z * i w i )) 1 < i ≤ N
We can then basically follow the idea for Π ubd in Section 7 by the following observation:

ct * 1,1 = Enc ext (mpk 1 , (x * 1 , z * 1 w 1 )), {ct * i ,2 = Enc ext (mpk 2 , (x * i , z * i w i ))} 1<i ≤N
looks like a ciphertext in Π ubd and KeyGen is exactly the same as in Π ubd . We note that:

in the simulator and throughout the proof, we don't change

ct * 1,2 = Enc ext (mpk 2 , (x * 1 , 0 0)), {ct * i ,1 = Enc ext (mpk 1 , (x * i , 0 0))} 1<i ≤N ;
and the reduction can always simulate them using mpk 1 , mpk 2 ;

-As before, the proof also use the fact that for all i ∈ [2, N ] and µ ∈ Z p , it holds that

{[-w i r j ] 2 , [µ + w i r j ] 2 , [r j ] 2 } j ∈[Q] ≈ c {[µ -w i r j ] 2 , [w i r j ] 2 , [r j ] 2 } j ∈[Q]
here we crucially relies on the fact that i ∉ S and w i is not leaked to the adversary; otherwise the above statement does not hold.

In the actual proof with general S, instead of enumerating over i ∈ [2, N ] in the games, we enumerate i ∈ S \{i * } where i * = min{ S}.

Simulator

Let S be the set indicating corrupted clients and i * := min{ S}, that is, the smallest value outside S. (Simulation is trivial if S = [N ].) We describe the simulator for Π mcl using the simulator for Π ext , i.e., (Setup * ext , Enc * ext , KeyGen * ext ), as in Section 7.2; also, the adversary needs to commit to the length N in advance.

-Setup * (1 λ , 1 n , 1 n , 1 N , S): Sample z 1 , . . . , z N ← Z n p , w 1 , . . . , w N ← Z k p and w 1 , . . . , w N ← Z k p such that i ∈[N ] w i = 0; run (mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ); (mpk 2 , msk 2 ) ← Setup ext (1 λ , 1 n , 1 n ) and output mpk = (mpk 1 , mpk 2 ) and msk * = (msk * 1 , msk 2 , (w i , w i , z i ) i ∈[N ] , S). -OTSKGen * (msk * ): Parse msk * = (msk * 1 , msk 2 , (w i , w i , z i ) i ∈[N ] , S) and output (otsk i = w i ) i ∈S . -Enc * (msk * , (x * i ) i ∉S ): Compute ct * i * ,1 ← Enc * ext (msk * 1 , x * i * ), ct * i * ,2 ← Enc ext (mpk 2 , (x * i * , z i * w i * )), ct * i ,1 ← Enc ext (mpk 1 , (x * i , z i w i )), ct * i ,2 ← Enc ext (mpk 2 , (x * i , -z i w i -w i )), ∀ i ∈ S \ {i * } and output (ct * i = (ct * i ,1 , ct * i ,2 )) i ∈ S and (x * i ) i ∈ S . -KeyGen * (msk * , (x * i ) i ∉S , f , µ ∈ Z p ): Pick r ← Z k p , compute sk * f ,1 ← KeyGen * ext msk * 1 , x * i * , ( f , [r] 2 ), [µ -f (x * i * ) z i * -w i * r -i ∈[N ]\{i * } w i r] 2 sk f ,2 ← KeyGen ext (msk 2 , ( f , [r] 2 ))
and output

sk * f = (sk * f ,1 , sk f ,2 , [r]
2 ) and f .

Remark 4 (decryption).

Observe that when we decrypt the simulated ciphertexts:

(ct * i ,1 , ct * i ,2 ) i ∈ S ← Enc * (msk * , (x * i ) i ∉S ) and (ct * i ,1 , ct * i ,2 ) ← Enc(mpk,otsk i , (x * i , z * i )), ∀i ∈ S with the simulated secret key (sk * f ,1 , sk * f ,2 , [r] 2 ) ← KeyGen * (msk * , (x * i ) i ∉S , f , i ∉S f (x * i ) z * i ), we get D i * ,1 = i ∉S f (x i ) z * i -f (x * i * ) z i * + (w i * -w i * ) r, D i * ,2 = f (x * i * ) z i * + (w i * ) r, D i ,1 = f (x * i ) z i + (w i ) r, D i ,2 = -f (x * i ) z i + (w i -w i ) r, ∀ i ∈ S \ {i * } D i ,1 = f (x * i ) z i + (w i ) r, D i ,2 = f (x * i ) (z * i -z i ) + (w i -w i ) r, ∀ i ∈ S
and end up with

D = i ∈[N ] (D i ,1 + D i ,2 ) = i ∈[N ] f (x * i ) z * i + i ∈[N ] w i r = i ∈[N ] f (x * i ) z * i
Furthermore, with the corruption of (otsk i = w i ) i ∈S , we can recover i ∉S

(D i ,1 + D i ,2 ) + i ∈S w i r = ( i ∉S f (x * i ) z * i + i ∉S w i r) + i ∈S w i r = i ∉S f (x * i ) z * i
Similarly, when we decrypt normal ciphertexts

(ct i ,1 , ct i ,2 ) ← Enc(mpk,otsk i , (x * i , z * i )), ∀i ∈ [N ]
with the simulated secret key (sk * f ,1 , sk * f ,2 , [r] 2 ), we get

D i ,1 = f (x * i ) z i + (w i ) r, D i ,2 = f (x * i ) (z * i -z i ) + (w i -w i ) r, ∀ i ∈ [N ]
and end up with i ∈

[N ] f (x * i ) z * i .

Proof sketch

Let S [N ] be the set of corrupted clients and i * := min{ S}, that is, the smallest value outside S. We use (x * i , z * i ) i ∉S to denote the challenge. Our proof basically follows the proof for Π ubd in Section 7 with an extra games and some modifications below. Also see a summary of game sequence in Fig 5 .   An extra game: Game 0 . After Game 0 , we introduce an extra game where we generate ct * i * = (ct i * ,1 , ct i * ,2 ) as follows:

ct i * ,1 ← Enc ext (mpk 1 , (x * i * , z * i * -z i * w i * -w i * )), ct i * ,2 ← Enc ext (mpk 2 , (x i * , z i * w i * )) instead of ct i * ,1 ← Enc ext (mpk 1 , (x * i * , z i * w i * )), ct i * ,2 ← Enc ext (mpk 2 , (x * i * , z * i * -z i * w i * -w i * ))
We can show Game 0 ≈ s Game 0 by the change of variables:

z i * → z * i * -z i * and w i * → w i * -w i * .
Modifications. Now we have Game sequence for Π mcl over η ∈ S \ {i * } in an ascending order where i * = min{ S}. Each cell has two rows corresponding to ct i ,1 and ct i ,2 , respectively. Each row is in the format "xxx:yyy" where xxx ∈ {real, sim} indicates whether the ciphertext/key component is generated using real algorithm or simulator and yyy gives out the information fed to algorithm/simulator. Throughout, the first input to KeyGen ext / KeyGen * ext for generating sk f ,1 is ( f , [r] 2 ); the same applies to sk f ,2 ; the sum of w i r is always over i ∈ [N ] \ {i * }.

ct * i = ct i * ,1 ← Enc ext (mpk 1 , (x * i * , z * i * -z i * w i * -w i * )), ct i * ,2 ← Enc ext (mpk 2 , (x * i * , z i * w i * )) i = i * ct i ,1 ← Enc ext (mpk 1 , (x * i , z i w i )), ct i ,2 ← Enc ext (mpk 2 , (x * i , z * i -z i w i -w i )) i ∈ S \

A Partial Garbling

The following is a restatement of the partial garbling schemes in [START_REF] Ishai | Partial garbling schemes and their applications[END_REF][START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] using our notation.

Basic lemma. We review the following lemma for f (x) z with f ∈ F ABP,n,n which is a subclass of ABP; this shows that we can use the computation of determinant to model the computation of f (x) z. Specifically, L x,z is obtained by removing the column corresponding to v 0 and the row corresponding to v 1 in the matrix A -I where A is the adjacency matrix of ABP.

In particular, the matrix L x,z has the following form where we have an affine function in x for each * :

L x,z =                
-1 z n                 
We use L x to denote the matrix obtained by removing the last column from L x,z . Note that L x only depends on x and f ∈ F ABP,n,n .

Partial Garbling Scheme. We now review the partial garbling scheme [START_REF] Ishai | Partial garbling schemes and their applications[END_REF][START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] for f (x) z. We first introduce a family of matrices of dimension m + n : The partial garbling scheme is as follows:

partial garbling for f , x, z: p f ,x,z = L x,z t 1 [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] with random coin t ← Z m+n -1 p . -reconstruction: we can recover f (x) z by computing det L x |p f ,x,z ) since det L x |p f ,x,z ) = det L x,z T = det L x,z = f (x) z [START_REF] Ishai | Perfect constant-round secure computation via perfect randomizing polynomials[END_REF] for some T ∈ T; here we rely on the property 1 and Lemma 12.

privacy: given f (x) z, we simulate

(L x |e 1 • f (x) z) t 1 , t ← Z m+n -1 p . ( 30
)
Here we rely on property 2, 3 and Lemma 12.

Fig. 1 .

 1 Fig. 1. Comparison of prior public-key schemes with our construction for N = 1. Throughout, x is public and z, z 1 , z 2 are private, and |ct| omits the contribution from x.

Fig. 3 .

 3 Fig. 3. Summary of game sequence for N = 3. In the figure, SIM-b ≈ c indicates that this step uses the simulate-based semi-adaptive

  Fig 3 where in DDH ≈ c , we use pseudorandomness of ([w 1 r ] 2 , [r ] 2 ) and ([w 2 r ] 2 , [r ] 2 ) respectively; in SIM-1 ≈ c and SIM-2

  1 and msk * = W, U, V, w, v, c, C ⊥ , A, a ⊥ where (A|c) (C ⊥ |a ⊥ ) = I k+1 . Here we assume that (A|c) has full rank, which happens with probability 1 -1/p. -Enc * (msk * , x * ): Output ct * = [c ] 1 , [ w ] 1 , [ v ] 1 and x * . -KeyGen * (msk * , x * , f , µ ∈ Z p ): Run (L 1 , L 0 ) ← lgen(f ) and ((p * 1 ) , (p * 2 ) ) ← pgb * ( f , x * , µ). Sample û ← Z nm p , T ← Z (k+1)×(m+n -1) p and R ← Z k×m p and output

  * x * ← Enc * (msk * , x * ) with the simulated secret key sk * f ← KeyGen * (msk * , x * , f , f (x * ) z * ), the sk * f [1] part cancels out and leaves just the sk * f [2] part since c C ⊥ = 0, c a ⊥ = 1 and we end up with ((p * 1 ) , (p * 2 ) )d f ,x * = f (x * ) z * where ((p * 1 ) , (p *

-

  KeyGen(msk,( f , [r] 2 )): Run (L 1 , L 0 ) ← lgen(f ) where L 1 ∈ Z (m+n -1)×mn p , L 0 ∈ Z (m+n -1)×m p (cf. Section 4.2). Sample T ← Z (k+1)×(m+n -1)p and R ← Z k×m p and output9

  2.0 = Game 1 and Game η.0 = Game η-1.3 for all η ∈ [3, N ]. Note that Game N .3 corresponds to the output of the simulator in the ideal game. We summarize the game sequence in Fig 4.

Fig. 4 .

 4 Fig.4. Game sequence for Π ubd with η ∈[2, N ], where Game 2.0 = Game 1 , Game 3.0 = Game 2,3 , . . . , Game N ,0 = Game N -1,3 . Each cell is in the format "xxx:yyy" where xxx ∈ {real, sim} indicates whether the ciphertext/key component is generated using real algorithm or simulator and yyy gives out the information fed to algorithm/simulator. Throughout, the first input to KeyGen ext / KeyGen * ext for generating sk f ,1 is ( f , [r] 2 ); the same applies to sk f ,2 . The sum of w i r is always over i ∈ [2, N ].

Fig. 5 .

 5 Fig.5. Game sequence for Π mcl over η ∈ S \ {i * } in an ascending order where i * = min{ S}. Each cell has two rows corresponding to ct i ,1 and ct i ,2 , respectively. Each row is in the format "xxx:yyy" where xxx ∈ {real, sim} indicates whether the ciphertext/key component is generated using real algorithm or simulator and yyy gives out the information fed to algorithm/simulator. Throughout, the first input to KeyGen ext / KeyGen * ext for generating sk f ,1 is ( f , [r] 2 ); the same applies to sk f ,2 ; the sum of w i r is always over i ∈[N ] \ {i * }.

Lemma 12 (

 12 [START_REF] Ishai | Perfect constant-round secure computation via perfect randomizing polynomials[END_REF][START_REF] Ishai | Partial garbling schemes and their applications[END_REF]). Given f ∈ F ABP,n,n and (x, z) ∈ Z n p ×Z n p , we can efficiently compute a matrix L x,z ∈ Z (m+n )×(m+n ) p over Z p with m depending on f such thatdet L x,z = f (x) z;each entry of L x,z is an affine function in x, z; -L x,z contains only -1's in the second diagonal and 0's below the second diagonal.

T = I m+n -1 t 1 : t ∈ Z m+n - 1 p 1 p} ≡ s { t 1 : t ← Z m+n - 1 p }; 3 .

 111113 and state the following properties:1. ∀ T ∈ T, we have det(T) = 1; 2. ∀ T ∈ T, we have {T t 1 : t ← Z m+n -∃ T ∈ T such that L x,z T = (L x |e 1 • f (x) z) for L x,z shown above.

  Summary of ciphertext and key sizes of our one-slot scheme Π one and unbounded-slot scheme Π ubd . Recall that n = |x| = |x i |, n = |z| = |z i |, m is proportional to the size of f and N is the number of slots. In the table, we count the number of group elements in G 1 (resp. G 2 ) in the column |ct| (resp. column |sk|). Note that SXDH=1-Lin.

	Scheme	|ct|	|sk|	Assumption
	Π one ( § 5)	n + 2k + 1	(k + 1)nm + (2k + 1)m + (k + 1)n	k-Lin
		n + 3	2nm + 3m + 2n	SXDH
	Π ubd ( § 7, § B) n N + (3k + 1)N	(2k + 2)nm + (4k + 2)m + (2k + 2)n + k	k-Lin
		n N + 4N	4nm + 6m + 4n + 1	SXDH
	Fig. 2.

  11 x 1 + a 12 x 2 + b 1 , a 21 x 1 + a 22 x 2 + b 2 , a 31 x 1 + a 32 x 2 + b 3 = (a 11 , a 21 , a 31 , a 12 , a 22 , a 32 ) x 1 x 2

  Lemma 10 (Game η.1 ≈ c Game η.2 ). For all A and all η ∈ [2, N ], there exists B 2 with Time(B 2 ) ≈ Time(A) such that

	|Adv	η.2

  {i * } and then our game sequence mirrors that for Π ubd in Section 7: we have -Game i * in the place of Game 1 ; and -Game η.0 , Game η.1 , Game η.2 , Game η.[START_REF] Abdalla | Simple functional encryption schemes for inner products[END_REF] enumerating over η ∉ S \ {i * } instead of η ∈ [2, N ].Among all games, we make changes to master key pair ((mpk 1 , mpk 2 ), (msk 1 , msk 2 )), secret keys sk f j = (sk f j ,1 , sk f j ,2 ) and (ct i * ,1 , (ct i ,2 ) i ∈ S\{i * } ) which involves (x * i , z * i ) i ∉S ; note that, we will never change (ct i * ,2 , (ct i ,1 ) i ∈ S\{i * } ). In more detail,in Game i * , we have (mpk 1 , msk * 1 ) ← Setup * ext (1 λ , 1 n , 1 n ) and compute )), sk f j ,1 ← KeyGen ext (msk 1 , ( f j , [r] 2 ))The simulation-based security of Π ext ensures that Game 0 ≈ c Game i * . The proof is analogous to that of Lemma 8.in Game η.0 , we compute ct i ,2 ← Enc ext (mpk 2 , (x * KeyGen ext (msk 2 , ( f j , [r] 2 ))The simulation-based security of Π ext ensures that Game η.0 ≈ c Game η.1 . The proof is analogous to that of Lemma 9. -in Game η.2 , we computesk f j ,1 ← KeyGen * ext msk * 1 , x * i * , ( f j , [r j ] 2 ), [ i ∉S,i ≤η f j (x * i ) z * if j (x * i * ) z i * -(w i * ) ri ∈[N ]\{i * } w i r] 2 sk f j ,2 ← KeyGen * ext msk * 2 , x * η , ( f j , [r j ] 2 ), [f j (x * η ) z η + w η r -(w η ) r ] 2We have Game η.1 ≈ s Game η.2 . This follows from[START_REF] Goyal | Semi-adaptive security and bundling functionalities made generic and easy[END_REF] as in Section 7. Here we crucially use the fact that w η is not leaked to the adversary; the statement (27) does not hold for w i with i ∈ S.in Game η.3 , we have (mpk 2 , msk 2 ) ← Setup * ext (1 λ , 1 n , 1 n ) and compute ct η,2 ← Enc ext (mpk 2 , (x * η , -z η w ηw η )), sk f j ,2 ← KeyGen ext (msk 2 , ( f j , [r] 2 )) We have Game η.2 ≈ Game η.3 and the proof is analogous to that for Game η.1 ≈ Game η.2 from the simulation-based security of Π ext . Note that, in the proof, the reduction always knows (x * ,1 ct i ,1 , i ∈ S \ {i * }, i < η ct η,1 ct i ,1 , i ∈ S \ {i * }, i > η sk f ,1 z i * w i *w i * real: x * i , z * iz i w iw i

	0 0	ct i * 1 ← Enc * ext (msk * 1 , x * ct η,2 i , z i w i real: x * ct i ,2 i real: ct i * ,2 ct i ,2 real: x * i * , z i * w i * real: real: x * i Remark sk f ,2 Real game real: x * i

* ),

sk f j ,1 ← KeyGen * ext msk * 1 , x * i * , ( f j , [r j ] 2 ), [ f j (x * i * ) z * i *f j (x * i * ) z i * + w i * r -(w i * ) r] 2

instead of having (mpk 1 , msk 1 ) ← Setup * ext (1 λ , 1 n , 1 n ) and computing

ct i * 1 ← Enc ext (mpk 1 , (x * i * , z * i * -z i * w i * -w i * i , -z i w iw i )), ∀i ∉ S ∧ i < η sk f j ,1 ← KeyGen * ext msk * 1 , x * i * , ( f j , [r j ] 2 ), [ i ∉S,i <η f j (x * i ) z * if j (x * i * ) z i * -(w i * ) ri ∈[N ]\{i * } w i r] 2 -in Game η.1 , we have (mpk 2 , msk * 2 ) ← Setup * ext (1 λ , 1 n , 1 n ) and compute ct η,2 ← Enc * ext (msk * 2 , x * η ), sk f j ,2 ← KeyGen * ext msk * 2 , x * η , ( f j , [r j ] 2 ), [ f j (x * η ) z * ηf j (x * η ) z η + w η r -(w η ) r] 2 instead of having (mpk 2 , msk 2 ) ← Setup * ext (1 λ , 1 n , 1 n ) and computing ct η,2 ← Enc ext (mpk 2 , (x * η , z * ηz η w ηw η )), sk f j ,2 ← i , z i , w i ) i ∈[N ]

and can simulate (ct i * ,2 , (ct i ,1 ) i ∈ S\{i * } ) using (mpk 1 , mpk 2 ).

Game

ct i * * , z * i * * , z * i *z i * w i *w i * real: x * i , z i w i real: change of variables real: x * i * , z i * w i * real: x * i , z * iz i w iw i real: i * sim : x * i * real: x * i , z i w i sim : [ f (x * i * ) z * i * -δw i r] 2 δ = f (x * i * ) z i * + (w i * ) r real: x * i * , z i * w i * real: x * i , z * iz i w iw i real: Π ext η.0 sim: x * i * real: x * i , z i w i real: x * η , z η w η real: x * i , z i w i sim: [ i ∉S,i <η f (x * i ) z * i -δw i r] 2 real: x * i * , z i * w i * real: x * i , -z i w iw i real: x * η , z * ηz η w ηw η real: x * i , z * iz i w iw i real: η.1 sim: x * i * real: x * i , z i w i real: x * η , z η w η real: x * i , z i w i sim: [ i ∉S,i <η f (x * i ) z * i -δw i r] 2 Π ext real: x * i * , z i * w i * real: x * i , -z i w iw i sim : x * η real: x * i , z * iz i w iw i sim : [ f (x * η ) z * ηf (x * η ) z η -(w η ) r + w η r] 2 η.2 sim: x * i * real: x * i , z i w i real: x * η , z η w η real: x * i , z i w i sim: [ i ∉S,i ≤η f (x * i ) z * i -δw i r] 2 MDDH real: x * i * , z i * w i * real: x * i , -z i w iw i sim: x * η real: x * i , z * iz i w iw i sim: [f (x * η ) z η -(w η ) r + w η r ] 2 η.3 sim: x * i * real: x * i , z i w i real: x * η , z η w η real: x * i , z i w i sim: [ i ∉S,i ≤η f (x * i ) z * i -δw i r] 2 Π ext real: x * i * , z i * w i * real: x * i , -z i w iw i real : x * η , -z η w ηw η real: x * i ,

z * iz i w iw i real : max{ S}.3 sim: x * i * real: x * i , z i w i sim: [ i ∉S f (x * i ) z * i -δw i r] 2 δ = f (x * i * ) z i * + (w i * ) r real: x * i * , z i * w i * real: x * i , -z i w iw i real: Simulator

We actually achieve semi-adaptive security[START_REF] Chen | Semi-adaptive attribute-based encryption and improved delegation for Boolean formula[END_REF], a slight strengthening of selective security.

Note that we can also capture the same class with a quadratic blow-up in ciphertext size.

The scheme in[START_REF] Wee | Attribute-hiding predicate encryption in bilinear groups, revisited[END_REF] has a larger ciphertext of the form:ct x,z = [s] 1 , [z + sw] 1 , [s(u + vx)] 1 ∈ G n+n +1 1 .

Recall that if we write u = (u 1 , . . . , u n ), then u (I n ⊗ r ) = (u 1 r , . . . , u n r ).

except that, for the j -th query f j , we compute

We use r instead of [r] 2 in the subscript here and note that the function is described by ( f , [r] 2 ) rather than ( f , r).

, z * 1z 1 w 1w 1 )), Enc ext (mpk

, (x * 1 , z 1 w 1 ))

Client Scheme, 28 §A. Partial Garbling, 37 §B. Concrete instantiation of Π ubd in Section 7, 38 Supported by ERC Project aSCEND (H2020 639554) and the French FUI project ANBLIC. Supported by NSFC-ISF Joint Scientific Research Program (61961146004) and the ERC Project aSCEND (H2020 639554). Part of this work was done while at ENS, Paris. Supported in part by ERC Project aSCEND (H2020 639554).

Analysis

The proof of correctness and security are the same as before in [START_REF] Baltico | Practical functional encryption for quadratic functions with applications to predicate encryption[END_REF] and Lemma 4,6, with the following modifications (indicated by the boxes):

-In the proof of correctness, we have

and we rely on reconstruction with shift w r.

-In Lemma 5, we also use

-Game 3 , we have:

-Game 4 , we have:

-In Lemma 7, recall that the difference between the two games lies in sk f j ,r j [START_REF] Abdalla | Decentralizing inner-product functional encryption[END_REF]:

where we use

in Game 4

pgb * ( f j , x * , f j (x * ) z * + (w * ) r j ; tj ) in Game 5

Π ubd : Unbounded-Slot Scheme

In this section, we describe our unbounded-slot FE scheme. We give a generic transformation from scheme Π ext in Section 6 and present a self-contained description of the scheme in Section B.

Scheme

Let Π ext = (Setup ext , Enc ext , KeyGen ext , Dec ext ) be the extended one-slot FE scheme in Section 6. Our unbounded-slot FE scheme Π ubd is as follows:

-

and output mpk = (mpk 1 , mpk 2 ) and msk = (msk 1 , msk 2 ).

-Enc(mpk,(

Algorithm lgen and pgb,pgb * . Let -L x ∈ Z m×(m+n -1) p be the matrix obtained by removing the last n rows from L x ; -t ∈ Z n p is a vector consisting of the last n entries of t;

we can rewrite

Here we also make a transpose for notational convenience in the context of functional encryptions. Furthermore, since each entry in L x is an affine function in x, we can write

where L 1 is formed from n matrices of size (m +n -1)×m, the i th of which consists of coefficients of x i in each entries of L x and L 0 includes the constant term in each entry. Note that L 1 and L 0 only depend on f . In Lemma 2, we let lgen output the input-independent matrices L 1 , L 0 on input f ; -pgb,pgb * output ( 28) and ( 30) using L 1 , L 0 applying ( 31) and [START_REF] Jain | Simplifying constructions and assumptions for i O[END_REF].

Then, it is straightforward to verify the privacy of our extension with shift in Section 4.2 from concrete expressions.

Algorithm rec. Computing det L x |p f ,x,z ) in ( 29) for reconstruction is computing a linear function in p f ,x,z by cofactor expansion. In Lemma 2, we let rec output this linear function, represented by a vector d f ,x , and we have p f ,x,z d f ,x = f (x) z. Furthermore, it is not hard to see that (0, e 1 )d f ,x = 1 which is sufficient to verify the reconstruction of our extension with shift in Section 4.2.

B Concrete instantiation of Π ubd in Section 7

We show the concrete instantiation of Π ubd in Section 7 with our concrete scheme Π ext in Section 6.

-

and output

-KeyGen(msk, f ): Run (L 1 , L 0 ) ← lgen(f ) where