Benoît Libert

Thomas Peters

⋆⋆

Joye Marc

Moti Yung

Non-Malleability from Malleability: Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure Encryption from Homomorphic Signatures

Keywords: NIZK proofs, simulation-soundness, chosen-ciphertext security, homomorphic cryptography

Verifiability is central to building protocols and systems with integrity. Initially, efficient methods employed the Fiat-Shamir heuristics. Since 2008, the Groth-Sahai techniques have been the most efficient in constructing non-interactive witness indistinguishable and zero-knowledge proofs for algebraic relations in the standard model. For the important task of proving membership in linear subspaces, Jutla and Roy (Asiacrypt 2013) gave significantly more efficient proofs in the quasi-adaptive setting (QA-NIZK). For membership of the row space of a t×n matrix, their QA-NIZK proofs save Ω(t) group elements compared to Groth-Sahai. Here, we give QA-NIZK proofs made of a constant number group elementsregardless of the number of equations or the number of variables -and additionally prove them unbounded simulation-sound. Unlike previous unbounded simulation-sound Groth-Sahai-based proofs, our construction does not involve quadratic pairing product equations and does not rely on a chosen-ciphertext-secure encryption scheme. Instead, we build on structure-preserving signatures with homomorphic properties. We apply our methods to design new and improved CCA2-secure encryption schemes. In particular, we build the first efficient threshold CCA-secure keyed-homomorphic encryption scheme (i.e., where homomorphic operations can only be carried out using a dedicated evaluation key) with publicly verifiable ciphertexts.

Introduction

Non-interactive zero-knowledge proofs [START_REF] Blum | Non-Interactive Zero-Knowledge and Its Applications[END_REF] play a fundamental role in the design of numerous cryptographic protocols. Unfortunately, until breakthrough results in the last decade [START_REF] Groth | Perfect non-interactive zero knowledge for NP[END_REF][START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF][START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], it was not known how to construct them efficiently without appealing to the random oracle methodology [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]. Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] described very efficient non-interactive witness indistinguishable (NIWI) and zero-knowledge (NIZK) proof systems for algebraic relations in groups equipped with a bilinear map. For these specific languages, the methodology of [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] does not require any proof of circuit satisfiability but rather leverages the properties of homomorphic commitments in bilinear groups. As a result, the length of each proof only depends on the number of equations and the number of variables.

While dramatically more efficient than general NIZK proofs, the GS techniques remain significantly more expensive than non-interactive proofs obtained from the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] in the random oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]: for example, proving that t variables satisfy a system of n linear equations demands Θ(t+n) group elements where Σ-protocols allow for Θ(t)-size proofs. In addition, GS proofs are known to be malleable which, although useful in certain applications [START_REF] Belenkiy | Randomizable Proofs and Delegatable Anonymous Credentials[END_REF][START_REF] Chase | Malleable Proof Systems and Applications[END_REF], is undesirable when NIZK proofs serve as building blocks for non-malleable protocols. To construct chosen-ciphertextsecure encryption schemes [START_REF] Rackoff | Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack[END_REF], for example, the Naor-Yung/Sahai [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF][START_REF] Sahai | Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security[END_REF] paradigm requires NIZK proofs satisfying a form of non-malleability called simulation-soundness [START_REF] Sahai | Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security[END_REF]: informally, this property captures the inability of the adversary to prove false statements by itself, even after having observed simulated proofs for possibly false statements of its choice.

Groth-Sahai proofs can be made simulation-sound using constructions suggested in [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF][START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF][START_REF] Hofheinz | Tightly Secure Signatures and Public-Key Encryption[END_REF].

However, even when starting from a linear equation, these techniques involve proofs for quadratic equations, which results in longer proofs. One-time simulation-soundness (i.e., where the adversary only sees one simulated proof) is more economical to achieve as shown in [START_REF] Katz | Round-Optimal Password-Based Authenticated Key Exchange[END_REF][START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF]. Jutla and Roy suggested a more efficient way to achieve a form of one-time simulation-soundness [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF].

Quasi-Adaptive NIZK Proofs. For languages consisting of linear subspaces of a vector space, Jutla and Roy [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] recently showed how to significantly improve upon the efficiency of the GS paradigm in the quasi-adaptive setting. In quasi-adaptive NIZK proofs (QA-NIZK) for a class of languages {L ρ } parametrized by ρ, the common reference string (CRS) is allowed to depend on the particular language L ρ of which membership must be proved. At the same time, a single simulator should be effective for the whole class of languages {L ρ }. As pointed out in [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF], QA-NIZK proofs are sufficient for many applications of Groth-Sahai proofs. In this setting, Jutla and Roy [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] gave very efficient QA-NIZK proofs of membership in linear subspaces. If A ∈ Z t×n p is a matrix or rank t < n, in order to prove membership of the language L = {v ∈ G n | ∃x ∈ Z t p s.t. v = g x•A }, the Jutla-Roy proofs only take O(nt) group elements -instead of Θ(n + t) in [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] -at the expense of settling for computational soundness. While highly efficient in the case t ≈ n, these proofs remain of linear size in n and may result in long proofs when t ≪ n, as is the case in, e.g., certain applications of the Naor-Yung paradigm [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF]. In the general case, we are still lacking a method for building proofs of size O(t) -at least without relying on non-falsifiable assumptions [START_REF] Naor | On cryptographic assumptions and challenges[END_REF] -which contrasts with the situation in the random oracle model.

The problem is even harder if we aim for simulation-soundness. While the Jutla-Roy solutions [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] nicely interact with their one-time simulation-sound proofs [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], they do not seem to readily extend into unbounded simulation-sound (USS) proofs (where the adversary can see an arbitrary number of simulated proofs before outputting a proof of its own) while retaining the same efficiency. For this reason, although they can be applied in specific cases like [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF], we cannot always use them in a modular way to build CCA2-secure encryption schemes in scenarios where security definitions involve many challenge ciphertexts.

Our Contributions. Recently, in [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF], it was pointed out that structure-preserving signatures (SPS) [START_REF] Abe | Signing on Elements in Bilinear Groups for Modular Protocol Design[END_REF][START_REF] Abe | Structure-Preserving Signatures and Commitments to Group Elements[END_REF] with (additive) homomorphic properties have unexpected applications in the design of non-malleable structure-preserving commitments. Here, we greatly extend their range of applications and demonstrate that they can surprisingly be used (albeit non-generically) in the design of strongly non-malleable primitives like simulation-sound proofs and chosen-ciphertext-secure cryptosystems.

Concretely, we describe unbounded simulation-sound QA-NIZK proofs of constant-size for linear subspaces. The length of a proof does not depend on the number of equations or the number of variables, but only on the underlying assumption. Like those of [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF], our proofs are computationally sound under standard assumptions 5 . Somewhat surprisingly, they are even asymptotically shorter than random-oracle-based proofs derived from Σ-protocols.

Moreover, our construction provides unbounded simulation-soundness. Under the Decision Linear assumption [START_REF] Boneh | Short group signatures[END_REF], we obtain QA-NIZK arguments consisting of 15 group elements and a one-time signature with its verification key. As it turns out, it is also the first unbounded simulation-sound proof system that does not involve quadratic pairing product equations or a CCA2-secure encryption scheme. Efficiency comparisons (given in Appendix E) show that we only need 20 group elements per proof where the best USS extension [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF] of Groth-Sahai costs 6t + 2n + 52 group elements. Under the k-linear assumption, the proof length becomes O(k 2 ) and thus avoids any dependency on the subspace dimension. Our proof system builds on the linearly homomorphic structure-preserving signatures of Libert, Peters, Joye and Yung [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF], which allow signing vectors of group elements without knowing their discrete logarithms.

For applications, like CCA2 security [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF][START_REF] Sahai | Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security[END_REF], where only one-time simulation-soundness is needed, we further optimize our proof system and obtain a relatively simulation-sound QA-NIZK proof system, as defined in [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], with constant-size proofs. Under the DLIN assumption (resp. the k-linear assumption), we achieve relative simulation-soundness with only 4 (resp. k + 2) group elements! As the first application of USS proofs, we construct a chosen-ciphertext-secure keyed-homomorphic encryption scheme with threshold decryption. Keyed-homomorphic encryption is a primitive, suggested by Emura et al. [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF], where homomorphic ciphertext manipulations are only possible to a party holding a devoted evaluation key SK h which, by itself, does not enable decryption. The scheme should provide IND-CCA2 security when the evaluation key is unavailable to the adversary and remain IND-CCA1 secure when SK h is exposed. Other approaches to reconcile homomorphism and non-malleability were taken in [47-49, 12, 18] but they inevitably satisfy weaker security notions than adaptive chosen-ciphertext security [START_REF] Rackoff | Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack[END_REF]. The results of [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF] showed that CCA2-security does not rule out homomorphicity when the capability to compute over encrypted data is restricted.

Emura et al. [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF] gave realizations of chosen-ciphertext-secure keyed-homomorphic schemes based on hash proof systems [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]. However, these do not readily enable threshold decryption -as would be desirable in voting protocols -since valid ciphertexts are not publicly recognizable, which makes it harder to prove CCA security in the threshold setting. Moreover, these solutions are not known to satisfy the strongest security definition of [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF]. The reason is that this definition seemingly requires a form of unbounded simulation-soundness. Our QA-NIZK proofs fulfill this requirement and provide an efficient CCA2-secure threshold keyed-homomorphic system where ciphertexts are 65% shorter than in instantiations of the same high-level idea using previous simulation-sound proofs.

Using our relatively simulation-sound QA-NIZK proofs, we then build adaptively secure noninteractive threshold cryptosystems with CCA2 security and improved efficiency. The constructions of Libert and Yung [START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF] were improved by Escala et al. [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF]. So far, the most efficient solution is obtained from the Jutla-Roy results [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF][START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] via relatively sound proofs [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF]. Using our relatively sound QA-NIZK proof system, we shorten ciphertexts by Θ(k) elements under the k-linear assumption.

Our Techniques. In our unbounded simulation-sound proofs, each QA-NIZK proof can be seen as a Groth-Sahai NIWI proof of knowledge of a one-time linearly homomorphic signature on the vector that allegedly belongs to the linear subspace. Here, the NIWI proof is generated for a Groth-Sahai CRS that depends on the verification key of a one-time signature (following an idea of Malkin et al. [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF]), the private key of which is used to sign the entire proof so as to prevent re-randomizations. The reason why it provides unbounded simulation-soundness is that, with non-negligible probability, the CRS is perfectly hiding on all simulated proofs and extractable in the adversarially-generated fake proof. Hence, if the adversary manages to prove membership of a vector outside the linear subspace, the reduction is able to extract a homomorphic signature that it would not have been able to compute itself, thereby breaking the DLIN assumption. At a high level, the system can be seen as a two-tier proof system made of a non-malleable proof of knowledge of a malleable proof of membership.

In our optimized relatively-sound proofs, we adapt ideas of Jutla and Roy [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF] and combine the one-time linearly homomorphic signature of [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF] with a smooth-projective hash function [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF].

Our threshold keyed-homomorphic cryptosystem combines a hash proof system and a publicly verifiable USS proof that the ciphertext is well-formed. The keyed-homomorphic property is achieved by using the simulation trapdoor of the proof system as an evaluation key SK h , allowing the evaluator to generate proofs without knowing the witnesses. As implicitly done in [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF] in the case of hash proof systems, the simulation trapdoor is thus used in the scheme and not only in the security proof.

Background and Definitions

Quasi-Adaptive NIZK Proofs

Quasi-Adaptive NIZK (QA-NIZK) proofs are NIZK proofs where the CRS is allowed to depend on the specific language for which proofs have to be generated. The CRS is divided into a fixed part Γ , (Γ, ψ, ρ) :

V(ψ, x, π, lbl) = 1 ∧ ¬(∃w : R ρ (x, w) = 1) ∧ (x, π, lbl) ∈ Q] ∈ negl(λ),
where the adversary is allowed unbounded access to an oracle S 2 (ψ, τ, ., .) that takes as input statement-label pairs (x, lbl) (where x may be outside L ρ ) and outputs simulated proofs π ← S 2 (ψ, τ sim , x, lbl) before updating the set Q = Q ∪ {(x, π, lbl)}, which is initially empty.

In the weaker notion of one-time simulation-soundness, only one query to the S 2 oracle is allowed.

In some applications, one may settle for a weaker notion, called relative soundness by Jutla and Roy [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], which allows for more efficient proofs, especially in the single-theorem case. Informally, relatively sound proof systems involve both a public verifier and a private verification algorithm, which has access to a trapdoor. For hard languages, the two verifiers should almost always agree on any adversarially-created proof. Moreover, the private verifier should not accept a non-trivial proof for a false statement, even if the adversary has already seen proofs for false statements.

A labeled single-theorem relatively sound QA-NIZK proof system is comprised of a quasi-adaptive labeled proof system (K 0 , K 1 , P, V) along with an efficient private verifier W and an efficient simulator (S 1 , S 2 ). Moreover, the following properties should hold for any PPT adversaries (A 1 , A 2 , A 3 , A 4 ).

Quasi Adaptive Relative Single-Theorem Zero-Knowledge:

Pr[Γ ← K 0 (λ); ρ ← D Γ ; ψ ← K 1 (Γ, ρ); (x, w, lbl, s) ← A V(ψ,.,.) 1 (Γ, ψ, ρ); π ← P(ψ, ρ, x, w, lbl) : A V(ψ,.,.) 2 (π, s) = 1] ≈ Pr[Γ ← K 0 (λ); ρ ← D Γ ; (ψ, τ ) ← S 1 (Γ, ρ); (x, w, lbl, s) ← A W(ψ,τ,.,.) 1 (Γ, ψ, ρ); π ← S 2 (ψ, ρ, τ, x, lbl) : A W(ψ,τ,.,.) 2 (π, s) = 1],
Here, A 1 is restricted to choosing (x, w) such that R ρ (x, w) = 1.

Quasi Adaptive Relative Single-Theorem Simulation-Soundness:

Pr[Γ ← K 0 (λ); ρ ← D Γ ; (ψ, τ ) ← S 1 (Γ, ρ); (x, lbl, s) ← A W(ψ,τ,.,.) 3 (Γ, ψ, ρ); π ← S 2 (ψ, ρ, τ, x, lbl) : (x ′ , lbl ′ , π ′ ) ← A W(ψ,τ,.,.) 4 (s, π) : (x, π, lbl) = (x ′ , π ′ , lbl ′ ) ∧ ∃w ′ s.t. R ρ (x ′ , w ′ ) = 1 ∧ W(ψ, τ, x ′ , lbl ′ , π ′ ) = 1] ∈ negl(λ)
Note that the definition of relative simulation-soundness does not require the adversary to provide a witness but the definition of single-theorem zero-knowledge does.

Definitions for Threshold Keyed-Homomorphic Encryption

A (t, N )-threshold keyed-homomorphic encryption scheme consists of the following algorithms.

Keygen(λ, t, N ): takes as input a security parameter λ and integers t, N ∈ poly(λ) (with

1 ≤ t ≤ N ),
where N is the number of decryption servers and t ≤ N is the decryption threshold. It outputs (P K, SK h , VK, SK d ), where P K is the public key, SK h is the homomorphic evaluation key,

SK d = (SK d,1 , . . . , SK d,N
) is a vector of private key shares and VK = (V K 1 , . . . , V K N ) is a vector of verification keys. For each i, the decryption server i is given the share (i, SK d,i ). The verification key V K i will be used to check the validity of decryption shares generated using SK d,i . Encrypt(P K, M ): takes a input a public key P K and a plaintext M . It outputs a ciphertext C. Ciphertext-Verify(P K, C): takes as input a public key P K and a ciphertext C. It outputs 1 if C is deemed valid w.r.t. P K and 0 otherwise. Share-Decrypt(P K, i, SK d,i , C): on input of a public key P K, a ciphertext C and a privatekey share (i, SK d,i ), this (possibly randomized) algorithm outputs a special symbol (i, ⊥) if Ciphertext-Verify(P K, C) = 0. Otherwise, it outputs a decryption share µ i = (i, μi ). Share-Verify(P K, V K i , C, µ i ): takes in P K, the verification key V K i , a ciphertext C and a purported decryption share µ i = (i, μi ). It outputs either 1 or 0. In the former case, µ i is said to be a valid decryption share. We adopt the convention that (i, ⊥) is an invalid decryption share. Combine(P K, VK, C, {µ i } i∈S ): takes in (P K, VK, C) and a t-subset S ⊂ {1, . . . , N } with decryption shares {µ i } i∈S . It outputs either a plaintext M or ⊥ if {µ i } i∈S contains invalid shares. Eval(P K, SK h , C (1) , C (2) ): takes as input P K, the evaluation key SK h and ciphertexts C (1) , C (2) .

If Ciphertext-Verify(P K, C (j) ) = 0 for some j ∈ {1, 2}, the algorithm returns ⊥. Otherwise, it conducts a binary homomorphic operation over C (1) and C (2) and outputs a ciphertext C.

The above syntax assumes a trusted dealer. It generalizes that of ordinary threshold cryptosystems. By setting SK h = ε and discarding the evaluation algorithm, we obtain a classical threshold system. Definition 1. A threshold keyed-homomorphic public-key cryptosystem is secure against chosenciphertext attacks (or KH-CCA secure) if no PPT adversary has noticeable advantage in this game:

1. The challenger runs Keygen(λ) to obtain a public key P K, vectors SK d = (SK d,1 , . . . , SK d,N ), VK = (V K 1 , . . . , V K N ) and a homomorphic evaluation key SK h . It gives P K and VK to the adversary A and keeps (SK h , SK d ) to itself. In addition, the challenge initializes a set D ← ∅, which is initially empty.

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

-Corruption query: at any time, A may decide to corrupt a decryption server. To this end, it specifies an index i ∈ {1, . . . , N } and obtains the private key share SK d,i . -Evaluation query: A can invoke the evaluation oracle Eval(SK h , .) on a pair (C (1) , C (2) ) of ciphertexts of its choice. If there exists j ∈ {1, 2} such that Ciphertext-Verify(P K, C (j) ) = 0, return ⊥. Otherwise, the oracle Eval(SK h , .) computes C ← Eval(SK h , C (1) , C (2) ) and returns C. In addition, if 3. The adversary A chooses two equal-length messages M 0 , M 1 and obtains C ⋆ = Encrypt(P K, M β ) for some random bit β R ← {0, 1}. In addition, the challenger sets D ← D ∪ {C ⋆ }. 4. A makes further queries as in step 2 with some restrictions. Namely, A cannot corrupt more than t -1 servers throughout the entire game. Moreover, if A chooses to obtain SK h (via the RevHK oracle) at some point, no more post-challenge decryption query is allowed beyond that point.

C (1) ∈ D or C (2) ∈ D,

5.

A outputs a bit β ′ and is deemed successful if β ′ = β. As usual, A's advantage is measured as the distance

Adv(A) = | Pr[β ′ = β] -1 2 |.
It is important to note that, even if A chooses to obtain SK h immediately after having seen the public key P K, it still has access to the decryption oracle before the challenge phase. In other words, the scheme should remain IND-CCA1 if A is given P K and SK h at the outset of the game. After the challenge phase, decryption queries are allowed until the moment when the adversary obtains SK h .

In [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF], Emura et al. suggested a weaker definition where the adversary is not allowed to query the evaluation oracle on derivatives of the challenge ciphertext. As a consequence, the set D is always the singleton {C ⋆ } after step 3. In this paper, we will stick to the stronger definition.

Hardness Assumptions

For simplicity, we use symmetric bilinear maps e : G × G → G T over groups of prime order p, but extensions to the asymmetric setting e : G × Ĝ → G T are possible.

Definition 2 ([10]

). The Decision Linear Problem (DLIN) in G, is to distinguish the distributions (g a , g b , g ac , g bd , g c+d ) and (g a , g b , g ac , g bd , g z ), with a, b, c, d

R ← Z p , z R ← Z p .
We sometimes use the Simultaneous Double Pairing (SDP) assumption, which is weaker than DLIN. As noted in [START_REF] Cathalo | Group Encryption: Non-Interactive Realization in the Standard Model[END_REF], any algorithm solving SDP immediately yields a DLIN distinguisher.

Definition 3. The Simultaneous Double Pairing problem (SDP) in (G, G T ) is, given group elements (g z , g r , h z , h u ) ∈ G 4 , to find a non-trivial triple (z, r, u) ∈ G 3 \{(1 G , 1 G , 1 G )} such that e(g z , z) • e(g r , r) = 1 G T and e(h z , z) • e(h u , u) = 1 G T .

Linearly Homomorphic Structure-Preserving Signatures

Linearly homomorphic SPS schemes are homomorphic signatures where messages and signatures live in the domain group G (see Appendix B for syntactic definitions) of a bilinear map. Libert et al. [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF] described the following one-time construction and proved its security under the SDP assumption. By "one-time", we mean that only one linear subspace can be safely signed using a given key pair.

Keygen(λ, n): given a security parameter λ and the dimension n ∈ N of vectors to be signed, choose bilinear group (G, G T ) of prime order p > 2 λ . Choose

g z , g r , h z , h u R ← G. Then, for i = 1 to n, pick χ i , γ i , δ i R ← Z p and compute g i = g z χ i g r γ i and h i = h z χ i h u δ i . The private key is sk = {(χ i , γ i , δ i )} n i=1 while the public key is pk = g z , g r , h z , h u , {(g i , h i )} n i=1 . Sign(sk, (M 1 , . . . , M n )): to sign a vector (M 1 , . . . , M n ) ∈ G n using sk = {(χ i , γ i , δ i )} n i=1 , compute and return (z, r, u) = n i=1 M -χ i i , n i=1 M -γ i i , n i=1 M -δ i i ∈ G 3 .
SignDerive(pk, {(ω i , σ (i) )} ℓ i=1 ): given a public key pk and ℓ tuples (ω i , σ (i) ), where ω i ∈ Z p for each i, parse σ (i) as σ (i) = z i , r i , u i ∈ G 3 for i = 1 to ℓ. Then, compute and return σ = (z, r, u), where z = ℓ i=1 z ω i i , r = ℓ i=1 r ω i i and u = ℓ i=1 u ω i i . Verify(pk, σ, (M 1 , . . . , M n )): given a signature σ = (z, r, u) ∈ G 3 and a vector (M 1 , . . . , M n ), return 1 if and only if (M 1 , . . . , M n ) = (1 G , . . . , 1 G ) and (z, r, u) satisfy

1 G T = e(g z , z) • e(g r , r) • n i=1 e(g i , M i ), 1 G T = e(h z , z) • e(h u , u) • n i=1 e(h i , M i ). ( 1
)
One particularity of this scheme is that, even if the private key is available, it is difficult to find two distinct signatures on the same vector if the SDP assumption holds: by dividing out the two signatures, one obtains the solution of an SDP instance (g z , g r , h z , h u ) contained in the public key.

Two constructions of full-fledged (as opposed to one-time) linearly homomorphic SPS were given in [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF]. One of these will serve as a basis for our proof system and is recalled in Appendix C. In these constructions, all algorithms additionally input a tag which identifies the dataset that vectors belongs to. Importantly, only vectors associated with the same tag can be homomorphically combined.

3 Unbounded Simulation-Sound Quasi-Adaptive NIZK Arguments

In the following, vectors are always considered as row vectors unless stated otherwise. If A ∈ Z t×n p is a matrix, we denote by g A ∈ G t×n the matrix obtained by exponentiating g using the entries of A.

We consider public parameters Γ = (G, G T , g) consisting of bilinear groups (G, G T ) with a generator g ∈ G. Like [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF], we will consider languages

L ρ = {g x•A ∈ G n | x ∈ Z t p } that are parametrized by ρ = g A ∈ G t×n , where A ∈ Z t×n q is a t × n matrix of rank t < n.
As in [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF], we assume that the distribution D Γ is efficiently samplable: there exists a PPT algorithm which outputs a pair (ρ, A) describing a relation R ρ and its associated language L ρ according to D Γ . One example of such a distribution is obtained by picking a uniform matrix A R ← Z t×n p which has full rank with overwhelming probability -and setting ρ = g A .

Our construction builds on the homomorphic signature recalled in Appendix C. Specifically, the language-dependent CRS ψ contains one-time linearly homomorphic signatures on the rows of the matrix ρ ∈ G t×n . For each vector v ∈ L ρ , the prover can use the witness x ∈ Z t p to derive and prove knowledge of a one-time homomorphic signature (z, r, u) on v. This signature (z, r, u) is already a QA-NIZK proof of membership but it does not provide simulation-soundness. To acquire this property, we follow [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF] and generate a NIWI proof of knowledge of (z, r, u) for a Groth-Sahai CRS that depends on the verification key of an ordinary one-time signature. The latter's private key is used to sign the NIWI proof so as to prevent unwanted proof manipulations. Using the private key of the homomorphic one-time signature as a trapdoor, the simulator is also able to create proofs for vectors v ∈ L ρ . Due to the use of perfectly NIWI proofs, these fake proofs do not leak any more information about the simulation key than the CRS does. At the same time, the CRS can be prepared in such a way that, with non-negligible probability, it becomes perfectly binding on an adversarially-generated proof, which allows extracting a non-trivial signature on a vector v ∈ L ρ .

Like [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF], our quasi-adaptive NIZK proof system (K 0 , K 1 , P, V) is a split CRS construction in that K 1 can be divided into two algorithms (K 10 , K 11 ). The first one K 10 outputs some state information s and a first CRS CRS 2 which is only used by the verifier and does not depend on the language L ρ . The second part K 11 of K 1 inputs the state information s and the output of Γ of K 0 and outputs CRS 1 which is only used by the prover. The construction goes as follows.

K 0 (λ): choose groups (G, G T ) of prime order p > 2 λ with g R ← G. Then, output Γ = (G, G T , g)

The dimensions (t, n) of the matrix A ∈ Z t×n p can be either fixed or part of the language, so that t, n can be given as input to the CRS generation algorithm K 1 .

K 1 (Γ, ρ): parse Γ as (G, G T , g) and ρ as a matrix ρ = G i,j 1≤i≤t, 1≤j≤n ∈ G t×n .

1. Generate a key pair (pk rand , sk rand ) for the randomizable signature of Appendix C in order to sign vectors of G n . Namely, choose g z , g r , h z , h u R ← G and do the following.

a. For i = 1 to n, pick χ i , γ i , δ i R ← Z p and compute g i = g z χ i g r γ i and h i = h z χ i h u δ i .
b. Generate L + 1 Groth-Sahai common reference strings, for some L ∈ poly(λ). To this end, choose

f 1 , f 2 R ← G and define f 1 = (f 1 , 1, g) ∈ G 3 , f 2 = (1, f 2 , g) ∈ G 3 . Then, pick f 3,i R ← G 3 for i = 0 to L. Let sk rand = {(χ i , γ i , δ i )} n
i=1 be the private key and the matching public key is

pk rand = g z , g r , h z , h u , {(g i , h i )} n i=1 , f = f 1 , f 2 , {f 3,i } L i=0 .
2. Use sk rand to generate one-time linearly homomorphic signatures {(z i , r i , u i )} t i=1 on the vectors ρ i = (G i1 , . . . , G in ) ∈ G n that form the rows of ρ. These are obtained as

(z i , r i , u i ) = n j=1 G -χ j i,j , n j=1 G -γ j i,j , n j=1 G -δ j i,j
∀i ∈ {1, . . . , t}.

3.

Choose a strongly unforgeable one-time signature Σ = (G, S, V) with verification keys consisting of L-bit strings. 4. The CRS ψ = (CRS 1 , CRS 2 ) consists of two parts which are defined as

CRS 1 = ρ, pk rand , {(z i , r i , u i )} t i=1 , Σ , CRS 2 = pk rand , Σ ,
while the simulation trapdoor τ sim is sk rand = {(χ i , γ i , δ i )} n i=1 . P(Γ, ψ, v, x, lbl): given a candidate v ∈ G n and a witness x = (x 1 , . . . , x t ) ∈ Z t p such that v = g x•A , generate a one-time signature key pair (SVK, SSK) ← G(λ) and do the following. 1. Using {(z j , r j , u j )} t j=1 , derive a one-time linearly homomorphic signature (z, r, u) on v.

Namely, compute z = t i=1 z x i i , r = t i=1 r x i i and u = t i=1 u x i i . 2. Using SVK = SVK[1] . . . SVK[L] ∈ {0, 1} L , define the vector f SVK = f 3,0 • L i=1 f SVK[i] 3,i and assemble a Groth-Sahai CRS f SVK = (f 1 , f 2 , f SVK ). Using f SVK , generate commitments C z , C r , C u
to the components of (z, r, u) ∈ G 3 along with NIWI proofs (π 1 , π 2 ) that v and (z, r, u) satisfy [START_REF] Abe | Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography[END_REF]. Let (C z , C r , C u , π 1 , π 2 ) ∈ G 15 be the resulting commitments and proofs.

Generate

σ = S(SSK, (v, C z , C r , C u , π 1 , π 2 , lbl)) and output π = (SVK, C z , C r , C u , π 1 , π 2 , σ) (2)
V(Γ, ψ, v, π, lbl): parse π as per (2) and return [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF] in Appendix C for the detailed verification equations). If either condition fails to hold, return 0.

1 if (i) V(SVK, (v, C z , C r , C u , π 1 , π 2 , lbl), σ) = 1; (ii) (C z , C r , C u , π 1 , π 2 ) forms a valid NIWI proof for the CRS f SVK = (f 1 , f 2 , f SVK ) (see
In order to simulate a proof for a given vector v ∈ G n , the simulator uses τ sim = sk rand to generate a fresh one-time homomorphic signature on v ∈ G n and proceeds as in steps 2-3 of algorithm P.

The proof π only consists of 15 group elements and a one-time pair (SVK, σ). Remarkably, its length does not depend on the number of equations n or the number of variables t. In comparison, Groth-Sahai proofs already require 3t + 2n group elements in their basic form and become even more expensive when it comes to achieve unbounded simulation-soundness. The Jutla-Roy techniques [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] reduce the proof length to 2(nt) elements -which only competes with our proofs when t ≈ nbut it is unclear how to extend them to get unbounded simulation-soundness without affecting their efficiency. Our CRS consists of O(t + n + L) group elements against O(t(nt)) in [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF]. More detailed comparisons are given in Appendix E between proof systems based on the DLIN assumption.

Interestingly, the above scheme even outperforms Fiat-Shamir-like proofs derived from Σ-protocols which would give Θ(t)-size proofs here. The construction readily extends to rely on the k-linear assumption for k > 2. In this case, the proof comprises (k + 1)(2k + 1) elements and its size thus only depends on k, as detailed in Appendix D.

Moreover, the verification algorithm only involves linear pairing product equations whereas all known unbounded simulation-sound extensions of Groth-Sahai proofs require either quadratic equations or a linearization step involving extra variables.

We finally remark that, if we give up the simulation-soundness property, the proof length drops to k + 1 group elements under the k-linear assumption.

Theorem 1. The scheme is an unbounded simulation-sound QA-NIZK proof system if the DLIN assumption holds in G and Σ is strongly unforgeable. (The proof is given in Appendix F).

We note that the above construction is not tightly secure as the gap between the simulationsoundness adversary's advantage and the probability to break the DLIN assumption depends on the number of simulated proofs obtained by the adversary. For applications like tightly secure public-key encryption [START_REF] Hofheinz | Tightly Secure Signatures and Public-Key Encryption[END_REF], it would be interesting to modify the proof system to obtain tight security.

Single-Theorem Relatively Sound Quasi-Adaptive NIZK Arguments

In applications where single-theorem relatively sound NIZK proofs suffice, we can further improve the efficiency. Under the k-linear assumption, the proof length reduces from O(k 2 ) elements to O(k) elements. Under the DLIN assumption, each proof fits within 4 elements and only costs 2n+6 pairings to verify. In comparison, the verifier needs 2(nt)(t + 2) pairing evaluations in [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF].

As in [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], we achieve relative soundness using smooth projective hash functions [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]. To this end, we need to encode the matrix ρ ∈ G t×n as a 2t × (2n + 1) matrix.

K 0 (λ): choose groups (G, G T ) of prime order p > 2 λ with g R ← G. Then, output Γ = (G, G T , g).
Again, the dimensions of A ∈ Z t×n p can be either fixed or part of L ρ , so that t, n can be given as input to the CRS generation algorithm K 1 .

K 1 (Γ, ρ): parse Γ as (G, G T , g) and ρ as ρ = G ij 1≤i≤t, 1≤j≤n ∈ G t×n and do the following.

Choose two n-vectors

d = (d 1 , . . . , d n ) R ← Z n p and e = (e 1 , . . . , e n ) R ← Z n p in order to define W = (W 1 , . . . , W t ) = g A•d ⊤ ∈ G t and Y = (Y 1 , . . . , Y t ) = g A•e ⊤ ∈ G t .
These will be used to define a projective hash function.

2. Generate a key pair (pk ots , sk ots ) for the one-time linearly homomorphic signature of Section 2.5 in order to sign vectors in

G 2n+1 . Let pk ots = (G, G T ), g z , g r , h z , h u , {(g i , h i )} 2n+1 i=1
be the public key and let sk ots = {(χ i , γ i , δ i )} 2n+1 i=1 be the corresponding private key. 3. Use sk ots to generate one-time linearly homomorphic signatures {(z i , r i , u i )} 2t i=1 on the independent vectors below, which are obtained from the rows of the matrix ρ = G i,j 1≤i≤t, 1≤j≤n .

H 2i-1 = (G i,1 , . . . , G i,n , Y i , 1 , . . . , 1 ) ∈ G 2n+1 i ∈ {1, . . . , t} H 2i = (1 , . . . , 1 , W i , G i,1 , . . . , G i,n ) ∈ G 2n+1
4. Choose a collision-resistant hash function H : {0, 1} * → Z p . 5. The CRS ψ consists of a first part CRS 1 that is only used by the prover and a second part CRS 2 which is only used by the verifier. These are defined as

CRS 1 = ρ, pk ots , W , Y , {(z i , r i , u i )} 2t i=1 , H , CRS 2 = pk ots , W , Y , H .
The simulation trapdoor τ sim is sk ots and the private verification trapdoor is τ v = {d, e}.

P(Γ, ψ, v, x, lbl): given a candidate v ∈ G n , a witness x = (x 1 , . . . , x t ) ∈ Z t p such that v = g x•A and a label lbl, compute α = H(ρ, v, lbl) ∈ Z p . Then, using {(z i , r i , u i )} 2t
i=1 , derive a one-time linearly homomorphic signature (z, r, u) on the vector ṽ

= v 1 , . . . , v n , π 0 , v α 1 , . . . , v α n ∈ G 2n+1 , where π 0 = t i=1 (W α i Y i ) x i .
Namely, compute and output the proof π = (z, r, u, π 0 ) ∈ G 4 , where

z = t i=1 (z 2i-1 • z α 2i ) x i , r = t i=1 (r 2i-1 • r α 2i ) x i , u = t i=1 (u 2i-1 • u α 2i ) x i π 0 = t i=1 (W α i Y i ) x i V(Γ, ψ, v, π, lbl): parse v as (v 1 , . . . , v n ) ∈ G n and π as (z, r, u, π 0 ) ∈ G 4 . Compute α = H(ρ, v, lbl)
and return 1 if and only if (z, r, u) is a valid signature on ṽ

= (v 1 , . . . , v n , π 0 , v α 1 , . . . , v α n ) ∈ G 2n+1 . Namely, it should satisfy the equalities 1 G T = e(g z , z) • e(g r , r) • n i=1 e(g i • g α i+n+1 , v i ) • e(g n+1 , π 0 ) and 1 G T = e(h z , z) • e(h u , u) • n i=1 e(h i • h α i+n+1 , v i ) • e(h n+1 , π 0 ). W(Γ, ψ, τ v , v, π, lbl): given v = (v 1 , . . . , v n ) ∈ G n , parse π as (z, r, u, π 0 ) ∈ G 4 and τ v as {d, e}, with d = (d 1 , . . . , d n ) ∈ Z n p and e = (e 1 , . . . , e n ) ∈ Z n p . Compute α = H(ρ, v, lbl) ∈ Z p and return 0 if the public verification test V fails. Otherwise, return 1 if π 0 = n j=1 v
e j +αd j j and 0 otherwise.

We note that, while the proving algorithm is deterministic, each statement has many valid proofs. However, finding two valid proofs for the same statement is computationally hard, as will be shown in the proof of Theorem 2.

The scheme readily extends to rest on the k-linear assumption with k > 2. In this case, the proof requires k + 2 group elements -whereas combining the techniques of [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF][START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] demands k(n + 1t) elements per proof -and a CRS of size O(k(n+t)). From a security standpoint, we prove the following result in Appendix G.

Theorem 2. The above proof system is a relatively sound QA-NIZK proof system if the SDP assumption holds in (G, G T ) and if H is a collision-resistant hash function.

As an application, we describe a new adaptively secure CCA2-secure non-interactive threshold cryptosystem based on the DLIN assumption in Appendix I. Under the k-linear assumption, the scheme provides ciphertexts that are Θ(k) group elements shorter than in previous such constructions. Under the DLIN assumption, ciphertexts consist of 8 elements of G, which spares one group element w.r.t. the best previous variants [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF][START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] of Cramer-Shoup with publicly verifiable ciphertexts.

5 An Efficient Threshold Keyed-Homomorphic KH-CCA-Secure Encryption Scheme from the DLIN Assumption

The use of linearly homomorphic signatures as publicly verifiable proofs of ciphertext validity in the Cramer-Shoup paradigm [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF][START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] was suggested in [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF]. However, the latter work only discusses nonadaptive (i.e., CCA1) attacks. In the CCA2 case, a natural idea is to proceed as in our unbounded simulation-sound proof system and use the verification key of a on-time signature as the tag of a homomorphic signature: since cross-tag homomorphic operations are disallowed, the one-time signature will prevent illegal ciphertext manipulations after the challenge phase.

To obtain the desired keyed-homomorphic property, we use the simulation trapdoor of a simulationsound proof system as the homomorphic evaluation key. This approach was already used by Emura et al. [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF] in the context of designated verifier proofs. Here, publicly verifiable proofs are obtained from a homomorphic signature scheme of which the private key serves as an evaluation key: anyone equipped with this key can multiply two ciphertexts (or, more precisely, their built-in homomorphic components), generate a new tag and sign the resulting ciphertext using the private key of the homomorphic signature. Moreover, we can leverage the fact that the latter private key is always available to the reduction in the security proof of the homomorphic signature [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF]. In the game of Definition 1, the simulator can thus hand over the evaluation key SK h to the adversary upon request.

Emura et al. [START_REF] Emura | Chosen Ciphertext Secure Keyed-Homomorphic Public-Key Encryption[END_REF] gave constructions of KH-CCA secure encryption schemes based on hash proof systems [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF]. However, these constructions are only known to provide a relaxed flavor of KH-CCA security where evaluation queries should not involve derivatives of the challenge ciphertext. The reason is that 2-universal hash proof systems [START_REF] Cramer | Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption[END_REF] only provide a form of one-time simulation soundness whereas the model of Definition 1 seemingly requires unbounded simulation-soundness. Indeed, when the evaluation oracle is queried on input of a derivative of the challenge ciphertext in the security proof, the homomorphic operation may result in a ciphertext containing a vector outside the language L ρ . Since the oracle has to simulate a proof for this vector, each homomorphic evaluation can carry a proof for a potentially false statement. In some sense, each output of the evaluation oracle can be seen as yet another challenge ciphertext. In this setting, our efficient unbounded simulation-sound QA-NIZK proof system comes in handy.

It remains to make sure that CCA1 security is always preserved, should the adversary obtain the evaluation key SK h at the outset of the game. To this end, we include a second derived one-time homomorphic signature (Z, R, U ) in the ciphertext without including its private key in SK h . Keygen(λ, t, N ): Choose bilinear groups (G, G T ) of prime order p > 2 λ . Then, do the following.

1. Pick f, g, h R ← G, x 0 , x 1 , x 2 R ← Z p and set X 1 = f x 1 g x 0 ∈ G, X 2 = h x 2 g x 0 ∈ G. Then, define f = (f, 1, g) ∈ G 3 and h = (1, h, g) ∈ G 3 . 2. Choose random polynomials P 1 [Z], P 2 [Z], P [Z] ∈ Z p [Z] of degree t -1 such that P 1 (0) = x 1 , P 2 (0) = x 2 and P (0) = x 0 . For each i ∈ {1, . . . , N }, compute V K i = (Y i,1 , Y i,2 ) where Y i,1 = f P 1 (i) g P (i) and Y i,2 = h P 2 (i) g P (i) . 3. Choose f r,1 , f r,2 R ← G in order to define vectors f r,1 = (f r,1 , 1, g), f r,2 = (1, f r,2 , g) and f r,3 = f φ 1 r,1 • f φ 2 r,2 • (1, 1, g) -1
, where φ 1 , φ 2 R ← Z p . These vectors will be used as a Groth-Sahai CRS for the generation of NIZK proofs showing the validity of decryption shares. 4. Choose a strongly unforgeable one-time signature Σ = (G, S, V) with verification keys consisting of L-bit strings, for some L ∈ poly(λ). 5. Generate a key pair for the one-time linearly homomorphic structure-preserving signature of Section 2.5 with n = 3. Let

pk ot = G z , G r , H z , H u , {(G i , H i )} 3
i=1 be the public key and let

sk ot = {(ϕ i , ϑ i , ̟ i )} 3
i=1 be the corresponding private key. 6. Generate one-time homomorphic signatures {(Z j , R j , U j )} j=1,2 on the vectors f = (f, 1, g) and h = (1, h, g). These signatures consist of (Z

1 , R 1 , U 1 ) = f -ϕ 1 g -ϕ 3 , f -ϑ 1 g -ϑ 3 , f -̟ 1 g -̟ 3 and (Z 2 , R 2 , U 2 ) = h -ϕ 2 g -ϕ 3 , h -ϑ 2 g -ϑ 3 , h -̟ 2 g -̟ 3
and erase sk ot .

7. Generate a key pair (pk rand , sk rand ) as in step 1 of the proof system in Section 3 with n = 3. Let sk rand = {(χ i , γ i , δ i )} 3 i=1 be the private key for which the corresponding public key is

pk rand = g z , g r , h z , h u , {(g i , h i )} 3 i=1 , f = f 1 , f 2 , {f 3,i } L i=0 .
8. Use sk rand to generate one-time linearly homomorphic signatures {(z j , r j , u j )} j=1,2 on the independent vectors f = (f, 1, g) ∈ G 3 and h = (1, h, g) ∈ G 3 . These are obtained as

(z 1 , r 1 , u 1 ) = f -χ 1 g -χ 3 , f -γ 1 g -γ 3 , f -δ 1 g -δ 3 , (z 2 , r 2 , u 2 ) = h -χ 2 g -χ 3 , h -γ 2 g -γ 3 , h -δ 2 g -δ 3 .
9. The public key is defined to be

P K = g, f , h, f r,1 , f r,2 , f r,3 , X 1 , X 2 , pk ot , pk rand , {(Z j , R j , U j )} 2 j=1 {(z j , r j , u j )} 2 j=1 .
The evaluation key is SK h = sk rand = {(χ i , γ i , δ i )} 3 i=1 while the i-th decryption key share is defined to be SK d,i = (P 1 (i), P 2 (i), P (i)). The vector of verification keys is defined as

VK = (V K 1 , . . . , V K N ), where V K i = (Y i,1 , Y i,2 ) for i = 1 to N .
Encrypt(M, P K): to encrypt M ∈ G, generate a one-time signature key pair (SVK, SSK) ← G(λ).

1. Choose θ 1 , θ 2 R ← Z p and compute C 0 = M • X θ 1 1 • X θ 2 2 , C 1 = f θ 1 , C 2 = h θ 2 , C 3 = g θ 1 +θ 2 .
2. Construct a first linearly homomorphic signature (Z, R, U ) on the vector

(C 1 , C 2 , C 3 ) ∈ G 3 . Namely, compute Z = Z θ 1 1 • Z θ 2 2 , R = R θ 1 1 • R θ 2 2 and U = U θ 1 1 • U θ 2 2 . 3. Using {(z j , r j , u j )} j=1,2 , derive another homomorphic signature (z, r, u) on (C 1 , C 2 , C 3 ). Namely, compute z = z θ 1 1 • z θ 2 2 , r = r θ 1 1 • r θ 2 2 and u = u θ 1 1 • u θ 2 2 . 4. Using SVK = SVK[1] . . . SVK[L] ∈ {0, 1} L , define the vector f SVK = f 3,0 • L i=1 f SVK[i] 3,i and assemble a Groth-Sahai CRS f SVK = (f 1 , f 2 , f SVK ). Using f SVK , generate commitments C z , C r , C u
to the components of (z, r, u) ∈ G 3 along with proofs (π 1 , π 2 ) as in step 2 of the proving algorithm of Section 3. Let (C z , C r , C u , π 1 , π 2 ) ∈ G 15 be the resulting NIWI proof. 5. Generate σ = S(SSK,

(C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 )) and output C = (SVK, C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 , σ) (3)
Ciphertext-Verify P K, C : parse C as in [START_REF] Abe | Signing on Elements in Bilinear Groups for Modular Protocol Design[END_REF]. Return 1 if and only if these conditions are satisfied:

(i) V(SVK, (C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 ), σ) = 1; (ii) (Z, R, U ) ∈ G 3 is a valid homo- morphic signature on (C 1 , C 2 , C 3 ); (iii) (C z , C r , C u , π 1 , π 2 ) ∈ G 15 is a valid proof w.r.t. the CRS (f 1 , f 2 , f SVK ) that committed (z, r, u) satisfy the relations (1) for the vector (C 1 , C 2 , C 3 ) ∈ G 3 .
Here, we define

f SVK = f 3,0 • L i=1 f SVK[i] 3,i . Share-Decrypt(P K, i, SK d,i , C): on inputs SK d,i = (P 1 (i), P 2 (i), P (i)) ∈ Z 3 p and C, return (i, ⊥) if Ciphertext-Verify P K, C = 0. Otherwise, compute μi = ν i , C P 1 , C P 2 , C P , π µ i which con- sists of a partial decryption ν i = C P 1 (i) 1 • C P 2 (i) 2 • C P (i) 3
as well as commitments C P 1 , C P 2 , C P to exponents P 1 (i), P 2 (i), P (i) ∈ Z p and a proof π ν i that these satisfy the equations

ν i = C P 1 (i) 1 • C P 2 (i) 2 • C P (i) 3 , Y i,1 = f P 1 (i) g P (i) , Y i,2 = h P 2 (i) g P (i) .
The commitments C P 1 , C P 2 , C P and the proof π ν i are generated using the CRS (f r,1 , f r,2 , f r,3 ) (see Appendix A for details). Then, return µ i = (i, μi ).

Share-Verify

P K, V K i , C, (i, μi ) : parse C as in (3) and V K i as (Y i,1 , Y i,2
= i∈S ν ∆ i,S (0) i , which equals ν = C x 1 1 • C x 2 2 • C x 0 3 = X θ 1 1 • X θ 2
2 and in turn reveals M = C 0 /ν. Eval(P K, SK h , C (1) , C (2) ): parse SK h as {(χ i , γ i , δ i )} 3 i=1 . For each j ∈ {1, 2}, parse C (j) as

C (j) = (SVK (j) , C (j) 0 , C (j) 1 , C (j) 2 , C (j) 3 , Z (j) , R (j) , U (j) , C (j) z , C (j) r , C (j) u , π (j) 1 , π (j) 2 , σ (j) )
and return ⊥ if either C (1) or C (2) is invalid. Otherwise,

1. Compute C 0 = 2 j=1 C (j) 0 , C 1 = 2 j=1 C (j) 1 , C 2 = 2 j=1 C (j) 2 and C 3 = 2 j=1 C (j)
3 as well as

Z = 2 j=1 Z (j) , R = 2 j=1 R (j) and U = 2 j=1 U (j) . 2. Generate a new one-time signature key pair (SVK, SSK) ← G(λ). Using SK h = {(χ i , γ i , δ i )} 3 i=1 , generate proof elements C z , C r , C u , π 1 , π 2 on the vector (C 1 , C 2 , C
3 ) using the simulator of the proof system in Section 3 with the one-time verification key SVK.

Return the derived ciphertext

C = (SVK, C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 , σ) where σ = S(SSK, (C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 )).
In Appendix H, we prove the KH-CCA security of the scheme assuming that Σ is a strongly unforgeable one-time signature and that the DLIN assumption holds in G.

In some applications, it may be desirable to add an extra randomization step to the evaluation algorithm in order to make sure that derived ciphertexts will be indistinguishable from freshly generated encryption (similarly to [START_REF] Prabhakaran | Homomorphic Encryption with CCA Security[END_REF]). It is straightforward to modify the scheme to obtain this property.

If the scheme is instantiated using Groth's one-time signature [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF], the ciphertext consists of 25 elements of G and two elements of Z p . It is interesting to compare the above system with an instantiation of the same design principle using the best known Groth-Sahai-based unbounded simulation-sound proof [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF][Appendix A.2], which requires 65 group elements in this specific case. With this proof system, we end up with 77 group elements per ciphertexts under the DLIN assumption (assuming that an element of Z p has the same length as the representation of a group element). The above realization thus saves 50 group elements and compresses ciphertexts to 35% of their original length.

We note that it is possible to adapt the scheme to rely on the Symmetric eXternal Diffie-Hellman assumption in asymmetric pairings e : G × Ĝ → G T . In this case, the ciphertext contains 9 elements of G, 2 elements of Ĝ and a one-time key pair (SVK, σ). Using the one-time signature of [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF], the ciphertext overhead amounts to 4096 bits on Barreto-Naehrig curves [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF] if each element of G (resp. each element of Ĝ) has a 256-bit (resp. 512-bit) representation.

A Groth-Sahai Proofs

In the notations of this section, when vectors A and B are vectors of group elements, A • B denotes their entry-wise product.

Under the DLIN assumption in symmetric bilinear groups (G, G T ), the Groth-Sahai (GS) proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] use a CRS consisting of three vectors g 1 , g 2 , g 3 ∈ G 3 , where g 1 = (g 1 , 1, g), g 2 = (1, g 2 , g) for some g 1 , g 2 ∈ R G. In this setting, a commitment to a group element X ∈ G is computed as

C = (1, 1, X) • g 1 r • g 2 s • g 3 t with r, s, t R ← Z * p .
In order to obtain perfectly sound proofs, g 3 is chosen as

g 3 = g 1 ξ 1 • g 2 ξ 2 , with ξ 1 , ξ 2 R ← Z * p , so that the commitment C = (g r+ξ 1 t 1 , g s+ξ 2 t 2 , X • g r+s+t(ξ 1 +ξ 2 )
) is extractable as it is distributed as a Boneh-Boyen-Shacham (BBS) ciphertext [START_REF] Boneh | Short group signatures[END_REF] that can be decrypted using the discrete logarithms α 1 = log g (g 1 ), α 2 = log g (g 2 ). In order to switch to the witness indistinguishability setting, the vectors g 1 , g 2 , g 3 must be linearly independent so as to span the entire space where C lives and make sure that C is a perfectly hiding commitment. Under the DLIN assumption, the two kinds of reference strings are computationally indistinguishable.

When it comes to commit to an exponent x ∈ Z p , the prover computes

C = ϕ x • g r 1 • g s 2 , with r, s R ← Z * p , using a CRS comprising vectors ϕ, g 1 , g 2 .
In the soundness setting ϕ, g 1 , g 2 are linearly independent vectors while, in the perfect WI setting, choosing ϕ in span(g 1 , g 2 ) yields a perfectly hiding commitment as C is always a BBS encryption of 1 G .

To prove that committed group elements or exponents satisfy certain relations, the Groth-Sahai methodology [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] requires one commitment per variable and one proof element per relation. Efficient NIWI proofs are available for multi-exponentiation equations of the form

m i=1 A y i i • n j=1 X b j j • m i=1 • n j=1 X y i γ ij j = T,
for variables X 1 , . . . , X n ∈ G, y 1 , . . . , y m ∈ Z p and constants T, A 1 , . . . , A m ∈ G, b 1 , . . . , b n ∈ Z p and γ ij ∈ Z p , for i ∈ {1, . . . , m}, j ∈ {1, . . . , n}.

For linear equations (i.e., where γ ij = 0 for all i, j) depends on the form of the considered equation.

Namely, linear multi-exponentiation equations of the type n j=1 X b j j

= T (resp. m i=1 A y i i = T ) demand 3 (resp. 2) group elements.

Multi-exponentiation equations admit NIZK proofs. On a simulated CRS, the representation

(ξ 1 , ξ 2 ) ∈ Z 2 p of ϕ as ϕ = g ξ 1 1 • g ξ 2 2
can serve as a trapdoor that makes it possible to perfectly simulate proofs without knowing the witnesses.

Efficient NIWI proofs also exist for pairing-product relations, which are the form

n i=1 e(A i , X i ) • n i=1 • n j=1 e(X i , X j ) a ij = t T , for variables X 1 , . . . , X n ∈ G and constants t T ∈ G T , A 1 , . . . , A n ∈ G, a ij ∈ Z p , for i, j ∈ {1, . . . , n}.
For each linear pairing product equation (where a ij = 0 for all i, j), a proof fits within 3 group elements. Quadratic equations are somewhat more space-consuming and take 9 group elements each.

At the cost of introducing extra variables, pairing product equations can also have NIZK proofs.

B Definitions for Linearly Homomorphic Structure-Preserving Signatures

Let (G, G T ) be groups of prime order p such that a bilinear map e : G × G → G T can be efficiently computed.

A signature scheme is structure-preserving [START_REF] Abe | Signing on Elements in Bilinear Groups for Modular Protocol Design[END_REF][START_REF] Abe | Structure-Preserving Signatures and Commitments to Group Elements[END_REF] if messages, signatures and public keys all live in the group G. In linearly homomorphic structure-preserving signatures, the message space M consists of pairs M := T × G n , for some n ∈ N, where T is a tag space. Depending on the application, one may want the tags to be group elements or not. In this paper, they can be arbitrary strings. Definition 4. A linearly homomorphic structure-preserving signature scheme over (G, G T ) is a tuple of efficient algorithms Σ = (Keygen, Sign, SignDerive, Verify) for which the message space consists of M := T × G n , for some integer n ∈ poly(λ) and some set T , and with the following specifications.

Keygen(λ, n): is a randomized algorithm that takes in a security parameter λ ∈ N and an integer n ∈ poly(λ) denoting the dimension of vectors to be signed. It outputs a key pair (pk, sk), where pk includes the description of a tag space T , where each tag serves as a file identifier. Sign(sk, τ, M ): is a possibly randomized algorithm that takes as input a private key sk, a file identifier τ ∈ T and a vector M = (M 1 , . . . , M n ) ∈ G n . It outputs a signature σ ∈ G ns , for some n s ∈ poly(λ). SignDerive(pk, τ, {(ω i , σ (i) )} ℓ i=1 ): is a (possibly randomized) derivation algorithm. It inputs a public key pk, a file identifier τ as well as ℓ pairs (ω i , σ (i) ), each of which consists of a coefficient ω i ∈ Z p and a signature σ (i) ∈ G ns . It outputs a signature σ ∈ G ns on the vector M = ℓ i=1 M ω i i , where σ (i) is a signature on M i . Verify(pk, τ, M , σ): is a deterministic verification algorithm that takes as input a public key pk, a file identifier τ ∈ T , a signature σ and a vector M = (M 1 , . . . , M n ). It outputs 0 or 1 depending on whether σ is deemed valid or not.

In a one-time linearly homomorphic SPS, the tag τ can be omitted in the specification as a given key pair (pk, sk) only allows signing one linear subspace.

As in all linearly homomorphic signatures, the security requirement is that the adversary be unable to create a valid triple (τ ⋆ , M ⋆ , σ ⋆ ) for a new file identifier τ ⋆ or, if τ ⋆ is recycled from one or more honestly generated signatures, for a vector M ⋆ outside the linear span of the vectors that have been legitimately signed for the tag τ ⋆ .

An important property is that the SignDerive algorithm must operate on vectors that are all labeled with the same tag.

C Randomizable Linearly Homomorphic Structure-Preserving Signatures

This section recalls the randomizable linearly homomorphic structure-preserving signature of [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF].

In the scheme, each signature basically consists of a Groth-Sahai NIWI proof of knowledge of a one-time signature (z, r, u) on the signed vector (M 1 , . . . , M n ). This proof of knowledge is generated for a Groth-Sahai CRS which depends on the tag that identifies the subspace being signed.

In the following notations, for each h ∈ G and any vector g = (g 1 , g 2 , g 3 ) ∈ G 3 , we denote by E(h, g) the vector (e(h, g 1 ), e(h, g 2 ), e(h, g 3 )) ∈ G 3 T .

Keygen(λ, n): given a security parameter λ and the dimension n ∈ N of the subspace to be signed, choose bilinear group (G, G T ) of order p > 2 λ with a generator g R ← G as well as g z , g r , h z , h u R ← G and do the following.

1. For i = 1 to n, pick χ i , γ i , δ i R ← Z p and compute g i = g z χ i g r γ i and h i = h z χ i h u δ i .
2. Generate L + 1 Groth-Sahai common reference strings, where L ∈ poly(λ) is the length of each tag τ ∈ T = {0, 1} L . To this end, choose

f 1 , f 2 R ← G and define vectors f 1 = (f 1 , 1, g) ∈ G 3 , f 2 = (1, f 2 , g) ∈ G 3 . Then, pick f 3,i R ← G 3 for i = 0 to L.
The public key consists of

pk = (G, G T ), g z , g r , h z , h u , {g i , h i } n i=1 , f = f 1 , f 2 , {f 3,i } L i=0 while the private key is sk = h z αr , {χ i , γ i , δ i } n i=1 . Sign(sk, τ, (M 1 , . . . , M n )): to sign a vector (M 1 , . . . , M n ) ∈ G n using sk = h z αr , {χ i , γ i , δ i } n i=1
with the file identifier τ , conduct the following steps.

1. Choose θ R ← Z p at random and compute z = g r θ • n i=1 M -χ i i , r = g z -θ • n i=1 M -γ i i and u = h z -θ•αr • n i=1 M -δ i i . 2. Using the bits τ [1] . . . τ [L] of τ ∈ {0, 1} L , define the vector f τ = f 3,0 • L i=1 f τ [i]
3,i so as to assemble a Groth-Sahai CRS

f τ = (f 1 , f 2 , f τ ). 3. Using f τ = (f 1 , f 2 , f τ ), compute commitments C z = (1 G , 1 G , z) • f ν z,1 1 • f ν z,2 2 • f ν z,3 τ and C r = (1 G , 1 G , r) • f ν r,1 1 • f ν r,2 2 • f ν r,3 τ C u = (1 G , 1 G , u) • f ν u,1 1 • f ν u,2 2 • f ν u,3 τ
to the derived z, r and u, respectively. Generate NIWI proofs

π 1 = (π 1,1 , π 1,2 , π 1,3 ) ∈ G 3 and π 2 = (π 2,1 , π 2,2 , π 2,3 ) ∈ G 3 that (z, r, u) satisfy the verification equations 1 G T = e(g z , z) • e(g r , r) • n i=1 e(g i , M i ) 1 G T = e(h z , z) • e(h u , u) • n i=1 e(h i , M i ).
These proofs are obtained as

π 1 = (π 1,1 , π 1,2 , π 1,3 ) = g z -ν z,1 • g r -ν r,1 , g z -ν z,2 • g r -ν r,2 , g z -ν z,3 • g r -ν r,3 π 2 = (π 2,1 , π 2,2 , π 2,3 ) = h z -ν z,1 • h u -ν u,1 , h z -ν z,2 • h u -ν u,2 , h z -ν z,3 • h u -ν u,3 . The signature consists of σ = (C z , C r , C u , π 1 , π 2 ) ∈ G 15 .
SignDerive(pk, τ, {(ω i , σ (i) )} ℓ i=1 ): given pk, a file identifier τ and ℓ tuples (ω i , σ (i) ), parse each signature σ (i) as a tuple of the form

σ (i) = (C z,i , C r,i , C u,i , π 1,i , π 2,i ) ∈ G 15 for i = 1 to ℓ. 1. Compute C z = ℓ i=1 C ω i z,i , C r = ℓ i=1 C ω i r,i , C u = ℓ i=1 C ω i u,i , π 1 = ℓ i=1 π ω i 1,i as well as π 2 = ℓ i=1 π ω i 2,i .

Re-randomize the above commitments and proofs and return

σ = (C z , C r , C u , π 1 , π 2 ).
Verify(pk, σ, τ, (M 1 , . . . , M n )): given (τ, (M 1 , . . . , M n )) and a purported signature σ, parse σ as

(C z , C r , C u , π 1 , π 2 ). Return 1 iff (M 1 , . . . , M n ) = (1 G , . . . , 1 G ) and the proofs (π 1 , π 2 ) satisfy n i=1 E g i , (1 G , 1 G , M i ) -1 = E g z , C z • E g r , C r • E(π 1,1 , f 1 ) • E(π 1,2 , f 2 ) • E(π 1,3 , f τ ) (4) n i=1 E h i , (1 G , 1 G , M i ) -1 = E h z , C z • E h u , C u • E(π 2,1 , f 1 ) • E(π 2,2 , f 2 ) • E(π 2,3 , f τ ).
We remark that the scheme can be simplified by setting θ = 0 in all algorithms: since all noninteractive proofs are generated for a perfectly NIWI Groth-Sahai CRS, this modification does not affect the distribution of signatures whatsoever. In Sections 3 and 5, we use this simplified version of the scheme.

The scheme is only known [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF] to be secure in a relaxed model where the adversary is only deemed successful if it additionally provides evidence that its output vector is indeed independent of those for which it obtained signatures with respect to the target tag τ ⋆ . In our applications, this restriction will not be a problem at all since, in all security proofs, the reduction will always be able to detect when the adversary has won without requiring explicit evidence for it.

D Extensions Based on the k-Linear Assumption

To instantiate our proof systems using the k-linear assumption with k > 2, we first need to extend the one-time linearly homomorphic structure-preserving signature of [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF]. To this end, we need to define the following assumption which is implied by the k-linear assumption in the same way as SDP is implied by DLIN. Definition 5. The Simultaneous k-wise Pairing (k-SDP) problem is, given a random tuple (g 1,z , . . . , g k,z , g 1,r , . . . , g k,r ) ∈ R G 2k , to find a non-trivial vector (z, r 1 , . . . , r k ) ∈ G k+1 such that e(g j,z , z) • e(g j,r , r j ) = 1 G T j ∈ {1, . . . , k}

and z = 1 G .

Given a k-linear instance (g 1,r , . . . , g k,r , g a 1 1,r , . . . , g a k k,r , η) ∈ G 2k+1 , for any non-trivial tuple (z, r 1 , . . . , r k ) satisfying e(g a j j,r , z) • e(g j,r , r j ) = 1 G T for each j ∈ {1, . . . , k}, we have

η = g k j=1 a j ⇔ e(g, k j=1 r j ) • e(z, η) = 1 G T .
Hence, any algorithm solving k-SDP with non-negligible probability implies a k-linear distinguisher. Under the k-SDP assumption, the one-time linearly homomorphic structure-preserving signature of [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF] can be extended as follows.

Keygen(λ, n): given a security parameter λ and the dimension n ∈ N of vectors to be signed, choose bilinear group (G, G T ) of prime order p > 2 λ . For j = 1 to k, choose generators g j,z , g j,r R ← G. Then, for each i = 1 to n, j = 1 to k, pick χ i R ← Z p , γ j,i R ← Z p and compute g j,i = g j,z χ i g j,r γ j,i . The private key is sk = {χ i , {γ j,i } k j=1 } n i=1 while the public key is pk = {g j,z , g j,r , {g j,i } n i=1 } k j=1 .

Sign(sk, (M 1 , . . . , M n )): to sign (M 1 , . . . , M n ) ∈ G n using sk = {χ i , {γ j,i } k j=1 } n i=1 , compute and output σ = (z, r 1 , . . . , r k ) ∈ G k+1 , where

z = n i=1 M -χ i i , r j = n i=1 M -γ j,i i j ∈ {1, . . . , k}.
SignDerive(pk, {(ω i , σ (i) )} ℓ i=1 ): given a public key pk and ℓ tuples (ω i , σ (i) ), where ω i ∈ Z p for each i, parse σ (i) as σ (i) = z i , r i,1 , . . . , r i,k ∈ G k+1 for i = 1 to ℓ. Then, compute and return σ = (z, r 1 , . . . , r k ), where z = ℓ i=1 z ω i i , r j = ℓ i=1 r ω i i,j for j = 1 to k. Verify(pk, σ, (M 1 , . . . , M n )): given σ = (z, r 1 , . . . , r k ) ∈ G k+1 and (M 1 , . . . , M n ), return 1 if and only if (M 1 , . . . , M n ) = (1 G , . . . , 1 G ) and, for each j ∈ {1, . . . , k}, the following equality holds:

1 G T = e(g j,z , z) • e(g j,r , r j ) • n i=1 e(g j,i , M i ). (6)
In order to adapt the unbounded simulation-sound proof system of Section 3, we need to commit to the components of (z, r 1 , . . . , r k ) and NIWI arguments showing that committed group elements satisfy the pairing product equations [START_REF] Bellare | Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme[END_REF]. Under the k-linear assumption, committing to a group element requires k + 1 group elements (see, e.g., [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF] for details) whereas each equation of the form (6) costs k + 1 elements to prove. Overall, we thus need (k + 1)(2k + 1) group elements and a one-time verification key pair (SVK, σ).

In the relatively-sound QA-NIZK proof of Section 4, the proof element π 0 remains unchanged and we simply need to replace the triple (z, r, u) by a one-time linearly homomorphic signature (z, r 1 , . . . , r k ). Hence, we only need k + 2 group elements.

E Comparisons

This section compares the various NIZK proofs of linear subspace membership based on the DLIN assumption. Comparisons are given in terms of CRS size, proof size, the number of pairing evaluations for the verifier and the need for a computational assumption to prove the soundness property.

In the table, we consider our basic proof system (without any form of simulation-soundness, where each proof is a one-time linearly homomorphic signature (z, r, u)), its unbounded simulation-sound variant and the relatively simulation-sound variant of Section 4. We compare these with the original Groth-Sahai proofs, their most efficient unbounded simulation-sound extensions due to Camenisch et al. [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF] and the Jutla-Roy techniques [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] with and without relative soundness. * The description ρ ∈ G t×n of the language is not counted as being part of the CRS here. † The table does not consider optimizations using randomized batch verification techniques here. ‡ We consider instantiations using Groth's one-time signature [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF], where verification keys and signatures consist of 3 group elements and two elements of Zp, respectively.

As can be observed in the table, our constructions all yield constant-size arguments. Moreover, the number of pairing evaluations is always independent of the number of variables t, which substantially fastens the verification process when t ≈ n/2.

We also note that randomized batch verification techniques can be used to drastically reduce the number of pairing computations. In our USS system, for example, the number of pairings drops to n + 18 if the two verification equations are processed together and further optimizations are possible.

Our common reference strings always fit within O(t + n) group elements (with another O(L) elements in the USS variant) and thus provide significant savings w.r.t. [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] when t ≈ n/2.

F Proof of Theorem 1

Proof. The quasi-adaptive completeness property follows directly from the correctness of the randomizable linearly homomorphic signature of Section 2.5. We thus focus on the quasi-adaptive zeroknowledge and quasi-adaptive unbounded simulation-soundness properties.

Quasi-Adaptive Zero-Knowledge. To prove this property we consider a sequence of two games which begins with a game where the adversary has access to a real prover P on a real CRS ψ. In the second game, the adversary will be faced with a simulator (S 1 , S 2 ).

Game 1 : is a game where the adversary A is given the description of the language L ρ and is granted access to a real CRS ψ and an actual prover P(ψ, ., .) which takes as input a vector v along with a witness x ∈ Z t p such that v = g x•A . At each invocation, the oracle outputs a genuine proof π by running the legal P algorithm. The adversary is allowed to query P(ψ, ., .) a polynomial number of times and eventually outputs a bit β ∈ {0, 1}. We denote by S 1 the event that β = 1.

Game 2 : This game is identical to Game 2 with the difference that, when the P(ψ, ., .) oracle is queried on a pair (v, x), it does not use the witness x ∈ Z t p anymore at step 1 of the proving algorithm. Instead, it uses the the private key sk rand = {(χ i , γ i , δ i )} n i=1 to compute a one-time signature (z, r, u)

= n j=1 v -χ j j , n j=1 v -γ j j
, n j=1 v -δ j j ) on the vector v = (v 1 , . . . , v n ) ∈ G n . The remaining parts of π are generated as in the real P(ψ, ., .) oracle in steps 2 and 3 of the proof generation algorithm. Although, the witness x ∈ Z t p is never used, it is easy to see that (z, r, u) has exactly the same distribution as in Game 2 if v ∈ L ρ (i.e., as long as v = g x•A for some x ∈ Z t p ). We thus have Pr[S 2 ] = Pr[S 1 ].

We define the simulator (S 1 , S 2 ) by having S 1 generate the CRS ψ as in Game 1 (so that ψ has the same distribution as the real CRS) and letting S 2 generate proofs without using the witnesses as in Game 2 . It easily comes that the system is perfectly quasi-adaptive zero-knowledge as, for all language members v ∈ G n , simulated proofs are distributed as real proofs.

Quasi-Adaptive Unbounded Simulation-Soundness. To prove this property, we proceed again with a sequence of games.

Game 1 : is the real game where the adversary A is given the description of the language L ρ and is granted access to a simulated CRS ψ and a simulated prover S 2 (ψ, τ sim , ., .) which takes as input a vector-label pair (v, lbl) and returns a simulated proof π that v ∈ L ρ . To generate ρ ∈ G t×n according to the distribution D Γ , the challenger generates a matrix A ∈ Z t×n p with the appropriate distribution (recall that D Γ is efficiently samplable by hypothesis) and computes ρ = g A . In addition, the challenger B computes a basis W ∈ Z n×(n-t) p of the right kernel of A and retains it for later use. The adversary is allowed to query the simulated prover S 2 (ψ, τ sim , ., .) on polynomially many occasions. The game ends with the adversary A outputting an element v ⋆ , a proof π ⋆ and a label lbl ⋆ . The adversary is deemed successful if v ⋆ ∈ L ρ (i.e., v ⋆ is not in the row space of ρ ∈ G t×n ) but (π ⋆ , lbl ⋆ ) is a valid proof. We denote by S 1 the latter event, which B can recognize by testing if

v = (v 1 , . . . , v n ) ∈ G n satisfies n j=1 v w ji j
= 1 G for each column w ⊤ i = (w 1i , . . . , w ni ) ⊤ of W. Indeed, the vectors y ∈ Z n p in the row space of A are exactly those for which y • W = 0. Game 2 : This game is identical to Game 1 but the challenger B aborts if the adversary A outputs a fake proof π ⋆ that recycles one of the one-time verification keys appearing in outputs of the S 2 (ψ, τ sim , ., .) oracle. Clearly, Game 2 and Game 1 are identical until the latter event occurs and this event contradicts the strong unforgeability of Σ: if q denotes the number of queries to S 2 (ψ, τ sim , ., .), a standard argument shows that

| Pr[S 2 ] -Pr[S 1 ]| ≤ q • Adv suf-ots (B).
Game 3 : This game is identical to Game 2 but we modify the generation of pk rand when the public key is set up. Namely, the vectors (f 1 , f 2 , {f 3,i } L i=0 ) are chosen by setting

f 1 = (f 1 , 1 G , g) and f 2 = (1 G , f 2 , g) where f 1 , f 2 R ← G are chosen at random. As for {f 3,i } L i=0
, they are obtained as

f 3,0 = f ξ 0,1 1 • f ξ 0,2 2 • (1, 1, g) ξ 0,3 • (1, 1, g) µ•ζ-ρ 0 (7) f 3,i = f ξ i,1 1 • f ξ i,2 2 • (1, 1, g) ξ i,3 • (1, 1, g) -ρ i , i ∈ {1, . . . , L} with µ R ← {0, . . . , L}, ξ 0,1 , ξ 1,1 , . . . , ξ L,1 R ← Z p , ξ 0,2 , ξ 1,2 , . . . , ξ L,2 R ← Z p , ξ 0,3 , ξ 1,3 , . . . , ξ L,3 R ← Z p and ρ 0 , ρ 1 , . . . , ρ L R ← {0, . . . , ζ -1}, with ζ = 2(q + 1
) and where q is the number of queries to the S 2 (ψ, τ sim , .) oracle. Note that this change is only conceptual since the distribution of {f 3,i } L i=0 has not changed since Game 2 . We thus have Pr

[S 3 ] = Pr[S 2 ].
Game 4 : This game is like Game 3 but we consider an event Good which causes the challenger B to abort if it does not occur. Let SVK 1 , . . . , SVK q be the distinct one-time verification keys appearing in outputs of the S 2 oracle throughout the game. Let also SVK ⋆ be the verification key involved in the fake proof π ⋆ produced by A. We know that SVK ⋆ ∈ {SVK 1 , . . . , SVK q } unless the failure event introduced in Game 2 occurs. For each verification key SVK ∈ {0, 1} L , we consider the function

J(SVK) = µ • ζ -ρ 0 -L i=1 ρ i • SVK[i],
where {ρ i } L i=0 are the values internally defined by the simulator in Game 3 . We also define Good to be the event that

J(SVK ⋆ ) = 0 ∧ j∈{1,...,q} J(SVK j ) = 0. ( 8
)
We remark that the random exponents ρ 0 , ρ 1 , . . . , ρ L are chosen independently of A's view: this means that the simulator could equivalently define {f 3,i } L i=0 first and only choose {ρ i } L i=0together with values {ξ 3,i } L i=0 explaining the {f 3,i } L i=0 -at the very end of the game, when SVK ⋆ , SVK 1 , . . . , SVK q , SVK have been defined. The same analysis as [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF] (using the simplifications of Bellare and Ristenpart [6, Theorem 3

.1]) shows that Pr[S 4 ∧Good] ≥ Pr[S 3 ] 2 /(27•(q+1)•(L+1)).
This follows from the fact that, for any set of queries, a lower bound on the probability of event Good is 1/(2q(L + 1)). Indeed, from the known results [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF][START_REF] Hofheinz | Programmable Hash Functions and Their Applications[END_REF] on the programmability of Waters' hash function, we know that the probability, taken over the choice of (µ, ρ 0 , . . . , ρ L ), to meet the conditions ( 8) is at least 1/(2q(L + 1)).

Game 5 : We modify again the way to compute pk rand in the generation of the public key. Namely, the vectors

f 1 = (f 1 , 1 G , g), f 2 = (1 G , f 2 , g
) are chosen as before. However, instead of generating {f 3,i } L i=0 as in Game 4 , we set them as

f 3,0 = f ξ 0,1 1 • f ξ 0,2 2 • (1, 1, g) µ•ζ-ρ 0 (9) f 3,i = f ξ i,1 1 • f ξ i,2 2 • (1, 1, g) -ρ i , i ∈ {1, . . . , L}
which amounts to setting ξ 0,3 = ξ 1,3 = . . . = ξ L,3 = 0. Clearly, {f 3,i } L i=0 are no longer uniform in the span of f 1 , f 2 , (1, 1, g) . Still, this change should not be noticeable to A if the DLIN assumption holds in G. Concretely, if the adversary wins (recall that the challenger can still detect this event using the matrix W ∈ Z n×(n-t) p as explained in Game 1 ) with substantially different probabilities in Game 5 and Game 4 , we can construct a DLIN distinguisher B DLIN in the group G. This distinguisher uses the random self-reducibility of DLIN to construct many independentlooking instances from the same distribution out of a given instance. The distinguisher then runs A on input of the CRS that was generated using the DLIN instances and it eventually outputs 1 if the adversary wins. We can thus write | Pr

[S 5 ∧ Good] -Pr[S 4 ∧ Good]| ≤ Adv B DLIN (λ).
In Game 5 , we show that a successful adversary implies an algorithm B solving a given SDP instance (g z , g r , h z , h u ) with non-negligible probability, which a fortiori breaks the DLIN assumption in G.

By hypothesis, we know that A manages to create a proof 15 and σ ⋆ satisfy the verification equations. At this point, if the event Good introduced in Game 4 occurs, we must have J(SVK ⋆ ) = 0, which implies that

π ⋆ = (SVK ⋆ , C ⋆ z , C ⋆ r , C ⋆ u , π ⋆ 1 , π ⋆ 2 , σ ⋆ ) for a vector v ⋆ = (v ⋆ 1 , . . . , v ⋆ n ) outside the row space of ρ but (C ⋆ z , C ⋆ r , C ⋆ u , π ⋆ 1 , π ⋆ 2 ) ∈ G
f SVK ⋆ = f 3,0 • L+1 i=1 f SVK ⋆ [i] 3,i lies in span(f 1 , f 2 ).
Consequently, C ⋆ z , C ⋆ r and C ⋆ u are necessarily perfectly binding and extractable commitments. Using (log g (f 1 ), log g (f 2 )), algorithm B can thus extract the committed group elements (z

⋆ , r ⋆ , u ⋆ ) ∈ G 3 by BBS-decrypting the ciphertexts (C ⋆ z , C ⋆ r , C ⋆ u ). Since (π ⋆ 1 , π ⋆ 2 )
are perfectly sound Groth-Sahai proofs, the extracted elements (z ⋆ , r ⋆ , u ⋆ ) necessarily satisfy

1 G T = e(g z , z ⋆ ) • e(g r , r ⋆ ) • n i=1 e(g i , v ⋆ i ) = e(h z , z ⋆ ) • e(h u , u ⋆ ) • n i=1 e(h i , v ⋆ i ). ( 10
)
Having extracted (z ⋆ , r ⋆ , u ⋆ ), B also computes

z † = n i=1 v ⋆ i -χ i r † = n i=1 v ⋆ i -γ i u † = n i=1 v ⋆ i -δ i , (11)
so that (z † , r † , u † ) also satisfies [START_REF] Boneh | Short group signatures[END_REF]. Since (z † , r † , u † ) and (z ⋆ , r ⋆ , u ⋆ ) both satisfy [START_REF] Boneh | Short group signatures[END_REF], the triple

(z ‡ , r ‡ , u ‡ ) = z ⋆ z † , r ⋆ r † , u ⋆ u † necessarily satisfies e(g z , z ‡ ) • e(g r , r ‡ ) = e(h z , z ‡ ) • e(h u , u ‡ ) = 1 G T .
To conclude the proof, we argue that z ‡ = 1 G with overwhelming probability.

To do this, we observe that, if the event Good defined in Game 4 actually comes about, then B never leaks any more information about (χ 1 , . . . , χ n ) than A can infer by just observing {(z j , r j , u j )} t j=1 in the public key. Indeed, in this case we have J(SVK ⋆ ) = 0 and J(SVK j ) = 0 for each j ∈ {1, . . . , q}. This means that, in the simulated proofs returned by S 2 (ψ, τ sim , ., .), the proofs (π 1 , π 2 ) are perfectly witness indistinguishable as they are generated for a perfectly hiding Groth-Sahai CRS. For these simulated proofs, the built-in homomorphic signatures (C z , C r , C u , π 1 , π 2 ) leak nothing about the specific vector (χ 1 , . . . , χ n ) used by B. As a consequence, the same arguments as in [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF]Theorem 1] show that z † = z ⋆ with probability 1 -1/p. Specifically, in the CRS, {(g i , h i )} n i=1 and {(z i , r i , u i )} t i=1 provide the adversary with a system of 2n + t < 3n equations in 3n unknowns {(χ i , γ i , δ i )} n i=1 , which leaves z † completely undetermined as long as v ⋆ is linearly independent of the rows of G i,j i,j . We thus find

Pr[S 5 ∧ Good] = Adv SDP B (λ) • 1 - 1 p -1
.

In turn, in Game 5 , B implies a PPT distinguisher B DLIN ′ for the DLIN assumption such that we have the inequality Pr

[S 5 ∧ Good] < 1 2 • Adv B DLIN ′ (λ) • 1 -1 p -1 . If Adv DLIN (λ)
denotes the maximal advantage of any PPT distinguisher against the DLIN assumption in G, the probability of event

S 4 ∧ Good can be bounded as Pr[S 4 ∧ Good] ≤ 3 2 • Adv DLIN (λ) • 1 -1 p -1 in Game 5 in Game 4 . This in turn yields Pr[S 3 ] ≤ 7 • q • (L + 1) • Adv DLIN (λ) • 1 - 1 p -1 ,
so that A's advantage in breaking the unbounded simulation-soundness of the system is at most

Adv uss (A) ≤ Adv suf-ots (λ) + 7 • q • (L + 1) • Adv DLIN (λ) • 1 - 1 p -1 . (12)
⊓ ⊔

G Proof of Theorem 2

Proof. The completeness property is straightforward to verify. To establish the result, we separately prove the relative quasi-adaptive zero-knowledge and relative quasi-adaptive simulation-soundness properties.

Quasi-Adaptive Relative Zero-Knowledge. We consider a sequence of two games which begins with a game where the adversary has oracle access to the actual prover P and a public verifier on a real CRS ψ. In the last game, the adversary will be interacting with a simulator (S 1 , S 2 ) and the private verifier.

Game 1 : is a game where the adversary A is given the description ρ of the language L ρ and a real CRS ψ = (CRS 1 , CRS 2 ). In addition, the adversary has access to a public verification oracle V(ψ, ., .), even though it can run the verification algorithm by itself. This will be useful to show that the private verifier always agrees with the public one when it interacts with a PPT adversary. At some point, the adversary chooses a pair (v, lbl) along with a witness x ∈ Z t p such that v = g x•A . The challenger replies by returning an actual proof π produced by running P(ψ, v, x, lbl). When A terminates, it outputs a bit β ∈ {0, 1}. We denote by S 1 the event that β = 1.

Game 2 : is like Game 1 but the adversary's public verification oracle V(ψ, ., .) is replaced by the private verification oracle W(ψ, τ v , ., .). Since the private verification algorithm begins by running the public one, both games are clearly identical until A queries the verification oracle on input of a candidate (v, (z, r, u, π 0 ), lbl) that is accepted by V(ψ, ., .) but rejected by W(ψ, τ v , ., .). If we call this event F 2 , we have

| Pr[S 1 ] -Pr[S 2 ]| ≤ Pr[F 2 ].
Claim 1. The probability of event F 2 can be bounded as Pr

[F 2 ] ≤ Adv SDP (λ) + 1 p .
Proof. We first remark that event F 2 can only occur for a candidate v, (z, r, u, π 0 ), lbl such that the vector

(v 1 , . . . , v n , π 0 , v α 1 , . . . , v α n ) is not in the span of {H 2i-1 , H 2i } t i=1 . Indeed, otherwise, there would exist x = (x 1 , . . . , x t ) ∈ Z t p such that (v 1 , . . . , v n ) = g x•A and π 0 = t i=1 (W α i Y i ) x i .
In this case, we would also have

g x•A•(e ⊤ +α•d ⊤ ) = t i=1 (W α i Y i ) x i ,
and the private verifier W(ψ, τ v , ., .) would accept the proof (z, r, u, π 0 ). It comes that the only way for the adversary to cause a divergence between W(ψ, τ v , ., .) and V(ψ, ., .) is to create a valid-looking one-time linearly homomorphic signature (z, r, u) on a vector outside span {H 2i-1 , H 2i } t i=1 . The result of [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF][ Theorem 1] shows that this occurs with probability at most Pr[F 2 ] ≤ Adv SDP (λ) + 1 p .

Game 3 : This game like Game 2 but, when the adversary outputs its triple (v, x, lbl), the challenger does not use the witness x ∈ Z t p any longer. To simulate the proof for (v, x, lbl), it first computes α = H(ρ, v, lbl). Then, using the private vectors d, e ∈ Z n p , it computes π 0 = n j=1 v e j +α•d j j before using the private key sk ots = {(χ i , γ i , δ i )} 2n+1

i=1 to compute a one-time signature

(z, r, u) = 2n+1 j=1 v -χ j j , 2n+1 j=1 v -γ j j , 2n+1 j=1 v -δ j j )
on the vector ṽ = (v 1 , . . . , v 2n+1 ), where v n+1 = π 0 and v n+i+1 = v α i for i = 1 to n. The resulting proof is easily seen to have the same distribution as in Game 2 when v ∈ L ρ . We thus have Pr

[S 3 ] = Pr[S 2 ].
We define the simulator (S 1 , S 2 ) by having S 1 generate the CRS ψ as in Game 3 (observe that it has not changed since Game 1 ) and S 2 generate compute the proof without using the witnesses as in Game 3 . The verification oracle is implemented as in Game 2 and Game 3 . It easily comes that the system is computationally quasi-adaptive relatively zero-knowledge if the SDP assumption holds.

Quasi-Adaptive Relative Simulation-Soundness. We have to prove that, even if the simulator (S 1 , S 2 ) provides the adversary A with a simulated proof π for a pair (v, lbl), where v ∈ G n may not be in L ρ , A will remain unable to produce a new proof (v

⋆ , π ⋆ , lbl ⋆ ) = (v, π, lbl) such that v ⋆ ∈ L ρ .
To prove the result, we rely on the smoothness of the projective hash function and on a specific property of the one-time linearly homomorphic signature of Section 2.5: namely, unless the SDP assumption is false, it is hard to compute two distinct signatures on the same vector, even when the private key is available.

We thus proceed with a sequence of games where the first game is the actual game and the last one is a game where the adversary has statistically no advantage. In Game i , we denote by S i the event that the adversary wins.

Game 1 : is the real game where the adversary A is given the description of L ρ , a simulated CRS ψ and access to a simulated prover S 2 (ψ, τ sim , ., .) which is queried only once. On this occasion, S 2 takes as input a vector v † ∈ G n and a label lbl † and it produces a simulated proof π † = (z † , r † , u † , π † 0 ) that v † ∈ L ρ . To generate ρ ∈ G t×n according to the distribution D Γ at the beginning of the game, the challenger computes ρ = g A after having sampled a matrix A ∈ Z t×n p with the appropriate distribution (which is possible since D Γ is efficiently samplable). Moreover, the challenger B computes a basis W ∈ Z n×(n-t) p of the right kernel of A. The adversary is allowed to query S 2 (ψ, τ sim , ., .) exactly once and the private verifier W(ψ, τ v , ., .) on polynomially many occasions. When A terminates, it outputs a triple (v ⋆ , π ⋆ , lbl ⋆ ). The adversary is successful if v ⋆ ∈ L ρ but (π ⋆ , lbl ⋆ ) passes the private verification test and (v ⋆ , π ⋆ , lbl ⋆ ) = (v † , π † , lbl † ). We denote by S 1 the latter event. Note that B can recognize this event as it can test if v ⋆ ∈ L ρ by checking whether

v ⋆ = (v ⋆ 1 , . . . , v ⋆ n ) ∈ G n satisfies n j=1 v ⋆ j w ji = 1 G for each column w ⊤ i = (w 1i , . . . , w ni ) ⊤ of W.
Indeed, the vectors y ∈ Z n p in the row space of A are exactly those for which y • W = 0. Game 2 : In this game, we modify the behavior of the private verification oracle W(ψ, τ v , ., .) . At each invocation (including the final invocation on the adversary's output (v ⋆ , π ⋆ , lbl ⋆ )) on input of a triple (v, π, lbl), the modified private verification oracle outputs 0

if (v, π, lbl) = (v † , π † , lbl † ) but H(ρ, v, lbl) = H(ρ, v † , lbl † ).
Clearly, Game 1 and Game 2 proceed identically until the latter event, called F 2 , occurs. We have

| Pr[S 2 ] -Pr[S 1 ]| ≤ Pr[F 2 ]. Moreover, F 2 is unlikely to occur if H is a collision-resistant hash function: we have Pr[F 2 ] ≤ Adv CR (λ).
Game 3 : This game is identical to Game 2 with the following difference. When the private verification oracle W(ψ, τ v , ., .) is run on input of the adversary's proof (v ⋆ , π ⋆ , lbl ⋆ ), it returns 0 in the event

that π ⋆ = (z ⋆ , r ⋆ , u ⋆ , π ⋆ 0 ) is such that (z ⋆ , r ⋆ , u ⋆ ) = (z † , r † , u † ) but (v ⋆ , lbl ⋆ ) = (v † , lbl † ).
If we call F 3 the event that the private verification oracle W(ψ, τ v , ., .) rejects a proof that would have been accepted in Game 2 , we have

| Pr[S 3 ] -Pr[S 2 ]| ≤ Pr[F 3 ]. Moreover, F 3 implies a breach in the SDP assumption. Indeed, if π ⋆ 0 = π † 0 , W(ψ, τ v , .
, .) would not accept π ⋆ in Game 2 either, regardless of whether (z ⋆ , r ⋆ , u ⋆ ) = (z † , r † , u † ) or not. If π ⋆ 0 = π † 0 , event F 3 provides the challenger with two distinct linearly homomorphic signatures (z ⋆ , r ⋆ , u ⋆ ) and (z † , r † , u † ) on the same vector

(v ⋆ 1 , . . . , v ⋆ n , π ⋆ 0 , v ⋆ 1 α ⋆ , . . . , v ⋆ n α ⋆
) as we also have α ⋆ = α † . As mentioned in Section 2.5 (and as can be easily observed from the verification equations), this would contradict the SDP assumption and we thus have

| Pr[S 3 ] -Pr[S 2 ]| ≤ Adv SDP (λ).
Game 4 : In this game, we further modify the behavior of W(ψ, τ v , ., .) when it assesses the the adversary's output (v ⋆ , π ⋆ , lbl ⋆ ). Using the basis W of the right kernel of A, the challenger B first checks if v ⋆ ∈ L ρ and forces W(ψ, τ v , ., .) to return 0 whenever this is the case. If we denote by F 4 the event that W(ψ, τ v , ., .) rejects an adversarially-generated triple (v ⋆ , π ⋆ , lbl ⋆ ) that would have survived the private verification test of Game Claim 2. The probability of event F 4 is at most Pr[F 4 ] ≤ 1/(pq), where q denotes the number of private verification queries.

Proof. The proof of the claim is a standard argument based on the smoothness of the projective hash function. If we consider the information that A can infer about the private evaluation key

τ v = d = (d 1 , . . . , d n
), e = (e 1 , . . . , e n ) by observing the CRS and the proof π † = (z † , r † , u † , π † 0 ), it amounts to the first 2t + 1 rows of the left-hand-side member of the following linear system:

    Y ⊤ W ⊤ π † 0 π ⋆ 0     =     A A log(v † ) α † • log(v † ) log(v ⋆ ) α ⋆ • log(v ⋆ )     • e ⊤ d ⊤ (13)
Let us assume that v † , v ⋆ ∈ L ρ . Since the above (2t+2)×2n matrix has full rank when α ⋆ = α (which is the case unless the failure event F 1 of Game 1 occurs), we see that the only value of π ⋆ 0 that would trick the private verification oracle W(ψ, τ, ., .) of Game 3 into accepting π ⋆ is completely independent of the information provided by the CRS and the simulated proof π † for v † . However, A can also take advantage of its private verification queries throughout the game. Without any verification query, (e, d) is constrained by the first 2t + 1 rows of [START_REF] Boyd | Digital Multisignatures[END_REF] to live in a subspace of dimension 2(nt) -1 ≥ 1 in Z 2n p , so that π ⋆ 0 has p equally likely values in A's view. Each private verification query provides A with an inequality, which allows it to rule out one candidate for the value of π ⋆ 0 that W(ψ, τ v , ., .) would accept. After q queries, A is thus left with pq equally likely candidates for π ⋆ 0 . We thus find Pr[F 4 ] ≤ 1/(pq), as claimed.

Putting the above altogether, A's advantage is breaking the quasi-adaptive relative simulationsoundness property is bounded as

Adv rss (A) ≤ Adv CR (λ) + Adv SDP (λ) + 1 2 λ -q .
⊓ ⊔ H Proof of KH-CCA Security for the Keyed-Homomorphic Scheme

Instead of relying on the simulation-soundness of the proof system in a modular manner, our proof of KH-CCA security uses a direct security analysis in order to obtain a tighter reduction.

Theorem 3. The threshold keyed-homomorphic cryptosystem of Section 5 provides KH-CCA security in the sense of Definition 1 assuming that: (i) Σ is a strongly unforgeable one-time signature; (ii) The DLIN assumption holds in G. Concretely, the advantage of any PPT adversary A is at most Adv kh-cca (A) < (q e + 1) • Adv suf-ots (λ) + 3 2

• Adv DLIN (λ)

+ 7 • (q e + 1) • (L + 1) • Adv DLIN (λ) • 1 - 1 p -1 + 1 p ,
where Adv suf-ots (λ) denotes A's probability to break the strong unforgeability of Σ and q e is the maximal number of evaluation queries involving derivatives of the challenge ciphertext.

Proof. The proof uses of a sequence of games starting with the real attack game and ending with a game where the adversary A has no advantage. For each i, we also denote by S i the event that the challenger outputs 1 in Game i .

Game 1 : is the actual attack game with the only difference that the challenger B does not erase sk ot during the key generation phase. In details, the adversary is given the public key P K and the set of verification keys VK = (V K 1 , . . . , V K N ). If A decides to query the RevHK oracle at some point, B reveals SK h . At each corruption query i ∈ {1, . . . , N }, B reveals the queried private key share SK i = (P 1 (i), P 2 (i), P (i)). At each decryption query, B faithfully runs the real shared decryption algorithm. At each evaluation query, A supplies two ciphertexts C (1) , C (2) which are processed by B as in the evaluation algorithm. We denote by C † 1 , . . . , C † qe the outputs of the Eval(SK h , .) oracle when the latter is queried on a pair (C (1) , C (2) ) such that C (j) ∈ D for some j ∈ {1, 2} (in other words, {C † l } qe l=1 are the results of evaluation queries which increase |D|). We also denote by SVK † 1 , . . . , SVK † qe the one-time verification keys appearing in these ciphertexts and assume w.l.o.g. that they are chosen by B at the very beginning of the game.

When the first phase is over, the adversary A chooses two distinct messages M 0 , M 1 ∈ G and obtains

C ⋆ = (SVK ⋆ , C ⋆ 0 , C ⋆ 1 , C ⋆ 2 , C ⋆ 3 , Z ⋆ , R ⋆ , U ⋆ , C ⋆ z , C ⋆ r , C ⋆ u , π ⋆ 1 , π ⋆ 2 , σ ⋆ )
which is an encryption of M β , for some random coin β R ← {0, 1} flipped by B. In the second phase, A makes more decryption, evaluation and corruption queries under the restriction of not asking for a partial decryption of a ciphertext in D or for more than t -1 private key shares throughout the entire game. Eventually, A halts and outputs β ′ ∈ {0, 1}. The challenger B outputs 1 if and only if β = β ′ . We denote this event by S 1 .

Game 2 : This game is identical to Game 1 with the difference that the challenger B rejects all decryption queries involving ciphertexts

C = (SVK, C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 , σ) such that SVK ∈ {SVK ⋆ , SVK † 1 , . . . , SVK † qe }.
It also returns ⊥ at each evaluation query (C (1) , C (2) ) for which there exists j ∈ {1, 2} for which C (j) contains a verification key SVK (j) such that SVK

(j) = SVK † l , for some SVK † l ∈ {SVK ⋆ , SVK † 1 , . . . , SVK † qe }, but C (j) = C † l .
If we define F 2 to be the event that B rejects a ciphertext that would not have been rejected in Game 1 , we see that Game 2 and Game 1 proceed identically until event F 2 occurs. We thus have the inequality

|Pr[S 2 ] -Pr[S 1 ]| ≤ Pr[F 2 ]
. Moreover, event F 2 would imply a breach in the strong unforgeability of the one-time signature. Indeed, since A is not allowed to query the partial decryption of any ciphertext in D, a standard argument allows proving the inequality |Pr[S 2 ] -Pr[S 1 ]| ≤ Pr[F 2 ] ≤ (q e + 1) • Adv suf-ots (λ). In the forthcoming games, we will assume that SVK ∈ {SVK ⋆ , SVK † 1 , . . . , SVK † qe } at each decryption query. Game 3 : We modify the generation of the challenge ciphertext C ⋆ . Namely, instead of computing

C ⋆ 0 = M β • X θ 1 • X θ 2
, using the encryption exponents θ 1 = log f (C ⋆ 1 ) and θ 2 = log h (C ⋆ 2 ), B uses the private key (x 0 , x 1 , x 2 ) and computes

C ⋆ 0 = M β • C ⋆ 1 x 1 • C ⋆ 2 x 2 • C ⋆ 3 x 0 .
Likewise, instead of using (θ 1 , θ 2 ) to derive the triple (z ⋆ , r ⋆ , u ⋆ ) at step 3 of the encryption algorithm, B uses the simulation trapdoor sk rand = {(χ i , γ i , δ i )} 3 i=1 of the USS proof system and computes

z ⋆ = 3 i=1 C ⋆ i -χ i r ⋆ = 3 i=1 C ⋆ i -γ i u ⋆ = 3 i=1 C ⋆ i -δ i . (14)
Finally, (Z ⋆ , R ⋆ , U ⋆ ) is generated using sk ot = {(ϕ i , ϑ i , ̟ i )} 3 i=1 as

Z ⋆ = 3 i=1 C ⋆ i -ϕ i R ⋆ = 3 i=1 C ⋆ i -ϑ i U ⋆ = 3 i=1 C ⋆ i -̟ i .
Then, B conducts steps 4-6 as in the actual encryption algorithm. It is easy to see that this change does not modify A's view since

C ⋆ 0 still equals C ⋆ 0 = M β • X θ 1 1 • X θ 2
2 and the distributions of (z ⋆ , r ⋆ , u ⋆ ) and (Z ⋆ , R ⋆ , U ⋆ ) remain the same as in Game Game 5 : From this point forward, we make explicit use of the discrete logarithms α f = log g (f ) and α h = log g (h), which is allowed since we are done with the transition consisting in tampering with C ⋆ 3 in the challenge ciphertext. In Game 5 , we first change the treatment of ciphertexts

C = (SVK, C 0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 , σ
) involved in pre-challenge decryption and evaluation queries. Namely, B simply ignores the linearly homomorphic signatures contained these ciphertexts and returns

⊥ if C 3 = C 1/α f 1 • C 1/α h 2
. Otherwise, it responds as in earlier games. If we call F 5 the event that B rejects a ciphertext that would not have been rejected in Game • Adv DLIN (λ) + 1/p. The proof of Lemma 1 implies that, even if A chooses to expose the evaluation key SK h at the very beginning of the game, it should not be able to create valid-looking ill-formed ciphertexts before the challenge phase unless the DLIN assumption is false. This will help us prove that the scheme remains IND-CCA1 if SK h is revealed to the adversary when the game begins.

Game 6 : We now modify the treatment of post-challenge queries and introduce yet another event F 6 .

In this game, the challenger B halts and outputs a random bit in the event that the adversary A manages to query the partial decryption oracle or the evaluation oracle on a ciphertext In Game 7 , it is easy to see that A has no advantage whatsoever, so that Pr[S 7 ] = 1/2. Indeed, in the challenge phase, we have (C

C ⋄ = (SVK ⋄ , C ⋄ 0 , C ⋄ 1 , C ⋄ 2 , C ⋄ 3 , Z ⋄ , R ⋄ , U ⋄ , C ⋄ z , C ⋄ r , C ⋄ u , π ⋄ 1 , π ⋄ 2 , σ ⋄ ) where SVK ⋄ ∈ {SVK ⋆ , SVK † 1 , . . . , SVK † qe } and C ⋄ 3 = C ⋄ 1 1/α f • C ⋄ 2 1/α h although (C ⋄ z , C ⋄ r , C ⋄ u , π ⋄ 1 , π ⋄ 2 ) is a valid linearly homomorphic signature on the vector (C ⋄ 1 , C ⋄ 2 , C ⋄ 3 ). We
] ≤ 7 • (q e + 1) • (L + 1) • Adv DLIN (λ) • 1 -1 p -1 .
⋆ 1 , C ⋆ 2 , C ⋆ 3 ) = (f θ 1 , h θ 2 , g θ 1 +θ 2 +θ 3 ), where θ 1 , θ 2 , θ 3 ∈ R Z p . This implies that C ⋆ 0 can be written as C ⋆ 0 = M β • X θ 1 1 • X θ 2 2 • g θ 3 •
x 0 . The latter equality implies that, as long as x 0 ∈ Z p remains independent of A's view, so does the challenger's bit β ∈ {0, 1}.

To see why A does not learn anything about x 0 ∈ Z p , we first note that the homomorphic evaluation key SK h is independent of x 0 , so that homomorphic evaluation queries leak nothing about it. We also remark that, in Game 7 , decryption shares μi contain NIZK proofs that are simulated without using private key shares. Hence, as long as A does not corrupt more than t -1 servers, the only possible way to infer information about x 0 = P (0) is to trick the partial decryption oracle into accepting an invalid ciphertext. However, in Game 7 , all invalid ciphertexts are explicitly rejected.

We thus find the announced result

| Pr[S 1 ] - 1 2 | < (q e + 1) • Adv suf-ots (λ) + 3 2 • Adv DLIN (λ) + 7 • (q e + 1) • (L + 1) • Adv DLIN (λ) • 1 - 1 p -1 + 1 p . ⊓ ⊔ Lemma 1. In Game 5 , the probability of event F 5 is at most Pr[F 5 ] ≤ 1 2 • Adv DLIN (λ) + 1 p . Proof.
We show that, if event F 5 occurs with non-negligible probability in Game 5 , there exists an efficient algorithm B that solves a SDP instance (G z , G r , H z , H u ) with nearly the same probability. In turn, B implies a distinguisher for the DLIN assumption in G.

Algorithm B generates public key components are defined as in the actual scheme. In particular,

B sets G i = G z ϕ i G r ϑ i and H i = H z ϕ i H u ̟ i with ϕ i , ϑ i , ̟ i R ← Z p for i ∈ {1, 2
, 3}. Throughout the game, the reduction B answers A's decryption queries in the same way as in Game 5 . Moreover, since B has generated (sk rand , pk rand ) faithfully, it is able to consistently reveal the evaluation key SK h in case A decides to corrupt the evaluator. If event F 5 occurs with non-negligible probability, we know that, before the challenge phase, A must query the partial decryption or the homomorphic evaluation of a ciphertext C = (SVK, C

0 , C 1 , C 2 , C 3 , Z, R, U, C z , C r , C u , π 1 , π 2 , σ) such that (Z, R, U ) is a valid one-time linearly homomorphic signature on (C 1 , C 2 , C 3 ) although (C 1 , C 2 , C 3 )
is outside the span of (f, 1, g) and (1, h, g). When algorithm B detects this event (by observing that

C 3 = C 1/α f 1 C 1/α h 2
), it computes its own signature

(Z † , R † , U † ) = ( 3 i=1 C i -ϕ i , 3 i=1 C i -ϑ i , 3 i=1 C i -̟ i ) (15)
on (C 1 , C 2 , C 3 ). We claim that, with overwhelming probability,

(Z ‡ , R ‡ , U ‡ ) = Z Z † , R R † , U U †
is a non-trivial solution to the SDP instance since Z ‡ = 1 G with overwhelming probability. Indeed, we remark that the vector (ϕ 1 , ϕ 2 , ϕ 3 ) is independent of A's view before the challenge phase. Consequently, since (C 1 , C 2 , C 3 ) is linearly independent of (f, 1, g) and (1, h, g), the adversary A is only able to predict the value Z † of (15) with probability 1/p. Given that we also have the inequality Adv SDP (λ) ≤ 1 2 • Adv DLIN (λ), we thus find Pr[F 5 ] ≤ 1 2 • Adv DLIN (λ) + 1 p as claimed. ⊓ ⊔

In the transition from Game 5 to Game 6 , we could rely on the unbounded simulation-soundness of the underlying QA-NIZK proof to argue that fatal decryption or evaluation queries only occur with negligible probability. To do this, we would have to build a reduction algorithm that interacts with a simulation-soundness challenger for a given matrix ρ ∈ G 2×3 and simultaneously emulates A's challenger in the KH-CCA game. Since the reduction would not have the matrix A ∈ Z 2×3 p , it would have no way to detect fatal queries. Consequently, the reduction would have to guess this query, which would introduce an extra degradation factor in the reduction. Lemma 2. In Game 6 , the probability of event F 6 is at most

Pr[F 6 ] ≤ 7 • (q e + 1) • (L + 1) • Adv DLIN (λ) • 1 - 1 p -1 .
Proof. The key argument of the proof is that, conditionally on a certain desirable event, the evaluation oracle Eval(SK h , .) will never information-theoretically reveal its evaluation key SK h . Assuming that event F 6 occurs with non-negligible probability in Game 6 , we show that there exists a distinguisher for the DLIN assumption in G. To this end, we consider a subsequence of games starting with Game 6 and ending with Game 6.2 . For each j ∈ {0, 1, 2}, we define F 6.j as the counterpart of event F 6 in Game 6.j (note that F 6.j is efficiently detectable for each j). We first show that, as long as the DLIN assumption holds, if Pr[F 6 ] is non-negligible, so is Pr[F 6.2 ]. Game 6.0 : This game is identical to Game 6 but we modify the generation of pk rand when the public key is set up. Namely, the vectors (f 1 , f 2 , {f 3,i } L i=0 ) are chosen by setting

f 1 = (f 1 , 1 G , g) and f 2 = (1 G , f 2 , g) where f 1 , f 2 R ← G are chosen at random. As for {f 3,i } L i=0
, they are obtained as

f 3,0 = f ξ 0,1 1 • f ξ 0,2 2 • (1, 1, g) ξ 0,3 • (1, 1, g) µ•ζ-ρ 0 (16) f 3,i = f ξ i,1 1 • f ξ i,2 2 • (1, 1, g) ξ i,3 • (1, 1, g) -ρ i , i ∈ {1, . . . , L} with µ R ← {0, . . . , L}, ξ 0,1 , ξ 1,1 , . . . , ξ L,1 R ← Z p , ξ 0,2 , ξ 1,2 , . . . , ξ L,2 R ← Z p , ξ 0,3 , ξ 1,3 , . . . , ξ L,3 R ← Z p and ρ 0 , ρ 1 , . . . , ρ L R ← {0, . . . , ζ -1}, with ζ = 2(q e +1
) and where q e is the number of evaluation queries that increase the cardinality of D. Note that this change is only conceptual since the distribution of {f 3,i } L i=0 has not changed since Game 6 . We thus have Pr[F 6.0 ] = Pr[F 6 ]. Game 6.1 : This game is like Game 6.0 but we consider another event Good which causes the challenger B to abort and output a random bit if it does not occur. Let SVK † 1 , . . . , SVK † qe be the distinct one-time verification keys appearing in outputs of the Eval(SK h , .) oracle when the latter is invoked on a ciphertext in D. Let also SVK ⋆ be the verification key involved in the challenge ciphertext C ⋆ and let SVK ⋄ be the one involved in the first fatal query C ⋄ . We know that SVK ⋄ ∈ {SVK ⋆ , SVK † 1 , . . . , SVK † qe }. For each verification key SVK ∈ {0, 1} L , we consider the function J

(SVK) = µ • ζ -ρ 0 -L i=1 ρ i • SVK[i].
We also define Good to be the event that

J(SVK ⋄ ) = 0 ∧ J(SVK ⋆ ) = 0 ∧ j∈{ 1 ,...,qe} J(SVK † j ) = 0. ( 17
)
We remark that the random exponents ρ 0 , ρ 1 , . . . , ρ L are chosen independently of A's view: this means that the simulator could equivalently define {f 3,i } L i=0 first and only choose {ρ i } L i=0together with values {ξ 3,i } L i=0 explaining the {f 3,i } L i=0 -at the very end of the game, when SVK ⋆ , SVK † 1 , . . . , SVK † qe , SVK ⋄ have been defined. The same analysis as [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF] (using the simplifications of Bellare and Ristenpart [START_REF] Bellare | Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme[END_REF]) shows that Pr

[F 6.1 ∧ Good] ≥ Pr[F 6.0 ] 2 /(27 • (q e + 1) • (L + 1)).
This follows from the fact that, for any set of queries, a lower bound on the probability of event Good is 1/(2(q e + 1)(L + 1)). Indeed, from the known results [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF][START_REF] Hofheinz | Programmable Hash Functions and Their Applications[END_REF] on the programmability of Waters' hash function, we know that the probability, taken over the choice of (µ, ρ 0 , . . . , ρ L ), to meet the conditions (17) is at least 1/(2(q e + 1)(L + 1)). Game 6.2 : We modify again the way to compute pk rand in the generation of the public key. Namely, the vectors

f 1 = (f 1 , 1 G , g), f 2 = (1 G , f 2
, g) are chosen as before. However, instead of generating {f 3,i } L i=0 as in Game 6.1 , we set them as As a use case for our relatively sound QA-NIZK proofs, we can construct a new robust non-interactive threshold encryption scheme based on the DLIN assumption and prove it secure against chosenciphertext attacks in the adaptive corruption setting [START_REF] Canetti | Adaptive Security for Threshold Cryptosystems[END_REF][START_REF] Frankel | Adaptively-Secure Distributed Public-Key Systems[END_REF]. Threshold cryptosystems were initially suggested in [START_REF] Boyd | Digital Multisignatures[END_REF][START_REF] Desmedt | Society and Group Oriented Cryptography: A New Concept[END_REF][START_REF] Desmedt | Threshold Cryptosystems[END_REF]. In the static corruption setting, several non-interactive CCA-secure threshold systems have been described in the random oracle model [START_REF] Shoup | Securing Threshold Cryptosystems against Chosen Ciphertext Attack[END_REF][START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF] and in the standard model [START_REF] Boneh | Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles[END_REF][START_REF] Boyen | Direct Chosen Ciphertext Security from Identity-Based Techniques[END_REF][START_REF] Wee | Threshold and Revocation Cryptosystems via Extractable Hash Proofs[END_REF].

f 3,0 = f ξ 0,1 1 • f ξ 0,2 2 • (1, 1, g) µ•ζ-ρ 0 (18) f 3,i = f ξ i,1 1 • f ξ i,2 2 • (1, 1, g) -ρ i , i ∈
Adaptively secure distributed cryptosystems with chosen-ciphertext security were proposed in [START_REF] Jarecki | Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures[END_REF][START_REF] Abe | Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography[END_REF] but they require some interaction during the decryption process. Non-interactive solutions were put forth in [START_REF] Libert | Adaptively Secure Non-Interactive Threshold Cryptosystems[END_REF][START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF] but, as we will see, they are less efficient than the solution proposed here.

Consider the DLIN-based cryptosystem based on 1-universal hash proof systems where the ci-

phertext (C 1 , C 2 , C 3 , C 0 ) = (f θ 1 , h θ 2 , g θ 1 +θ 2 , M • X θ 1 1 • X θ 2 2 ) is decrypted as M = C 0 • C -x 1 1 C -x 2 2 C -x 0 3
, where (X 1 , X 2 ) = (f x 1 g y , h x 2 g x 0 ) is the public key and (x 1 , x 2 , x 0 ) is the private key. In [START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF], chosenciphertext security was achieved using a publicly verifiable one-time simulation-sound proof of wellformedness for (C 1 , C 2 , C 3 ). In the security proof, the one-time simulation-soundness property guarantees that the adversary is unable to trick the decryption oracle into returning the decryption of an invalid ciphertext, by generating a fake proof for an invalid triple (C 1 , C 2 , C 3 ). For this reason, the specific private key (x 1 , x 2 , x 0 ) used by the reduction remains perfectly hidden. Consequently, if the challenge ciphertext is computed by choosing a random tuple (C 1 , C 2 , C 3 ) ∈ R G 3 and computing

C 0 = M • C 1 x 1 • C 2 x 2 • C 3
x 0 , the plaintext M is independent of the adversary's view. To prove adaptive security in the threshold setting, [START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF] took advantage of the fact that the private key (more precisely, all private key shares) is known to the reduction at all times in the Cramer-Shoup paradigm.

A similar approach was taken in6 [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], where a different method was used to achieve a form of one-time simulation-soundness. In combination with relatively sound proofs [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], the techniques of Jutla and Roy [START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] reduce the size of ciphertexts to 9 group elements under the DLIN assumption.

Here, as already suggested in [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF], we obtain shorter ciphertexts by using linearly homomorphic signatures. We include in the public key the verification key of a one-time linearly homomorphic SPS for n = 3 as well as signatures on (f, 1 G , g) and (1 G , h, g). This allows publicly deriving a homomorphic signature (z, r, u) on the vector (C 1 , C 2 , C 3 ) = (f θ 1 , h θ 2 , g θ 1 +θ 2 ) and each ciphertext consists of (z, r, u, C 0 , C 1 , C 2 , C 3 ). In the security proof, the signature (z, r, u) serves as evidence that (C 1 , C 2 , C 3 ) has the right form at each pre-challenge decryption query: in order to generate a proof for a false statement, the adversary has to break the security of the homomorphic signature, by deriving a signature on a vector (C 1 , C 2 , C 3 ) outside the span of (f, 1, g) and (1, h, g).

While this technique does provide IND-CCA1 security, the scheme remains malleable and thus vulnerable to post-challenge decryption queries. This is where the relatively sound proof system of Section 4 comes into play. By using (C 0 , C 1 , C 2 , C 3 ) as a label in the relatively sound proof that (C 1 , C 2 , C 3 ) lives in span((f, 1, g), (1, h, g)), we can make sure that, with all but negligible probability, the reduction will never accept a proof for a malformed (C 1 , C 2 , C 3 ) after the challenge phase without breaking the DLIN assumption. The key idea of the techniques of [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF] is to guarantee that the adversary will not be able to send a decryption query for which the private verifier and the public verifier disagree on (C 1 , C 2 , C 3 ).

I.1 Construction

In the threshold setting, the construction can be seen as a DLIN-based version of the Cramer-Shoup encryption scheme [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF] (which is identical to the scheme in [START_REF] Shacham | A Cramer-Shoup encryption scheme from the linear assumption and from progressively weaker linear variants[END_REF]), where the ciphertext components (C 1 , C 2 , C 3 ) and the designated verifier proof C 4 are additionally signed using a homomorphic signature. The scheme goes as follows.

Keygen(λ, t, N ): choose bilinear groups (G, G T ) of prime order p > 2 λ and do the following.

1. Choose g, f, h R ← G. 2. Choose random x 0 , x 1 , x 2 R ← Z p , y 0 , y 1 , y 2 R ← Z p and w 0 , w 1 , w 2 R ← Z p in order to compute X 1 = f x 1 g x 0 , X 2 = h x 2 g x 0 , Y 1 = f y 1 g y 0 , Y 2 = h y 2 g y 0 and W 1 = f w 1 g w 0 , W 2 = h w 2 g w 0 .

3. Generate a Groth-Sahai CRS (f 1 , f 2 , f 3 ) to be used for proving the validity of decryption shares. Namely, choose f 1 , f 2 R ← G as well as φ 1 , φ 2 R ← Z p and define vectors

f 1 = (f 1 , 1, g), f 2 = (1, f 2 , g) f 3 = f φ 1 1 • f φ 2 2 • (1, 1, g).
4. Choose random polynomials P 1 [Z], P 2 [Z], P 0 [Z] ∈ Z p [Z] of degree t -1 such that P 1 (0) = x 1 , P 2 (0) = x 2 and P 0 (0) = x 0 . Set X i,1 = f P 1 (i) g P 0 (i) and X i,2 = h P 2 (i) g P 0 (i) for i = 1 to N . 5. Choose a collision-resistant hash function H : {0, 1} * → Z p . 6. Generate a key pair for the one-time linearly homomorphic signature of Section 2.5 with n = 7.

Let g z , g r , h z , h u , {(g i , h i )} 7 i=1 be the public key and let {(χ i , γ i , δ i )} 7 i=1 be the corresponding private key. 7. Generate one-time homomorphic signatures {(Z j , R j , U j )} 4 j=1 on the independent vectors 8. Define decryption key shares SK = (SK 1 , . . . , SK N ) as SK i = (P 1 (i), P 2 (i), P 0 (i)) ∈ Z 3 p for each i ∈ {1, . . . , N }. The vector VK = (V K 1 , . . . , V K N ) of verification keys is defined as V K i = (X i,1 , X i,2 ) ∈ G 2 for each i ∈ {1, . . . , N }. The public key is defined to be

P K = g, f 1 , f 2 , f 3 , X 1 , X 2 , Y 1 , Y 2 , W 1 , W 2 , g z , g r , h z , h u , {g i , h i } 7
i=1 , {(Z j , R j , U j )} 4 j=1 , H .

Encrypt(M, P K): to encrypt a message M ∈ G, conduct the following steps.

1. Choose θ 1 , θ 2 R ← Z p and compute

C 0 = M • X θ 1 1 • X θ 2 2 , C 1 = f θ 1 , C 2 = h θ 2 , C 3 = g θ 1 +θ 2 C 4 = (W α 1 Y 1 ) θ 1 • (W α 2 Y 2 ) θ 2 ,
where α = H(C 0 , C 1 , C 2 , C 3 ) ∈ Z p . 2. Construct a linearly homomorphic signature (Z, R, U ) on (C 1 , C 2 , C 3 , C 4 , C α 1 , C α 2 , C α 3 ) ∈ G 7 . Namely, compute

Z = Z θ 1 1 • Z θ 2 2 • Z θ 1 •α 3 • Z θ 2 •α 4 , R = R θ 1 1 • R θ 2 2 • R θ 1 •α 3 • R θ 2 •α 4 , U = U θ 1 1 • U θ 2 2 • U θ 1 •α 3 • U θ 2 •α
not in span(h 1 , h 2 , h 3 , h 4 ). When B detects this event, it defines (C 5 , C 6 , C 7 ) = (C 1 α , C 2 α , C 3 α ) and computes its own signature (Z † , R † , U † ) = (

7 i=1 C i -χ i , 7 i=1 C i -γ i , 7 i=1 C i -δ i ) (26)
on (C 1 , C 2 , C 3 , C 4 , C 5 , C 6 , C 7 ). We claim that, with overwhelming probability,

(Z ‡ , R ‡ , U ‡ ) = Z Z † , R R † , U U †
is a non-trivial solution to the SDP instance since Z ‡ = 1 G with all but negligible probability.

To see this, we first note that the vector (χ 1 , . . . , χ 7 ) is independent of A's view before the challenge phase. Hence, since (C 1 , C 2 , C 3 , C 4 , C 5 , C 6 , C 7 ) is linearly independent of (h 1 , h 2 , h 3 , h 4 ), the adversary A can only predict Z † (as it is computed in ( 26)) with negligible probability 1/p. The probability Pr[F 6 ] can thus be bounded as Pr[F 6 ] ≤ Adv SDP B (λ) + 1 p .

⊓ ⊔

In the proof of the above theorem, the relative simulation-soundness property of the proof system is notably used in the transition from Game 8 to Game 9 . In order to obtain a tighter reduction, we chose not to rely on this property in a modular way. In the modular approach, we would have to build an algorithm B rs that contradicts this property using an adversary for which event F 9 occurs with non-negligible probability. This algorithm B rs would have to interact with the relative soundness challenger for a given language ρ ∈ G 2×3 for which B rs does not have the underlying matrix A ∈ Z 2×3 p of discrete logarithms. For this reason, B rs would not be able to efficiently detect when F 9 occurs. To break the relative soundness property, B rs would have to guess the decryption query for which this event occurs, which is only possible with probability 1/q. In the exact security result [START_REF] Desmedt | Threshold Cryptosystems[END_REF], we would thus lose a multiplicative factor of O(q).

  it sets D ← D ∪ {C}. -Reveal query: at any time, A may also decide to corrupt the evaluator by invoking the RevHK oracle on a unique occasion. The oracle responds by returning SK h . -Decryption query: A can also invoke the partial decryption oracle on arbitrary ciphertexts C and indexes i ∈ {1, . . . , n}. If Ciphertext-Verify(P K, C) = 0 or if C ∈ D, the oracle returns ⊥. Otherwise, the oracle returns the decryption share µ i ← Share-Decrypt(P K, i, SK d,i , C).

3 ,

 3 we have | Pr[S 4 ] -Pr[S 3 ]| ≤ Pr[F 4 ]. Since Pr[S 4 ] = 0 by construction, we are left with the task of bounding Pr[F 4 ].

2 .

 2 We thus have Pr[S 3 ] = Pr[S 2 ].

Game 4 : 3 R

 43 This game is identical to Game 3 with a new modification in the challenge ciphertext. Namely, instead of settingC ⋆ 3 = g θ 1 +θ 2 , where θ 1 = log f (C ⋆ 1 ) and θ 2 = log h (C ⋆ 2 ), we choose it as C ⋆ ← G.At the third step of the encryption algorithm, the linearly homomorphic signature (z ⋆ , r ⋆ , u ⋆ ) is computed according to (14), as previously. Under the DLIN assumption in G, this modification should not significantly alter A's behavior. In particular, we have |Pr[S 4 ]-Pr[S 3 ]| ≤ Adv DLIN (λ).

4 ,

 4 Game 5 and Game 4 are clearly identical until F 5 occurs, so that | Pr[S 5 ] -Pr[S 4 ]| ≤ Pr[F 5 ]. At the same time, Lemma 1 shows that Pr[F 5 ] ≤ 1 2

Game 7 :

 7 We now modify the partial decryption oracle and replace the non-interactive proofs contained in decryption shares μi by simulated NIZK proofs. This entails to turn (f 1 , f 2 , f 3 ) into a perfectly hiding Groth-Sahai CRS (where f 3 is in the span of f 1 and f 2 ) and non-interactive proofs for multi-exponentiation equations are simulated using the trapdoor of the simulated CRS. Under the DLIN assumption, this change is not noticeable to A and we have | Pr[S 7 ]-Pr[S 6 ]| ≤ Adv DLIN (λ).

2 • 1 p- 1 inI

 211 {1, . . . , L} be bounded as Pr[F 6.1 ∧ Good] ≤ 3 Adv DLIN (λ) • 1 -Game 6.1 . This eventually yields the stated result Pr[F 6 ] ≤ 7 • (q e + 1) • (L + 1) • Adv DLIN (λ) • 1 -More Efficient Adaptively Secure CCA2-Secure Threshold Cryptosystems from the DLIN and k-Linear Assumptions

h 1 = 7 h 3 = ( 1 , 1 , 1 ,

 173111 (f, 1, g, Y 1 , 1, 1, 1) ∈ G 7 , h 2 = (1, h, g, Y 2 , 1, 1, 1) ∈ G W 1 , f, 1, g) ∈ G 7 , h 4 = (1, 1, 1, W 2 , 1, h, g) ∈ G 7 .

4 3 .

 3 Output the ciphertextC = (C 0 , C 1 , C 2 , C 3 , C 4 , Z, R, U ) ∈ G 8

Table 1 .

 1 Comparison between proof systems for linear subspaces

	Proof systems	CRS size ♦ *	Proof length ♦	# of pairings †	Soundness
				at verification	property
	Groth-Sahai [33]	6	3t + 2n	3n(t + 3)	perfect
	Jutla-Roy [38]	4t(n -t) + 3	2(n -t)	2(n-t)(t+2)	computational
	Jutla-Roy RSS [38] + [37]	4t(n + 1 -t) + 3	2(n + 1 -t) + 1	2(n + 1 -t)(t + 2)	computational
	Groth-Sahai USS [15]	18	6t + 2n + 52 ‡	O(tn)	computational
	Our basic QA-NIZK proofs	2n + 3t + 4	3	2n + 2	computational
	Our RSS QA-NIZK proofs	4n + 8t + 6	4	2n + 6	computational
	Our USS QA-NIZK proofs	2n + 3t + 3L + 10	20 ‡	2n + 30	computational

n: number of equations; t: number of variables; L: length of a hashed one-time verification key ♦ These sizes are measured in terms of number of group elements.

  say that C ⋄ is a fatal query in this case. Since Game 6 is identical to Game 5 until event F 6 occurs, we have| Pr[S 6 ] -Pr[S 5 ]| ≤ Pr[F 6 ]. Lemma 2 demonstrates that the DLIN assumption can be broken in the group G if event F 6 occurs with non-negligible probability.

	More precisely, Lemma 2 shows that Pr[F 6

Note that these results do not contradict the impossibility results of Gentry and Wichs[START_REF] Gentry | Separating succinct non-interactive arguments from all falsifiable assumptions[END_REF] because, in the quasiadaptive setting, the CRS may hide a trapdoor that allows recognizing elements of the language. The proof of[START_REF] Gentry | Separating succinct non-interactive arguments from all falsifiable assumptions[END_REF] applies to reductions that cannot efficiently detect when the adversary breaks the soundness property.

Although it was not mentioned in[START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], relatively sound proofs can be used to acquire CCA2 security in the threshold setting as well, as will be emphasized later on.

Note that the techniques of Lewko[START_REF] Lewko | Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting[END_REF] can be applied to the scheme of[START_REF] Libert | Adaptively Secure Non-Interactive Threshold Cryptosystems[END_REF] to get a DLIN-based system where ciphertexts contain 7 group elements and a one-time key pair (SVK, σ). However, the reduction involves a degradation factor proportional to the number of decryption queries.

⋆ This work was done while this author was at Technicolor (France). ⋆⋆ This author was supported by the CAMUS Walloon Region Project.

which amounts to setting ξ 0,3 = ξ 1,3 = . . . = ξ L,3 = 0. Clearly, {f 3,i } L i=0 are no longer uniform in the span of f 1 , f 2 , (1, 1, g) . Still, this change should have no noticeable effect on A if the DLIN assumption holds in G. Concretely, if a fatal decryption/evaluation query occurs with substantially different probabilities in Game 6.2 and Game 6.1 , we can construct a DLIN distinguisher B DLIN in the group G (recall that the reduction can detect fatal queries using α f = log g (f ) and α h = log g (h)). This distinguisher uses the random self-reducibility of DLIN to construct many independentlooking instances from the same distribution out of a given instance. For this reason, we can write | Pr[F 6.2 ∧ Good] -Pr[F 6.1 ∧ Good]| ≤ Adv B DLIN (λ).

In Game 6.2 , we show that an occurrence of event F 6.2 implies an algorithm B solving a given SDP instance (g z , g r , h z , h u ) with non-negligible probability, which a fortiori breaks the DLIN assumption in G as the latter is implied by SDP.

By hypothesis, we know that the adversary A somehow manages to produce a fatal decryption/evaluation query on a ciphertext C ⋄ for which (C ⋄ 1 , C ⋄ 2 , C ⋄ 3 ) is outside the span of (f, 1 G , g) and ( 1 15 satisfies the verification equations. At this point, if the event Good introduced in Game 6.1 occurs, we must have J(SVK ⋄ ) = 0, which implies that

lies in span(f 1 , f 2 ). Consequently, C ⋄ z , C ⋄ r and C ⋄ u are necessarily perfectly binding and extractable commitments. Using (log g (f 1 ), log g (f 2 )), B can thus extract the committed group elements (z

are perfectly sound Groth-Sahai proofs, the extracted elements (z ⋄ , r ⋄ , u ⋄ ) necessarily satisfy

Having extracted (z ⋄ , r ⋄ , u ⋄ ), B also computes

so that (z † , r † , u † ) also satisfies [START_REF] Coron | Practical Multilinear Maps over the Integers[END_REF]. Since (z † , r † , u † ) and (z ⋄ , r ⋄ , u ⋄ ) both satisfy [START_REF] Coron | Practical Multilinear Maps over the Integers[END_REF], the triple

To conclude the proof, we argue that z ‡ = 1 G with overwhelming probability.

To do this, we observe that, if the event Good defined in Game 6.1 actually comes about, then B never leaks any more information about (χ 1 , χ 2 , χ 3 ) than A can infer by just observing {(z j , r j , u j )} 2 j=1 in the public key. Indeed, in this case we have J(SVK ⋆ ) = 0 and J(SVK † j ) = 0 for each j ∈ {1, . . . , q e }. This means that, in the challenge ciphertext and all its homomorphic evaluations, the proofs (π 1 , π 2 ) are perfectly WI as they are generated for a perfectly hiding Groth-Sahai CRS. For these ciphertexts, the built-in homomorphic signatures (C z , C r , C u , π 1 , π 2 ) leak nothing about the specific vector (χ 1 , χ 2 , χ 3 ) ∈ Z 3 p used by B. As a consequence, we can apply the same arguments as in the proof of Lemma 1 when it comes to argue that z † = z ⋄ with probability 1 -1/p. We thus find

.

In turn, B implies a PPT distinguisher B DLIN ′ for the DLIN assumption such that we have the inequality Pr[F

Share-Decrypt(P K, i, SK i , C): on inputs SK i = (P 1 (i), P 2 (i), P 0 (i)) ∈ Z 3 p and C, return (i, ⊥) in the event that Ciphertext-Verify P K, C = 0. Otherwise, compute μi = ν i , C P 1 , C P 2 , C P , π µ i which consists of a partial decryption

, commitments C P 1 , C P 2 , C P 0 to exponents P 1 (i), P 2 (i), P 0 (i) ∈ Z p and a proof π ν i that these satisfy the equations

The commitments C P 1 , C P 2 , C P 0 and the proof π ν i are generated using the CRS f = (f 1 , f 2 , f 3 ).

Share-Verify

In any other situation, return 0.

If each element has a 256-bit representation on BN curves [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF] at the 128-bit security level, the ciphertext overhead amounts to 1792 bits. The DLIN-based scheme of [START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF] has a ciphertext overhead comprised of 14 group elements and a one-time signature with its verification key (or 4864 bits using Groth's one-time signature [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF]). The results of Escala et al. [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF] reduce this overhead to 3328 bits. The recent techniques of Jutla and Roy [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF][START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF] -which also work in the threshold setting although it was not explicitly stated in [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF] -lead to ciphertexts comprised of 9 group elements under the DLIN assumption and 3k + 3 under the k-linear assumption. Under DLIN, we thus further compress ciphertexts by 11% while relying on the same assumption and retaining tight security 7 . Under the k-linear assumption, our improvement becomes more important as the ciphertext reduces to 2k + 4 group elements. Specifically, we need k + 1 elements for the homomorphic signature of Appendix D, another k + 1 elements to contain the k-linear instance, one element for the Cramer-Shoup-like proof π 0 and one element to carry the plaintext. This allows saving k -1 group elements with respect to the techniques of [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF][START_REF] Jutla | Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces[END_REF].

We believe this result to be of importance as these schemes can potentially serve as building blocks for protocols in the multi-linear setting [START_REF] Garg | Candidate Multilinear Maps from Ideal Lattices[END_REF][START_REF] Coron | Practical Multilinear Maps over the Integers[END_REF]. Indeed, the (k -1)-linear problem is easy in groups equipped with a k-linear map (as shown in, e.g., [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF]) but we can hope for instantiations where the k-linear assumption holds, as seems to be the case in [START_REF] Coron | Practical Multilinear Maps over the Integers[END_REF].

From a computational standpoint, the validity of a ciphertext only requires to compute a product of 7 pairings. Under the the DLIN assumption, the framework of [START_REF] Libert | Non-Interactive CCA2-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions[END_REF] requires a product of 12 pairings in the ciphertext verification algorithm.

I.2 Security

We prove security in the sense of a definition which is identical to Definition 1 with the difference that there is no evaluation key SK h , no evaluation oracle and no RevHK oracle.

As in the scheme of [START_REF] Jutla | Relatively-Sound NIZKs and Password-Based Key-Exchange[END_REF], the security proof appeals to the private verification algorithm while the scheme itself only uses the public verification algorithm.

While it would be possible to rely on the relative zero-knowledge and relative soundness properties of the proof system in a modular way, we obtain a better exact security via a direct analysis.

Theorem 4. The above threshold cryptosystem is IND-CCA secure against adaptive corruptions assuming that: (i) H is collision-resistant; (ii) The DLIN assumption holds in G. More precisely, the advantage of any PPT adversary A is at most

where q is the number of decryption queries and the first term of the right-hand-side member accounts for the maximal advantage of any PPT collision-finding algorithm for H.

Proof. The proof uses of a sequence of games starting with the real attack game and ending with a game where the adversary A has no advantage. For each i, S i stands for the event that the challenger B outputs 1 at the end of Game i .

Game 1 : is the real attack game. In details, the adversary is given the public key P K and the set of verification keys VK = (V K 1 , . . . , V K N ). At each corruption query i ∈ {1, . . . , n}, the challenger B reveals the queried private key share SK i = (P 1 (i), P 2 (i), P 0 (i)). At each decryption query, B faithfully runs the real shared decryption algorithm. In the challenge phase, the adversary A chooses messages M 0 , M 1 ∈ G and obtains

which is an encryption of M β , for some random coin β R ← {0, 1} flipped by B. We can assume w.l.o.g. that (C ⋆ 1 , C ⋆ 2 , C ⋆ 3 ) are computed at the beginning of the game as they do not depend on M β . In the second phase, A makes more adaptive queries under the restriction of not asking for a partial decryption of C ⋆ or for more than t -1 private key shares throughout the entire game. Eventually, A halts and outputs β ′ . At this point, B outputs 1 if β = β ′ and 0 otherwise.

Game 2 : This game is like Game 1 except that the challenger B halts and outputs a random bit in the event that, before the challenger phase, A queries the partial decryption oracle on a ciphertext

3 ) are invisible to A until the challenge phase, this event can only occur with probability q/p, so that

Game 3 : We introduce another failure event F 3 and let B halt and output a random bit if this event occurs. We define F 3 as the event that A makes a decryption query involving a valid

). We see that Game 3 and Game 2 are identical until event F 3 occurs, which would contradict the collision-resistance of H. We thus have |Pr

3 ), we will henceforth assume that α = α ⋆ for each decryption query

Game 4 : In this game, we modify the decryption oracle and reject all post-challenge decryption queries

. Clearly Game 4 is identical to Game 3 until B rejects a ciphertext that would not have been rejected in Game 3 .

If we call the latter event F 4 , we find that

, which in turn breaks the SDP assumption by the specific property of the linearly homomorphic signature (see Section 2.5). It comes that Pr[F 4 ] ≤ Adv SDP (B).

Game 5 : We modify the generation of

. Likewise, instead of using the encryption exponents (θ 1 , θ 2 ) to derive a one-time linearly homomorphic signature (Z ⋆ , R ⋆ , U ⋆ ) from the public key, the challenger B uses {(χ i , γ i , δ i )} 7 i=1 and computes

where

2 and the distribution of (C ⋆ 4 , Z ⋆ , R ⋆ , U ⋆ ) has not changed either. We thus have Pr[S 5 ] = Pr[S 4 ]. Game 6 : Here, we modify the decryption oracle and make use of the exponents (y 0 , y 1 , y 2 , w 0 , w 1 , w 2 ) that were chosen by B during the key generation phase. Namely, the challenger B does not only reject all ciphertexts

3 ) but also rejects those for which

. We raise a failure event F 6 , which causes B to halt and output a random bit if it occurs. This event F 6 is defined to be the event that the adversary A queries the decryption oracle on a ciphertext that gets rejected in Game 6 and would not have been rejected in Game 5 . Since Game 6 is identical to Game 5 until F 6 occurs, we have

At the same time, Lemma 3 shows that Pr[F 6 ] ≤ Adv SDP (λ) + 1 p . We remark that a side-effect of this modified decryption oracle is that it now rejects all post-challenge decryption queries

Since F 6 is always efficiently detectable by the challenger B, we can build an efficient DLIN distinguisher if the probability of event F 6 increases when C ⋆ 3 is tampered with in the challenge ciphertext as in the next game.

Game 7 : This game is identical to Game 6 with one modification in the challenge ciphertext. Instead of setting Game 9 : In this game, we modify again the decryption oracle and make use of the discrete logarithms α f = log g (f ) and α h = log g (h). Since we are done with the transition consisting in replacing C ⋆ 3 by a random element, we are free to use (α f , α h ) from this point forward. We thus introduce a modification in the treatment of decryption queries C = (C 0 , C 1 , C 2 , C 3 , C 4 , Z, R, U ). This, B rejects all ciphertexts C such that

. Otherwise, it answers as in Game 8 . If we define F 9 to be the event that B rejects a ciphertext which would not have been rejected in Game 8 , we see that Game The same arguments as in the proof of Cramer and Shoup show that Pr[F 9 ] ≤ q/(pq). More precisely, after i decryption queries, the adversary is left with pi equally likely candidates for the value of C 4 that would have been accepted by the private ciphertext validation algorithm.

The probability that the i-th decryption query satisfies the test given that the first i -1 queries have failed it is thus at most i/(pi).

In Game 9 , it is easy to see that A has no advantage whatsoever and we have Pr[S 9 ] = 1/2. Indeed, in the challenge phase, we have (C

The latter equality implies that, as long as x 0 ∈ Z p is independent of A's view, so is the bit β ∈ {0, 1}.

We also note that, in Game 9 , decryption shares μi contain NIZK proofs that are simulated without using private key shares and thus leak no information about these. It comes that, as long as A does not corrupt more than t -1 servers, the only possible way to infer information about x 0 = P (0) is to make decryption queries on invalid ciphertexts (i.e., for which (C 1 , C 2 , C 3 ) lies outside the span of f and h).

We thus find

Since any algorithm solving SDP immediately provides a DLIN distinguisher, we also have the inequality Adv SDP (λ) ≤ 1 2 Adv DLIN (λ), which yields

and the claimed result follows. ⊓ ⊔ Lemma 3. In Game 6 , the probability of event F 6 is at most Pr[F 6 ] ≤ Adv SDP (λ) + 1 p .

Proof. We show that, if event F 6 occurs with non-negligible probability ε in Game 6 , there exists an efficient algorithm B that solves a SDP instance (g z , g r , h z , h u ) with about the same probability. To this end, we first remark that F 6 can only occur for a decryption query (C 0 , C • C y 0 +αw 0 3 and the rejection rule of Game 6 does not apply. Using the technique of [START_REF] Libert | Linearly Homomorphic Structure-Preserving Signatures and their Applications[END_REF][Theorem 1], we show that event F 6 implies an algorithm solving the given SDP instance with nearly the same probability. Algorithm B begins by setting up g i = g z χ i g r γ i

and h i = h z χ i h u δ i , with χ i , γ i , δ i R ← Z p for i ∈ {1, . . . , 7}. Other public key components are generated as in the real scheme and the public key is given to the adversary.

Throughout the game, the reduction B answers A's decryption queries in the same way as in Game , which implies that the vector is