Benoît Libert

Amin Sakzad

Damien Stehlé

Ron Steinfeld

All-But-Many Lossy Trapdoor Functions and Selective Opening Chosen-Ciphertext Security from LWE

Keywords: lossy trapdoor functions, chosen-ciphertext security, selective-opening security, tight security reductions

Selective opening (SO) security refers to adversaries that receive a number of ciphertexts and, after having corrupted a subset of the senders (thus obtaining the plaintexts and the senders' random coins), aim at breaking the security of remaining ciphertexts. So far, very few public-key encryption schemes are known to provide simulation-based selective opening (SIM-SO-CCA2) security under chosen-ciphertext attacks and most of them encrypt messages bit-wise. The only exceptions to date rely on all-but-many lossy trapdoor functions (as introduced by Hofheinz; Eurocrypt'12) and the Composite Residuosity assumption. In this paper, we describe the first all-but-many lossy trapdoor function with security relying on the presumed hardness of the Learning-With-Errors problem (LWE) with standard parameters. Our construction exploits homomorphic computations on lattice trapdoors for lossy LWE matrices. By carefully embedding a lattice trapdoor in lossy public keys, we are able to prove SIM-SO-CCA2 security under the LWE assumption. As a result of independent interest, we describe a variant of our scheme whose multi-challenge CCA2 security tightly relates to the hardness of LWE and the security of a pseudo-random function.

Keywords. LWE,

Introduction

Lossy Trapdoor Functions. As introduced by Peikert and Waters [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], lossy tradpoor functions (LTFs) are function families where injective functions -which can be inverted using a trapdoor -are indistinguishable from lossy functions, where the image is much smaller than the domain. The last decade, they received continuous attention (see, e.g., [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF][START_REF] Hemenway | Extended-DDH and lossy trapdoor functions[END_REF][START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF][START_REF] Wee | Dual projective hashing and its applications -lossy trapdoor functions and more[END_REF][START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF][START_REF] Zhandry | The magic of ELFs[END_REF]) and found many amazing applications in cryptography. These include black-box realizations of cryptosystems with chosen-ciphertext (IND-CCA2) security [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], deterministic public-key encryption in the standard model [START_REF] Boldyreva | On notions of security for deterministic encryption, and efficient constructions without random oracles[END_REF][START_REF] Brakerski | Better security for deterministic public-key encryption: The auxiliary-input setting[END_REF][START_REF] Raghunathan | Deterministic public-key encryption for adaptively chosen plaintext distributions[END_REF] and encryption schemes retaining some security in the absence of reliable randomness [START_REF] Bellare | Hedged public-key encryption: How to protect against bad randomness[END_REF][START_REF] Bellare | Resisting randomness subversion: Fast deterministic and hedged public-key encryption in the standard model[END_REF]. As another prominent application, they enabled the design [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF][START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF] of encryption schemes secure against selective-opening (SO) adversaries, thereby providing an elegant solution to a 10 year-old problem raised by Dwork et al. [START_REF] Dwork | Magic functions[END_REF].

When it comes to constructing CCA2-secure [START_REF] Rackoff | Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack[END_REF] encryption schemes, LTFs are often combined with all-but-one trapdoor functions (ABO-LTFs) [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], which enable a variant of the two-key simulation paradigm [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF] in the security proof. In ABO-LTF families, each function takes as arguments an input x and a tag t in such a way that the function f abo (t, •) is injective for any t, except a special tag t * for which f abo (t * , •) behaves as a lossy function. In the security proof of [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], the lossy tag t * is used to compute the challenge ciphertext, whereas decryption queries are handled by inverting f abo (t, •) for all injective tags t = t . One limitation of ABO-LTFs is the uniqueness of the lossy tag t which must be determined at key generation time. As such, ABO-LTFs are in fact insufficient to prove security in attack models that inherently involve multiple challenge ciphertexts: examples include the keydependent message [START_REF] Black | Encryption-scheme security in the presence of key-dependent messages[END_REF] and selective opening [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] settings, where multi-challenge security does not reduce to single-challenge security via the usual hybrid argument [START_REF] Bellare | Public-key encryption in a multi-user setting: Security proofs and improvements[END_REF].

To overcome the aforementioned shortcoming, Hofheinz [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF] introduced all-but-many lossy trapdoor functions (ABM-LTFs) which extend ABO-LTFs by allowing the security proof to dynamically create arbitrarily many lossy tags using a trapdoor. Each tag t = (t c , t a ) is comprised of an auxiliary component t a and a core component t c so that, by generating t c as a suitable function of t a , the reduction is able to assign a lossy (but random-looking) tag to each challenge ciphertext while making sure that the adversary will be unable to create lossy tags by itself in decryption queries. Using carefully designed ABM-LTFs and variants thereof [START_REF] Hofheinz | Circular chosen-ciphertext security with compact ciphertexts[END_REF], Hofheinz gave several constructions [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF][START_REF] Hofheinz | Circular chosen-ciphertext security with compact ciphertexts[END_REF] of public-key encryption schemes in scenarios involving multiple challenge ciphertexts.

Selective Opening Security. In the context of public-key encryption, selective opening (SO) attacks take place in a scenario involving a receiver and N senders. Those encrypt possibly correlated messages (Msg 1 , . . . , Msg N ) under the receiver's public key P K and, upon receiving the ciphertexts (C 1 , . . . , C N ), the adversary decides to corrupt a subset of the senders. Namely, by choosing I ⊂ [N ], it obtains the messages {Msg i } i∈I as well as the random coins {r i } i∈I for which C i = Encrypt(P K, Msg i , r i ). Then, the adversary aims at breaking the security of unopened ciphertexts {C i } i∈[N ]\I . It is tempting to believe that standard notions like semantic security carry over to such adversaries due to the independence of random coins {r i } i∈ [N ] . However, this is not true in general [START_REF] Canetti | Adaptively secure multi-party computation[END_REF] as even the strong standard notion of IND-CCA security [START_REF] Rackoff | Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack[END_REF] was shown [START_REF] Bellare | Standard security does not imply security against selectiveopening[END_REF][START_REF] Hofheinz | Standard security does not imply indistinguishability under selective opening[END_REF] not to guarantee anything under selective openings. Proving SO security turns out to be a challenging task for two main reasons. The first one is that the adversary must also obtain the random coins {r i } i∈I of opened ciphertexts (and not only the underlying plaintexts) as reliably erasing them can be very difficult in practice. Note that having the reduction guess the set I of corrupted senders beforehand is not an option since it is only possible with negligible probability 1/ N N/2 . The second difficulty arises from the potential correlation between {Msg i } i∈I and {Msg i } i∈[N ]\I , which hinders the use of standard proof techniques and already makes selective opening security non-trivial to formalize.

Towards defining SO security, the indistinguishability-based (IND-SO) approach [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF][START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF] demands that unopened plaintexts {Msg i } i∈[N ]\I be indistinguishable from independently resampled ones {Msg i } i∈[N ]\I conditionally on the adversary's view. However, such definitions are not fully satisfactory. Since {Msg i } i∈[N ] may be correlated, the resampling of {Msg i } i∈[N ]\I must be conditioned on {Msg i } i∈I to make the adversary's task non-trivial. This implies that, in the security experiment, the challenger can only be efficient for message distributions that admit efficient conditional resampling, which is a much stronger restriction than efficient samplability. Indeed, many natural message distributions (e.g., where some messages are hard-to-invert functions of other messages) do not support efficient conditional resampling.

Our contribution is three-fold. We first provide an all-but-many lossy trapdoor function based on the Learning-With-Errors (LWE) assumption [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. We tightly relate the security of our ABM-LTF to that of the underlying PRF and the hardness of the LWE problem.

As a second result, we use our ABM-LTF to pave the way towards public-key encryption schemes with tight (or, more precisely, almost tight in the terminology of [START_REF] Chen | Fully, (almost) tightly secure ibe and dual system groups[END_REF]) chosenciphertext security in the multi-challenge setting [START_REF] Bellare | Public-key encryption in a multi-user setting: Security proofs and improvements[END_REF]. By "tight CCA security", as in [START_REF] Hofheinz | Tightly secure signatures and public-key encryption[END_REF][START_REF] Libert | Compactly hiding linear spans -tightly secure constant-size simulation-sound QA-NIZK proofs and applications[END_REF][START_REF] Hofheinz | Algebraic partitioning: Fully compact and (almost) tightly secure cryptography[END_REF][START_REF] Gay | Tightly CCA-secure encryption without pairings[END_REF][START_REF] Hofheinz | Adaptive partitioning[END_REF], we mean that the multiplicative gap between the adversary's advantage and the hardness assumption only depends on the security parameter and not on the number of challenge ciphertexts. The strength of the underlying LWE assumption depends on the specific PRF used to instantiate our scheme. So far, known tightly secure lattice-based PRFs rely on rather strong LWE assumptions with exponential modulus and inverse error rate [START_REF] Banerjee | Pseudo-random functions and lattices[END_REF], or only handle polynomially-bounded adversaries [START_REF] Döttling | Efficient pseudorandom functions via on-the-fly adaptation[END_REF] (and hence do not fully exploit the conjectured exponential hardness of LWE). However, any future realization of low-depth PRF with tight security under standard LWE assumptions (i.e., with polynomial approximation factor) could be plugged into our scheme so as to obtain tight CCA security under the same assumption. Especially, if we had such a tightly secure PRF with an evaluation circuit in NC 1 , our scheme would be instantiable with a polynomial-size modulus by translating the evaluation circuit into a branching program via Barrington's theorem [START_REF] Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in nc1[END_REF] and exploiting the asymmetric noise growth of the GSW FHE as in [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF][START_REF] Gorbunov | Riding on asymmetry: Efficient ABE for branching programs[END_REF].

As a third and main result, we modify our construction so as to prove it secure against selective opening chosen-ciphertext attacks in the indistinguishability-based (i.e., IND-SO-CCA2) sense. By instantiating our system with a carefully chosen universal hash function, we finally upgrade it from IND-SO-CCA2 to SIM-SO-CCA2 security. For this purpose, we prove that the upgraded scheme is a lossy encryption scheme with efficient opening. As defined by Bellare et al. [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF][START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF], a lossy encryption scheme is one where normal public keys are indistinguishable from lossy keys, for which ciphertexts statistically hide the plaintext. It was shown in [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF][START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] that any lossy cryptosystem is in fact IND-SO-CPA-secure. Moreover, if a lossy ciphertext C can be efficiently opened to any desired plaintext Msg (i.e., by finding plausible random coins r that explain C as an encryption of Msg) using the secret key, the scheme also provides SIM-SO-CPA security. We show that our IND-SO-CCA-secure construction has this property when we embed a lattice trapdoor [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF][START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] in lossy secret keys.

This provides us with the first multi-bit LWE-based public-key cryptosystem with SIM-SO-CCA security. So far, the only known method [START_REF] Liu | Simulation-based selective opening CCA security for PKE from key encapsulation mechanisms[END_REF] to attain the same security notion under quantum-resistant assumptions was to apply a generic construction where each bit of plaintext requires a full key encapsulation (KEM) using a CCA2-secure KEM. In terms of ciphertext size, our system avoids this overhead and can be instantiated with a polynomialsize modulus as long as the underlying PRF can be evaluated in NC 1 . For example, the Banerjee-Peikert PRF [START_REF] Banerjee | New and improved key-homomorphic pseudo-random functions[END_REF] -which relies on a much weaker LWE assumption than [START_REF] Banerjee | Pseudo-random functions and lattices[END_REF] as it only requires on a slightly superpolynomial modulus -satisfies this condition when the input of the PRF is hardwired into the circuit.

As a result of independent interest, we show that lattice trapdoors can also be used to reach SIM-SO-CPA security in lossy encryption schemes built upon lossy trapdoor functions based on DDH-like assumptions. This shows that techniques from lattice-based cryptography can also come in handy to obtain simulation-based security from conventional number theoretic assumptions.

Our Techniques

Our ABM-LTF construction relies on the observation -previously used in [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF][START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF] -that the LWE function f LWE : Z n q × Z m → Z m q : (x, e) → A • x + e is lossy. Indeed, under the LWE assumption, the random matrix A ∈ Z m×n q can be replaced by a matrix of the form A = B • C + F, for a random B ∈ Z m× q such that < n and a small-norm F ∈ Z m×n , without the adversary noticing. However, we depart from [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF][START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF] in several ways.

First, in lossy mode, we sample C uniformly in Z ×n q (rather than as a small-norm matrix as in [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF]) because, in order to achieve SIM-SO security, we need to generate C with a trapdoor. Our application to SIM-SO security also requires to sample (x, e) from discrete Gaussian distributions, rather than uniformly over an interval as in [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF]. Second, we assume that the noise e ∈ Z m is part of the input instead of using the Rounding technique 4 [6] as in the lossy function of Alwen et al. [START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF]. The reason is that, in our ABM-LTF, we apply the LWE-based function (x, e) → A t • x + e for tag-dependent matrices A t and, if we were to use the rounding technique, the lower parts of matrices A t would have to be statistically independent for different tags. Since we cannot guarantee this independence, we consider the noise term e to be part of the input. In this case, we can prove that, for any lossy tag, the vector x retains at least Ω(n log n) bits of min-entropy conditionally on A t • x + e and this holds even if {A t } t are not statistically independent for distinct lossy tags t.

One difficulty is that our ABM-LTF only loses less than half of its input bits for lossy tags, which prevents it from being correlation-secure in the sense of [START_REF] Rosen | Chosen-ciphertext security via correlated products[END_REF]. For this reason, our encryption schemes cannot proceed exactly as in [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF][START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF] by simultaneously outputting an ABM-LTF evaluation f ABM (x, e) = A t • x + e and a lossy function evaluation f LTF (x, e) = A • x + e as this would leak (x, e). Fortunately, we can still build CCA2-secure systems by evaluating f LTF (•) and f ABM (•) for the same x and distinct noise vectors e 0 , e. In this case, we can prove that the two functions are jointly lossy: conditionally on (f LTF (x, e 0 ), f ABM (x, e)), the input x retains Ω(n log n) bits of entropy, which allows us to blind the message as Msg + h(x) using a universal hash function h.

Our ABM-LTF extends the all-but-one trapdoor function of Alwen et al. [START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF] by homomorphically evaluating a pseudorandom function. Letting Ā ∈ Z m×n q be a lossy matrix and G ∈ Z m×n q denote the gadget matrix of Micciancio and Peikert [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], the evaluation key of our ABM-LTF contains Gentry-Sahai-Waters (GSW) encryptions

B i = R i • Ā + K[i] • G ∈ Z m×n q of the bits K[i] of a PRF seed K ∈ {0, 1} λ , where R i ∈ {-1, 1} m×m . Given a tag t = (t c , t a ), the evaluation algorithm computes a GSW encryption B t = R t • Ā + h t • G ∈ Z m×n q
of the Hamming distance h t between t c and PRF(K, t a ) before using

A t = [ Ā | B t ] to evaluate f ABM (x, e) = A t • x + e.
In a lossy tag t = (PRF(K, t a ), t a ), we have h t = 0, so that the matrix

A t = [ Ā | (R t • Ā) ] induces a lossy function f ABM (t, •).
At the same time, any injective tag t = (t c , t a ) satisfies t c = PRF(K, t a ) and thus h t = 0, which allows inverting f ABM (x, e) = A t • x + e using the public trapdoor [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] of the matrix G.

The pseudorandomness of the PRF ensures that: (i) Lossy tags are indistinguishable from random tags; (ii) They are computationally hard to find without the seed K. In order to prove both statements, we resort to the LWE assumption as the matrix Ā is not statistically uniform over Z m×n q . Our tightly IND-CCA2-secure public-key cryptosystem uses ciphertexts of the form (f LTF (x, e 0 ), f ABM (x, e), Msg + h(x)), where t a is the verification key of the one-time signature. Instantiating this scheme with a polynomial-size modulus requires a tightly secure PRF which is computable in NC 1 when the input of the circuit is the key (rather than the input of the PRF). 5 To overcome this problem and as a result of independent interest, we provide a tighter proof for the key-homomorphic PRF of Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] (where the concrete security loss is made independent of the number of evaluation queries), which gives us tight CCA2-security under a strong LWE assumption.

In our IND-SO-CCA2 system, an additional difficulty arises since we cannot use one-time signatures to bind ciphertext components altogether. One alternative is to rely on the hybrid encryption paradigm as in [START_REF] Boyen | Direct chosen ciphertext security from identity-based technique[END_REF] by setting t a = f LTF (x, e 0 ) and encrypting Msg using a CCAsecure secret-key encryption scheme keyed by h(x). In a direct adaptation of this technique, the chosen-ciphertext adversary can modify f ABM (x, e) by re-randomizing the underlying e. Our solution to this problem is to apply the encrypt-then-MAC approach and incorporate f ABM (x, e) into the inputs of the MAC so as to prevent the adversary from randomizing e. Using the lossiness of f ABM (•) and f LTF (•), we can indeed prove that the hybrid construction provides IND-SO-CCA2 security.

In order to obtain SIM-SO-CCA2 security, we have to show that lossy ciphertexts can be equivocated in the same way as a chameleon hash function. Indeed, the result of [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF][START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF] implies that any lossy encryption scheme with this property is simulation-secure and the result carries over to the chosen-ciphertext setting. We show that ciphertexts can be trapdoor-opened if we instantiate the scheme using a particular universal hash function

h : Z n → Z L q which maps x ∈ Z n to h(x) = H U H • x ∈ Z L q , for a random matrix H U H ∈ Z L×n q .
In order to generate the evaluation keys ek and ek of f LTF and f ABM , we use random matrices

B LTF ∈ Z 2m× q , C LTF ∈ Z ×n q , B ABM ∈ Z m× q , C ABM ∈ Z ×n q
as well as small-norm F LTF ∈ Z 2m×n , F ABM ∈ Z m×n so as to set up lossy matrices

A LTF = B LTF • C LTF + F LTF and A ABM = B ABM • C ABM + F ABM .
The key idea is to run the trapdoor generation algorithm of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] to generate a statistically uniform

C = [C LTF | C ABM | H U H ] ∈ Z (2 +L)×n q
together with a trapdoor allowing to sample short integer vectors in any coset of the lattice Λ ⊥ (C). By choosing the target vector t ∈ Z 2 +L q as a function of the desired message Msg 1 , the initial message Msg 0 and the initial random coins (x, e 0 , e), we can find a short x ∈ Z n such that C • x = t mod q and subsequently define (e 0 , e ) ∈ Z 2m × Z m so that they explain the lossy ciphertext as an encryption of Msg 1 using the coins (x , e 0 , e ). Moreover, we prove that these have the suitable distribution conditionally on the lossy ciphertext and Msg 1 .

Related Work

While selective opening security was first considered by Dwork et al. [START_REF] Dwork | Magic functions[END_REF], the feasibility of SOA-secure public-key encryption remained open until the work of Bellare, Hofheinz and Yilek [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF][START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF]. They showed that IND-SO security can be generically achieved from any lossy trapdoor function and, more efficiently, under the DDH assumption. They also achieved SIM-SO-CPA security under the Quadratic Residuosity and DDH assumptions, but at the expense of encrypting messages bitwise. In particular, they proved the SIM-SO security of the Goldwasser-Micali system [START_REF] Goldwasser | Probabilistic encryption[END_REF] and their result was extended to Paillier [START_REF] Hemenway | Lossy encryption: Constructions from general assumptions and efficient selective opening chosen ciphertext security[END_REF]. Hofheinz, Jager and Rupp recently described space-efficient schemes under DDH-like assumption. Meanwhile, the notion of SIM-SO-CPA security was realized in the identity-based setting by Bellare, Waters and Yilek [START_REF] Bellare | Identity-based encryption secure against selective opening attack[END_REF]. Recently, Hoang et al. [START_REF] Hoang | Selective-opening security in the presence of randomness failures[END_REF] investigated the feasibility of SO security using imperfect randomness.

Selective opening security was considered for chosen-ciphertext adversaries in several works [START_REF] Fehr | Encryption schemes secure against chosen-ciphertext selective opening attacks[END_REF][START_REF] Huang | Sender equivocable encryption schemes secure against chosen-ciphertext attacks revisited[END_REF][START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF][START_REF] Lai | Identity-based encryption secure against selective-opening chosen-ciphertext attack[END_REF][START_REF] Liu | Simulation-based selective opening CCA security for PKE from key encapsulation mechanisms[END_REF]. Except constructions [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF][START_REF] Fujisaki | All-but-many encryption -a new framework for fully-equipped UC commitments[END_REF] based on (variants of) the Composite Residuosity assumption, all of them process messages in a bit-wise fashion, incurring an expansion factor Ω(λ). In the random oracle model [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF], much more efficient solutions are possible. In particular, Heuer et al. [START_REF] Heuer | On the selective opening security of practical public-key encryption schemes[END_REF] gave evidence that several practical schemes like RSA-OAEP [START_REF] Bellare | Optimal asymmetric encryption[END_REF] are actually secure in the SIM-SO-CCA sense.

The exact security of public-key encryption in the multi-challenge, multi-user setting was first taken into account by Bellare, Boldyreva and Micali [START_REF] Bellare | Public-key encryption in a multi-user setting: Security proofs and improvements[END_REF] who proved that Cramer-Shoup [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF] was tightly secure in the number of users, but not w.r.t. the number Q of challenge ciphertexts. Using ABM-LTFs, Hofheinz managed to obtain tight multi-challenge security [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF] (i.e., without a security loss Ω(Q) between the advantages of the adversary and the reduction) at the expense of non-standard, variable-size assumptions. Under simple DDHlike assumptions, Hofheinz and Jager [START_REF] Hofheinz | Tightly secure signatures and public-key encryption[END_REF] gave the first feasibility results in groups with a bilinear map. More efficient tight multi-challenge realizations were given in [START_REF] Libert | Compactly hiding linear spans -tightly secure constant-size simulation-sound QA-NIZK proofs and applications[END_REF][START_REF] Hofheinz | Algebraic partitioning: Fully compact and (almost) tightly secure cryptography[END_REF][START_REF] Gay | Tightly CCA-secure encryption without pairings[END_REF][START_REF] Hofheinz | Adaptive partitioning[END_REF] but, for the time being, the only solutions that do not rely on bilinear maps are those of [START_REF] Gay | Tightly CCA-secure encryption without pairings[END_REF][START_REF] Hofheinz | Adaptive partitioning[END_REF]. In particular, constructions from lattice assumptions have remained lacking so far. By instantiating our scheme with a suitable PRF [START_REF] Banerjee | Pseudo-random functions and lattices[END_REF], we take the first step in this direction (albeit under a strong LWE assumption with an exponential approximation factor). Paradoxically, while we can tightly reduce the security of the underlying PRF to the multi-challenge security of our scheme, we do not know how to prove tight multi-user security.

A common feature between our security proofs and those of [START_REF] Libert | Compactly hiding linear spans -tightly secure constant-size simulation-sound QA-NIZK proofs and applications[END_REF][START_REF] Hofheinz | Algebraic partitioning: Fully compact and (almost) tightly secure cryptography[END_REF][START_REF] Gay | Tightly CCA-secure encryption without pairings[END_REF][START_REF] Hofheinz | Adaptive partitioning[END_REF] is that they (implicitly) rely on the technique of the Naor-Reingold PRF [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF]. However, while they gradually introduce random values in semi-functional spaces (which do not appear in our setting), we exploit a different degree of freedom enabled by lattices, which is the homomorphic evaluation of low-depth PRFs.

The GSW FHE scheme [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] inspired homomorphic manipulations [START_REF] Boneh | Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[END_REF] of Micciancio-Peikert trapdoors [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], which proved useful in the design of attribute-based encryption (ABE) for circuits [START_REF] Boneh | Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[END_REF][START_REF] Brakerski | Circuit-ABE from LWE: unbounded attributes and semi-adaptive security[END_REF] and fully homomorphic signatures [START_REF] Gorbunov | Leveled fully homomorphic signatures from standard lattices[END_REF]. In particular, the homomorphic evaluation of PRF circuits was considered by Brakerski and Vaikuntanathan [START_REF] Brakerski | Circuit-ABE from LWE: unbounded attributes and semi-adaptive security[END_REF] to construct an unbounded ABE system. Boyen and Li [START_REF] Boyen | Towards tightly secure lattice short signature and ID-based encryption[END_REF] used similar ideas to build tightly secure IBE and signatures from lattice assumptions. Our constructions depart from [START_REF] Boyen | Towards tightly secure lattice short signature and ID-based encryption[END_REF] in that PRFs are also used in the schemes, and not only in the security proofs. Another difference is that [START_REF] Brakerski | Circuit-ABE from LWE: unbounded attributes and semi-adaptive security[END_REF][START_REF] Boyen | Towards tightly secure lattice short signature and ID-based encryption[END_REF] only need PRFs with binary outputs, whereas our ABM-LTFs require a PRF with an exponentially-large range in order to prevent the adversary from predicting its output with noticeable probability.

We finally remark that merely applying the Canetti-Halevi-Katz paradigm [START_REF] Canetti | Chosen-ciphertext security from identity-based encryption[END_REF] to the Boyen-Li IBE [START_REF] Boyen | Towards tightly secure lattice short signature and ID-based encryption[END_REF] does not imply tight CCA2 security in the multi-challenge setting since the proof of [START_REF] Boyen | Towards tightly secure lattice short signature and ID-based encryption[END_REF] is only tight for one identity: in a game with Q challenge ciphertexts, the best known reduction would still lose a factor Q via the standard hybrid argument.

Concurrent Work. In a concurrent and independent paper, Boyen and Li [START_REF] Boyen | All-but-many lossy trapdoor functions from lattices and applications[END_REF] investigated the construction of all-but-many lossy trapdoor functions from LWE and their applications to (selective-opening) CCA2 security.

Background

For any q ≥ 2, we let Z q denote the ring of integers with addition and multiplication modulo q. We always set q as a prime integer. If x is a vector over R, then x denotes its Euclidean norm. If M is a matrix over R, then M denotes its induced norm. We let σ n (M) denote the least singular value of M, where n is the rank of M. For a finite set S, we let U (S) denote the uniform distribution over S. If X is a random variable over a countable domain, the min-entropy of X is defined as H ∞ (X) = min x (-log 2 Pr[X = x]). If X and Y are distributions over the same domain, then ∆(X, Y ) denotes their statistical distance.

Randomness Extraction

We first recall the Leftover Hash Lemma, as it was stated in [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF].

Lemma 1 ([1]

). Let H = {h : X → Y } h∈H be a family of universal hash functions, for countable sets X, Y . For any random variable T taking values in X, we have

∆ (h, h(T )), (h, U (Y )) ≤ 1 2 • 2 -H∞(T ) • |Y |.
More generally, let (T i ) i≤k be independent random variables with values in X, for some k > 0.

We have ∆ (h, (h

(T i )) i≤k ), (h, (U (Y )) (i) ) i≤k )) ≤ k 2 • 2 -H∞(T ) • |Y |.
A consequence of Lemma 1 was used by Agrawal et al. [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] to re-randomize matrices over Z q by multiplying them with small-norm matrices.

Lemma 2 ([1]

). Let us assume that m > 2n • log q, for some prime q > 2. For any integer

k ∈ poly(n), if A ← U (Z m×n q ), B ← U (Z k×n q ), R ← U ({-1, 1} k×m ), the distributions (A, R • A) and (A, B) are within 2 -Ω(n) statistical distance.

Reminders on Lattices

Let Σ ∈ R n×n be a symmetric definite positive matrix, and c ∈ R n . We define the Gaussian function on R n by ρ Σ,c (x) = exp(-π(x -c) Σ -1 (x -c)) and if Σ = σ 2 • I n and c = 0 we denote it by ρ σ . For an n-dimensional lattice Λ, we define η ε (Λ) as the smallest r > 0 such that ρ 1/r ( Λ \ 0) ≤ ε with Λ denoting the dual of Λ, for any ε ∈ (0, 1). In particular, we have

η 2 -n (Z n ) ≤ O( √ n).
We denote by λ ∞ 1 (Λ) the infinity norm of the shortest non-zero vector of Λ.

For a matrix A ∈ Z m×n q , we define

Λ ⊥ (A) = {x ∈ Z m : x • A = 0 mod q} and Λ(A) = A • Z n + qZ m .
Lemma 3 (Adapted from [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Lemma 5.3]). Let m ≥ 2n and q ≥ 2 prime. With probability ≥ 1 -2 -Ω(n) , we have

η 2 -n (Λ ⊥ (A)) ≤ η 2 -m (Λ ⊥ (A)) ≤ O( √ m) • q n/m and λ ∞ 1 (Λ(A)) ≥ q 1-n/m /4.
Let Λ be a full-rank n-dimensional lattice, Σ ∈ R n×n be a symmetric definite positive matrix, and x , c ∈ R n . We define the discrete Gaussian distribution of support Λ + x and parameters Σ and c by D Λ+x ,Σ,c (x) ∼ ρ Σ,c (x), for every x ∈ Λ + x . For a subset S ⊆ Λ + x , we denote by D S Λ+x ,Σ,c the distribution obtained by restricting the distribution D Λ+x ,Σ,c to the support S. For x ∈ S, we have D S Λ+x ,Σ,c (x) = D Λ+x ,Σ,c (x)/p a , where p a (S) = D Λ+x ,Σ,c (S). Assuming that 1/p a (S) = n O (1) , membership in S is efficiently testable and D Λ+x ,Σ,c is efficiently samplable, the distribution D S Λ+x ,Σ,c can be efficiently sampled from using rejection sampling.

We will use the following standard results on lattice Gaussians.

Lemma 4 (Adapted from [29, Lemma 2.3]

). There exists a ppt algorithm that, given a basis (b i ) i≤n of a full-rank lattice Λ, x , c ∈ R n and Σ ∈ R n×n symmetric definite positive such that Ω(

√ log n) • max i Σ -1/2 • b i ≤ 1, returns a sample from D Λ+x ,Σ,c .
Lemma 5 (Adapted from [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF]Lemma 4.4]). For any n-dimensional lattice Λ, x , c ∈ R n and symmetric positive definite

Σ ∈ R n×n satisfying σ n ( √ Σ) ≥ η 2 -n (Λ), we have Pr x← D Λ+x ,Σ,c [ x -c ≥ √ n • √ Σ ] ≤ 2 -n+2 .
Lemma 6 (Adapted from [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF]Lemma 4.4]). For any n-dimensional lattice Λ, x , c ∈ R n and symmetric positive definite

Σ ∈ R n×n satisfying σ n ( √ Σ) ≥ η 2 -n (Λ), we have ρ Σ,c (Λ + x ) ∈ [1 -2 -n , 1 + 2 -n ] • det(Σ) 1/2 /det(Λ).
We will also use the following result on the singular values of discrete Gaussian random matrices.

Lemma 7 ([2, Lemma 8]). Assume that m ≥ 2n. Let F ∈ Z m×n with each entry sampled from D Z,σ , for some σ ≥ Ω( √ n). Then with probability ≥ 1-2 -Ω(n) , we have F ≤ O( √ mσ) and σ n (F) ≥ Ω( √ mσ).

The Learning With Errors Problem

We recall the Learning With Errors problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Note that we make the number of samples m explicit in our definition.

Definition 1. Let λ ∈ N be a security parameter and let integers n = n(λ), m = m(λ), q = q(λ). Let χ = χ(λ) be an efficiently samplable distribution over Z q . The LWE n,m,q,χ assumption posits that the following distance is a negligible function for any ppt algorithm A:

Adv A,LWE n,m,q,χ (λ) := Pr[A(1 λ , A, u) = 1 | A ← U (Z n×m q ), u ← U (Z m q )] -Pr[A(1 λ , A, A • s + e) = 1 | A ← U (Z m×n q ), s ← U (Z n q ), e ← χ m ] .
A typical choice for χ is the integer Gaussian distribution D Z,α•q for some parameter α ∈ ( √ n/q, 1). In particular, in this case, there exist reductions from standard lattice problems to LWE (see [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Brakerski | On the classical hardness of learning with errors[END_REF]).

In [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], Micciancio and Peikert described a trapdoor mechanism for LWE. Their technique uses a "gadget" matrix G ∈ Z m×n q for which anyone can publicly sample short vectors x ∈ Z m such that x G = 0. As in [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], we call R ∈ Z m×m a G-trapdoor for a matrix

A ∈ Z 2m×n q if [R | I m ] • A = G • H for some invertible matrix H ∈ Z n×n q
which is referred to as the trapdoor tag. If H = 0, then R is called a "punctured" trapdoor for A. Lemma 8 ([69,Section 5]). Assume that m ≥ 2n log q. There exists a ppt algorithm GenTrap that takes as inputs matrices Ā ∈ Z m×n q , H ∈ Z n×n q and outputs matrices R ∈ {-1, 1} m×m and

A = Ā -R Ā + GH ∈ Z 2m×n q such that if H ∈ Z n×n q is invertible, then R is a G-trapdoor for A with tag H; and if H = 0, then R is a punctured trapdoor.
Further, in case of a G-trapdoor, one can efficiently compute from A, R and H a basis

(b i ) i≤2m of Λ ⊥ (A) such that max i b i ≤ O(m 3/2 ).
Micciancio and Peikert also showed that a G-trapdoor for A ∈ Z 2m×n q can be used to invert the LWE function (s, e) → A•s+e, for any s ∈ Z n q and any sufficiently short e ∈ Z 2m . Lemma 9 ([69, Theorem 5.4]). There exists a deterministic polynomial time algorithm Invert that takes as inputs matrices R ∈ Z m×m , A ∈ Z 2m×n q , H ∈ Z n×n q such that R is a Gtrapdoor for A with invertible tag H, and a vector A•s+e with s ∈ Z n q and e ≤ q/(10• R ), and outputs s and e.

As showed in [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF][START_REF] Boneh | Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[END_REF], homomorphic computations can be performed on G-trapdoors with respect to trapdoor tags H i corresponding to scalars. As observed in [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF], when the circuit belongs to NC 1 , it is advantageous to convert the circuit into a branching program, using Barrington's theorem. This is interesting to allow for a polynomial modulus q but imposes a circuit depth restriction (so that the evaluation algorithms are guaranteed to run in polynomial-time).

Lemma 10 (Adapted from [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF][START_REF] Boneh | Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[END_REF]).

Let C : {0, 1} κ → {0, 1} be a NAND Boolean circuit of depth d. Let B i = R i • Ā + x i • G ∈ Z m×n q with Ā ∈ Z m×n q , R i ∈ {-1, 1} m×m and x i ∈ {0, 1}, for i ≤ κ.
• There exist deterministic algorithms Eval pub CCT and Eval priv CCT that satisfy: d) . These algorithms run in time poly(|C|, κ, m, n, log q) • There exist deterministic algorithms Eval pub BP and Eval priv BP that satisfy:

Eval pub CCT (C, (B i ) i ) = Eval priv CCT (C, (R i ) i ) • Ā + C(x 1 , . . . , x κ ) • G, and Eval priv CCT (C, (R i ) i ) ≤ m O(
Eval pub BP (C, (B i ) i ) = Eval priv BP (C, (R i ) i ) • Ā + C(x 1 , . . . , x κ ) • G, and Eval priv BP (C, (R i ) i ) ≤ 4 d •O(m 3/2
). These algorithms run in time poly(4 d , κ, m, n, log q). Note that we impose that the Eval pub and Eval priv algorithms are deterministic, although probabilistic variants are considered in the literature. This is important in our case, as it will be used in the function evaluation algorithm of our all-but-many lossy trapdoor function family LTF function evaluation.

Lossy Trapdoor Functions

We consider a variant of the notion of Lossy Trapdoor Functions (LTF) introduced by [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], for which the function input may be sampled from a distribution that differs from the uniform distribution. In our constructions, for lossiness security, we actually allow the function evaluation algorithm to sample from a larger domain Dom E λ than the domain Dom D λ on which the inversion algorithm guaranteed to succeed. A sample over Dom E λ has an overwhelming probability to land in Dom D λ with respect to the sampling distribution.

Definition 2. For an integer l(λ) > 0, a family of l-lossy trapdoor functions LTF with security parameter λ, evaluation sampling domain Dom E λ , efficiently samplable distribution D Dom E λ on Dom E λ , inversion domain Dom D λ ⊆ Dom E λ and range Rng λ is a tuple of ppt algorithms (IGen, LGen, Eval, Invert) with the following functionalities:

Injective key generation. LTF.IGen(1 λ ) outputs an evaluation key ek for an injective function together with an inversion key ik. Lossy key generation. LTF.

LGen(1 λ ) outputs an evaluation key ek for a lossy function.

In this case, there is no inversion key and we define ik = ⊥. Evaluation. LTF.Eval(ek, X) takes as inputs the evaluation key ek and a function input

X ∈ Dom E λ . It outputs an image Y = f ek (X). Inversion. LTF.Invert(ik, Y ) inputs the inversion key ik = ⊥ and a Y ∈ Rng λ . It outputs the unique X = f -1 ik (Y ) such that Y = f ek (X) (if it exists).
In addition, LTF has to meet the following requirements:

Inversion Correctness. For an injective key pair (ek, ik) ← LTF.IGen(1 λ ), we have, except with negligible probability over (ek, ik), that for all inputs

X ∈ Dom D λ , X = f -1 ik (f ek (X)). Eval Sampling Correctness. For X sampled from D Dom E λ , we have X ∈ Dom D λ except with negligible probability. l-Lossiness. For (ek, ⊥) ← LTF.LGen(1 λ ) and X ← D Dom E λ , we have H ∞ (X | ek = ek, f ek (X) = y) ≥ l,
for all (ek, y) except a set of negligible probability. Indistinguishability. The distribution of lossy functions is computationally indistinguishable from that of injective functions, namely:

Adv A,LTF (λ) := Pr[A(1 λ , ek) = 1 | (ek, ik) ← LTF.IGen(1 λ )] -Pr[A(1 λ , ek) = 1 | (ek, ⊥) ← LTF.LGen(1 λ )]
is a negligible function for any ppt algorithm A.

All-But-Many Lossy Trapdoor Functions

We consider a variant of the definition of All-But-Many Lossy Trapdoor Functions (ABM-LTF) from [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF], in which the distribution over the domain may not be the uniform one.

Definition 3. For an integer l(λ) > 0, a family of all-but-many l-lossy trapdoor functions ABM with security parameter λ, evaluation sampling domain Dom E λ , efficiently samplable distribution D Dom E λ on Dom E λ , inversion domain Dom D λ ⊆ Dom E λ , and range Rng λ consists of the following ppt algorithms: Key generation. ABM.Gen(1 λ ) outputs an evaluation key ek, an inversion key ik and a tag key tk. The evaluation key ek defines a set T = T c × T a containing the disjoint sets of lossy tags T loss and injective tags T inj . Each tag t = (t c , t a ) is described by a core part t c ∈ T c and an auxiliary part t a ∈ T a .

Evaluation. ABM.Eval(ek, t, X) takes as inputs an evaluation key ek, a tag t ∈ T and a function input X ∈ Dom E λ . It outputs an image Y = f ek,t (X). Inversion. ABM.Invert(ik, t, Y ) takes as inputs an inversion key ik, a tag t ∈ T and a Y ∈ Rng λ . It outputs the unique X = f -1 ik,t (Y ) such that Y = f ek,t (X). Lossy tag generation. ABM.LTag(tk, t a ) takes as input an auxiliary part t a ∈ T a and outputs a core part t c such that t = (t c , t a ) forms a lossy tag.

In addition, ABM has to meet the following requirements:

Inversion Correctness. For (ek, ik, tk) produced by ABM.Gen(1 λ ), we have, except with negligible probability over (ek, ik, tk), that for all injective tags t ∈ T inj and all inputs

X ∈ Dom D λ , that X = f -1 ik,t (f ek,t (X)). Eval Sampling Correctness. For X sampled from D Dom E λ , we have X ∈ Dom D λ except with negligible probability. Lossiness. For (ek, ik, tk) ← ABM.Gen(1 λ ), any t a ∈ T a , t c ← ABM.LTag(tk, t a ) and X ← D Dom E λ , we have that H ∞ (X | ek = ek, f ek,(tc,ta) (X) = y) ≥ l
, for all (ek, y) except a set of negligible probability. Indistinguishability. Multiple lossy tags are computationally indistinguishable from random tags, namely:

Adv A,ind Q (λ) := Pr[A(1 λ , ek) ABM.LTag(tk,•) = 1] -Pr[A(1 λ , ek) O Tc (•) = 1]
is negligible for any ppt algorithm A, where (ek, ik, tk) ← ABM.Gen(1 λ ) and O Tc (•) is an oracle that assigns a random core tag t c ← U (T c ) to each auxiliary tag t a ∈ T a (rather than a core tag that makes t = (t c , t a ) lossy). Here Q denotes the number of oracle queries made by A. Evasiveness. Non-injective tags are computationally hard to find, even with access to an oracle outputting multiple lossy tags, namely:

Adv A,eva Q 1 ,Q 2 (λ) := Pr[A(1 λ , ek) ABM.LTag(tk,•),ABM.IsLossy(tk,•) ∈ T \T inj ]
is negligible for legitimate adversary A, where (ek, ik, tk) ← ABM.Gen(1 λ ) and A is given access to the following oracles: -ABM.LTag(tk, •) which acts exactly as the lossy tag generation algorithm.

-ABM.IsLossy(tk, •) that takes as input a tag t = (t c , t a ) and outputs 1 if t ∈ T \T inj and otherwise outputs 0. We denote by Q 1 and Q 2 the number of queries to these two oracles. By "legitimate adversary", we mean that A is ppt and never outputs a tag t = (t c , t a ) such that t c was obtained by invoking the ABM.LTag oracle on t a .

As pointed out in [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF], the evasiveness property mirrors the notion of strong unforgeability for signature schemes. Indeed, the adversary is considered successful even if it outputs a (t c , t a ) such that t a was submitted to ABM.LTag(tk, •) as long as the response t a of the latter was such that t a = t a .

In order to simplify the tight proof of our public-key encryption scheme, we slightly modified the original definition of evasiveness in [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF] by introducing a lossiness-testing oracle ABM.IsLossy(tk, •). When it comes to proving tight CCA security, it will save the reduction from having to guess which decryption query contradicts the evasiveness property of the underlying ABM-LTF.

Selective-Opening Chosen-Ciphertext Security

A public-key encryption scheme consists of a tuple (Par-Gen, Keygen, Encrypt,Decrypt) of ppt algorithms, where Par-Gen takes as input a security parameter 1 λ and generates common public parameters Γ , Keygen takes in Γ and outputs a key pair (SK, P K), while Encrypt and Decrypt proceed in the usual way.

As a first step, we will consider encryption schemes that provide SO security in the sense of an indistinguishability-based definition (or IND-SOA security). This notion is captured by a game where the adversary obtains N (λ) ciphertexts, opens an arbitrary subset of these (meaning that it obtains both the plaintexts and the encryption coins) and asks that remaining ciphertexts be indistinguishable from messages that are independently re-sampled conditionally on opened ones. In the IND-SO-CCA2 scenario, this should remain true even if the adversary has a decryption oracle. A formal definition is recalled in Appendix B. [START_REF] Alwen | Key-indistinguishable message authentication codes[END_REF].

A stronger notion is that of simulation-based security, which demands that an efficient simulator be able to perform about as well as the adversary without seeing neither the ciphertexts nor the public key. Formally, two experiments are required to have indistinguishable output distributions.

In the real experiment, the challenger samples Msg = (Msg 1 , . . . , Msg N ) ← M from the joint message distribution and picks random coins r 1 , . . . , r N ← R to compute ciphertexts {C i ← Encrypt(P K, Msg i , r i )} i∈[N ] which are given to the adversary A. The latter responds by choosing a subset I ⊂ [N ] and gets back {(Msg i , r i )} i∈I . The adversary A outputs a string out A and the output of the experiment is a predicate R(M, Msg, out A ).

In the ideal experiment, the challenger samples Msg = (Msg 1 , . . . , Msg N ) ← M from the joint message distribution. Without seeing any encryptions, the simulator chooses a subset I and some state information st. After having seen the messages {Msg i } i∈I and the state information but without seeing any randomness, the simulator outputs a string out S . The outcome of the ideal experiment is the predicate R(M, Msg, out S ). As in [START_REF] Fehr | Encryption schemes secure against chosen-ciphertext selective opening attacks[END_REF][START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF], we allow the adversary to choose the message distribution M. While this distribution should be efficiently samplable, it is not required to support efficient conditional re-sampling.

Definition 4 ( [START_REF] Fehr | Encryption schemes secure against chosen-ciphertext selective opening attacks[END_REF][START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF]). A public-key encryption scheme (Par-Gen, Keygen, Encrypt, Decrypt) provides simulation-based selective opening (SIM-SO-CPA) security if, for any ppt function R and any ppt adversary A = (A 0 , A 1 , A 2 ) in the real experiment Exp cpa-so-real (λ), there is an efficient simulator S = (S 0 , S 1 , S 2 ) in the ideal experiment Exp so-ideal (λ) s.t.

| Pr[Exp cpa-so-real (λ) = 1] -Pr[Exp so-ideal (λ) = 1]|
is negligible, where the two experiments are defined as follows:

Exp cpa-so-real (λ):

Exp so-ideal (λ): Γ ← Par-Gen(1 λ ); Γ ← Par-Gen(1 λ ); (P K, SK) ← Keygen(Γ ) (M, st0) ← S0(Γ ) (M, st0) ← A0(P K, Γ ) Msg = (Msg 1 , . . . , Msg N ) ← M Msg = (Msg 1 , . . . , Msg N ) ← M (I, st1) ← S1(st0, 1 |Msg i | ) r1, . . . , rn ← R outS ← S2 st1, {Msg i }i∈I Ci ← Encrypt(P K, Msg i , ri) ∀i ∈ [N ], Output R(M, Msg, outS) (I, st1) ← A1 st0, C1, . . . , CN outA ← A2 st1, (Msg i , ri)i∈I Output R(M, Msg, outA)
As usual, the adversarially-chosen message distribution M is efficiently samplable and encoded as a polynomial-size circuit.

The notion of simulation-based chosen-ciphertext (SIM-SO-CCA) security is defined analogously. The only difference is in the real experiment Exp cca-so-real , which is obtained from Exp cpa-so-real by granting the adversary access to a decryption oracle at all stages. Of course, the adversary is disallowed to query the decryption of any ciphertext in the set

{C i } i∈[N ] of challenge ciphertexts.
It is known [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] that SIM-SO-CPA security can be achieved from lossy encryption schemes [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF] when there exists an efficient Opener algorithm which, using the lossy secret key, can explain a lossy ciphertext C as an encryption of any given plaintext. As observed in [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF][START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF], this Opener algorithm can use the initial coins used in the generation of C for this purpose. This property, formalized by Definition 11, is called efficient weak opening.

An All-But-Many Lossy Trapdoor Function from LWE

As a warm-up, we first describe a variant of the lossy trapdoor function suggested by Bellare et al. [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF]Section 5.2] that is better suited to our needs. We then extend this LWE-based LTF into an ABM-LTF in Section 3.2.

An LWE-Based Lossy Trapdoor Function

All algorithms use a prime modulus q > 2, integers n ∈ poly(λ), m ≥ 2n log q and > 0, an LWE noise distribution χ, and parameters σ x , σ e , γ x , γ e > 0. The function evaluation sampling domain

Dom E λ = Dom E x × Dom E e where Dom E x (resp. Dom E e ) is the set of x (resp. e) in Z n (resp. Z 2m ) with x ≤ γ x • √ n • σ x (resp. e ≤ γ e √ 2m • σ e ). Its inversion domain is Dom D λ = Dom D x × Dom D e , where Dom D x (resp. Dom D e ) is the set of x (resp. e) in Z n (resp. Z 2m ) with x ≤ √ n • σ x (resp. e ≤ √ 2m
• σ e ) and its range is Rng λ = Z 2m q . The function inputs are sampled from the distribution

D Dom E λ = D Dom E x Z n ,σx × D Dom E e Z 2m ,σe .
Injective key generation. LTF.IGen(1 λ ) samples Ā ← U (Z m×n q ) and runs (A, R) ← GenTrap( Ā, I n ) to obtain A ∈ Z 2m×n q together with a G-trapdoor R ∈ {-1, 1} m×m . It outputs ek := A and ik := R.

Lossy key generation. LTF.LGen(1 λ ) generates A ∈ Z 2m×n q as a matrix of the form

A = B • C + F with B ← U (Z 2m× q ), C ← U (Z ×n
q ) and F ← χ 2m×n . It outputs ek := A and ik :=⊥. Evaluation. LTF.Eval(ek, (x, e)) takes as input a domain element (x, e) ∈ Dom E λ and maps it to y = A • x + e ∈ Z 2m q . Inversion. LTF.Invert(ik, y) inputs a vector y ∈ Z 2m q , uses the G-trapdoor ik = R of A to find the unique (x, e) ∈ Dom D λ such that y = A • x + e. This is done by applying the LWE inversion algorithm from Lemma 9.

Note that the construction differs from the lossy function of [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF] in two ways. First, in [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF], the considered distribution over the function domain is uniform over a parallelepiped. We instead consider a discrete Gaussian distribution. Second, in [START_REF] Bellare | Identity-based (lossy) trapdoor functions and applications[END_REF], the matrix C is chosen as a small-norm integer matrix sampled from the LWE noise distribution. We instead sample it uniformly. Both modifications are motivated by our application to SO-CCA security. Indeed, in the security proof, we will generate C along with a lattice trapdoor (using GenTrap), which we will use to simulate the function domain distribution conditioned on an image value.

We first study the conditional distribution of the pair (x, e) given its image under a lossy function. This will be used to quantify the lossiness of the LTF.

Lemma 11. Let C ∈ Z ×n q and F ∈ Z 2m×n . Sample (x, e) ← D Domx Z n ,σx × D Dome Z 2m ,σe and de- fine (u, f ) = (C • x, F • x + e) ∈ Z n q × Z 2m .
Note that e is fully determined by x, u and f . Further, the conditional distribution of

x given (u, f ) is D S F,u,f Λ ⊥ (C )+x , √ Σ,c , with support S F,u,f = x ∈ Λ ⊥ (C ) + x : x ∈ Dom x , f -F • x ∈ Dom e ,
where x is any solution to C • x = u and:

Σ = σ 2 x • σ 2 e • (σ 2 x • F • F + σ 2 e • I n ) -1 , c = σ 2 x • (σ 2 x • F • F + σ 2 e • I n ) -1 • F • f . Proof. We first remark that the support of x|(u, f ) is S F,u,f , since the set of solutions x ∈ Z n to u = C • x ∈ Z q is Λ ⊥ (C ) +
x and each such x has a non-zero conditional probability if and only if the corresponding ē = f -F • x is in Dom e . Now, for x ∈ Z n in the support S F,u,f , we have

Pr[x = x|(u, f )] ∼ D Z n ,σx (x) • D Z 2m ,σe (f -F • x) ∼ exp -π x 2 σ 2 x + f -F • x 2 σ 2 e ∼ exp -π (x -c) • Σ -1 • (x -c) .
The last equality follows from expanding the norms and collecting terms.

We now formally state for which parameters we can prove that the scheme above is an LTF. The second part of the theorem will be useful for our SO-CCA encryption application.

Theorem 1. Let χ = D Z,β/(2 √ λ)
for some β > 0. Let us assume that ≥ λ, n = Ω( log q) and m ≥ 2n log q, γ x ≥ 3 m/n and γ e ≥ 3. Assume further that σ x ≥ Ω(n), σ e ≤ O(q/m 3/2 ) and σ e ≥ Ω( √ mn • β • σ x ). Then, under the LWE ,2m,q,χ hardness assumption, the above construction is an l-lossy LTF with l ≥ n log σ x -2 -log q > Ω(n log n). Further, any ppt indistinguishability adversary A implies an LWE distinguisher D with comparable running time such that Adv A,LTF (λ) ≤ n • Adv D,LWE ,2m,q,χ (λ). Moreover, there is a ppt sampling algorithm, that given (B, C, F) generated by LTF.

LGen(1 λ ), a trapdoor basis

(b i ) i≤n for Λ ⊥ (C ) such that max i b i ≤ σ x σ e /(Ω(log n) • 2mnβ 2 σ 2
x + σ 2 e ) and a function output y = LTF.Eval(ek, (x, e)) for an input (x, e) ← D

Dom E x Z n ,σx × D Dom E e Z 2m
,σe , outputs, with probability ≥ 1 -2 -Ω(λ) over ek and (x, e), an independent sample (x, ē) from the conditional distribution of (x, e) conditioned on y = LTF.Eval(ek, (x, e)).

Proof. First, the construction is correct. Indeed, by Lemmas 4 and 5, if

σ x ≥ Ω( √ m) and σ e ≥ Ω( √ m), the distribution D Z n ,σx × D Z 2m
,σe is efficiently samplable, and a sample from it belongs to Dom E λ with probability ≥ 1 -2 -Ω(λ) , so D Dom E λ is efficiently samplable. For inversion correctness, we consider (x, e) ∈ Dom D λ , and set y = A • x + e. By Lemma 9, we can recover (x, e) from y using the G-trapdoor R of A if e ≤ q/(10 • R ). The fact that R ≤ m and the parameter choices guarantee this.

The lossy and injective modes are computationally indistinguishable under the LWE ,2m,q,χ assumption. A standard hybrid argument over the columns of A ∈ Z 2m×n q provides the inequality between the respective success advantages.

We now focus on the lossiness property. Note that Lemma 11 describes the conditional distribution of (x, e) conditioned on (C • x, F • x + e). We claim that, except with probability ≤ 2 -Ω(λ) over ek generated by LTF.

LGen(1 λ ), this is also the distribution of (x, e) conditioned on LTF.Eval(ek, (x, e)). Indeed, LTF.Eval(ek, (x, e)) = B

• C • x + F • x + e ∈ Z 2m q uniquely determines u = C • x ∈ Z q and f = F • x + e ∈ Dom e if f ∞ < λ ∞ 1 (Λ(B)
)/2 for all (x, e) ∈ Dom E . The latter condition is satisfied except with probability ≤ 2 -Ω(λ) over the choice of ek. This is because

f ∞ ≤ √ 2m • β √ nσ x + √ 2mσ x ≤ 2 √ 2m
• σ e < q/8 except with probability 2 -Ω(λ) over the choice of F, and λ ∞ 1 (Λ(B))/2 ≥ q/4 with probability ≤ 2 -Ω(λ) over the choice of B, by Lemma 3.

We now show that the conditional distribution D

S F,u,f Λ ⊥ (C )+x , √ Σ,c
given by Lemma 11 for x conditioned on LTF.Eval(ek, (x, e)) has min-entropy at least l and is efficiently samplable. For every x ∈ S F,u,f , we have

D S F,u,f Λ ⊥ (C )+x , √ Σ,c (x) = 1 p a • D Λ ⊥ (C )+x , √ Σ,c (x), p a = D Λ ⊥ (C )+x , √ Σ,c (S F,u,f ).
For min-entropy, we observe that, by Lemma 6, the point with highest probability in

D Λ ⊥ (C )+x , √ Σ,c has probability ≤ 2 det(Λ ⊥ (C ))/ det(Σ) . We can apply Lemma 6 because σ n ( √ Σ) ≥ η 2 -n (Λ ⊥ (C )
) with overwhelming probability. Indeed, thanks to assumption on χ, λ) . When this inequality holds, we have

we have F • F ≤ 2mnβ 2 with probability ≥ 1 -2 -Ω(
σ n ( √ Σ) ≥ σ x σ e / 2mnβ 2 σ 2 x + σ 2 e . Further, by Lemma 3, we have η 2 -n (Λ ⊥ (C )) ≤ O( √ nq /n ) with probability ≥ 1 -2 -Ω( ) .
Hence the assumption of Lemma 6 holds, thanks to our parameter choices. Overall, we obtain that the scheme is l-lossy for

l ≥ log √ det Σ -log det(Λ ⊥ (C )) -1 -log(1/p a ).
By calculations similar to those above, we have that √ det Σ ≤ σ n x . Further, matrix C has rank with probability ≥ 1 -2 -Ω( ) , and, when this is the case, we have det(Λ ⊥ (C )) = q . We obtain l ≥ n log σ x -1 -log q -log(1/p a ).

To complete the lossiness proof, we show that p a ≥ 1 -2 -Ω(λ) so that log(1/p a ) ≤ 1, except with probability ≤ 2 -Ω(λ) over (F, C,x,e). For this, we have by a union bound that p a ≥ 1 -(p x + p e ), where p x is the probability that a sample x from

D Λ ⊥ (C )+x , √ Σ,c lands outside Dom E x (i.e., x > γ x • √ n • σ x )
, and p e is the probability that a sample x from

D Λ ⊥ (C )+x , √ Σ,c is such that f -F • x lands outside Dom E e (i.e., f -F • x > γ e • √ 2m
• σ e ). In order to bound p x , we observe that it is at most

p x = Pr x← D Λ ⊥ (C )+x , √ Σ,c [ x -c > √ Σ • √ n] if γ x • √ n • σ x ≥ c + √ Σ • √ n. Now, using that F ≤ √ 2mn • β, x ≤ √ n • σ x and e ≤ √ 2m
• σ e except with probability 2 -Ω(λ) , by Lemma 5, we get with the same probability that c

≤ (σ x /σ e ) 2 • √ 2mnβ • ( √ 2mn • β • σ x • √ n + σ e • √ 2m
). Furthermore, using √ Σ ≤ σ x /σ e , we have that the condition

γ x • √ n • σ x ≥ c + √ Σ • √
n is satisfied by our choice of parameters. Also, as shown above, we have σ n ( √ Σ) ≥ η 2 -n (Λ ⊥ (C )) with overwhelming probability, so that we can apply Lemma 5 to conclude that p x ≤ p x ≤ 2 -n+2 with probability ≥ 1 -2 -Ω(λ) .

In order to bound p e , we follow a similar computation as for p x . Namely, we first observe that, if x is sampled from

D Λ ⊥ (C )+x , √ Σ,c , then ē = f -F • x is distributed as D F•Λ ⊥ (C )+f -F•x , √ FΣF ,f -F•c
. Therefore, the probability p e is at most the probability p e that a sample ē from

D F•Λ ⊥ (C )+f -F•x , √ FΣF ,f -F•c satisfies ē -(f -F • c) > √ FΣF • √ 2m, assuming that the condition γ e • √ 2m • σ e ≥ f -F • c + √ FΣF • √ 2m, (1)
is satisfied. Now, using f -F • c ≤ f + F • c and the above bounds on F , f and c and our choice of parameters, we have that condition (1) is satisfied with overwhelming probability. In order to apply Lemma 5 and bound p e , we also need the inequality

σ n ( √ FΣF ) ≥ η 2 -n (F • Λ ⊥ (C )) to be satisfied. Now, note that σ n ( √ FΣF ) = σ x • σ e / σ 2 x + σ 2 e /σ n (F) 2 .
By Lemma 7, we have σ n (F) ≥ Ω( √ m • β) with overwhelming probability. We conclude that σ n (

√ FΣF ) ≥ Ω(σ x • √ m • β).
On the other hand, Lemma 7 also implies that

η 2 -n (F • Λ ⊥ (C )) ≤ F • η 2 -n (Λ ⊥ (C )) = O( F • √ n) ≤ O(β • √ m • n)
with overwhelming probability. Hence, the condition σ n (

√ FΣF ) ≥ η 2 -n (F • Λ ⊥ (C )
) holds with with the same probability thanks to our choice of parameters. We can thus apply Lemma 5 to conclude that p e ≤ p e ≤ 2 -n+2 with overwhelming probability.

Overall, we have that p a ≥ 1 -(p x + p e ) ≥ 1 -2 -Ω(λ) which completes the proof of lossiness. This also immediately implies that the conditional distribution D Key generation. ABM.Gen(1 λ ) conducts the following steps.

1. For parameters n, , m, γ, χ, generate Ā ∈ Z m×n

q as Ā = B•C+F with B ← U (Z m× q ), C ← U (Z ×n q ) and F ← χ m×n . 2. Choose a PRF family PRF : {0, 1} λ × {0, 1} k → {0, 1} λ with input length k = k(λ)
and key length λ. Choose a seed K ← U ({0, 1} λ ) for PRF. 3. Sample matrices R 1 , . . . , R λ ← U ({-1, 1} m×m ) and compute

B i = R i • Ā + K[i] • G ∈ Z m×n q ∀i ≤ λ.
4. Output the evaluation key ek, the inversion key ik and the lossy tag generation key tk, which consist of

ek := Ā, (B i ) i≤λ , ik := (R i ) i≤λ , K , tk := K. (2)
A tag t = (t c , t a ) ∈ {0, 1} λ × {0, 1} k will be injective whenever t c = PRF(K, t a ).

Lossy tag generation. ABM.LTag(tk, t a ) takes as input an auxiliary tag component t a ∈ {0, 1} k and uses tk = K to compute and output t c = PRF(K, t a ).

Evaluation. ABM.Eval(ek, t, (x, e)) takes in the function input (x, e) ∈ Dom E λ , the tag t = (t c , t a ) ∈ {0, 1} λ × {0, 1} k and proceeds as follows. 1. For each j ≤ λ, let C PRF,j (t a ) : {0, 1} λ → {0, 1} be the NAND Boolean circuit, where t a ∈ {0, 1} k is hard-wired, which evaluates the j-th bit of PRF( K, t a ) ∈ {0, 1} λ for any K ∈ {0, 1} λ . Run the public evaluation algorithm of Lemma 10 to obtain6 B PRF,j ← Eval pub (C PRF,j (t a ), (B i ) i≤λ ).

Define the matrix

A t = Ā j≤λ (-1) tc[j] • B PRF,j + t c [j] • G ∈ Z 2m×n q ,
and compute the output y = A t • x + e ∈ Z 2m q . Inversion. ABM.Invert(ik, t, y) inputs the inversion key ik := (R i ) i≤λ , K , the tag t = (t c , t a ) ∈ {0, 1} λ × {0, 1} k and y ∈ Rng λ , and proceeds as follows.

1. Return ⊥ if t c = PRF(K, t a ). 2. Otherwise, for each j ≤ λ, run the private evaluation algorithm from Lemma 10 to obtain R PRF,j ← Eval priv (C PRF,j (t a ), (R i ) i≤λ ) and compute the (small-norm) matrix BP instead. Indeed, under this small-depth assumption, these algorithms still run in polynomial-time, and have the advantage of leading to smaller R t 's. This eventually allows one to set q as a polynomial function of λ. In the rest of this section, we choose these variants of Eval pub and Eval priv . The results can be readily adapted to the other option.

R t = j≤λ (-1) tc[j] • R PRF,j ∈ Z m×m . 3.
Theorem 2. Let χ = D Z,β/(2 √ λ) for some β > 0. Assume that PRF has depth d = O(log λ)
when the circuit input is the key and the PRF input is hard-coded in the circuit. Assume that ≥ λ, n = Ω( log q) and m ≥ 2n log q, γ x ≥ 3 m/n and γ e ≥ 3. Assume also that

σ x ≥ Ω(n), σ e ≥ Ω(4 d • m 2 • β • √ n • σ x ) and σ e ≤ O(q/(λ • 4 d • m 2 )).
Then, under the PRF security and LWE ,2m,q,χ hardness assumptions, the above function is an l-lossy ABM LTF with l = Ω(n log n).

The theorem follows from the lemmas below.

Lemma 12 (Correctness). Let us assume that and q/σ e ≥ λ•4 d •O(m 2 ). Assume that PRF has logarithmic depth O(log λ) when the circuit input is the key and the PRF input is hardcoded in the circuit. Then, for any triple (ek, ik, tk) produced by ABM.Gen(1 λ ), for any tag t = (t c , t a ) ∈ {0, 1} λ × {0, 1} k satisfying t c = PRF(K, t a ) and for any input (x, e) ∈ Dom D λ , the inversion correctness condition (x, e) = ABM.Invert(ik, t, ABM.Eval(ek, t, (x, e))) is satisfied.

Proof. By Lemma 10, we have

R t ≤ λ • 4 d • O(m 3/2 ) and A t = Ā R t • Ā + h t • G mod q,
where h t is the Hamming distance between t c and PRF(K, t a ) ∈ {0, 1} λ . As q > λ is prime, integer h t is invertible modulo q, and R t is a G-trapdoor with tag h t for A t . Thanks to our parameters, we have e ≤ q/(10 • R t ) and hence algorithm Invert from Lemma 9 recovers (x, e).

Our ABM-LTF provides evasiveness unless the PRF family is not unpredictable, which would contradict its pseudorandomness. In order to meaningfully rely on the pseudorandomness of PRF, the proof of Lemma 13 also appeals to the LWE assumption so as to first move to a game where the lossy matrix Ā ∈ Z m×n q is traded for a random matrix. Since the matrices

B i = R i • Ā + K[i]
• G depend the bits of the seed K, moving to a uniform matrix Ā is necessary to make sure that the evaluation key ek is statistically independent of K.

Lemma 13 (Evasiveness). Assume that m ≥ 2n log q. Any ppt evasiveness adversary A making Q 1 and Q 2 queries to ABM.LTag and ABM.IsLossy, respectively, implies an LWE distinguisher D 1 and a PRF distinguisher D 2 such that

Adv A,eva Q 1 ,Q 2 (λ) ≤ n • Adv D 1 ,LWE ,m,q,χ (λ) + Adv D 2 ,PRF Q 1 +Q 2 (λ) + Q 2 + 1 2 λ .
Proof. Let us assume the existence of a ppt evasiveness adversary A with non-negligible advantage Adv A,eva Q 1 ,Q 2 (λ). Without loss of generality, we can consider the adversary A as successful as soon as it manages to query the ABM.IsLossy(tk, •) oracle with input a non-trivial lossy tag t = (t c , t a ), i.e., a tag such that t a has never been submitted to the ABM.LTag(tk, •) oracle. Note that, for any input (t c , t a ) = (t c , t a ) such that t c ← ABM.LTag(tk, t a ), the oracle ABM.IsLossy(tk, •) returns 0 since t c is a deterministic function of t a .

We show that A implies either an LWE ,m,q,χ distinguisher D 1 or a PRF distinguisher D 2 with noticeable advantage. To this end, we consider a sequence of games that begins with the real evasiveness game and ends with a game where the adversary's advantage is statistically negligible. For each i, we call W i the event that the adversary wins, in which case the challenger outputs 1.

Game 0: This is the real evasiveness game where the adversary A is fed with a real evaluation ek and interacts with the real ABM.LTag(tk, •) oracle. We call W 0 the event that, at some point of the game, the adversary A queries ABM.IsLossy(tk, •) for a nontrivial input t = (t c , t a ) such that t c = PRF(K, t a ), where tk = K, and t a has never been queried to ABM.LTag(tk, •). By assumption, we know that A wins with probability Pr[W 0 ] = Adv A,eva Q 1 ,Q 2 (λ). Game 1: This game is identical Game 0, except that we modify the distribution of the evaluation key ek. Namely, the matrix Ā ∈ Z m×n q is now sampled uniformly. Under the LWE ,m,q,χ assumption, this change does not significantly affect A's winning probability. Using the hybrid argument, we obtain that

| Pr[W 1 ] -Pr[W 0 ]| ≤ n • Adv D 1 ,LWE
,m,q,χ (λ), for some efficient algorithm D 1 . Game 2: This game is identical to Game 1 with the difference that the matrices (B i ) i≤λ are now sampled uniformly in Z m×n q . Lemma 2 implies that the distribution of ek remains statistically unchanged: we have

| Pr[W 2 ] -Pr[W 1 ]| ≤ 2 -λ .
We remark that the PRF seed tk = K is now perfectly independent of ek. Game 3: This game is like Game 2 but we modify the ABM.LTag(tk, •) and ABM.IsLossy(tk, •) oracles. Instead of returning t c = PRF(K, t a ) at each query of the form ABM.LTag(tk, t a ), the ABM.LTag(tk, •) oracle outputs R(t a ) ∈ {0, 1} λ , where R : {0, 1} k → {0, 1} λ is a uniformly random function, which the challenger lazily defines by uniformly sampling a λ-bit string at each new query t a ∈ {0, 1} k . At each query to ABM.IsLossy(tk, •), adversary A chooses a tag t and we call W 3 the event that one of these tags t = (t c , t a ) satisfies t c = R(t a ) although t a has never been queried to ABM.LTag(tk, •). Given that R(•) is a truly random function, we have Pr[W 3 ] = Q 2 /2 λ , where Q 2 is the number of queries to ABM.IsLossy(tk, •). Moreover, as explained below, there exists a PRF distinguisher D 2 that makes at most

Q 1 + Q 2 PRF evaluation queries and such that | Pr[W 3 ] -Pr[W 2 ]| ≤ Adv D 2 ,PRF Q 1 +Q 2 (λ)
. Algorithm D 2 interacts with a PRF challenger that chooses a uniform key K ← U ({0, 1} λ ) and either always outputs PRF(K , M ) at each query M or always outputs uniform values in the range {0, 1} λ of PRF(K , •).

To generate the evaluation key for A, D 2 chooses random matrices Ā ← U (Z m×n q

) and B i ← U (Z m×n q ) for each i ≤ λ and runs A on input of ek = Ā, (B i ) i≤λ . Note that the distribution of ek is identical to that of Game 2. Whenever A invokes ABM.LTag(tk, •) on input of an auxiliary tag part t a ∈ {0, 1} k , distinguisher D 2 submits t a to its own PRF challenger and relays the response back to A. At each query t = (t c , t a ) made by A to ABM.IsLossy(tk, •), distinguisher D 2 submits the corresponding t a ∈ {0, 1} k to its PRF challenger. When obtaining the response v ∈ {0, 1} λ , it checks if t c = v. If so, distinguisher D 2 halts, and outputs 1 to declare the adversary successful. If A terminates without having queried ABM.IsLossy(tk, •) on such a lossy tag, distinguisher D 2 outputs 0.

Let us assume that D 2 's challenger always outputs pseudo-random values PRF(K , t a ) when invoked on the input t a . In this case, A's view is the same as in Game 2, so that Putting the above altogether completes the proof of the lemma.

The pseudo-randomness of core tag components also guarantees that lossy tags are computationally indistinguishable from uniformly random tags. The proof of Lemma 14 also relies on the LWE assumption since the evaluation key ek only hides the PRF seed K in the computational sense. It follows the same strategy as the proof of Lemma 13. Lemma 14 (Indistinguishability). Assume that m > 2n log q. Then ppt indistinguishability adversary A implies either either an LWE distinguisher D 1 or a PRF distinguisher D 2 such that:

Adv A,ind Q (λ) ≤ 2n • Adv D 1 ,LWE ,m,q,χ (λ) + Adv D 2 ,PRF Q (λ) + 1 2 λ-1 ,
where Q denotes the number of (genuine or uniform) lossy tag generation queries.

Proof. Let A be an adversary that has non-negligible advantage in distinguishing outputs of the lossy tag generation oracle ABM.LTag(tk, •) from uniform elements in T c = {0, 1} λ . We show that A implies either an LWE ,m,q,χ distinguisher D 1 or a PRF distinguisher D 2 . We prove this claim using a sequence of games that begins with a game where A interacts with an oracle ABM.LTag(tk, •) that always outputs the unique t c such that t = (t c , t a ) ∈ T loss at each query t a . In the final game, adversary A interacts with an oracle O Tc (•) that outputs uniform strings in {0, 1} λ . For each i, we call W i the event that the adversary outputs 1.

Game 0: In this game, adversary A is given a real evaluation key ek and interacts with an oracle ABM.LTag(tk, •) that outputs t c = PRF(K, t a ), where tk = K, at each query t a ∈ {0, 1} k . When A halts, it outputs a bit b ∈ {0, 1} and we call W 0 the event that b = 1.

Game 1: This game is like Game 0 except that we modify the distribution of the evaluation key ek. Namely, the matrix Ā ∈ Z m×n q is sampled uniformly. As in the proof of Lemma 13, we have

| Pr[W 1 ] -Pr[W 0 ]| ≤ n • Adv D 1 ,LWE
,m,q,χ (λ), for some efficient algorithm D 1 Game 2: This game is like Game 1 except that the matrices (B i ) i≤λ are now sampled uniformly in Z m×n q . As in the proof of Lemma 13, we have

| Pr[W 2 ] -Pr[W 1 ]| ≤ 2 -λ .
Game 3: This game is identical to Game 2 but we replace the ABM.LTag(tk, •) oracle by the oracle O Tc (•) that outputs random λ-bit strings at each new query and consistently returns the same outputs if a given query t a occurs more than once. Instead of returning t c = PRF(K, t a ) at each query t a , the oracle thus outputs R(t a ) ∈ {0, 1} λ , where R : {0, 1} k → {0, 1} λ is a uniformly random function, which is lazily defined by sampling random strings in {0, 1} λ at each new query t a ∈ {0, 1} k . When A halts, it outputs a bit b ∈ {0, 1} and we call W 3 the event that b = 1.

It can be seen that Pr

[W 3 ] is close to Pr[W 2 ] if PRF is a pseudo-random function fam- ily, as there is a distinguisher D 2 such that | Pr[W 3 ] -Pr[W 2 ]| ≤ Adv D 2 ,PRF Q (λ).
In short, distinguisher D 2 interacts with a PRF challenger that chooses a key K ← U ({0, 1} λ ) and either always outputs PRF(K , M ) at each query M or always outputs random strings {0, 1} λ at each fresh query. To generate the evaluation key for A, distinguisher D 2 samples Ā ← U (Z m×n q ) and B i ← U (Z m×n q ) for each i ≤ λ and feeds A with ek = Ā, (B i ) i≤λ . Whenever A queries ABM.LTag(tk, •) on input of an auxiliary tag t a ∈ {0, 1} k , distinguisher D 2 queries t a to its PRF challenger and relays the answer to A. When A terminates, distinguisher D 2 outputs whatever A outputs. If D 2 's challenger always outputs pseudo-random values PRF(K , t a ) on input of t a , then A's view is clearly the same as in Game 2. If D 2 's challenger always outputs uniformly random strings in {0, 1} λ , then D 2 is providing A with the same view as in Game 3. We thus have | Pr

[W 3 ] -Pr[W 2 ]| ≤ Adv D 2 ,PRF Q (λ), as claimed.
Game 4: This game is like Game 3, except that we change again the generation of matrices (B i ) i≤λ in the evaluation key ek. For each i ≤ λ, we step back to computing

B i = R i • Ā+K[i]• G ∈ Z m×n q , with R i ← U ({-1, 1} m×m ) and K[i] ← U ({0, 1})
. By the same argument as in Game 2, the view of A remains statistically unchanged and we have | Pr

[W 4 ]-Pr[W 3 ]| ≤ 2 -λ .
Game 5: We restore the matrix Ā ∈ Z m×n q back to its original distribution. Under the LWE ,m,q,χ assumption, we have | Pr

[W 5 ] -Pr[W 4 ]| ≤ n • Adv D 1 ,LWE
,m,q,χ (λ), for some efficient algorithm D 1 .

Combining the above leads to the claimed bound on Adv

A,ind Q (λ).
The proof of lossiness is essentially identical to that of the LTF (Theorem 1).

Lemma 15 (Lossiness). Let χ = D Z,β/(2 √ λ) for some β > 0. Assume that the depth d of PRF is in O(log λ), when the circuit input is the key and the PRF input is hardwired in the circuit. Let us assume that ≥ λ and n = Ω( log q). Assume also that σ e ≥ Ω(

4 d • m 2 • β • σ x • √ n).
Then, for any lossy tag t = (t c , t a ), the above ABM-LTF is l-lossy with l = Ω(n log n).

Proof. We rely on the fact that, for any lossy tag t = (t c , t a ) (i.e., for which t c = PRF(K, t a )), we have

A t = Ā R t • Ā = B R t • B • C + F R t • F , (3)
where B ← U (Z m× q ), C ← U (Z ×n q ), F ← χ m×n and R t is as in the ABM.Invert description. As a consequence, by the same argument as in the proof of Theorem 1, the distribution of the input (x, e) conditioned on ABM.Eval(ek, t, (x, e)) is the same as the distribution of (x, e) conditioned on (C • x, F • x + e). From this point, the proof is identical to that of Theorem 1, with

F new = [F | (R t • F)
] playing the role of F in the original proof. The two properties of F new used in the proof are Lemma 10, which leads to a larger σ e by the factor O(4 d • m 3/2 ). The other property is a lower bound on σ n (F new ) and since the latter is ≥ σ n (F), no parameters are affected.

F new ≤ (1 + R t ) • F ≤ O(4 d • m 3/2 ) • F , using
In [4, Section 7], Alwen et al. used the a rounding technique [START_REF] Banerjee | Pseudo-random functions and lattices[END_REF] to build an all-butone trapdoor function. While our construction bears resemblance with theirs, our proof of lossiness is very different. In [4, Theorem 7.3], they consider a matrix of the form (3) and crucially rely on the statistical independence of the rows of [B | (R 0 • B) ] , for some R 0 ∈ {-1, 1} m×m , conditionally on R 0 • F. Here, we cannot guarantee that matrices R t • B be statistically independent for different tags t, and hence it does not seem possible to directly use the rounding technique from [START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF]. Fortunately, the proof of Lemma 15 does not require the rows of the matrix [B | (R t • B) ] to be statistically independent and neither does it rely on the independence of R t • B for different tags t.

Joint Use of Lossy and All-But-Many Functions

We remark that our LTF and ABM-LTF are not lossy enough to be correlation-secure in the sense of Rosen and Segev [START_REF] Rosen | Chosen-ciphertext security via correlated products[END_REF]: indeed, the result of [80, Theorem 3.3] requires lossy functions that lose at least half of their input. In particular, we cannot reveal y 0 = A • x + e and y = A t • x + e for the same input (x, e) as this would expose yy 0 = (A -A t ) • x, which would leak (x, e). However, we can safely reveal y 0 = LTF.Eval(ek , (x, e 0 )) = A • x + e 0 and y = ABM.Eval(ek, t, (x, e)) = A t • x + e for distinct Gaussian terms e 0 , e ∈ Z 2m . Indeed, conditionally on LTF.Eval(ek , (x, e 0 )) and ABM.Eval(ek, t, (x, e)), the distribution of x retains l bits of min-entropy, where l = Ω(n • log n). As in the proof of Theorem 1, this follows by observing that the residual distribution on x is a discrete Gaussian (by Lemma 15) whose covariance matrix is above the smoothing parameter of the support.

Lemma 16. The LTF of Section 3.1 and the above ABM-LTF are jointly lossy when they share the first part x of their inputs.

Let χ = D Z,β/(2 √ λ) for some β > 0. Assume that the depth d of PRF is in O(log λ), when the circuit input is the key and the PRF input is hardwired in the circuit. Let us assume that ≥ λ and n = Ω( log q). Assume also that σ e ≥ Ω(

4 d • m 2 • β • √ n • σ x ).
Then, except with probability ≤ 2 -Ω(λ) over the choice of ek ← LTF.

LGen(1 λ ), ek ← ABM.Gen(1 λ ), x ← Dom x , and e 0 , e ← Dom e , we have, for any lossy tag t:

H ∞ x | LTF.Eval(ek , (x, e 0 )), ABM.Eval(ek, t, (x, e)) ≥ n • log σ x -2 -log q > Ω(n • log n).
Proof. The result follows by generalizing the proofs of Theorem 1 and Lemma 15 in a straightforward manner. If

A LTF = B LTF •C LTF +F LTF ∈ Z 2m×n q and Ā = B ABM •C ABM +F ABM ∈ Z m×n q
are the lossy matrices of both functions, the information revealed by LTF.Eval(ek , (x, e 0 )) and ABM.Eval(ek, t, (x, e)) is

  B LTF 0 2m× 0 m× B ABM 0 m× R t • B ABM   • C LTF C ABM • x +   F LTF F ABM R t • F ABM   • x + e 0 e .

It is thus entirely determined by the product [C

LTF | C ABM ] • x ∈ Z 2 q and the integer vector [F LTF | F ABM | (R t • F ABM ) ] • x + [e 0 | e 1 ] ∈ Z 4m
. We obtain the result by repeating the arguments in the proof of Theorem 1 and Lemma 15.

Selective Opening Chosen-Ciphertext Security

We now combine our ABM-LTF and the LWE-based LTF of Section 3 to build an IND-SO-CCA2-secure public-key encryption scheme from the LWE assumption. The scheme can be seen as instantiating a variant of the Peikert-Waters methodology [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], as generalized by Hofheinz [57, Section 6.3] to the case of multiple lossy tags. In [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF], ciphertexts consists of (f lossy (x), f ABM (t, x), Msg ⊕ h(x)), where f lossy (x) (resp. f ABM (t, x)) is a lossy (resp. all-butmany) function of x; t is the tag of the ciphertext; and h(x) is a universal hash of x.

Nevertheless, our scheme is not a generic instantiation of this paradigm as we cannot use exactly the same input x in the two functions f lossy (•) and f ABM (t, •). As we mentioned earlier, we cannot give out function outputs y 0 = A • x + e and y = A t • x + e for the same input (x, e). For this reason, our lossy and ABM functions have to use distinct noise terms (e 0 , e) in the two evaluations y 0 = A • x + e 0 and y = A t • x + e. The decryption algorithm can proceed by inverting (x, e 0 ) ← f -1 lossy (y 0 ) as before. However, instead of simply testing if y = f ABM (t, (x, e 0 )) by evaluating f ABM (t, .) in the forward direction as in [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF][START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF], the receiver has to test whether y -A t • x is a small-norm vector, analogously to [START_REF] Peikert | Public-key cryptosystems from the worst-case shortest vector problem[END_REF]Section 4.4]. For this reason, the message Msg is hidden by the universal hash of x only, which is sufficient in our security proof. Moreover, our extension to SIM-SO-CCA2 security requires h(•) to operate on x alone.

Unlike [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF], we cannot use one-time signatures to bind ciphertext components in a nonmalleable manner. Indeed, at each corruption query, the challenger would have to reveal the one-time secret keys of the challenge ciphertexts, which would allow the adversary to make decryption queries for lossy tags.

Instead, we rely on hybrid encryption and proceed analogously to Boyen et al. [START_REF] Boyen | Direct chosen ciphertext security from identity-based technique[END_REF]: namely, we define the auxiliary tags to be the output y 0 = Π LTF .Eval(ek , (x, e 0 )) of the lossy function while resorting to the hybrid encryption paradigm and authenticate the messagecarrying part c 0 = Msg + h(x) of the ciphertext via the encrypt-then-MAC approach. One difficulty is that, since y 0 = Π LTF .Eval(ek , (x, e 0 )) and y = Π ABM .Eval(ek, t, (x, e)) involve distinct small-norm vectors e 0 , e, we must find a different way to prevent the adversary from tampering with e in one of the challenge ciphertexts (indeed, the ABM-LTF output y is no longer authenticated by a one-time signature). Our solution to this problem is to include y = Π ABM .Eval(ek, t, (x, e)) in the input of the MAC, which simultaneously authenticates y and c 0 . For simplicity, we assume MACs with the uniqueness property but the proof can be adapted to rely on any strongly unforgeable MAC.

As mentioned in [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF]Section 6], the application to IND-SO-CCA2 security requires the core tag space T c of ABM-LTFs to be efficiently samplable and explainable. As defined in [57, Definition 6.2], "explainability" (a.k.a. "invertible samplability" [START_REF] Damgård | Improved non-committing encryption schemes based on a general complexity assumption[END_REF]) means that any core tag t c can be explained by the challenger as having been uniformly chosen "without ulterior motive" when the adversary opens a given ciphertext in the game of Definition 10. Our ABM-LTF clearly satisfies this property since core tags t c are just random λ-bit strings.

Description

Par-Gen(1 λ ): Selects public parameters consisting of:

-A modulus q > 2, integers , 0 , 1 , n ∈ poly(λ), m = cn • log q , for some constant c > 0, and parameters β, σ x , σ e > 0. -The specification MAC = (KG, Sig, Ver) of a unique message authentication code with message space MsgSp mac := Z 2m q × Z 0 q and key space

K mac := Z 1 q . -A family UH of universal hash functions h : [-σ x √ n, σ x √ n] n → Z 0 + 1 q
that range over MsgSp := Z 0 q . The public parameters Γ = { , 0 , 1 , n, m, q, β, σ x , σ e , MAC} define the plaintext space MsgSp := Z 0 q and will be shared by the LWE-based LTF of Section 3.1 and our ABM-LTF of Section 3.2.

Keygen(Γ ): Let Π LTF = (IGen,
LGen, Eval, Invert) be an instance of the LTF of Section 3.1 and let Π ABM = (Gen, Eval, Invert, LTag) be an instance of the ABM-LTF of Section 3.2. We assume Π LTF and Π ABM both operate over the domain

Dom D λ := {(x, e) ∈ Z n × Z 2m | x ≤ σ x √ n, e ≤ σ e √ 2m}.
The public key is generated via the following steps.

1. Generate a pair (ek , ik ) ← Π LTF .IGen(1 λ ) for an injective function of the lossy trapdoor function family Π LTF .

2. Generate (ek, ik, tk) ← Π ABM .Gen(1 λ ) as an ABM-LTF key pair. We assume that the space of auxiliary tags is T a = Z m q 3. Choose a random member h ← UH of the universal hash family.

Output (P K, SK) where P K = ek , ek, h and SK = ik .

Encrypt(P K, Msg): To encrypt Msg ∈ Z 0 q , choose x ← D Z n ,σx , e 0 ← D Z 2m ,σe , e ← D Z 2m ,σe and do the following.

1. Compute y 0 = Π LTF .Eval(ek , (x, e 0 )) = A • x + e 0 ∈ Z 2m q . 2. Define t a = y 0 and choose a random t c ← U (T c ). Then, let t = (t c , t a ) and compute y = Π ABM .Eval(ek, t, (x, e))

= A t • x + e ∈ Z 2m q . 3. Compute (k sym , k mac ) = h(x) ∈ Z 0 q × Z 1 q . 4. Set c 0 = Msg + k sym ∈ Z 0
q and c 1 = MAC.Sig(k mac , (y, c 0 )). Output the ciphertext C = (t c , c 0 , c 1 , y 0 , y).

Decrypt(SK, C):

To decrypt C = (t c , c 0 , c 1 , y 0 , y) using SK = ik , 1. Compute (x, e 0 ) ← Π LTF .Invert(ik , y 0 ). Return ⊥ if the vector y 0 ∈ Z 2m q is not in the range 7 of Π LTF .Eval(ek , •) or if (x, e 0 ) ∈ Dom D λ . 2. Define the tag t = (t c , y 0 ). If y -A t • x > σ e √ 2m, return ⊥. 3. Compute (k sym , k mac ) = h(x) ∈ Z 0 q × Z 1 q . 4. If MAC.Ver(k mac , (y, c 0 ), c 1 ) = 0, return ⊥. Otherwise, compute and output the plain- text Msg = c 0 -k sym ∈ Z 0 q .
We note that, while the encryption algorithm requires to homomorphically compute λ circuits, these evaluations can take place in an off-line phase, where y 0 and y are pre-computed before knowing Msg.

In order to instantiate the scheme with a polynomial-size modulus q, we need a PRF with an evaluation circuit in NC 1 , which translates into a polynomial-length branching program. By applying Lemma 10 and exploiting the asymmetric noise growth of the GSW FHE as in [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF], we can indeed keep q small. For this purpose, the Banerjee-Peikert PRF [START_REF] Banerjee | New and improved key-homomorphic pseudo-random functions[END_REF] is a suitable candidate. While its evaluation circuit is in NC 2 in general, we can still homomorphically evaluate input-dependent circuits C PRF,j (•) over the encrypted key K using an NC 1 circuit. For public moduli p, q and matrices A 0 , A 1 ∈ Z n×n log q q , their PRF maps an input x ∈ {0, 1} k to (p/q) • (k • A x mod q) , where k ∈ Z n q is the secret key and the input-dependent matrix A x is publicly computable from A 0 , A 1 . This allows hard-coding A x into an NC 1 circuit to be evaluated over the "encrypted" bits of k in order to obtain "encryptions" of the bits of (p/q) • k • A x . Indeed, matrix-vector products and rounding can both be computed in TC 0 ⊆ NC 1 , which allows using a polynomial-size q by applying Lemma 10. The resulting instantiation relies on the same LWE assumption as the Banerjee-Peikert PRF [START_REF] Banerjee | New and improved key-homomorphic pseudo-random functions[END_REF], where the modulus-to-noise ratio is only slightly super-polynomial.

Keygen(Γ, loss): Given public parameters Γ = { , 0 , 1 , n, m, q, β, σ x , σ e } containing integers , 0 , n, m such that n > 2 • (2 + 0 + 1 ) • log q and m > 2(n + ) • log q, conduct the following steps. 1. Choose a random matrix C 0 ← U Z n× ¯ q , where ¯ = (2 + 0 + 1 ) and n = n-¯ • log q which is used to run the (C, R sim ) ← GenTrap(C 0 , I¯ , σ x ) algorithm of Lemma 8 to produce a statistically uniform C ∈ Z ¯ ×n q with a a small-norm R sim ∈ Z ¯ • log q ×n forming a G sim -trapdoor, where G sim ∈ Z ¯ • log q × ¯ q is the gadget matrix of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]. Parse

C ∈ Z ¯ ×n q as C =   C LTF C ABM H U H   ∈ Z ¯ ×n q , ( 4
)
where

C LTF , C ABM ∈ Z ×n q and H U H ∈ Z ( 0 + 1 )×n q . 2. Sample matrices B LTF ← U (Z 2m× q ), B ABM ← U (Z m× q ), F LTF ← χ 2m×n , F ABM ← χ m×n in order to define A LTF = B LTF • C LTF + F LTF ∈ Z 2m×n q A ABM = B ABM • C ABM + F ABM ∈ Z m×n q ,
which are statistically close to outputs of Lossy(1 n , 1 m , 1 , q, χ) as C LTF and C ABM are statistically uniform over Z ×n q . 3. Define ek = A LTF ∈ Z 2m×n q to be the evaluation key of Π LTF . Then, run Steps 2-4 of the key generation algorithm of Π ABM while setting Ā = A ABM ∈ Z m×n q at Step 1. The resulting keys (ek, ik, tk) consist of

ek := A ABM , {B i } λ i=1 , ik := {R i } λ i=1 , K , tk := K
and are statistically close to the output distribution (2) of Π ABM .Gen.

Return P K loss = (ek , ek, H U H ) and

SK loss = R sim , C 0 , B LTF , B ABM , F LTF , F ABM , ik . (5)
Opener(Γ, P K loss , SK loss , Msg 0 , (x, e 0 , e 1 ), Msg 1 ): Parse SK loss as in ( 5) and conduct the following steps.

1. Compute t LTF,x = C LTF • x ∈ Z q , t ABM,x = C ABM • x ∈ Z q and k sym,x k mac,x = H U H • x ∈ Z 0 + 1 q .
Then, set t Msg,x = (Msg 0 -Msg 1 ) + k sym,x ∈ Z 0 q and define

t x = t LTF,x | t ABM,x | t Msg,x | k mac,x ∈ Z ¯ q .
2. Using the trapdoor R sim ∈ Z ¯ • log q ×n , sample a small-norm vector x ← D

S F,tx,f Λ ⊥ (C)+z, √ Σ,c
so as to have a short integer vector x ∈ Z n satisfying C • x = t x mod q, using an

arbitrary solution z ∈ Z n of C • z = t x ∈ Z ¯ q
, where Σ and c are defined based on Lemma 11, for

F :=   F LTF F ABM R t • F ABM   ∈ Z 4m×n , e := e 0 e ∈ Z 4m , f := F • x + e ∈ Z 4m . ( 6
)
3. Output (x , e 0 , e ) where

   e 0 = F LTF • (x -x ) + e 0 ∈ Z 2m e = F ABM R t • F ABM • (x -x ) + e ∈ Z 2m (7)
We observe that algorithm Opener is efficient. In particular, at Step 2, it can compute the matrix Σ and the vector c of Lemma 11 by first reconstructing the matrix F ∈ Z 4m×n of (6) and the vector f = F • x + e ∈ Z 4m , which requires to deterministically re-compute the integer matrix R t obtained at Step 2 of ABM.Invert(ik, t, .) using ik = ((R i ) i≤λ , K).

We easily check that, for any vector x sampled at Step 2, the corresponding

k sym,x k mac,x = H U H • x ∈ Z 0 + 1 q
satisfy k mac,x = k mac,x 0 and k sym,x = (Msg 0 -Msg 1 ) + k sym,x mod q. As a consequence, if C = (t c , c 0 , c 1 , y 0 , y) ← Encrypt(P K loss , Msg 0 , (x, e 0 , e)), the obtained ciphertext C contains c 0 = Msg 0 + k sym,x mod q, c 1 = MAC.Sig(k mac,x , (y, c 0 )), which coincide with c 0 = Msg 1 + k sym,x and c 1 = MAC.Sig(k mac,x , (y, c 0 )). Moreover, we also have

C LTF • x = C LTF • x and C ABM • x = C ABM • x .
The following theorem formally states the correctness of the Opener algorithm.

Theorem 4. For any key pair (P K loss , SK loss ) in the support of Keygen(Γ, loss), algorithm Opener outputs (x , e 0 , e ) with the correct distribution conditionally on Encrypt(P K loss, , Msg 0 , (x, e 0 , e)) = Encrypt(P K loss, , Msg 1 , (x , e 0 , e )).

Proof. For any lossy tag t = (t c , t a ), the matrix A t used by Π ABM .Eval(ek, t, .) is of the form

A t = A ABM R t • A ABM = B ABM R t • B ABM • C ABM + F ABM R t • F ABM , (8)
where R t ∈ Z m×m is the integer matrix obtained in ABM.Invert(ik, t, .). At the same time, ek consists of a matrix of the form

A LTF = B LTF • C LTF + F LTF .
We now claim that, due to the way to sample x at Step 2 of Opener and the definition of e 0 and e at Step 3, the distribution of y 0 and y , with

y 0 = A LTF • x + e 0 ∈ Z 2m y = A t • x + e ∈ Z 2m (9)
is the same as that of the real encryptions explained in the beginning of this Section. By replacing A LTF , A t and e 0 and e we get:

y 0 = (B LTF • C LTF + F LTF ) • x + (F LTF • (x -x ) + e 0 ) = B LTF • C LTF • x + F LTF • x + e 0 = B LTF • C LTF • x + F LTF • x + e 0 = A LTF • x + e 0 ∈ Z m and y = B ABM R t • B ABM • C ABM + F ABM R t • F ABM • x + F ABM R t • F ABM • (x -x ) + e (10)
= B ABM R t • B ABM • C ABM • x + F ABM R t • F ABM • x + e = B ABM R t • B ABM • C ABM • x + F ABM R t • F ABM • x + e = A t • x + e ∈ Z 2m
It remains to show that (x , e 0 , e ) have the correct distribution. Recall that x is sampled by applying the second part of Theorem 1 at Step 2. By applying Lemma 11 to the matrix C of (4) with u = t x , the conditional distribution of x given (t x ,

F • x + e) is statistically close to D S F,tx,f Λ ⊥ (C)+z, √ Σ,c
, where z is an arbitrary solution of C • z = t x . Since x can be efficiently sampled by Theorem 1, this provides the claimed result.

In Appendix E, we show that lattice trapdoors can also be used to obtain SIM-SO-CPA security from LTFs based on DDH-like assumptions.

A Efficiency Improvements for the Scheme of Section 4 Using MACs Instead of PRFs

The bottleneck of our constructions is the need to homomorphically evaluate O(λ) circuits when evaluating the all-but-many function in the encryption and decryption algorithms.

In our ABM-LTF, the motivation for using a PRF was to prove the feasibility of tightly CCA2-secure public-key encryption under lattice assumptions. In our SIM-SO-CCA2-secure encryption scheme (which is not meant to be tightly secure), we can substantially improve the efficiency by trading the PRF for a MAC in our ABM-LTF construction.

Concretely, we can have the matrices

B i = R i • Ā + K[i]
• G encrypt the bits of the MAC secret key K ∈ {0, 1} λ and define lossy tags t = (t c , t a ) to be those for which MAC.Ver(K, t a , t c ) = 1. At Step 1 of the evaluation algorithm ABM.Eval(ek, t, •), we define C(t c , t a ) : {0, 1} λ → {0, 1} to be the circuit, where (t c , t a ) are hardwired, that outputs 1 -MAC.Ver(K, t a , t c ) ∈ {0, 1}. By doing so, we only need to evaluate one circuit.

In order to preserve the evasiveness property of the modified ABM-LTF, the MAC can be randomized but has to be strongly unforgeable. As for the indistinguishability property, we need the MAC to satisfy a stronger flavor of the notion of key-indistinguishability8 introduced by Alwen et al. [START_REF] Alwen | Key-indistinguishable message authentication codes[END_REF]. Namely, we need valid MACs to be computationally indistinguishable from random elements of the ambient space T c . If the MAC is both strongly unforgeable and pseudorandom, everything goes through in the proofs of IND-SO-CCA2 and SIM-SO-CCA2 security with the modified ABM-LTF.

In [3, Section 3.2], Alwen et al. proved the key-indistinguishability of the LPN-based MAC of [START_REF] Kiltz | Efficient authentication from hard learning problems[END_REF] (of which LWE-based variants were described in [START_REF] Kiltz | Efficient authentication from hard learning problems[END_REF]Appendix A.3]) by implicitly showing it pseudorandom (see [START_REF] Alwen | Key-indistinguishable message authentication codes[END_REF]Theorem 2]). Moreover, they also showed that this specific MAC can be made strongly unforgeable via a circuit-depth-preserving transformation due to Dodis et al. [39, Section 3.1], which maintains its pseudorandomness. Moreover, the verification algorithm of the resulting MAC fits within an NC 1 circuit as it basically requires two matrix-vector products followed by a Hamming weight test.

B Definitions for Cryptographic Primitives

B.1 Public-Key Encryption in the Multi-Challenge Setting Bellare, Boldyreva and Micali [START_REF] Bellare | Public-key encryption in a multi-user setting: Security proofs and improvements[END_REF] considered the following security definition, which accounts for multiple users and multiple challenge ciphertexts per user.

Definition 5. A public-key encryption scheme is (µ, Q E , Q D )-IND-CCA secure, for integers µ, Q E , Q D ,
if no ppt adversary has noticeable advantage in this game:

1. The challenger first generates Γ ← Par-Gen(1 λ ) and runs (SK (j) , P K (j) ) ← Keygen(Γ ) for j ≤ µ. It gives (P K (j) ) j≤µ to the adversary A and retains (SK (j) ) j≤µ . In addition, the challenger initializes a set Q ← ∅ and counters i e , i d ← 0. Finally, it chooses a random bit b ← U ({0, 1}).

The adversary A adaptively makes queries to the following oracles on multiple occasions:

-Encryption query: A chooses an index j ≤ µ and a pair (Msg 0 , Msg 1 ) of equallength messages; if i e = Q E , the oracle returns ⊥; otherwise, it computes C ← Encrypt(P K (j) , Msg b ) and returns C; in addition, it sets Q ← Q ∪ {(j, C)} and i e ← i e + 1. -Decryption query: A chooses an index j ≤ µ and an element C of the ciphertext domain; if i d = Q D or (j, C) ∈ Q, the oracle returns ⊥; otherwise, the oracle returns Msg ← Decrypt(SK (j) , C), which may be ⊥ if C is an invalid ciphertext, and sets

i d ← i d + 1. 3. The adversary A outputs a bit b and is deemed successful if b = b. As usual, A's advan- tage is measured as the distance Adv CCA µ,Q E ,Q D (λ) := | Pr[b = b] -1/2|.
Using the random self-reducibility property of DDH, well-known constructions (e.g., the Cramer-Shoup encryption scheme [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF]) were shown [START_REF] Bellare | Public-key encryption in a multi-user setting: Security proofs and improvements[END_REF] to provide tight (poly, 1, poly)-IND-CCA security. Hofheinz and Jager [START_REF] Hofheinz | Tightly secure signatures and public-key encryption[END_REF] gave the first tight security result in the most general (poly, poly, poly) case. Here, we restrict ourselves to the single-user (1, poly, poly) setting, in which we provide the first tight multi-challenge security results under lattice assumptions.

B.2 One-Time Signatures, Message Authentication Codes and Pseudorandom Functions

A one time signature is a tuple of efficient algorithms (G, S, V), where:

-G takes as input a security parameter 1 λ and, optionally, a set of public parameters Γ . It outputs a key pair (SVK, SSK) -S is a possibly randomized algorithm that takes as input a message M and a secret key SSK. It outputs a signature sig. -V is a deterministic algorithm taking as input a verification key SVK, a message M and a candidate signature sig. It outputs 1 or 0.

We consider a security definition in the multi-signer setting (see, e.g., [START_REF] Hofheinz | Algebraic partitioning: Fully compact and (almost) tightly secure cryptography[END_REF]). Note that, while security in the single-user setting implies security in the multi-user setting via a standard hybrid argument, this argument is not tight as it incurs a linear security loss w.r.t. N .

Definition 6. A one-time signature (G, S, V) provides one-time strong unforgeability in the multi-user setting if no ppt adversary has non-negligible advantage in the following game.

1. The challenger generates N key pairs (SVK i , SSK i ) ← G(Γ, 1 λ ) and gives (SVK i ) i≤N to the adversary A. 2. The adversary adaptively makes up to N queries of the form (i, M i ). At each query, it obtains sig i ← S(SSK i , M i ). Note that a single query is allowed for each index i ≤ N . 3. A outputs (i , M , sig ) and wins if V(SVK i , M , sig ) = 1 and (M , sig ) = (M i , sig i ).

The adversary's advantage Adv A,suf-OTS N (λ) its probability of success taken over all random coins.

A message authentication code (MAC) is a triple MAC = (KG, Sig, Ver) of efficient algorithms which are associated with a key space K and a message space M. The syntax of these algorithms is the following: MAC.KG(1 λ ) takes as input a security parameter 1 λ and outputs a random secret key k ∈ K. MAC.Sig(k, M ) is an algorithm taking as input a message M ∈ M and a secret key k ∈ K.

It outputs an authentication value s ← MAC.Sig(k, M ). MAC.Ver(k, M, s) is a deterministic algorithm that takes in a secret key k ∈ K, a message M ∈ M and a candidate MAC value s. It outputs 1 or 0.

Definition 7.

A MAC is strongly one-time unforgeable under chosen-message attacks (sUF-OT-CMA) if no ppt adversary has non-negligible advantage in the following game:

1. The challenger chooses a random key k ∈ K. The adversary A is run on input of the security parameter 1 λ . 2. Adversary A adaptively makes the following kinds of queries:

-MAC queries: A chooses an arbitrary message M ∈ M. The challenger computes s ← MAC.Sig(k, M ) and returns σ. We insist that, in the above definition, the challenger is only efficient for distributions supporting efficient conditional resampling. It is known [START_REF] Hofheinz | Standard security does not imply indistinguishability under selective opening[END_REF] that, under certain conditions, standard security notions for public-key encryption do not imply security under indistinguishability-based selective openings.

B.4 Lossy Encryption

In [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] Bellare, Hofheinz and Yilek defined the notion of lossy encryption. In short, a lossy encryption scheme admits two computationally indistinguishable distributions of public keys. On injective keys, the system behaves in the usual way whereas, for lossy public keys, ciphertexts are statistically independent of the message they encrypt. Yet, no ppt adversary should be able to distinguish normal keys from lossy keys. It was proved in [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] that any lossy encryption scheme provides IND-SO-CPA security.

Bellare et al. [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] also consider a property, called openability, which allows a possibly inefficient algorithm Opener to open a ciphertext C generated under a lossy key to any arbitrary plaintext Msg by outputting coins r ∈ R such that C = Encrypt(P K, Msg, r). While lossy encryption is limited to provide IND-SO-CPA security, simulation-based security is also achieved when Opener is a ppt algorithm. As pointed out in [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF], a relaxed notion of efficient openability (termed weak efficient openability by Hofheinz et al. [START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF]) suffices to ensure SIM-SO-CPA security: in this relaxed flavor of openability, the Opener algorithm is given access to the original message and random coins that were used to create the ciphertext, which must now be opened to a different plaintext. Here, we adapt this definition to the case of a non-uniform random coin distribution. Definition 11 ([12,[START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF]). A lossy PKE scheme with weak efficient opening consists of a tuple (Par-Gen, Keygen, Encrypt, Decrypt) of efficient algorithms such that -Keygen(Γ, inj) outputs injective keys (P K inj , SK inj ).

-Keygen(Γ, loss) outputs keys (P K loss , SK loss ), which are called lossy keys.

Moreover, these algorithms must satisfy the following properties: and such that, for each R ∈ S P K,Msg,C , we have

D P K,Msg,C (R) = Pr R ← D R [R = R | Encrypt(P K, Msg, R ) = C].
There exists a ppt sampling algorithm Opener such that, given public parameters Γ ← Par-Gen(1 λ ), lossy keys (P K loss , SK loss ) ← Keygen(Γ, loss), random coins R ← R and any two messages Msg 0 , Msg 1 ∈ MsgSp, outputs, with probability ≥ 1 -2 -Ω(λ) over (SK loss , P K loss , R), an independent sample R from the distribution D P K,Msg 1 ,C , where C = Encrypt(P K loss , Msg 0 , R).

While weak efficient openability (i.e., property 4) is a weaker property than that of efficient openability, it suffices to guarantee simulation-based selective opening security. Lemma 17 ([12,[START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF]). Any lossy encryption scheme with efficient weak opening is SIM-SO-CPA secure.

While the above result was only proved for chosen-plaintext adversaries, it carries over to the chosen-ciphertext scenario. Namely, any IND-SO-CCA2 secure lossy encryption scheme is also secure in the SIM-SO-CCA2 sense.

C Tight Chosen-Ciphertext Security from LWE

Here, we combine our ABM-LTF and our LTF of Section 3 to obtain a public-key encryption scheme whose chosen-ciphertext security in the multi-challenge setting tightly relates to the LWE assumption if instantiated with a tightly secure LWE-based PRF.

The construction is similar to that of Section 4. The difference is that, instead of relying on the hybrid encryption paradigm, it uses one-time signatures, which allows for a tight reduction as we do not lose a factor Q E (i.e., the number of queries to the encryption oracle) w.r.t. the computational security of the MAC. Note that, in Section 4, we cannot rely on an unconditionally secure one-time MAC since the MAC secret key would have to be longer than the plaintext, which would not be compatible with the parameters of our Opener algorithm.

C.1 Description

We assume w.l.o.g. that the verification key SVK of the one-time signature fits within the space of auxiliary tags of the ABM-LTF, since it can always be hashed for this purpose.

Par-Gen(1 λ ). Selects public parameters consisting of:

-A modulus q > 2, integers , 0 , n ∈ poly(λ), m = cn • log q , for some constant c > 0, parameters σ x , σ e > 0, and an efficiently samplable LWE noise distribution. -The specification Σ = (G, S, V) of a one-time signature.

-A family UH of universal hash functions h : [-σ x √ n, σ x √ n] n → Z 0 q . The public parameters Γ = { , 0 , n, m, q, σ x , σ e , χ, Σ, UH} define the plaintext space MsgSp := Z 0 q and will be shared by the LTF of Section 3.1 and the ABM-LTF of Section 3.2.

Keygen(Γ ). Let Π LTF = (IGen, LGen, Eval, Invert) be an instance of the LTF family of Section 3.1 and let Π ABM = (Gen, Eval, Invert, LTag) be an instance of the ABM-LTF family of Section 3.2. We assume that functions Π LTF and Π ABM operate over the common domain

Dom D λ := {(x, e) ∈ Z n × Z 2m | x ≤ σ x • √ n, e ≤ σ e • √ 2m}.
The public key is generated via the following steps.

1. Generate (ek , ik ) ← Π LTF .IGen(1 λ ) for an injective function of the LTF family to obtain ek = A ∈ Z 2m×n q and ik = R ∈ {-1, 1} m×m . 2. Generate (ek, ik, tk) ← Π ABM .Gen(1 λ ) to obtain ek = ( Ā, (B i ) i≤λ ) and ik = ((R i ) i≤λ , K). 3. Sample an element h ← U (UH) of the universal hash family.

Output (P K, SK) where the public key is P K = ek , ek, h and the underlying private key consists of SK = ik .

Encrypt(P K, Msg). To encrypt Msg ∈ Z 0 q , generate a key pair (SVK, SSK) ← G(1 λ ) and do the following.

1. Sample (x, e 0 , e) ← D Z n ,σx × D Z 2m ,σe × D Z 2m ,σe . 2. Compute c 0 = Msg + h(x) ∈ Z 0 q .
3. Compute y 0 = Π LTF .Eval(ek , (x, e 0 )) = A • x + e 0 ∈ Z 2m q . 4. Define the auxiliary tag t a = SVK and choose a random t c ← U (T c ). Let t = (t c , t a )

and compute y = Π ABM .Eval(ek, t, (x, e)) = A t • x + e ∈ Z 2m q . 5. Generate a one-time signature sig = S(SSK, (t c , c 0 , y 0 , y)).

Output the ciphertext C = (SVK, t c , c 0 , y 0 , y, sig).

Decrypt(SK, C).

To decrypt C = (SVK, t c , c 0 , y 0 , y, sig) using SK = ik , 1. If V(SVK, (t c , c 0 , y 0 , y), sig) = 0, return ⊥. 2. Compute (x, e 0 ) ← Π LTF .Invert(ik , y 0 ) and return ⊥ if y 0 is not in the range of

Π LTF .Eval(ek , •) or if (x, e 0 ) ∈ Dom D λ . 3. Define the tag t = (t c , SVK). If y -A t • x 0 > σ e • √ 2m, return ⊥. 4. Return Msg = c 0 -h(x) ∈ Z 0
q . In order to instantiate the above construction with a polynomial-size modulus q, we need a PRF that can be evaluated via an NC 1 circuit -and thus a polynomial-length branching program [START_REF] Barrington | Bounded-width polynomial-size branching programs recognize exactly those languages in nc1[END_REF] -in order to apply Lemma 10. For this purpose, a tempting idea is to use the PRF 9 of Banerjee, Peikert and Rosen [6, Section 5], which has a tight reduction from an LWE assumption. However, as mentioned in [6, Section 5.2], evaluating this function in NC 1 is possible when the key is fixed and hard-coded into the circuit. In our setting, the input of the circuit should be the seed K -which is GSW-encrypted in the matrices {B i } i≤λ contained in ek -while it is the public string t a that can be hard-wired in the circuit to be evaluated on the encrypted K ∈ {0, 1}. In this case, the construction of [6, Section 5.2] seemingly requires an NC 2 circuit.

Another PRF candidate is the key-homomorphic construction of Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] as it is easily computable in NC 1 when the input is fixed. One hurdle is that the security proof of [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] is not tight as it incurs a concrete security loss (i.e., the ratio between the advantages of the adversary and the reduction) proportional to the number of evaluation queries. Fortunately, in Appendix F, we give a tighter security proof which eliminates the multiplicative gap proportional to the number of evaluation queries. This new proof thus allows instantiating the above cryptosystem system with a polynomial-size modulus while retaining a tight proof of CCA2 security (albeit under a strong LWE assumption).

C.2 Security

We show that the scheme provides almost tight (according to the terminology of [START_REF] Chen | Fully, (almost) tightly secure ibe and dual system groups[END_REF]) CCA2 security in the multi-challenge setting (in the sense of Definition 5 in Appendix B.1) under the LWE assumption. Namely, the security bound does not depend on the number Q E of challenge ciphertext obtained by the adversary. In order to avoid a degradation factor proportional to the number of decryption queries (which appears in [57, Theorem 6.5]), the security proof exploits the fact that our definition of evasiveness involves an ABM.IsLossy oracle to detect when the adversary creates a breach in the evasiveness property. This saves the reduction from losing a factor Q D , where Q D is the number of decryption queries. 9 This PRF maps inputs x ∈ {0, 1} κ to outputs (p/q) • A • κ i=1 S x i i , for secret matrices A ∈ Z m×n q and Si ∈ Z n×n and prime moduli p < q.

Theorem 5. The above scheme provides (1, Q E , Q D )-IND-CCA security assuming that: (i) Π LTF is an LTF; (ii) Π ABM is an ABM-LTF; (iii) PRF is a pseudo-random function family; (iv) Σ is a strongly unforgeable one-time signature. In our instantiation, for any ppt adversary A, there exists an LWE distinguisher D 1 , a PRF adversary D 2 and a signature forger B which all run in about the same time as A and such that

Adv A,CCA 1,Q E ,Q D (λ) ≤ 4n • Adv D 1 ,LWE ,2m,q,χ (λ) + 2 • Adv D 2 ,PRF Q E +Q D (λ) + Adv B,suf-OTS Q E + Q D + Q E + 2 2 λ-1 . (11)
To properly instantiate the above construction, we need a lattice-based one-time signature with a tight security proof in the multi-user setting (as defined in Appendix B.2) as the adversary can see signatures for up to Q E verification keys in the proof of Theorem 5. We provide a simple example in Appendix C.3.

Proof (of Theorem 5). The proof proceeds with a sequence of games. For each i, we let S i denote the event that the adversary A wins (by outputting b ∈ {0, 1} such that b = b) in Game i.

Game 0: This is the real game. It begins with the challenger B choosing a bit b ← U ({0, 1}) and generating P K = (ek , ek, h) while keeping SK = (ik, ik ) to itself. We may assume w.l.o.g. that the auxiliary tags t a = SVK (i) of all challenge ciphertexts are chosen at the very beginning of the game. At the outset of the game, B thus samples (x (1) , e

0 , e (1) ), . . . , (x (Q E ) , e

(Q E ) 0 , e (Q E ) ) ← D Z n ,σx × D Z 2m ,σe × D Z 2m ,σe .
For each i ∈ [Q E ], it then computes y (i) 0 = Π LTF .Eval(ek , (x (i) , e (i) )) and k sym,(i) = h(x (i) ). It also defines t

(i) a = SVK (i) , defines t (i) = (t (i) c , t (i)
a ) for a random core tag t (i) c ← U (T c ) and computes y (i) = Π ABM .Eval ek, t (i) , (x (i) , e (i) ) .

At each encryption query Msg

(i) 0 , Msg (i)
1 , the adversary obtains an encryption of Msg

(i) b . We denote by C (i) = (SVK (i) , t (i) c , c (i) 0 , y (i) 0 , y (i) , sig (i) ) the i-th challenge ciphertext, which is obtained as c (i) 0 = Msg (i) b + k sym,(i) mod q y (i) 0 = Π LTF .Eval ek , (x (i) , e (i) 0 ) y (i) = Π ABM .Eval ek, t (i) , (x (i) , e (i) ) .
All decryption queries are answered using the inversion trapdoor ik of Π LTF . When A halts, it outputs a bit b ∈ {0, 1} and we call S 0 the event that b = b.

Game 1: In this game, B rejects all decryption queries C = (SVK, t c , c 0 , y 0 , y, sig) such that SVK = SVK (i) for some i ∈ [Q E ]. It is easy to see that, if Σ is a strongly unforgeable one-time signature, B does not reject any ciphertext that it would not also reject in Game 0. We have

| Pr[S 1 ] -Pr[S 0 ]| ≤ Adv suf-ots (λ).
Game 2: We modify the encryption oracle. At each encryption query (Msg

(i) 0 , Msg (i) 1 ), the challenger encrypts C (i) = (SVK (i) , t (i) c , c (i) 0 , y (i) 0 , y (i) , sig (i) ) on a lossy tag t (i) = (t (i) c , SVK (i) ).
In the instantiation based on our ABM-LTF, this implies that the core tag component t

[S 2 ] -Pr[S 1 ]| ≤ 2n • Adv D 1 ,lwe ,m,q,χ (λ) + Adv D 2 ,prf Q E (λ) + 1 2 λ-1
, for some efficient distinguishers D 1 and D 2 .

Game 3: In this game, we modify the decryption oracle. Namely, at each decryption query C = (SVK, t c , c 0 , y 0 , y, sig), B still rejects C if SVK ∈ {SVK (1) , . . . , SVK (Q E ) }. However, it also rejects C in the event that SVK ∈ {SVK (1) , . . . , SVK (Q E ) } but the corresponding tag t = t c , SVK is a lossy tag. Clearly, Game 4 is identical to Game 3 until the event F 3 that B rejects a ciphertext that would not have been rejected in Game 3. In this case, A manages to break the evasiveness property of our ABM-LTF.

We claim that Pr

[F 3 ] ≤ Adv A,eva Q E ,Q D (λ).
To see this, we describe an evasiveness adversary B with advantage Pr[F 3 ]. Concretely, B interacts with an evasiveness challenger that provides it with an evaluation key ek and oracles ABM.LTag(tk, .) and ABM.IsLossy(tk, .). The adversary is run on input of the public encryption key P K = ek , ek, h where the evaluation key ek of Π LTF is obtained by generating (ek , ik ) ← Π LTF .IGen(1 λ ). At the i-th encryption query (Msg

(i) 0 , Msg (i)
1 ) made by A during the game, D defines t (i) a = SVK (i) , which it queries to its ABM.LTag(tk, .) oracle and obtains t

(i) c ∈ {0, 1} λ . Next, B fetches (x (i) , e (i)
0 , e (i) ) and computes y (i) 0 = Π LTF .Eval(ek , (x (i) , e (i) 0 )) as well as y (i) = Π ABM .Eval(ek, t (i) , (x (i) , e (i) )), where t (i) = (t

(i) c , SVK (i) ). Then, it returns the ciphertext C (i) = (SVK (i) , t (i) c , c (i) 0 , y (i) 0 , y (i) , sig (i) ) to A.
At each decryption query C = (SVK, t c , c 0 , y 0 , y, sig), our evasiveness adversary B queries its ABM.IsLossy(tk, .) oracle on the input (t c , y 0 ). If the response is 1, then B halts and outputs (t c , SVK). Otherwise, B continues and uses the LTF inversion key ik -which it knows from the key generation phase -to faithfully run the real decryption algorithm. If B did not halt by the time A terminates, it aborts. It is easy to see that B succeeds in breaking the evasiveness with probability Pr[F 3 ]. This yields the announced lower bound Adv A,eva

Q E ,Q D (λ) ≥ Pr[F 3 ]. Using our concrete LWE-based ABM-LTF, the result of Lemma 13 implies the inequality | Pr[S 3 ] -Pr[S 2 ]| ≤ Pr[F 3 ] ≤ n • Adv D 1 ,lwe ,m,q,χ (λ) + Adv D 2 ,prf Q E +Q D (λ) + Q D + 1 2 λ .
In subsequent games, we do not rely on the pseudo-randomness of the PRF any more and we can henceforth explicitly use its seed K to detect lossy tags when they show up.

Game 4: In this game, we modify again the decryption oracle. In this game, we do no longer use the inversion trapdoor ik of Π LTF but rather use the trapdoor ik of the ABM-LTF function Π ABM . At each decryption query C = (SVK, t c , c 0 , y 0 , y, sig), B still rejects C -as in Game 3 -in the event that SVK ∈ {SVK (1) , . . . , SVK (Q E ) } and t = (t c , SVK) is a lossy tag. Otherwise the tag t = (t c , SVK) must be injective. This allows B to compute the preimage (x, e) = Π ABM .Invert(ik, t, y). Having obtained (x, e), B returns ⊥ if (x, e) ∈ Dom D λ or Tightly secure signatures based on the SIS assumption (and hence the LWE assumption) were previously described [START_REF] Blazy | Tightly-secure signatures from chameleon hash functions[END_REF] in the single-user setting. In the multi-user setting, we give a simple construction, which is inspired from a SIS-based signature due to Böhl et al. [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF]. In particular, it combines a weakly secure one-time signature (i.e., which is only secure against non-adaptive attacks, where the adversary chooses the messages to be signed before seeing the public key) with a chameleon hash function suggested in [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF].

We assume public parameters Γ which contain random matrices A 0 ← U (Z m/2×n q

), B 0 , B 1 ← U (Z m×n q ) and D ← U (Z k×n q ), where m > 4n log q and k = n log q . G(Γ, 1 λ ): Run (A, R) ← GenTrap(A 0 , I n , γ) and choose u ← U (Z n q ). Output (SVK, SSK), where SVK = (A, u) ∈ Z m×n q × Z n q and SSK = R ∈ Z m/2×m/2 . S(SSK, m): To sign m ∈ {0, 1} m , using SSK = R, do the following:

1. Compute a chameleon hash c M = m • B 0 + r B 1 mod q, using a short Gaussian vector r ← D Z m ,γ .

Define u

M = u + g -1 (c M ) • D mod q, where g -1 (c M ) ∈ {0, 1} k is the binary de- composition of c M ∈ Z n q . 3. Using SSK = R, sample v ← D Λ u M q (A),γ to obtain a v ∈ Z m such that v 2 ≤ γ √ m and v • A = u + g -1 m • B 0 + r • B 1 • D mod q (13)
and output sig = (r, v) ∈ Z m × Z m .

V(SVK, m, sig = (r, v)): Given a candidate signature sig = (r, v) and m ∈ {0, 1} m , return 1 if and only if r 2 ≤ γ √ m, v 2 ≤ γ √ m and equality (13) is satisfied.

One disadvantage of the above construction is its long public key, which contains A ∈ Z m×n q . In our CCA2-secure encryption scheme, it requires to introduce a full n × m matrix in the ciphertext. Ideally, one would clearly prefer verification keys SVK that live in Z n q . In standard lattices, however, we are not aware of any one-time signature with O(n)-size verification key, let alone with tight security. We leave it as an interesting open problem. Theorem 6. The above one-time signature is tightly secure under the SIS assumption.

Proof. Assuming a forger A against the signature scheme in the game of Definition 6, we build a SIS solver B which takes as input a matrix Ā ∈ Z m×n q and finds an integer vector e ∈ Z m of Λ ⊥ q ( Ā) of norm e 2 ≤ β. The reduction distinguishes two kinds of attacks.

Type I attacks: The adversary outputs (i , m , sig = (r , v )) such that

m • B 0 + r • B 1 = m (i ) • B 0 + r (i ) • B 1 mod q,
where m (i ) , sig (i ) = (r (i ) , v (i ) denotes the message-signature pair obtained by A for SVK (i ) = (A (i ) , u (i ) ). cryption schemes [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF] which can be instantiated so as to admit an efficient opening algorithm. This provides evidence that, in the DDH setting, lossy trapdoor functions can also provide simulation-based selective opening security.

We illustrate this with the LTF of Freeman et al. [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF], modulo a slight modification in its specification. Definition 13. Let k, ∈ N with > k. We call D ,k a matrix distribution if it outputs matrices in Z ×k q of full rank k in polynomial time.

We assume w.l.o.g. that the first k rows of A ← U (D ,k ) form an invertible matrix over Z q .

In discrete-logarithm-hard groups, we rely on the matrix Diffie-Hellman assumption [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF], which posits the infeasibility of distinguishing full-rank matrices from lower-rank matrices when they are given in the exponent. Definition 14 (D ,k -Matrix Diffie-Hellman Assumption D ,k -MDDH). Let D ,k be a matrix distribution. Let G = g be a cyclic group of prime order q. We say that the D ,k -Matrix Diffie-Hellman (D ,k -MDDH) assumption holds in G if, for any ppt distinguisher A, we have

Adv mddh D ,k (A) := | Pr[A(G, g A , g A•w ) = 1 | A ← U (D ,k ), w ← U (Z k q )] -Pr[A(G, g A , g u ) = 1 | A ← U (D ,k ), u ← U (Z q )]| ∈ negl(λ).
It is easy to see (see, e.g., [START_REF] Gay | Tightly CCA-secure encryption without pairings[END_REF]) that the above assumption implies the Q-fold D ,k -Matrix Diffie-Hellman Assumption. Definition 15. Let D ,k be a matrix distribution and let G = g be a cyclic group of prime order q. The Q-fold D ,k -Matrix Diffie-Hellman assumption holds in G says that, for any ppt distinguisher A, we have As in [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF], we use a distribution D n,k = U n,k , which outputs uniformly random matrices A ← U (Z n×k q ), where n denotes the input length. We rely on an n-fold U n,k -MDDH assumption saying that the distributions

D 0 := {g, g A , g A•W | A ← U (Z n×k q ), W ← U (Z k×n q )} D 1 := {g, g A , g U | A ← U (Z n×k q
), U ← U (Z n×n q )} are computationally indistinguishable. Naor and Segev [START_REF] Naor | Public-key cryptosystems resilient to key leakage[END_REF] showed that this assumption is implied by the k-linear assumption [START_REF] Boneh | Short group signatures[END_REF] in G, which is the infeasibility of distinguishing the distributions D 0 := {(g, g 1 , . . . , g k , g a 1 1 , . . . , g a k k , g k i=1 a i ) | g 1 , . . . , g k ← U (G), a 1 , . . . , a k ← U (Z q )}, D 1 := {(g, g 1 , . . . , g k , g a 1 1 , . . . , g a k k , g b ) | g 1 , . . . , g k ← U (G), a 1 , . . . , a k , b ← U (Z q )} and which boils down to the DDH assumption for k = 1.

Par-Gen(1 λ ): Choose a cyclic group G of prime order q > 2 λ with g ← U (G). The public parameters Γ = {G, g, 0 , q, UH, σ} specify the message space MsgSp := Z 0 q , a universal hash function family UH and an integer γ > 0.

Keygen(Γ ): Let Π LTF = (IGen, LGen, Eval, Invert) be an instance of the LTF family recalled in Section E.1. Let Dom D λ = {x ∈ Z n | x ≤ σ √ n} be the inversion domain of the function. The public key is generated via the following steps.

1. Generate a pair (ek, ik) ← Π LTF .IGen(1 λ ) for an injective function of the LTF family Π LTF . 2. Choose the key of a function h : Dom λ → Z 0 q from the universal hash family, which consists of a random matrix H U H ← U (Z 0 ×n q ). Output (P K, SK), where P K := ek = g A , H U H and the underlying private key is SK := ik = A -1 ∈ Z n×n q .

Encrypt(P K, Msg): To encrypt Msg ∈ Z 0 q , do the following. We now present the lossy key generation algorithm and the efficient opening procedure. We require that n > 2(k + 0 ) • log q so that the matrix W ∈ Z k×n q of the lossy mode can be generated with a Micciancio-Peikert trapdoor.

Keygen(Γ, loss): Choose a random matrix Ā ← U (Z n×k q ). In order to generate W ∈ Z k×n q , conduct the following steps.

1. Choose C 0 ← U Z n× ¯ q , where ¯ = k + 0 and n = n -¯ • log q which is used to run the (C, R sim ) ← GenTrap(C 0 , I¯ , σ) algorithm of Lemma 8 to produce a statistically uniform matrix of the form

C = C 0 -R sim • C 0 + G sim ∈ Z n× ¯ q ,
where G sim ∈ Z ¯ • log q × ¯ q is the gadget matrix of [START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF] and a small-norm matrix R sim ∈ Z ¯ • log q ×n . Then, parse C ∈ Z ¯ ×n q as

C = W H U H ∈ Z ¯ ×n q ,
where W ∈ Z k×n q and H U H ∈ Z 0 ×n q . 52 2. Define A = Ā • W ∈ Z n×n q and compute ek := g A ∈ G n×n .

Return P K loss = (ek, H U H ) and SK loss = R sim , C 0 , Ā .

Opener(Γ, P K loss , SK loss , Msg 0 , x, Msg 1 ): Given x ∈ Dom E λ , parse the lossy secret key SK loss as R sim , C 0 , Ā and do the following. 2. Using the trapdoor R sim ∈ Z ¯ • log q ×n , sample a small-norm vector x ← D Λ tx q (C),σ so as to have a short x ∈ Z n such that W H U H

• x = t x mod q.

If x ∈ Dom D λ , output x . Otherwise, repeat Step 2 until a suitable x is found. It is easy to see that, as long as Opener finds a suitable x at Step 2, this vector satisfies Encrypt(P K loss , Msg 1 , x ) = Encrypt(P K loss , Msg 0 , x). Moreover, the obtained vector x has the required distribution since, by [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF][Lemma 5.2], {C • x | x ← D Z n ,σ } is statistically close to the uniform distribution over Z ¯ q and the two distributions

{(x , C • x ) | x ← D Z n ,σ } , {(x , C • x ) | t x ← U (Z ¯ q ), x ← D Λ tx
q (C),σ } are statistically indistinguishable.

The above scheme thus provides an alternative construction with SIM-SO-CPA security under Matrix Diffie-Hellman assumptions. Solutions based on similar DDH-like assumptions were previously reported in [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF][START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF][START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF]. The schemes of [START_REF] Hofheinz | Public-key encryption with simulation-based selective-opening security and compact ciphertexts[END_REF] feature short ciphertexts, but incur O(|Msg| 2 ) exponentiations to encrypt messages of bitlength |Msg|. In comparison, our ciphertexts require n > 2(k + 0 )• log q (which amounts to 2|Msg| for k = 1) group elements and each encryption costs O(log σ • |Msg| 2 ) group operations.

While less efficient than the bit-wise DDH-based scheme of [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF]Section 5.4] in terms of key sizes and computational overhead, we believe the above construction to be of interest. First, it shows that lattice trapdoors can come in handy to obtain simulation-based SOA security from traditional number-theoretic tools (i.e., which do not rely on lattice assumptions). Moreover, combining the above system with suitable pairing-based ABM-LTFs could open the way to new realizations providing SIM-SO-CCA security under discrete-logarithm-related assumptions.

F Tighter Security Proof for the BLMR PRF

This section shows that the key-homomorphic PRF of Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] enjoys a tighter security proof than previously known, under the same assumption as in [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF]. By "tighter," we mean that the upper bound [START_REF] Blazy | Tightly-secure signatures from chameleon hash functions[END_REF] on the adversary's advantage does not depend on the number of adversarial queries, except in a statistically negligible term. Definition 16 ([25]). Let λ be a security parameter and let integers k = k(λ), m = m(λ), q = q(λ). Let χ = χ(λ) and η = η(λ) be distributions over Z q . The Non-Uniform Learning-With-Errors (NLWE k,m,q,χ,η ) assumption posits that Adv A,NLWE k,m,q,χ,η (λ) := Pr[A(1 λ , A, u) = 1 | A ← η m×k , u ← U (Z m q )] -Pr[A(1 λ , A, A • s + e) = 1 | A ← η m×k , s ← U (Z k q ), e ← χ m ] is a negligible function for any ppt algorithm A.

Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] gave an advantage-preserving reduction from LWE to NLWE for several distributions η, called "coset-samplable," which include the binary uniform distribution η bin(k) = U ({0, 1}). For this specific distribution, they showed that solving NLWE in dimension k = n log q is as hard as solving LWE in dimension n for the same modulus q (assuming that 2 log q /q -1 is negligible, i.e., that q is close to a power of 2).10

The BLMR PRF. For any x ∈ Z q , let x p := (p/q)•x ∈ Z p , the notation being extended to vectors in the obvious way. Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] showed that, under the NLWE assumption, one can construct a PRF F : Z m q × {0, 1} κ → Z m p keyed by a uniformly random vector k ← U (Z m q ), where m = n log q , which maps a κ-bit input x = x[1] . . . x[κ] ∈ {0, 1} κ to the output

F (k, x) = κ i=1 A x[i] • k p , (18)
for distinct moduli p, q such that p|q and A 0 , A 1 ∈ {0, 1} m×m are random Z q -invertible binary public matrices.

One advantage of this construction is that the matrices A 0 , A 1 may be public. When the input x is fixed, a pre-processing phase allows hard-coding the product κ i=1 A x[i] into an NC 1 circuit to be evaluated on an encrypted key k (note that the rounding step can be computed in constant depth).

Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] proved the security of the above PRF family under the NLWE assumption via a reduction that loses a factor Q between the advantage of the pseudorandomness adversary and the distinguishing advantage against the problem of Definition 16. Indeed, the proof of [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF]Claim 5.4] uses an NLWE instance with Q secrets, where Q is the number of PRF evaluation queries. Analogously to LWE, the only known reductions from NLWE to its multi-secret variants (where the secret S is a k × Q matrix) proceed via a hybrid argument over the columns of S ∈ Z k×Q q , implying a multiplicative gap Ω(Q) in terms of concrete security.

In order to give a tighter reduction here, we need a variant of the Leftover Hash Lemma due to Dodis et al. [START_REF] Dodis | Fuzzy extractors: How to generate strong keys from biometrics and other noisy data[END_REF], which is stated as in [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF]

S

  F,u,f Λ ⊥ (C )+x , √ Σ,c is efficiently samplable by rejection sampling, given an efficient sampler for D Λ ⊥ (C )+x , √ Σ,c . The latter sampler can be implemented with a ppt algorithm by Lemma 4 and the fact that max i b i < σ n (Σ) with overwhelming probability by the bound on σ n ( √ Σ). 3.2 An All-But-Many Lossy Trapdoor Function from LWE Parameters and domains are defined as in Section 3.1.

D 2

 2 outputs 1 with probability Pr[W 2 ]. If D 2 's challenger always returns evaluations of a perfectly random function, distinguisher D 2 outputs 1 with probability Pr[W 3 ] as A's view corresponds to Game 3. It comes that D 2 's advantage as a PRF distinguisher is at least | Pr[W 3 ] -Pr[W 2 ]|, as claimed.

1 .

 1 The challenger flips a random coin b ← U ({0, 1}). It generates public parameters Γ ← Par-Gen(1 λ ) with a key pair (SK, P K) ← Keygen(Γ ) and gives (Γ, P K) to A which adaptively makes the following kinds of queries: • Challenge Query: let M be a message sampler for MsgSp(λ). The challenger samples Msg = (Msg 1 , . . . , Msg N ) ← M and returns N target ciphertextsC = (C 1 , . . . , C N ) ← Encrypt(P K, Msg 1 , r 1 ), . . . , Encrypt(P K, Msg N , r N ) .which are computed using independent random coins r 1 , . . . , r N ← R. • Corrupt Query: A chooses an arbitrary subset I ⊂ {1, . . . , N }. The challenger then reveals {(Msg i , r i )} i∈I to A. As for indexes i ∈ [N ] \ I, the challenger does the following: -If b = 1, reveal {Msg j } j / ∈I to A. -In b = 0, re-sample (Msg 1 , . . . , Msg N ) ← ReSamp M (I, {(i, Msg i )} i∈I ) and return the subset {Msg j } j / ∈I of re-sampled messages. • Decryption Queries: A chooses a ciphertext C such that C = C i for each i ∈ [N ] and obtains Decrypt(SK, C) ∈ MsgSp(λ) ∪ {⊥}. After polynomially-many decryption queries and exactly one challenge query followed by one corruption query, A outputs a bit b ∈ {0, 1} and wins if b = b. Its advantage is defined as the distance Adv IND-SO-CCA2 A (λ) := | Pr[b = b] -1/2|, where the probability is taken over all coin tosses.

1 . 2 .

 12 For any public parameters Γ ← Par-Gen(1 λ ), if (P K, SK) ← Keygen(Γ, inj), for any Msg ∈ MsgSp, we have Decrypt(SK, Encrypt(P K, Msg)) = Msg with overwhelming probability. Lossy public keys are computationally indistinguishable from injective ones. Namely, for any public parameters Γ ← Par-Gen(1 λ ), we have{P K | (P K, SK) ← Keygen(Γ, inj)} ≈ c {P K | (P K, SK) ← Keygen(Γ,loss)} 3. If Γ ← Par-Gen(1 λ ) and (P K, SK) ← Keygen(Γ, loss), then for any distinct messages Msg 0 , Msg 1 ∈ MsgSp, the two distributions {C | C ← Encrypt(P K loss , Msg 0 )}, {C | C ← Encrypt(P K loss , Msg 1 )} are statistically close. 4. Let D R denote the distribution of random coins input to Encrypt. For any message Msg ∈ MsgSp and ciphertext C, let D P K,Msg,C denote the probability distribution on randomness space R with support S P K,Msg,C = {R ∈ R : Encrypt(P K, Msg, R) = C},

  a pseudo-random function t(i) c = PRF(K, t (i)a ) of the auxiliary tag component t (i) a = SVK (i) at the beginning of the game. The indistinguishability property of our ABM-LTF ensures that this change will not noticeably increase A's probability Pr[S 2 ] of success. We have | Pr

  Adv mddh D ,k (A) := | Pr[A(G, g A , g A•W ) = 1 | A ← U (D ,k ), W ← U (Z k×Q q )] -Pr[A(G, g A , g U ) = 1 | A ← U (D ,k ), U ← U (Z ×Q q )]| ∈ negl(λ).

1 .

 1 Choose x ← D Z n ,σ and compute Y = Π LTF .Eval(ek, x) = g A•x . 2. Compute c 0 = Msg + H U H • x ∈ Z 0 q . Output the ciphertext C = (Y, c 0 ).Decrypt(SK, C):To decrypt C = (Y, c 0 ) using SK = ik, do the following.1. Compute x = Π LTF .Invert(ik, Y) and return ⊥ if x ∈ Dom D λ . 2. Return Msg = c 0 -H U H • x ∈ Z 0 q .

1 .

 1 Compute c LTF,x = W • x ∈ Z k q and c x = (Msg 0 -Msg 1 ) + H U H • x. Define t x = c LTF,x | c x ∈ Z ¯ q .

  Let h t denote the Hamming distance between t c and PRF(K, t a ). Use the G-trapdoor R t of A t with tag h t to find the unique (x, e) ∈ Dom D λ such that y = A t • x + e. This is done by applying the LWE inversion algorithm of Lemma 9. All algorithms involved run in polynomial-time, if one uses Eval pub CCT and Eval priv CCT from Lemma 10. If the circuits C PRF,j (t a ) (having the PRF key as input, and the PRF input hardwired) have logarithmic depth d ≤ O(log λ), then it is preferable to use Eval pub BP and Eval priv

The function of[START_REF] Alwen | Learning with rounding, revisited: New reduction, properties and applications[END_REF] maps x to f LWR (x) = (p/q) • A • x , for some prime moduli p < q.

Note that the same holds for the construction of[START_REF] Boyen | Towards tightly secure lattice short signature and ID-based encryption[END_REF], in which the PRF from[START_REF] Banerjee | Pseudo-random functions and lattices[END_REF] should be replaced by another one which is in NC 1 as a function the key (e.g., the one from[START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF]).

One may use either Eval pub CCT or Eval pub BP , but the choice must be consistent with the Eval priv variant used in function inversion.

Note that y0 may be far from the image of A in an invalid ciphertext but the inversion algorithm can detect this using ik .

Key indistinguishability refers to the indistinguishability of two games. In the first one, the adversary has access to MAC and verification oracles for two independent keys while, in the second game, the two oracles use the same secret key.

Note that for inputs of length k, our modulus q will be required to be of magnitude 2 Ω(k) . We may choose a q that satisfies 2 log q /q -1 ≤ 2 -Ω(k) .

Acknowledgements

We thank Fabrice Benhamouda and Radu Titiu for useful discussions. Part of this research was funded by the French ANR ALAMBIC project (ANR-16-CE39-0006) and by BPI-France in the context of the national project RISQ (P141580). The third author was supported by ERC Starting Grant ERC-2013-StG-335086-LATTAC. The second and fourth authors were supported by Australian Research Council Discovery Grant DP150100285.

Indistinguishability-Based (IND-SO-CCA2) Security

We first prove that the scheme provides IND-SO-CCA2 security. While we can tightly relate the IND-SO-CCA security of the scheme to the pseudorandomness of the underlying PRF, the reduction from the unforgeability of the MAC loses a factor proportional to the number of challenges. Theorem 3. The scheme provides IND-SO-CCA2 security assuming that: (i) Π LTF is a LTF; (ii) Π ABM is an ABM-LTF; (iii) PRF is a pseudorandom function family; (iv) MAC provides sUF-OT-CMA security. In our instantiation, for any adversary A, there exists an LWE ,m,q,χ distinguisher D 1 , a PRF adversary D 2 and a MAC forger B with comparable running time and such that

where N is the number of challenge ciphertexts and Q D is the number of decryption queries made by the adversary. (The proof is given in Appendix D.1.)

In Appendix C, we describe a variant of the scheme which, while not secure under selective openings, can be proved tightly CCA2-secure in the multi-challenge setting (cf. Definition 5 in Appendix B.1) as long as the PRF is itself tightly secure. In order to enable instantiations with a polynomial-size modulus q, we give a tighter security proof for the PRF of [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] in Appendix F.

Achieving Simulation-Based (SIM-SO-CCA2) Security

We show that our scheme can be instantiated so as to achieve the stronger notion of SIM-SO-CCA2 security. To this end, we show that it is in fact a lossy encryption scheme with weak efficient opening. We first detail the lossy key generation algorithm (which can be used in the final game in the proof of IND-SO-CCA2 security) and the Opener algorithm.

In order for Opener to run efficiently, we instantiate our scheme with a universal hash family UH, where each function h :

is keyed by a public matrix H U H ∈ Z ( 0 + 1 )×n q , which is included in the public key P K loss and allows evaluating

before computing c 0 = Msg + k sym ∈ Z 0 q and c 1 = MAC.Sig(k sym , (y, c 0 )). We also require Par-Gen to output public parameters , 0 , n satisfying the constraint n > 2 • (2 + 0 + 1 ) • log q, where 0 is the message length, 1 is the key length of the MAC and is the dimension of the underlying LWE assumption.

-Verification queries: A chooses an arbitrary pair (M, s). The challenger returns the output of MAC.Ver(k, M, s) ∈ {0, 1} to A.

While A can make arbitrarily many verification queries, only one MAC query is allowed and we call (M † , s † ) the input-output pair of that query. 3. When A halts, it outputs a pair (M , s ) and wins if the following conditions are satisfied:

We define the adversary's advantage Adv B,MAC Q V (λ) after Q V verification queries as its probability of success taken over all random choices.

We will consider unique one-time MACs, where MAC.Sig does not use any random coins and each message M has only one valid s. For example, any PRF is a unique MAC. Definition 8. Let λ be a security parameter and let κ = κ(λ). A pseudorandom function PRF : {0, 1} λ × {0, 1} κ → {0, 1} λ is an efficiently computable function where the first input K ∈ {0, 1} λ is the key. Let Ω be the set of all functions that map κ-bit inputs to λ-bit strings. The advantage of a PRF distinguisher D making Q evaluation queries is defined as

where the probability is taken over the random choice of K ← U ({0, 1} λ ) and F ← U (Ω) and the coin tosses of D.

B.3 Definition of Indistinguishability-Based Selective Opening

Chosen-Ciphertext (IND-SO-CCA2) Security

It was shown [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF][START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF] that, for message distributions supporting efficient conditional resampling, lossy trapdoor functions imply SOA security in the sense of an indistinguishabilitybased definition.

Definition 9 ([57]

). Let N = N (λ) and let M be a joint distribution over MsgSp(λ) N . We say that M supports efficient conditional re-sampling if there is an efficient algorithm ReSamp M such that, for any I ⊆ [N ], and any set Msg I of pairs

For such distributions, as in [START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF], we first aim at IND-SOA security under chosenciphertext attacks: i.e., when the adversary is granted access to a decryption oracle.

Definition 10 ( [START_REF] Hemenway | Lossy encryption: Constructions from general assumptions and efficient selective opening chosen ciphertext security[END_REF][START_REF] Hofheinz | All-but-many lossy trapdoor functions[END_REF]). A public-key encryption scheme (Par-Gen, Keygen, Encrypt, Decrypt) provides indistinguishability-based selective-opening security under chosen-ciphertext attacks (or IND-SO-CCA2 security) if, for any polynomial N ∈ poly(λ) and any message distribution M ∈ MsgSp(λ) N supporting efficient conditional re-sampling, no ppt adversary A has non-negligible advantage in this game.

Otherwise, it computes k sym = h(x) and returns Msg = c 0 -k sym ∈ Z 0 q . It is easy to see that the adversary's view is the same as in Game 3 since B does not reject any ciphertext that would not have been rejected in Game 3. We thus have Pr[S 4 ] = Pr[S 3 ].

Game 5: In this game, we modify the key generation phase. Instead of choosing the evaluation/inversion keys (ek , ik ) ← Π LTF .IGen(1 λ ) as in an injective function, D generates (ek , ⊥) ← Π LTF .LGen(1 λ ) as the evaluation key of a lossy function. By the properties of the lossy trapdoor function of Section 3.1, we know that this change will not be noticeable to A under the LWE assumption. We have

Game 6: We modify the preparation stage of the challenger. Instead of deriving the symmetric encryption keys k sym,(i) = h(x (i) ) for each i ∈ [Q E ], B samples them as uniformly random one-time keys k sym,(i) ← U (Z 0 q ) for each i ∈ [Q E ]. We claim that this change leaves A's view statistically unchanged. Indeed, for lossy tags

the input x (i) retains at least n bits of min-entropy. More precisely, Lemma 16 implies

Lemma 1 implies that we can bound the statistical distance as ∆ (ek, ek , t (i) , y (i) 0 , y (i) , h(x (i) )), (ek, ek , t (i) , y

which is smaller than 2 -λ as long as n • log σ x is sufficiently large. By repeating the same argument for each challenge ciphertext, we obtain

In Game 6, we finally remark that c

q perfectly hide the underlying messages in all encryption queries since the one-time symmetric keys act as onetime pads. We conclude that b ∈ {0, 1} is independent of A's view, so that Pr[S 6 ] = 1/2.

C.3 Tightly Secure One-Time Signatures from the SIS Assumption

In this section, we describe a one-time signature with a tight security proof under the SIS assumption in the multi-user setting. Definition 12. Let m, n, q, β be functions of a parameter 1 λ . The Short Integer Solution problem SIS m,q,β is as follows: Given A ← U (Z m×n q ), find a non-zero x ∈ Z m such that x • A = 0 1×n and 0 < x ≤ β.

Type II attacks: The adversary outputs (i , m , sig = (r , v )) such that

Type I attacks yield a collision on the chameleon hash function, which has a tight security proof under SIS assumption [START_REF] Cash | Bonsai trees, or how to delegate a lattice basis[END_REF]. We thus focus on Type II forgeries.

In order to build public parameters and N verification keys

) at random and generates B 1 ∈ Z m×n q as a statistically uniform matrix for which it knows a trapdoor

When A makes a signing query (i, m i ), B uses the trapdoor T B 1 to sample a vector

we obtain Proof. The proof proceeds with a sequence of games. For each i, we denote by S i the event that the adversary A wins (by outputting b ∈ {0, 1} such that b = b) in Game i.

Game 0: This is the real game. It begins with the challenger B choosing a bit b ← U ({0, 1}) and generating P K = (ek , ek, h) while keeping SK = (ik, ik ) to itself. Before starting its interaction with A, B samples (x (1) , e

0 , e (1) ), . . . , (x (N ) , e

For each i ∈ [N ], it computes y

)) and derives symmetric keys

In response to its challenge query, the adversary

a ). In the instantiation based on our ABM-LTF, t

We modify the decryption oracle. At each decryption query C = (t c , c 0 , c 1 , y 0 , y), B rejects C if the corresponding tag t = t c , y 0 is a lossy tag but y 0 ∈ {y (1) 0 , . . . , y (N ) 0 }. Game 2 is identical to Game 1 until the event F 2 that B rejects a ciphertext that would have deemed valid in Game 1. This event would break the evasiveness property of our ABM-LTF. Indeed, the same argument as in the proof of Theorem 5 shows that any evasiveness adversary implies either an LWE ,m,q,χ distinguisher D 1 or a PRF adversary D 2 with nonnegligible advantage after N + Q D evaluation queries. Lemma 13 implies

From here on, we are done with relying on the pseudo-randomness of the PRF and we thus explicitly use the seed K in subsequent games.

Game 3: In this game, we do not use the inversion trapdoor ik of Π LTF any longer but rather use the trapdoor ik of Π ABM to answer decryption queries. For each decryption query C = (t c , c 0 , c 1 , y 0 , y), B aborts (as in Game 2) if y 0 ∈ {y y is not in the range of Π ABM .Eval(ek, t, .);

If none of the above rejection rules applies, B derives (

is the only core tag that makes t = (t (i) c , y (i) 0 ) lossy. This allows B to proceed by running Π ABM .Invert(ik, t, .) as in the previous case. c. If there is an index i ∈ [N ] such that y 0 = y (i) 0 and t c = t (i) c , B recalls the input x (i) that was chosen in the preparation phase and returns ⊥ if y -A t • x (i) > σ e √ 2m. Otherwise, it recalls the symmetric key (k sym,(i) , k mac,(i) ) = h(x (i) ) that were derived from x (i) . As in Steps 3-4 of the actual decryption algorithm, B returns the plaintext Msg = c 0 -k sym,(i) ∈ Z 0 q if MAC.Ver(k mac,(i) , (y, c 0 ), c 1 ) = 1 and ⊥ otherwise. By inspection, it is easy to see that A's view is exactly as in Game 2, so that Pr[S 3 ] = Pr[S 2 ].

Game 4: We modify the key generation phase and replace ek by the evaluation key of a lossy function. Instead of generating (ek , ik ) ← Π LTF .IGen(1 λ ) as an injective function, D chooses it as (ek , ⊥) ← Π LTF .LGen(1 λ ). Since the inversion key ik of Π LTF was not used in Game 4, this change will not be noticeable to A under the LWE assumption. We have

For all indexes i ∈ [N ], due to the lossiness of all challenge ciphertexts, Lemma 16 tell us that

By Lemma 1, this implies ∆ (ek, ek , t (i) , y

which is smaller than 2 -λ when n • log σ x is sufficiently large.

Game 5: We change the treatment of decryption queries C = (t c , c 0 , c 1 , y 0 , y) corresponding to cases a or b of Game 3. In both cases, B can compute (x, e) = Π ABM .Invert(ik, t, y) since the tag t = (t c , y 0 ) is injective. The modification is that B now rejects

We claim that, except with negligible probability, B does not reject any ciphertext that would not be rejected in Game 4.

To see this, we note that, for lossy tags t (i) ,

jointly leak a limited number bits about x (i) , which retains at least λ bits of min-entropy due to [START_REF] Bellare | Identity-based encryption secure against selective opening attack[END_REF]. Taking a union bound over all decryption queries and all indices i ∈ [N ], the probability to reject a ciphertext that would not be rejected in Game 4 is at most

Game 6: We modify the decryption oracle and let B reject all potentially harmful decryption queries, which could possibly reveal h(x (i) ) for unopened ciphertexts. Namely, the challenger B introduces two rejection rules:

A. It rejects queries (t

1 , for some i ∈ [N ]. B. It rejects all decryption queries of the form (t (i) c , c 0 , c 1 , y (i) 0 , y), for some i ∈ [N ], such that (y, c 0 ) = (y (i) , c (i) 0 ) and which either -involve the index i ∈ [N ] \ I of an unopened ciphertext C i after the corruption query; -occur between the challenge query and the corruption query (and thus before the adversary obtains the random coins of C i ).

Due to the uniqueness property of the MAC, we easily see that rule A does not change anything to the adversary's view. So, Game 6 only departs from Game 5 when rule B rejects a ciphertext that would not be rejected in Game 5. If we call F 6 the latter event, Lemma shows that Pr

In Game 6, we argue that Pr[S 6 ] = 1/2 + N/2 λ , so that the adversary's advantage is statistically negligible. For each decryption query of the form (t

) and for some i ∈ [N ]\I, the decryption oracle returns ⊥. As for decryption queries (t c , c

c , they are also rejected when the inversion algorithm Π ABM .Invert(tk, (t c , y (i) 0 ), y (i) ) outputs (x (i) , •) due to the change introduced in Game 5. For all unopened ciphertexts {C i } i∈[N ]\I , A never tricks the decryption oracle into revealing h(x (i) ). Conditionally on the adversary's view, {k sym,(i) } i∈[N ]\I are thus within distance 2 -λ from the uniform distribution U (Z 0 q ) and they statistically hide {Msg i } i∈[N ]\I . We conclude that b ∈ {0, 1} is statistically independent of A's view, as claimed. Lemma 18. In Game 6, event F 6 occurs with negligible probability if MAC is a strongly secure one-time MAC. We have Pr

, where Adv mac,Q D B (λ) denotes B's probability to break the strong unforgeability of the MAC after Q D verification queries.

Proof. By hypothesis, we know that, at some point of Game 6, rule B will cause B to reject

0 , y (i) that would not have been rejected in Game 5. We build a MAC forger B with advantage (Pr[F 6 ] -2 -λ )/N .

To this end, we need to consider two modifications of Game 6, which we call Game 6.1 and Game 6.2. We modify the preparation phase and replace the i -th MAC key k mac,(i ) by a uniformly random key k mac, ← U (Z 1 q ). Since k mac,(i ) is statistically close to the uniform distribution for any unopened ciphertext, [START_REF] Bellare | Encryption schemes secure under selective opening attack[END_REF]

Game

denotes the counterpart of event F 6.1 in Game 6.2.

In Game 6.2, we can turn B into a MAC forger such that Pr[F 6.2 ] ≥ Adv mac,Q D B (λ). This forger proceeds by initially choosing i ← U ([N ]) as a predication of the index for which event F 6 will occur for the first time. It implicitly defines the i -th MAC secret key k mac,(i ) to be the key k mac, of its MAC challenger. The remaining MAC keys {k mac,(i) } i =i are chosen by computing (k sym,(i) , k mac,(i) ) = h(x (i) ) as in Game 6. In the challenge phase, B generates (t

, where c (i) 0 = Msg i +k sym,(i) ∈ Z 0 q , as in Game 6. The generation of c

B queries the verification of ((y, c 0 ), c 1 ) to its MAC challenger. If the response is 1, B aborts if i = i . Otherwise (i.e., if i = i ), B outputs ((y, c 0 ), c 1 ) and wins the game of Definition 7.

Since the choice of i ∈ [Q E ] is independent of A's view, we immediately obtain the claimed lower bound on B's advantage as a MAC forger.

E SIM-SO-CPA Security from DDH-based Lossy Trapdoor Functions

In this section, we show that lossy trapdoor functions based on the Decision Diffie-Hellman assumption (or, more generally, the matrix Diffie-Hellman assumption [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF]) imply lossy en-

E.1 Lossy Trapdoor Functions from Matrix Diffie-Hellman Assumptions

We describe a natural variant of a DDH-like LTF suggested by Freeman et al. [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF]Section 6]. The main difference between the construction below and the one of [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF]Section 6] is the domain of the function family. While inputs consist of n-bit strings in [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF], we use small-norm integer vectors sampled from a discrete Gaussian distribution: namely, we define

for some standard deviation σ > 0 and some parameter.

For k = 1, Peikert and Waters [START_REF] Peikert | Lossy trapdoor functions and their applications[END_REF] previously suggested to use small-norm integer (rather than binary) vectors to improve the efficiency of their DDH-based LTF. We further constrain them to have discrete Gaussian entries in order to efficiently open lossy ciphertexts in the resulting lossy encryption scheme.

Injective Key generation. LTF.IGen(1 λ ) chooses a random A ← U (Z n×n q ), which is Z qinvertible w.h.p. (the process is repeated until an invertible matrix is found). It outputs the evaluation key ek := g A ∈ G n×n while the inversion key is ik

λ such that X = g x . If no such vector is found, output ⊥. Otherwise, output x.

It is easy to see that, in lossy mode, the output is completely determined by W • x, so that the function has image size smaller than k • log q. The proof of the following Lemma is completely similar to that of [START_REF] Freeman | More constructions of lossy and correlationsecure trapdoor functions[END_REF]Lemma 6.3] and omitted. Lemma 19. Under the n-fold U n,k -MDDH assumption, the above function is an entropic lossy trapdoor function for which

Since a vector x sampled from the distribution D Z n ,γ has at least n bits of min-entropy, we have

E.2 A Lossy Encryption Scheme with Efficient Opening from Matrix Diffie-Hellman Assumptions

For k = 1, the scheme coincides with the one of Bellare and Yilek [17, Section 5.2] instantiated with a specific universal hash functions, except that we modify the space of random coins.

Lemma 20. Let H = {h : X → Y } h∈H be a family of universal hash functions and f : X → Z be a function, for countable sets X, Y, Z. For any random variable T taking values in X:

More generally, let (T i ) i≤k be independent random variables taking values in X. In this case, we have:

In the following, for any x = x [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF] . . . x[κ] ∈ {0, 1} κ and any index j ≤ κ, we let x| j ∈ {0, 1} κ-j+1 denote the sub-string comprised of the bits x[j], . . . , x[κ] of x.

As in the parameter choice recommended in [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF], we may set κ = n ε / log n, p = 2 n ε -ω(log n) and choose χ = D αq with rejection of samples of magnitude ≥ B = αq √ λ, for some α = 2 -n ε with 0 < ε < 1.

Theorem 7. Assume that q is odd. If α ≤ 1/(4(m log q+λ) √ λq) and α•(2m) κ •p ≤ 2 -ω(log n) , the BLMR PRF is secure under the NLWE assumption. Specifically, the advantage of any PRF distinguisher making at most Q queries is smaller than

To prove the result we consider a sequence of games. For each j, we call W j the event that the adversary A outputs 1 in Game j for each j ∈ {0, . . . , κ + 1}. For convenience, we first describe Game κ + 1 which corresponds to the adversary interacting with the real PRF.

Game κ + 1: In this game, the adversary interacts with the real function as defined by [START_REF] Black | Encryption-scheme security in the presence of key-dependent messages[END_REF]. Game j (0 ≤ j ≤ κ): In this game, the adversary interacts with a "hybrid" function which, for each query x ∈ {0, 1} κ , consists of a rounded product of

where k x| j = R(x| j ) ∈ Z m q , for a truly uniform function R : {0, 1} κ-j+1 → Z m q . The function R : {0, 1} κ-j+1 → Z m q can be lazily defined by choosing random outputs in Z m q as A makes queries and bookkeeping the queries and answers.

Note that, in Game 0, the adversary interacts with a truly random function

since p|q and R : {0, 1} κ → Z m q is itself truly random. To prove the result, we show that, for each j ∈ {0, . . . , κ}, Game j is computationally indistinguishable from Game j + 1. To this end, we define a modification of Game j.

Game j.0 (1 ≤ j ≤ κ): In this game, we modify the way the adversary computes the hybrid function for each query x ∈ {0, 1} κ . Before starting its interaction with the adversary, the challenger picks a uniformly random matrix B ← U Z 2m×(2m log q+2λ) q

. At each query x ∈ {0, 1} κ , the challenger looks up a list L (which is initially empty) and checks if it contains an entry (x| j+1 , t x| j ) for some vector t x| j ∈ Z 2m q . If so, it parses t x| j as in [START_REF] Böhl | Confined guessing: New signatures from standard assumptions[END_REF] and uses it to compute F (j) (x) as in [START_REF] Böhl | On definitions of selective opening security[END_REF]. If no such entry is in L, the challenger samples

q , which it parses as

where k 0||x| j+1 , k 1||x| j+1 ∈ Z m q . Then, it stores (x| j+1 , t x| j ) in the list L and computes

We remark that, since B is uniformly distributed over Z 2m×(2m log q+2λ) q

, the distribution of the vector t x| j = B • r x| j+1 is statistically close to the distribution U (Z 2m q ) by the Leftover Hash Lemma. 11 By taking a union bound over the number Q of evaluation queries, we obtain the inequality | Pr

This game is identical to Game j.0 except that we replace the uniformly random matrix B by a matrix of the form

and E ← χ 2m×(2m log q+2λ) .

Under the NLWE assumption, Game j.1 is indistinguishable from Game j.0: there exists an NLWE distinguisher such that | Pr[W j.0 ] -Pr[W j.1 ]| ≤ (2m log q + 2λ) • Adv D,nlwe m,2m,q,χ,η (λ). We remark that in Game j.1, the vector t x| j of ( 20) is of the form

where

We change the distribution of the vectors t x| j of ( 22) which, for each query x ∈ {0, 1} κ , are now computed as

11 Note that the assumption that q is odd guarantees that we have a family of universal hash functions.

56

for some uniformly random vector k x| j+1 ← U (Z m q ) which is a random function of the last κ -j bits x[j + 1], . . . , x[κ] of x (i.e., if these bits are the same, the output is the same, independently of the first j bits)).

We observe that Game j.2 is statistically close to Game j.1 by Lemma 20. We know that each entry of E • r x| j+1 ∈ Z 2m is bounded by 2B(2m log q + 2λ) in magnitude. The partial information E • r x| j+1 ∈ Z 2m about r x| j+1 thus lives in a set of size (4B(m log q + λ)) 2m .

If r x| j+1 is sampled from U ({-1, 1} 2m log q+2λ ), conditionally on E • r x| j+1 , the distribution of S • r x| j+1 ∈ Z m q is within statistical distance

from the distribution U (Z m q ). This is because B = αq √ λ ≤ √ q/(4(m log q + λ)), by assumption on α. Taking a union bound over all queries, we obtain

Game j.3 (1 ≤ j ≤ κ): In this game, we change again the distribution of the vectors t x| j of ( 23) and remove the terms E 0 • r x| j+1 and E 1 • r x| j+1 from the right-hand-side member of [START_REF] Boneh | Short group signatures[END_REF]. The vectors t x| j of ( 23) are thus changed into

We show that, except with negligible probability, this modification has no impact on A's view since it does not affect the rounding operation in [START_REF] Böhl | On definitions of selective opening security[END_REF]. In other words, with overwhelming probability, the vector t x| j of (24) leads to the same value of F (j) (x) as the one of (23).

To see this, let us call bad j.3 the event that Game j.3 deviates from Game j.2. To bound Pr[bad j.3 ], we first note that, since χ is a B-bounded distribution, each entry of E 0 • r x| j+1 and E 1 • r x| j+1 is smaller than 4B(m log q + λ) in magnitude. If we define

for b ∈ {0, 1}, we have w b,x ≤ B max = 4m κ-1 √ mB(m log q + λ). Defining

we see that bad j.3 happens when y x + w x[j],x p = y x p , which implies that at least one of the coordinates of y x is within distance B max from the nearest multiple of q/p. For a given query x, we call this event bad x,j.3 . For a given query x, we know that k x| j+1 is uniformly distributed over Z m q . Since A 0 , A 1 ∈ {0, 1} m×m are Z q -invertible, so is any multi-product of these matrices and the vector y x of 57 [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] is thus uniformly distributed over Z m q . The probability that any given coordinate of y x lands within distance B max from a multiple of q/p is at most 8m κ-1 √ mB(m log q + λ) • (p/q). A union bound over the m coordinates yields the inequality Pr[bad x,j.3 ] ≤ 8m κ √ mB(m log q + λ) • p q .

Taking a union bound over the number Q < 2 κ of queries, we get

Now, we observe that Game j.3 is identical to Game j + 1 as the hybrid function that A interacts with can be written