Julien Devevey

Benoît Libert

Khoa Nguyen

Thomas Peters

Non-Interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without Pairings

Keywords: Threshold cryptography, adaptive security, non-interactive schemes, standard model, chosen-ciphertext security, DCR, LWE

We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.

Introduction

Threshold cryptography [START_REF] Desmedt | Society and group oriented cryptography: A new concept[END_REF][START_REF] Desmedt | Threshold cryptosystems[END_REF][START_REF] Boyd | Digital multisignatures[END_REF][START_REF] Santis | How to share a function securely[END_REF] avoids a single point of failure by splitting the secret key into > 1 shares and handing them over to different servers. This is done in such a way that any set of size at least t ≤ servers can jointly compute private key operations whereas no subset of up to t -1 servers can similarly compute or otherwise compromise the cryptosystem's security.

Chosen-ciphertext (IND-CCA) security [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF][START_REF] Rackoff | Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack[END_REF] is recognized as the de facto security notion for public-key encryption. Designing threshold IND-CCA2-secure cryptosystems is non-trivial, and particularly challenging when we aim to combine all desirable properties. In this paper, we are interested in CCA2-secure threshold public-key encryption schemes that are simultaneously: secure under adaptive corruptions (namely, where adversaries can choose whom to corrupt based on the previously obtained information during the protocol), and noninteractive. By "non-interactive" we mean that decryption servers do not communicate with one another in a time consuming protocol, but rather only send a single message to a combiner which gathers these partial decryptions to produce the cleartext. In addition, our goal is to prove security in the standard model (i.e., without the random oracle idealization) and without assuming reliable erasures on behalf of decryption servers. Finally, we also wish to achieve robustness and prevent corrupted servers from hindering the decryption process.

We re-emphasize that we aim at simple non-interactive client/servers protocols where, in order to decrypt a message, a client sends a ciphertext to a decryption server that responds with a decryption share (along with a non-interactive proof of share correctness) without having to talk to other servers. As advocated in [START_REF] Shoup | Securing threshold cryptosystems against chosen ciphertext attack[END_REF], such non-interactive protocols are attractive as they require no synchronization among servers, and do not rely on network latency guarantees.

To our knowledge, all solutions that combine all the aforementioned properties [START_REF] Libert | Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF][START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF] rely on bilinear maps. In this paper, we consider the problem of schemes realizing the above under other well-established and non-pairing-related standard assumptions.

Non-Interactive Schemes. When we aim to avoid interaction during the decryption process in the design of threshold CCA2 schemes, the common stumbling block is that decryption servers often need to know whether an incoming ciphertext is valid or not before releasing their partial decryption result. The early solutions to this problem involved non-interactive zero-knowledge (NIZK) proofs [START_REF] Shoup | Securing threshold cryptosystems against chosen ciphertext attack[END_REF][START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF] of ciphertext well-formedness in the random oracle model. In the standard model, Canetti and Goldwasser [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen-ciphertext attacks[END_REF] thresholdized the Cramer-Shoup cryptosystem [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF] by means of a randomized decryption protocol. Their approach involves shared randomizers in order to prevent partial decryptions on invalid ciphertexts from leaking information on the secret key shares. To remove interaction from the process, shareholders have to store a large number of pre-shared randomizers, which entails a prohibitively large storage cost. Cramer, Damgård and Ishai suggested [START_REF] Cramer | Share conversion, pseudorandom secretsharing and applications to secure computation[END_REF] a non-interactive distributed randomization technique but it only supports a small number of servers. Boneh et al. [START_REF] Boneh | Key-homomorphic PRFs and their applications[END_REF] observed that, at least for static adversaries, these limitations can be avoided if shared randomizers are generated using non-interactive distributed pseudorandom functions.

In the static corruption setting, generic or partially generic CCA2-secure threshold constructions were proposed in [START_REF] Dodis | Chosen-ciphertext security of multiple encryption[END_REF][START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF][START_REF] Wee | Threshold and revocation cryptosystems via extractable hash proofs[END_REF][START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF]. Boneh, Boyen and Halevi [START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF] notably came up with the first fully non-interactive realization in the standard model. Their scheme crucially relies on pairings to publicly check the validity of ciphertexts, which drastically simplifies the problem of proving security in the threshold setting. Bilinear maps also provide robustness essentially for free, by making the validity of decryption shares publicly verifiable. Similar appli-cations of the Canetti-Halevi-Katz [START_REF] Canetti | Chosen-ciphertext security from identity-based encryption[END_REF] methodology to threshold cryptography were considered in [START_REF] Boyen | Direct chosen-ciphertext security from identitybased techniques[END_REF][START_REF] Kiltz | Chosen-ciphertext security from tag-based encryption[END_REF]. Wee [START_REF] Wee | Threshold and revocation cryptosystems via extractable hash proofs[END_REF] subsequently laid out a framework for the design of non-interactive threshold signatures and CCA2-secure cryptosystems in the random oracle model under static corruptions.

More recently, Boneh et al. [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF] introduced a tool, called universal thresholdizer, that essentially turns any non-interactive cryptographic scheme (such as public-key encryption, digital signatures or pseudorandom functions) into a threshold variant of the same primitive. Their compiler builds on fully homomorphic encryption (FHE) [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] and notably implies CCA2-secure non-interactive threshold encryption schemes in the static corruption setting.

Adaptive Corruptions. Most threshold cryptosystems (e.g., [START_REF] Shoup | Securing threshold cryptosystems against chosen ciphertext attack[END_REF][START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen-ciphertext attacks[END_REF][START_REF] Dodis | Chosen-ciphertext security of multiple encryption[END_REF][START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF][START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF]) have been analyzed in a static corruption model, where the adversary commits to the set of corrupted servers before the protocol execution. Unfortunately, security under static corruptions does not imply security against more realistic adversaries that can adaptively corrupt servers based on previously and dynamically collected information. Canetti et al. [START_REF] Canetti | Adaptive security for threshold cryptosystems[END_REF] put forth adaptively secure key generation protocols for the distributed generation of discrete-log-based keys as well as adaptively secure threshold DSA signatures. Frankel, MacKenzie and Yung [START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Frankel | Optimal-resilience proactive public-key cryptosystems[END_REF] independently showed different methods to achieve adaptive security. Their techniques were extended [START_REF] Almansa | Simplified threshold RSA with adaptive and proactive security[END_REF] to obtain proactive [START_REF] Ostrovsky | How to withstand mobile virus attacks[END_REF] RSA signatures.

The constructions of [START_REF] Canetti | Adaptive security for threshold cryptosystems[END_REF][START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Frankel | Optimal-resilience proactive public-key cryptosystems[END_REF] inherently require interaction as they rely on the so-called "single inconsistent player" (SIP) technique. The latter consists of transforming a t-out-of-secret sharing into an additive t-out-of-t sharing of the same secret. In the latter case, only one server (which is randomly chosen ahead of time by the simulator among the severs) has an inconsistent internal state that causes the simulation to fail if it gets corrupted. Since this occurs with probability ≈ 1/2, the stuck simulator can rewind the adversary and use different random coins with the hope of avoiding a new corruption of the inconsistent player. The threshold schemes of [START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Frankel | Optimal-resilience proactive public-key cryptosystems[END_REF] thus proceed by switching from a (t, ) polynomial secret sharing to a (t, t) additive secret sharing by first choosing a set of t participants. If a single participant fails to provide a valid contribution, the whole protocol must restart from scratch. 6 Jarecki and Lysyanskaya [START_REF] Jarecki | Adaptively secure threshold cryptography: Introducing concurrency, removing erasures[END_REF] extended the SIP technique to eliminate the need for erasures and described an adaptively secure variant of the Canetti-Goldwasser scheme [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen-ciphertext attacks[END_REF]. Abe and Fehr [START_REF] Abe | Adaptively secure Feldman VSS and applications to universally-composable threshold cryptography[END_REF] removed zero-knowledge proofs from the Jarecki-Lysyanskaya construction and proved it secure in (a variant of) the universal composability framework. However, [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] both require interaction during the decryption protocol. As in previous threshold variants of Cramer-Shoup, it requires either a large amount of synchronized interaction or a storage of a large number (i.e., proportional to the total number of decryption queries over the lifetime of the system) of preshared secrets. As argued in [START_REF] Shoup | Securing threshold cryptosystems against chosen ciphertext attack[END_REF], none of the schemes in [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen-ciphertext attacks[END_REF][START_REF] Abe | Robust distributed multiplicaton with out interaction[END_REF][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] is a simple, non-interactive, client/server protocol.

An adaptively secure extension of the Boneh-Boyen-Halevi construction [START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF] was proposed by Libert and Yung [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF] using bilinear maps in composite order groups. It was subsequently shown [START_REF] Libert | Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF][START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF] that pairing-based NIWI/NIZK arguments [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF][START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] can be used to remove interaction from threshold variants of Cramer-Shoup while proving security under adaptive corruptions in the standard model. A natural question to ask (from an algebraic perspective aiming not to put all one's eggs in the same [pairing] basket) is whether similarly simple non-interactive adaptively secure systems can be realized in the standard model outside the world of pairing-based cryptography.

Our Contribution. In this paper, we provide IND-CCA-secure non-interactive threshold cryptosystems proven secure in the sense of a game-based definition of adaptive security under the Decision Composite Residuosity assumption [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] (DCR) and the Learning-With-Errors (LWE) assumption [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

Our first construction relies on both assumptions and features ciphertexts that are about as short as in standard (i.e., non-threshold) DCR-based CCA2secure encryption schemes based on the Cramer-Shoup paradigm [START_REF] Cramer | Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption[END_REF][START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]. Indeed, ciphertexts are only roughly 3 times as large as those of [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]. Our scheme offers at least two advantages over the DCR-based system obtained by applying universal thresholdizers [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF] to, e.g., the Camenisch-Shoup cryptosystem [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]Section 3.2]. First, in line with our goal, we can prove adaptive security under a polynomial reduction for t, = poly(λ) without relying on complexity leveraging. 7 Indeed, universal thresholdizers are not known to enable adaptive security under our definition. Second, the scheme implies a more efficient voting-friendly threshold cryptosystem [START_REF] Bernhard | Adapting helios for provable ballot privacy[END_REF] in the sense that its ciphertexts can be publicly "downgraded" (by discarding the ciphertext components that ensure CCA2 security) into an additively homomorphic encryption scheme which is much more efficient than the voting-friendly scheme derived from [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF][START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]. The reason is that the shared decryption algorithm of [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF] would proceed by homomorphically evaluating the decryption circuit of the standard Paillier-based scheme [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF] over FHE-encrypted Paillier secret keys.

Our second construction relies on the sole LWE assumption. To our knowledge, it is the first adaptively secure non-interactive threshold cryptosystem with CCA2 security in the standard model under a quantum-safe assumption. One caveat is that, analogously to previous LWE-based threshold cryptosystems, it relies on an LWE assumption with super-polynomial approximation factor. The reason is that, as in all earlier threshold LWE-based constructions [START_REF] Bendlin | Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems[END_REF][START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF], decryption servers need to add a noise flooding term (which requires a super-polynomial modulus-to-noise ratio) in order to not leak their secret key shares when computing partial decryptions. It remains an open problem to prove adaptive security under a more common LWE assumption with polynomial approximation factor. Technical Overview. Our schemes build on hash proof systems [START_REF] Cramer | Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption[END_REF] and can be seen as pairing-free adaptation of constructions proposed by Libert and Yung [START_REF] Libert | Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF]. In [START_REF] Libert | Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF], they exploit the property that, in the security proofs of encryption schemes built upon hash proof systems, the simulator always knows the secret keys, which makes it easier to answer adaptive corruption queries (a similar observation was made by Dodis and Fazio [START_REF] Dodis | Public-key trace and revoke scheme secure against adaptive chosen ciphertext attack[END_REF] in the context of trace-and-revoke schemes). In the threshold setting, the reduction knows all secret key shares and can always provide a consistent internal state for adaptively corrupted servers.

To address the difficulty that valid ciphertexts are not publicly recognizable, [START_REF] Libert | Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF][START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF] replaced the designated-verifier NIZK proofs of ciphertext validity [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 chosen ciphertext secure public key encryption[END_REF] by publicly verifiable pairing-based NIZK arguments. This eliminates the need for randomized decryption -which was the culprit of interaction in [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen-ciphertext attacks[END_REF][START_REF] Jarecki | Adaptively secure threshold cryptography: Introducing concurrency, removing erasures[END_REF] -since the shared decryption oracle can just reject invalid ciphertexts. This, in turn, preserves the entropy of the centralized secret key (which is used to create the challenge ciphertext in [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 chosen ciphertext secure public key encryption[END_REF]) as decryption queries on valid ciphertexts do not decrease the entropy of secret keys conditionally on the adversary's view. In the challenge ciphertext, the reduction must be able to simulate a fake argument of ciphertext validity while making sure that the adversary cannot come up with such a fake argument in decryption queries. For this purpose, the underlying NIZK argument has to provide one-time simulation-soundness [START_REF] Sahai | Non-malleable non-interactive zero knowledge and adaptive chosenciphertext security[END_REF].

Our first scheme is a threshold version of (a variant of) an Elgamal-Paillier combination proposed in [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]. The public key contains h = g 4N •x mod N 2 , where N is a safe-prime product and x ∈ Z is the secret key. Messages Msg ∈ Z N are encrypted as

(C 0 , C 1 ) = (g 2N •r , (1 + N ) Msg • h r ) ∈ (Z * N 2 ) 2
and can be decrypted using x. The security proof of [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF] involves a hybrid game where C 0 is sampled as a random quadratic residue (instead of a 2N -th residue) in

Z * N 2 before computing C 1 = (1 + N ) Msg • C 2x 0 mod N 2 .
In order to exploit the entropy of x mod N in the challenge phase, each ciphertext (C 0 , C 1 ) should come with a simulation-sound NIZK proof/argument that C 0 is an N -th residue in Z * N 2 . This NIZK component can be realized from recent results [START_REF] Canetti | Fiat-Shamir: From practice to theory[END_REF][START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF][START_REF] Peikert | Non-interactive zero knowledge for NP from (plain) Learning With Errors[END_REF] on the standard-model instantiability of the Fiat-Shamir paradigm [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. In our setting, we can use an argument of composite residuosity described by Libert et al. [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF], which argues soundness in one shot (i.e., without parallel repetitions). However, the latter construction is somewhat an overkill for our purposes as it provides unbounded simulation-soundness (USS) while we only need one-time simulationsoundness in the context of threshold CCA2 security. We, thus, construct an optimized version of the NIZK argument of [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF], where the common reference string (CRS) only contains O(1) Paillier ciphertexts, instead of O(λ) in [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF]. This new optimized NIZK argument suffices for all applications that only need one-time simulation soundness. 8Like its unbounded counterpart [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF], our one-time simulation-sound argument adapts a compiler from [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF], which builds USS arguments from trapdoor Σ-protocols. In short, these are Σ-protocols in the CRS model where an efficiently computable function BadChallenge uses a trapdoor to compute the only challenge Chall admitting a valid response z for a given false statement x ∈ L and a given first prover message a. The USS argument of [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] uses a technique due to Damgård [36] that consists of having the prover first send an equivocable commitment to its first Σ-protocol message before opening the commitment in the response z. In [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF], the equivocable commitment was replaced by a strengthened version of the R-lossy encryption primitive of Boyle et al. [START_REF] Boyle | Fully leakage-resilient signatures[END_REF]. In a nutshell, an R-lossy PKE scheme is a tag-based encryption scheme where ciphertexts are injective for all tags t satisfying some relation R(K, t) (where K is an initialization value chosen at key generation time) and equivocable when R(K, t) = 0. By equivocating the ciphertext in all simulated proofs while keeping it extractable in the adversary's fake proof, we can use the extraction trapdoor to compute the BadChallenge function (in order to ensure soundness via the techniques of [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF]), even after having simulated proofs by means of ciphertext equivocation. This can be seen as applying the simulation-sound zero-knowledge techniques of Garay et al. [START_REF] Garay | Strengthening zero-knowledge protocols using signatures[END_REF] in the context of the BadChallenge function methodology [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF].

In [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF], it was shown that the underlying equivocable R-lossy PKE scheme can be instantiated from the DCR assumption using public keys comprised of O(λ) Paillier ciphertexts. In Section 3, we show that, if we only need to simulate one argument of a false statement, we can use a more efficient R-lossy PKE scheme for a different relation allowing for constant-size public keys. While [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF] uses the bit-matching relation of [START_REF] Boyle | Fully leakage-resilient signatures[END_REF] which incurs long public keys as it must be combined with admissible hash functions [START_REF] Boneh | Secure identity based encryption without random oracles[END_REF], we can simply use the inequality relation where R(K, t) = 1 if and only if K = t. In our DCR-based instantiation, we can thus encrypt/commit to Msg ∈ Z N under the tag t by computing ct = (u t • v) Msg • r N mod N 2 , which can be decrypted as a standard Paillier ciphertext when N divides the order of u t • v. When u t • v is an N -th residue, we can equivocate ct by finding r ∈ Z * N that explains ct as an encryption of an arbitrary plaintext. By suitably programming u, v ∈ Z * N 2 , we can make sure that u t • v is an N -th residue for one specific tag t = K. Importantly, we need to equivocate without knowing the factorization of N since, in our application to simulation-soundness, we rely on the DCR assumption to switch between settings where either only one tag is equivocable or all tags are equivocable.

We note that the above tools do not quite make valid ciphertexts publicly recognizable because the NIZK argument only guarantees that C 0 is a composite residue without proving that it is also a square in Z * N 2 . However, it does not affect the application to CCA2 security since decryption servers can simply square C 0 themselves to make sure that C 2 0 lives in the subgroup of 2N -th residues before releasing decryption shares C 2•ski 0 . Our LWE-based construction relies on the dual Regev cryptosystem [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF], where public keys contain random matrices A ∈ Z n×m q and U = A • R ∈ Z n×L q , for some n, m, L ∈ poly(λ) such that n < m, and secret keys are small-norm integer matrices R ∈ Z m×L . Since the columns of R have a lot of entropy conditionally on (A, U), it is tempting to adapt the approach of our DCR-based system and use LWE in an hash-proof-like fashion (as previously done in, e.g., [START_REF] Alperin-Sheriff | Circular and KDM security for identity-based encryption[END_REF]). However, this requires preventing the adversary from inferring information on R by making decryption queries on ill-formed ciphertexts. This cannot be achieved via designated-verifier NIZK proofs [START_REF] Cramer | Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption[END_REF] since known LWE-based hash proof systems (e.g., [START_REF] Katz | Smooth projective hashing and password-based authenticated key-exchange from lattices[END_REF][START_REF] Wee | Dual projective hashing and its applications -lossy trapdoor functions and more[END_REF]) do not provide smoothness in the worst-case. Namely, nothing is guaranteed on the unpredictability of R c 0 when c 0 is neither a vector of LWE samples for A ∈ Z n×m q nor a uniform vector over Z m q , but something in between (e.g., a vector c 0 = A • s + e 0 where e 0 ∈ Z m is slightly too large).

To address the problem of showing that c 0 is well-formed (i.e., of the form c 0 = A • s + e 0 for a small enough e 0 ∈ Z m ), we replace the designated-verifier NIZK proof by a Fiat-Shamir-based [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] publicly verifiable NIZK argument, which is known to provide soundness in the standard model under the LWE assumption [START_REF] Peikert | Non-interactive zero knowledge for NP from (plain) Learning With Errors[END_REF]. To avoid relying on a generic Karp reduction to the Graph Hamiltonicity language used in [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF], we rely on the simulation-sound NIZK argument of Libert et al. [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF]Appendix G] which allows showing that a vector c 0 is indeed of the form c 0 = A • s + e 0 for a small e 0 ∈ Z m . Since their construction provides publicly verifiable arguments, its soundness property does not rely on the entropy of a verifier's secret key and bypasses the difficulties arising from the use of designated-verifier NIZK proofs. In particular, it keeps the verifier from accepting proofs for vectors c 0 = A • s + e 0 where e 0 is only slightly too large, which preserves the entropy of the centralized secret key R ∈ Z m× .

In the threshold setting, both schemes share their secret keys using the linear integer secret sharing (LISS) primitive of Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF], which are similar to linear secret sharing schemes except that they work over Z. In our LWE-based construction, we crucially exploit the fact that LISS schemes have small linear reconstruction coefficients that can multiply decryption shares without blowing up the underlying noise terms. We could have alternatively used {0, 1}-linear secret sharing (which can also express monotone Boolean formulas [START_REF] Lewko | Decentralizing attribute-based encryption[END_REF]) as in [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF]. However, as observed in [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] in the adaptive corruption setting, LISS nicely interact with discrete Gaussian distributions and make it easier to analyze the remaining entropy of shared secret keys after all decryption queries and corruption queries. Indeed, our DCR-based TPKE bears similarities to the inner product functional encryption scheme of Agrawal et al. [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF] in that it samples secret keys x ∈ Z from a Gaussian distribution over the integers. By sharing them with a LISS, we can adapt arguments used in [START_REF] Agrawal | Fully secure functional encryption for inner products, from standard assumptions[END_REF][START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] in order to assess the entropy of secret keys after all queries.

Related Work. Back in 2001, Fouque and Pointcheval [START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF] used the Naor-Yung paradigm [START_REF] Naor | Public-key cryptosystems provably secure against chosen ciphertext attacks[END_REF] to construct a CCA2-secure threshold cryptosystem under the DCR assumption in the random oracle model. In Supplementary Material E, we show, as a comment, that the proof of IND-CCA security of [START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF] is actually incorrect as an adversary can break the soundness of the proof of plaintext equalities between Paillier ciphertexts with different moduli. It can be fixed by having the encryptor prove that the plaintext is a positive integer smaller than both moduli.

The first LWE-based threshold encryption scheme was proposed by Bendlin and Damgård [START_REF] Bendlin | Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems[END_REF] who showed a threshold version of Regev's cryptosystem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Xie et al. [START_REF] Xie | Efficient threshold encryption from lossy trapdoor functions[END_REF] gave a threshold CCA-secure realization where the size of public keys and ciphertexts grows at least linearly with the number of servers. Boneh et al. gave a compiler [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF] that turns any IND-CCA secure into a non-interactive threshold variant thereof using fully homomorphic encryption. Bendlin et al. [START_REF] Bendlin | How to share a lattice trapdoor: Threshold protocols for signatures and (H)IBE[END_REF] considered lattice-based threshold signatures and IBE schemes. However, the servers can only compute an a priori bounded number of non-interactive private key operations without using interaction. Libert et al. [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF] described non-interactive threshold pseudorandom functions from LWE. Our LWE-based TPKE and its security proof are actually inspired by their use of LISS schemes.

Organization. In Section 2, we first recall some definitions and tools that will be used in our constructions. Section 3 then presents our one-time simulationsound NIZK arguments, which builds on our DCR-based R-lossy PKE scheme described in Section 3.1. Our DCR-based threshold cryptosystem is explained in Section 4. Its variant based on the sole LWE assumption is given in Section 5. For simplicity, we first present non-robust variants of both schemes. In Supplementary Material C, we show that standard techniques can be applied to hedge against malicious adversaries.

Background and Definitions

Lattices

For any q ≥ 2, Z q denotes the ring of integers with addition and multiplication modulo q. If x ∈ R n is a vector, x = n i=1 x 2 i denotes its Euclidean norm and

x ∞ = max i |x i | its infinity norm. If M is a matrix over R, then M := sup x =0 Mx x and M ∞ := sup x =0 Mx ∞ x ∞
denote its induced norms. For a finite set S, U (S) stands for the uniform distribution over S. If X and Y are distributions over the same domain, ∆(X, Y ) denotes their statistical distance.

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

ρ Λ,Σ,c (x) = ρ Σ,c ρ Σ,c
For a matrix A ∈ Z n×m q , we define Λ ⊥ (A) = {x ∈ Z m : A • x = 0 mod q} and Λ(A) = A • Z n + qZ m . For an arbitrary vector u ∈ Z n q , we also define the shifted lattice

Λ u (A) = {x ∈ Z m : A • x = u mod q}.
We now recall the definition of the Learning-With-Errors (LWE) assumption introduced by Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Definition 2.1 (LWE assumption). Let m ≥ n ≥ 1, q ≥ 2 and α ∈ (0, 1) be functions of a security parameter λ. The LWE problem consists in distinguishing between the distributions (A, As + e) and U (Z m×n q × Z m q ), where A ∼ U (Z m×n q ), s ∼ U (Z n q ) and e ∼ D Z m ,αq .

Lemma 2.2 ([54, Theorem 4.1]

). There is a PPT algorithm that, given a basis B of an n-dimensional Λ = Λ(B), a parameter s > B • ω( √ log n), and a center c ∈ R n , outputs a sample from a distribution statistically close to D Λ,s,c .

= (n) such that Pr x← D Z n ,σ [ x > σ √ n] ≤ 1+ 1-• 2 -n . Lemma 2.4 ([68, Lemma 2.6]). Let ∈ (0, 1), c ∈ R and σ > 0, such that σ ≥ ln 2(1 + 1/ )/π. Then H ∞ (D Z,σ,c ) ≥ log σ -log 1 + 2 1- . For σ = Ω( √ n), we get H ∞ (D Z,σ,c ) ≥ log(σ) -2 -n .
Lemma 2.5 ([47]). Let β > 0, q ∈ Z and y ∈ Z. Then, the following holds: ∆(D Zq,β•q,0 , D Zq,β•q,y ) ≤ |y| βq .

Lemma 2.6 ([74, Theorem 2]

). There exists an efficient randomized algorithm TrapGen(1 n , 1 m , q) that given any integers n ≥ 1,q ≥ 2 and sufficiently large m = O(n log q) outputs a matrix A ∈ Z n×m q and a trapdoor T A such that the distribution of A is statistically close to uniform. Lemma 2.7 (Adapted from [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]Cor. 2.8]). Let Λ ⊆ Λ ⊆ R n be two lattices with the same dimension. Let ∈ (0, 1/2). Then, for any c ∈ R n and any σ ≥ η (Λ ), the distribution D Λ,σ,c mod Λ is within statistical distance 2 from the uniform distribution over Λ/Λ .

Composite Residuosity Assumption

We now recall Paillier's Composite Residuosity assumption and its variant considered by Damgård and Jurik. Definition 2.8 ( [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF][START_REF] Damgård | A generalisation, a simplification and some applications of Paillier's probabilistic public-key system[END_REF]). Let integers N = pq and s > 1 for primes p, q. The s-Decision Composite Residuosity (s-DCR) assumption states that the

distributions {x = w N s mod N s+1 | w ← U (Z N )} and {x | x ← U (Z N s+1 )} are computationally indistinguishable.
It is known [START_REF] Damgård | A generalisation, a simplification and some applications of Paillier's probabilistic public-key system[END_REF] that the s-DCR assumption is equivalent to the standard 1-DCR of [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] for any s > 1.

Linear Integer Secret Sharing

This section recalls the concept of linear integer secret sharing (LISS), as defined by Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF]. Definitions below are taken from [START_REF] Thorbek | Linear integer secret sharing[END_REF] where the secret to be shared lives in an interval [-2 l , 2 l ] centered in 0, for some l ∈ N. Definition 2.9. A monotone access structure on [ ] is a non-empty collection A of sets A ⊆ [ ] such that ∅ ∈ A and, for all A ∈ A and all sets B such that A ⊆ B ⊆ [ ], we have B ∈ A. For an integer t ∈ [ ], the threshold-t access structure T t, is the collection of sets A ⊆ [ ] such that |A| ≥ t. Sets A ∈ A are called qualified and sets B / ∈ A are called forbidden.

Let P = [ ] be a set of shareholders. In a LISS scheme, a dealer D wants to share a secret s in a publicly known interval [-2 l , 2 l ]. To this end, D uses a share generating matrix M ∈ Z d×e and a random vector ρ = (s, ρ 2 , . . . , ρ e ) , where s is the secret to be shared and {ρ i } e i=2 are randomly sampled in [-2 l0+λ , 2 l0+λ ] e-1 , for some l 0 ≥ l ∈ . Usually, the distribution of the ρ i is uniform but, in the following, we will set l 0 = l and ρ i ← D Z,σ . The dealer D computes a vector s = (s 1 , . . . , s d ) of share units as s = (s 1 , . . . , s d ) = M • ρ ∈ Z d . Each party in P = {1, . . . , } is assigned a set of share units. Letting ψ : {1, . . . , d} → P be a surjective function, the i-th share unit s i is assigned to the shareholder ψ(i) ∈ P , in which case player ψ(i) is said to own the i-th row of M. If A ⊆ P is a set of shareholders, M A ∈ Z d A ×e denotes the set of rows jointly owned by A. Likewise, s A ∈ Z d A denotes the restriction of s ∈ Z d to the coordinates jointly owned by the parties in A. The j-th shareholder's share consists of s ψ -1 (j) ∈ Z dj , so that it receives d j = |ψ -1 (j)| out of the d = j=1 d j share units. The expansion rate µ = d/ is defined to be the average number of share units per player.

There exist security notions for LISS schemes but, since we do not explicitly rely on them, we omit their exposition for conciseness.

To construct LISS schemes, Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] used integer span programs [START_REF] Cramer | Optimal black-box secret sharing over arbitrary abelian groups[END_REF].

Definition 2.10 ( [START_REF] Cramer | Optimal black-box secret sharing over arbitrary abelian groups[END_REF]). An integer span program (ISP) is a tuple formed by three elements M = (M, ψ, ε), where M ∈ Z d×e is an integer matrix whose rows are labeled by a surjective function ψ : {1, . . . , d} → {1, . . . , } and ε = (1, 0, . . . , 0) is called target vector. The size of M is the number of rows d in M. Definition 2.11. Let Γ be a monotone access structure and let M = (M, ψ, ε) an integer span program. Then, M is an ISP for Γ if it computes Γ : namely, for all A ⊆ {1, . . . , }, the following conditions hold:

1. If A ∈ Γ , there is a reconstruction vector λ ∈ Z d A such that λ • M A = ε . 2. If A ∈ Γ , there exists κ = (κ 1 , . . . , κ e ) ∈ Z e such that M A • κ = 0 ∈ Z d
and κ • ε = 1. In this case, κ is called a sweeping vector for A.

We also define κ max = max{|a| | a is an entry in some sweeping vector}.

Damgård and Thorbek [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] observed that a LISS can be built by setting the share generating matrix to be the matrix M of an ISP M = (M, ψ, ε) that computes the access structure Γ . We may then specify a LISS scheme L = (M = (M, ψ, ε), Γ, R, K) by an ISP for the access structure Γ , a space R of reconstruction vectors satisfying Condition 1 of Definition 2.11, and a space K of sweeping vectors satisfying Condition 2. The last step is building an ISP for any access structure with small reconstruction vectors and small sweeping vectors. Damgård and Thorbek showed in [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] that LISS schemes can be obtained from [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF][START_REF] Cramer | Optimal black-box secret sharing over arbitrary abelian groups[END_REF]. While the Benaloh-Leichter (BL) secret sharing [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF] was designed to work over finite groups, it was generalized in [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF] to share integers using access structures consisting of monotone Boolean formulas. In turn, this implies a LISS scheme for any threshold access structure by applying a result of Valiant [START_REF] Valiant | Short monotone formulae for the majority function[END_REF][START_REF] Goldreich | Valiant's polynomial-size monotone formula for majority[END_REF]. Their LISS scheme built upon Benaloh-Leichter [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF] satisfies what we want: as can be observed from [START_REF] Damgård | Linear integer secret sharing and distributed exponentiation[END_REF]Lemma 4], every coefficient of any reconstruction vector λ lives in {-1, 0, 1} and [38, Lemma 5] shows that κ max = 1. Let a monotone Boolean formula f , then the BL-based technique allows us to build binary share distribution matrices M ∈ {0, 1} d×e such that d, e = O(size(f )). Moreover they have at most depth(f ) + 1 non-zero entries, so that each share unit s i has magnitude O(2 l0+λ • depth(f )).

Finally, Valiant's result [START_REF] Valiant | Short monotone formulae for the majority function[END_REF] implies the existence of a monotone Boolean formula of the threshold-t function T t, , which has size d = O( 5.3 ) and depth O(log ). Recall that each player will receive about d/ rows of M on average, then the average share size is O( 4.3 •(l 0 +λ+log log )) bits. Valiant's construction was improved by Hoory et al. [START_REF] Hoory | Monotone circuits for the majority function[END_REF] who gave a monotone formula of size O( 1+ √ 2 ) and depth O(log ) for the majority function. 9 This in turn reduces the average share size to O( √ 2 • (l 0 + λ + log log )) bits.

Threshold PKE

In this section, we slightly adapt the TPKE syntax defined by Boneh et al. [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF]. Definition 2.12 (Threshold PKE). For any ∈ N, let S( ) be a class of efficient monotone access structure on [ ]. A Threshold PKE scheme (TPKE) for the family S(•) is a tuple of efficient PPT algorithms (Keygen, Encrypt, PartDec, PartVerify, Combine) with the following specifications:

-Keygen(1 λ , A) → (pp, pk, sk 1 , sk 2 , . . . , sk ): On input a security parameter λ, A ∈ S( ) an access structure on [ ], for some (corresponding to the biggest element(s) of A for the inclusion), the algorithm outputs a set of public parameters pp (which are implicit in the inputs of all other algorithms and) that defines the message space M, a public key pk and a set of secret key shares sk 1 , sk 2 , . . . , sk . -Encrypt(pk, Msg) → ct: On input the public parameters pp, the encryption key pk and a message Msg ∈ M, the algorithm outputs a ciphertext ct. -PartDec(pk, ct, sk i ) → µ i : Given public parameters pp, a ciphertext ct and a secret key share sk i , this algorithm outputs a partial decryption µ i . -PartVerify(pk, ct, µ i ) → b ∈ {0, 1}: On input of public parameters pp, a ciphertext ct and a partial decryption µ i , this algorithm outputs a bit b. -Combine (pk, B = (S, {φ(µ i )} i∈S ), ct) → Msg : Given public parameters and a set of images of φ of partial decryptions, the algorithm outputs a message Msg ∈ M. The function φ is public and deterministic. 10We aim to construct a TPKE scheme that satisfies the following compactness, correctness and requirements. Our definition of compactness captures that the size of ciphertexts and public keys is not impacted by the number of servers. Unlike [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF], the next definition relies on the family S = ∪ ∈poly(λ) S( ).

Definition 2.13 (Compactness [START_REF] Boneh | Threshold cryptosystems from threshold fully homomorphic encryption[END_REF]). A TPKE scheme satisfies compactness if there exist polynomials P and Q such that ∀λ, ∀A ∈ S, |pk| ≤ P (λ) ∧ |ct| ≤ Q(λ), where (pp, pk, sk 1 , sk 2 , . . . , sk ) ← Keygen(1 λ , A) and the ciphertext is generated as ct ← Encrypt(pk, Msg) for any Msg ∈ M.

Definition 2.14 (Decryption Correctness).

A TPKE provides decryption correctness if the following holds. For any λ ∈ N, any access structure A ∈ S, any set S ∈ A and any message Msg ∈ M, if we run (pp, pk, sk 1 , sk 2 , . . . , sk

) ← Keygen(1 λ , A), ct ← Encrypt(pk, Msg) and then µ i ← PartDec(pp, sk i , ct), ∀i ∈ S, we have Pr[Combine (pk, (S, {φ(µ i )} i∈S ) , ct) = Msg] = 1 -negl(λ).

Definition 2.15 (Partial Verification Correctness).

A TPKE provides partial verification correctness if the following holds. For any λ ∈ N, any A ∈ S, any S ∈ A and any message Msg ∈ M, if we run (pp, pk, sk 1 , sk 2 , . . . , sk

) ← Keygen(1 λ , A), ct ← Encrypt(pk, Msg) and µ i ← PartDec(pp, sk i , ct), ∀i ∈ S, then Pr[PartVerify(pk, ct, µ i ) = 1] = 1 -negl(λ).
We can now define chosen-ciphertext security in a model allowing the adversary to adaptively corrupt decryption servers. We now recall the notion of robustness, which informally captures that no malicious adversary can prevent a honest majority from decrypting a valid ciphertext.

Definition 2.17 ([17]). A TPKE scheme satisfies robustness if no PPT adversary A can cause the following experiment Expt robust A,TPKE (1 λ ) to output 1 with non-negligible probability.

1. On input the security parameter λ, A chooses an access structure A. 2. The challenger samples (pp, pk, sk 1 , sk 2 , . . . , sk ) ← Keygen(1 λ , A) and provides (pp, pk, sk 1 , sk 2 , . . . , sk ) to A.

A outputs a partial decryption forgery

ct , µ i , i , where i ∈ [ ]. 4. The experiment outputs 1 if we have φ(μ i ) = φ(PartDec(pk, sk i , ct )) while PartVerify(pk, ct , µ i ) = 1.
We note that the function φ allows considering as robust a TPKE such that µ i = (μ i , π i ) and where Combine only runs on μ i and not on π i . While, given (μ i , π i ), Combine could have simply striped π i , such a formalization would prevent showing as robust a TPKE where μ i is an element of an admissible language and π i is a probabilistic membership argument whose validity does not necessarily guarantee that π i is in the range of honestly computed arguments. Thanks to φ, such case will not be artificially discarded.

A weaker robustness notion, a.k.a. consistency [START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF], captures the robustness of schemes where the generation of μ i is probabilistic and its validity tolerates a gap with respect to honestly computed statements. We recall it in Supplementary Material A.2. Here, we will focus on the (stronger) notion of robustness.

Correlation Intractable Hash Functions

We consider unique-output efficiently searchable relations [START_REF] Canetti | Fiat-Shamir: From practice to theory[END_REF].

Definition 2.18. A relation R ⊆ X × Y is searchable in time T if there exists a function f : X → Y which is computable in time T and such that, if there exists y such that (x, y) ∈ R, then f (x) = y.

Let λ ∈ N a security parameter. A hash family with input length n(λ) and output length m(λ) is a collection H = {h λ : {0, 1} s(λ) ×{0, 1} n(λ) → {0, 1} m(λ) } of keyed functions induced by efficient algorithms (Gen, Hash), where Gen(1 λ ) outputs a key k ∈ {0, 1} s(λ) and Hash

(k, x) computes h λ (k, x) ∈ {0, 1} m(λ) . Definition 2.19. For a relation ensemble {R λ ⊆ {0, 1} n(λ) ×{0, 1} m(λ) }, a hash function family H = {h λ : {0, 1} s(λ) ×{0, 1} n(λ) → {0, 1} m(λ) } is R-correlation intractable if, for any probabilistic polynomial time (PPT) adversary A, we have Pr k ← Gen(1 λ )), x ← A(k) : (x, h λ (k, x)) ∈ R = negl(λ).
Peikert and Shiehian [START_REF] Peikert | Non-interactive zero knowledge for NP from (plain) Learning With Errors[END_REF] described a correlation-intractable hash family for any searchable relation (in the sense of Definition 2.18) defined by functions f of bounded depth. When f is computable by a branching program, their construction relies on the standard SIS assumption with polynomial approximation factors. Under the LWE assumption with polynomial approximation factors, their bootstrapping theorem allows handling arbitrary bounded-depth functions.

Trapdoor Σ-protocols

Canetti et al. [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF] considered a definition of Σ-protocols that slightly differs from the usual formulation [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF][START_REF] Cramer | Modular design of secure, yet practical cryptographic protocols[END_REF]. Definition 2.20 (Adapted from [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF][START_REF] Asharov | Multiparty computation with low communication, computation and interaction via threshold FHE[END_REF]). Let a language L = (L zk , L sound ) associated with two NP relations R zk , R sound . A 3-move interactive proof system Π = (Gen par , Gen L , P, V) in the common reference string model is a Gap Σprotocol for L if it satisfies the following conditions:

-3-Move Form: P and V both take as input crs = (par, crs L ), with par ← Gen par (1 λ ) and crs L ← Gen L (par, L), and a statement x and proceed as follows: (i) P takes in w ∈ R zk (x), computes (a, st) ← P(crs, x, w) and sends a to the verifier; (ii) V sends back a random challenge Chall from the challenge space C; (iii) P finally sends a response z = P(crs, x, w, a, Chall, st) to V; (iv) On input of (a, Chall, z), V outputs 1 or 0. -Completeness: If (x, w) ∈ R zk and P honestly computes (a, z) for a challenge Chall, V(crs, x, (a, Chall, z)) outputs 1 with probability 1 -negl(λ). -Special zero-knowledge: There is a PPT simulator ZKSim that inputs crs,

x ∈ L zk and a challenge Chall ∈ C. It outputs (a, z) ← ZKSim(crs, x, Chall) such that (a, Chall, z) is computationally indistinguishable from a real transcript with challenge Chall (for w ∈ R zk (x)). -Special soundness: For any CRS crs = (par, crs L ) obtained as par ← Gen par (1 λ ), crs L ← Gen L (par, L), any x ∈ L sound , and any first message a sent by P, there is at most one challenge Chall = f (crs, x, a) for which an accepting transcript (crs, x, a, Chall, z) exists for some third message z. The function f is called the "bad challenge function" of Π. That is, if x ∈ L sound and the challenge differs from the bad challenge, the verifier never accepts.

Definition 2.20 is taken from [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF] and relaxes the standard special soundness property in that extractability is not required. Instead, it considers a bad challenge function f , which may not be efficiently computable. Canetti et al. [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF] define trapdoor Σ-protocols as Σ-protocols where the bad challenge function is efficiently computable using a trapdoor. Here, we use a definition where the CRS and the trapdoor may depend on the language. The common reference string crs = (par, crs L ) consists of a fixed part par and a language-dependent part crs L which is generated as a function of par and a language parameter L = (L zk , L sound ). Definition 2.21 (Adapted from [START_REF] Canetti | Fiat-Shamir: From Practice to Theory, Part II (NIZK and Correlation Intractability from Circular-Secure FHE)[END_REF]). A Σ-protocol Π = (Gen par , Gen L , P, V) with bad challenge function f for a trapdoor language L = (L zk , L sound ) is a trapdoor Σ-protocol if it satisfies the properties of Definition 2.20 and there exist PPT algorithms (TrapGen, BadChallenge) with the following properties.

• Gen par inputs λ ∈ N and outputs public parameters par ← Gen par (1 λ ).

• Gen L is a randomized algorithm that, on input of public parameters par, outputs the language-dependent part crs L ← Gen L (par, L) of crs = (par, crs L ).

• TrapGen(par, L, τ L ) takes as input public parameters par and a membershiptesting trapdoor τ L for the language L sound . It outputs a common reference string crs L and a trapdoor τ Σ ∈ {0, 1} τ , for some τ (λ). • BadChallenge(τ Σ , crs, x, a) takes in a trapdoor τ Σ , a CRS crs = (par, crs L ), an instance x, and a first prover message a. It outputs a challenge Chall.

In addition, the following properties are required.

• CRS indistinguishability: For any par ← Gen par (1 λ ), and any trapdoor τ L for the language L, an honestly generated crs L is computationally indistinguishable from a CRS produced by TrapGen(par, L, τ L ). Namely, for any aux and any PPT distinguisher A, we have

Adv indist-Σ A (λ) := | Pr[crs L ← Gen L (par, L) : A(par, crs L ) = 1] -Pr[(crs L , τ Σ ) ← TrapGen(par, L, τ L ) : A(par, crs L ) = 1]| ≤ negl(λ).
• Correctness: There exists a language-specific trapdoor τ L such that, for any instance x ∈ L sound and all pairs (crs L , τ Σ ) ← TrapGen(par, L, τ L ), we have

BadChallenge(τ Σ , crs, x, a) = f (crs, x, a) .
Note that the TrapGen algorithm does not take a specific statement x as input, but only a trapdoor τ L allowing to recognize elements of L sound .

R-Lossy Public-Key Encryption With Efficient Opening

In [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF], Libert et al. formalized a generalization of the notion of R-lossy encryption introduced by Boyle et al. [START_REF] Boyle | Fully leakage-resilient signatures[END_REF]. The primitive is a tag-based encryption scheme [START_REF] Kiltz | Chosen-ciphertext security from tag-based encryption[END_REF] where the tag space T is partitioned into injective tags and lossy tags. When ciphertexts are generated for an injective tag, the decryption algorithm correctly recovers the underlying plaintext. When messages are encrypted under lossy tags, the ciphertext is statistically independent of the plaintext. In R-lossy PKE schemes, the tag space is partitioned according to a binary relation R ⊆ K × T . The key generation algorithm takes as input an initialization value K ∈ K and partitions T in such a way that injective tags t ∈ T are exactly those for which (K, t) ∈ R (i.e., all tags t for which (K, t) ∈ R are lossy). From a security standpoint, the definitions of [START_REF] Boyle | Fully leakage-resilient signatures[END_REF] require the initialization value K to be computationally hidden by the public key. The definition of [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] requires the existence of a lossy key generation algorithm LKeygen which outputs public keys with respect to which all tags t are lossy (in contrast with injective keys where the only lossy tags are those for which (K, t) ∈ R). In addition, [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] also asks that the secret key allows equivocating lossy ciphertexts (a property called efficient opening by Bellare et al. [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF]) using an algorithm called Opener. For the purpose of constructing simulation-sound arguments, [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] uses two distinct opening algorithms Opener and LOpener. The former operates over injective public keys for lossy tags while the latter can equivocate ciphertexts encrypted under lossy keys for any tag. Definition 2.22. Let R ⊆ K λ × T λ be an efficiently computable binary relation. An R-lossy PKE scheme with efficient opening is a 7-uple of PPT algorithms (Par-Gen, Keygen, LKeygen, Encrypt, Decrypt, Opener, LOpener) such that:

Parameter generation: On input of a security parameter λ, a desired length of of initialization values L ∈ poly(λ) and a lower bound B ∈ poly(λ) on the message length, Par-Gen(1 λ , 1 L , 1 B ) outputs public parameters Γ that specify a tag space T , a space of initialization values K, a public key space PK, a secret key space SK and a trapdoor space T K. Key generation: For an initialization value K ∈ K and public parameters Γ , algorithm Keygen(Γ, K) outputs an injective public key pk ∈ PK, a decryption key sk ∈ SK and a trapdoor key tk ∈ T K. The public key specifies a ciphertext space CtSp and a randomness space R LPKE . Lossy Key generation: Given an initialization value K ∈ K and public parameters Γ , the lossy key generation algorithm LKeygen(Γ, K) outputs a lossy public key pk ∈ PK, a lossy secret key sk ∈ SK and a trapdoor key tk ∈ T K. Decryption under injective tags: For any Γ ← Par-Gen(1 λ , 1 L , 1 B ), any initialization value K ∈ K, any tag t ∈ T such that (K, t) ∈ R, and any message Msg ∈ MsgSp, we have

Pr ∃r ∈ R LPKE : Decrypt sk, t, Encrypt(pk, t, Msg; r) = Msg < ν(λ) ,
for some negligible function ν(λ), where (pk, sk, tk) ← Keygen(Γ, K) and the probability is taken over the randomness of Keygen. Indistinguishability: For any Γ ← Par-Gen(1 λ , 1 L , 1 B ), the key generation algorithms LKeygen and Keygen satisfy the following: (ii) For any initialization values K, K ∈ K, the two distributions {pk | (pk, sk, tk) ← LKeygen(Γ, K)} and {pk | (pk, sk, tk) ← LKeygen(Γ, K )} are statistically indistinguishable. We require them to be 2 -Ω(λ) -close in terms of statistical distance.

Lossiness: For any Γ ← Par-Gen(1 λ , 1 L , 1 B ), any initialization value K ∈ K and tag t ∈ T such that (K, t) ∈ R, any (pk, sk, tk) ← Keygen(Γ, K), and any Msg 0 , Msg 1 ∈ MsgSp, the following distributions are statistically close:

{C | C ← Encrypt(pk, t, Msg 0 )} ≈ s {C | C ← Encrypt(pk, t, Msg 1 )}.
For any (pk, sk, tk) ← LKeygen(Γ, K), the above holds for any tag t (and not only those for which (K, t) ∈ R).

Equivocation under lossy tags: For any Γ ← Par-Gen(1 λ , 1 L , 1 B ), any K ∈ K, any keys (pk, sk, tk) ← Keygen(Γ, K) let D R denote the distribution, defined over the randomness space R LPKE , from which the random coins used by Encrypt are sampled. For any message Msg ∈ MsgSp and ciphertext C, let D pk,Msg,C,t denote the probability distribution on R LPKE with support

S pk,Msg,C,t = {r ∈ R LPKE | Encrypt(pk, t, Msg, r) = C} ,
and such that, for each r ∈ S P K,Msg,C,t , we have

D pk,Msg,C,t (r) = Pr r ← D R [r = r | Encrypt(pk, t, Msg, r ) = C] . (1)
For any random coins r ← D R , any tag t ∈ T λ such that (K, t) ∈ R, and any messages Msg 0 , Msg 1 ∈ MsgSp, algorithm Opener takes as inputs pk, C = Encrypt(pk, t, Msg 0 , r), r t, and tk. It outputs a sample r from a distribution statistically close to D pk,Msg 1 ,C,t .

Equivocation under lossy keys: For any initialization value K ∈ K λ , any keys (pk, sk, tk) ← LKeygen(Γ, K), any random coins r ← D R , any tag t ∈ T λ , and any distinct messages Msg 0 , Msg 1 ∈ MsgSp, algorithm LOpener takes as input C = Encrypt(pk, t, Msg 0 , r), r, t and sk. It outputs r ∈ R LPKE such that C = Encrypt(pk, t, Msg 1 , r). We require that, for any t ∈ T λ such that (K, t) ∈ R, the distributions

{r ← LOpener(pk, sk, t, ct, Msg 0 , Msg 1 , r) | r ← D R }
and {r ← Opener(pk, tk, t, ct, Msg 0 , Msg 1 , r) | r ← D R } be statistically close.

The above definition is slightly weaker than the one of [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] in the property of equivocation under lossy keys. Here, we do not require that the outputs of Opener and LOpener be statistically close to D pk,Msg 1 ,C,t as defined in (1): We only require that, on lossy keys and lossy tags, Opener and LOpener sample random coins from statistically close distributions. In fact, the first indistinguishability property implies (since the distinguisher is given tk) that the outputs of both algorithms will be computationally indistinguishable from D pk,Msg 1 ,C,t . Our definition turns out to be sufficient for the purpose of simulation-sound arguments and will allow us to obtain a construction from the DCR assumption. We note that the property of decryption under injective tags does not assume that random coins are honestly sampled, but only that they belong to some predefined set R LPKE .

Trapdoor Σ-Protocol Showing Composite Residuosity

We recall the trapdoor Σ-protocol of [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF], which allows proving that an element of Z * N 2 is a composite residue (i.e., a Paillier encryption of 0). Namely, let N = pq be an RSA modulus and let an integer ζ > 1. We describe a trapdoor Σ-protocol for the language

L DCR := {x ∈ Z * N ζ+1 | ∃w ∈ Z N : x = w N ζ mod N ζ+1 }.
We assume that the challenge space is {0, . . . , 2 λ -1} and that p, q > 2 l(λ) , for some polynomial l : N → N such that l(λ) > λ for any sufficiently large λ ∈ N. The condition p, q > 2 λ will ensure that the difference between any two challenges be co-prime with N .

In order to obtain a BadChallenge function that identifies bad challenges for elements x ∈ L DCR , one difficulty is the case of elements x ∈ Z * N ζ+1 that are encryptions of an element α x ∈ Z N such that 1 < gcd(α x , N ζ ) < N ζ . Indeed, we cannot immediately identify a unique bad challenge by inverting α x in Z N ζ . However, a closer analysis shows that, even when ζ > 1 and gcd(α x , N ζ ) > 1, at most one bad challenge can exist in the set {0, 1, . . . , 2 λ -1}.

Gen par (1 λ ) : Given the security parameter λ, define par = {λ}. Gen L (par, L DCR ) : Given public parameters par as well as a description of a language L DCR , consisting of an RSA modulus N = pq with p and q prime satisfying p, q > 2 l(λ) , for some polynomial l : N → N such that l(λ) > λ, define the language-dependent crs L = {N }. The global CRS is

crs = ({λ}, crs L ).
TrapGen(par, L DCR , τ L ) : Given par, the description of a language L DCR that specifies an RSA modulus N and a membership-testing trapdoor τ L = (p, q) consisting of the factorization of N = pq, output the language-dependent crs L = {N } which defines crs = ({λ}, crs L ) and the trapdoor τ Σ = (p, q). P crs, x, w ↔ V(crs, x) : Given a crs, a statement x = w N ζ mod N ζ+1 , P (who has the witness w ∈ Z N ) and V interact as follows:

1. P chooses a random r ← U (Z * N ) and sends a = r N ζ mod N ζ+1 to V . 2. V sends a random challenge Chall ← U ({0, . . . , 2 λ -1}) to P . 3. P computes the response z = r • w Chall mod N and sends it to

V . 4. V checks if a • x Chall ≡ z N ζ (mod N ζ+1
) and returns 0 if this condition is not satisfied.

BadChallenge par, τ Σ , crs, x, a : Given τ Σ = (p, q), decrypt x and a to obtain

α x = D τ Σ (x) ∈ Z N ζ , α a = D τ Σ (a) ∈ Z N ζ . 1. If α a = 0, return Chall = 0. 2. If α a = 0, let d x = gcd(α x , N ζ
), which lives in the set

{p i q j | 0 ≤ i < ζ, 0 ≤ j < ζ} ∪ {p i q ζ | 0 ≤ i < ζ} ∪ {p s q j | 0 ≤ j < ζ}.
Then, do the following:

a. If 1 < d x < N ζ , return ⊥ if d x does not divide N ζ -α a . b. Otherwise, the congruence α a +Chall•α x ≡ 0 (mod N ζ dx ) has a unique solution Chall = -α -1 x • α a ∈ Z N ζ /dx since gcd(α x , N ζ /d x ) = 1. If Chall ∈ Z N ζ /dx \{0, . . . , 2 λ -1}, return ⊥. Else, return Chall = Chall .
In [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF], it is shown that the above construction is a trapdoor Σ-protocol with large challenge space. By applying [START_REF] Peikert | Non-interactive zero knowledge for NP from (plain) Learning With Errors[END_REF], this implies compact NIZK arguments (i.e., without using parallel repetitions to achieve negligible soundness error) for the language L DCR assuming that the LWE assumption holds.

Lemma 2.23 ([66]). The above protocol is a trapdoor Σ-protocol for the language L DCR .

NIZK Arguments With One-Time Simulation-Soundness

Libert et al. [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] gave a method that directly compiles (i.e., without relying on generic NIZK techniques [START_REF] Santis | Robust non-interactive zero-knowledge[END_REF]) any trapdoor Σ-protocol for a trapdoor language into an unbounded simulation-sound NIZK argument for the same language. As a building block, their construction uses an LWE-based equivocable R-lossy PKE scheme for the bit-matching relation. Under the DCR assumption, a more efficient R-lossy PKE scheme was described in [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF]. In this section, we show that, in applications that only require one-time simulation-soundness, we can use an R-lossy PKE scheme with a constant-size public key. In contrast, the R-lossy PKE system of [START_REF] Libert | One-shot Fiat-Shamir-based NIZK arguments of composite residuosity in the standard model[END_REF] has a large public key comprised of Θ(λ) Paillier ciphertexts.

In our one-time simulation-sound arguments, we use an R-lossy PKE scheme for the inequality relation. Par-Gen(1 λ , 1 L , 1 B ): Define K = T = {0, 1} L , so that the tag and initialization value spaces coincide. Define public parameters as Γ = (1 λ , 1 L , 1 B ).

Keygen(Γ, K): On input of public parameters Γ and K ∈ K, generate a key pair as follows.

1. Choose an RSA modulus N = pq such that p, q > 2 l(λ) , for some polynomial l : N → N such that l(λ) > L(λ) for any sufficiently large λ, and

an integer ζ ∈ poly(λ) such that N ζ > 2 B . 2. Pick u ← U (Z * N ζ+1 ), v ← U (Z * N ) and compute v = u -K •v N ζ mod N ζ+1 , where K is interpreted as an element of Z N ζ . Define R LPKE = Z *
N and output sk = (p, q, K) as well as

pk := N, ζ, u, v , tk = (v, K).
LKeygen(Γ, K): On input of public parameters Γ and an initialization value K ∈ K, generate a key pair as follows.

1. Choose an RSA modulus N = pq such that p, q > 2 l(λ) , for some polynomial l : N → N such that l(λ) > L(λ) for any sufficiently large λ, and an integer ζ ∈ poly(λ) such that

N ζ > 2 B . 2. Choose ū, v ← U (Z * N ) uniformly. Compute u = ūN ζ mod N ζ+1 and v = u -K • vN ζ mod N ζ+1 , where K is interpreted as an element of Z N ζ . Define R LPKE = Z *
N and output sk = (ū, v, K) as well as pk := N, ζ, u, v and tk = (v, K).

Encrypt(pk, t, Msg): To encrypt Msg ∈ Z N ζ for the tag t ∈ {0, 1} L , interpret t as an element of Z N ζ . Pick r ← U (Z * N ) and compute ct = (u t • v) Msg • r N ζ mod N ζ+1 .
Decrypt(sk, t, ct): Given sk = (p, q, t ) and the tag t ∈ {0, 1} L , interpret t as an element of Z N ζ . Then, do the following:

1. Letting λ(N ) = lcm(p -1, q -1), compute h t = (u t • v) λ(N ) mod N ζ+1 , which can be written h t = 1 + g t N mod N ζ+1 , for some g t ∈ Z N ζ , since its order is at most N ζ . Return ⊥ if g t = 0 or gcd(g t , N ζ ) > 1. 2. Otherwise, compute Msg = (ct λ(N ) mod N ζ+1 )-1 N • g -1 t mod N ζ
, where the division is computed over Z, and output Msg ∈ Z N ζ .

Opener(pk, tk, t, ct, Msg 0 , Msg 1 , r): Given tk = (v, K) and t ∈ {0, 1} L , return ⊥ if t = K when they are interpreted as elements of

Z N ζ . Otherwise, given Msg 0 , Msg 1 ∈ Z N ζ and r ∈ Z * N such that ct = (u t • v) Msg 0 • r N ζ = (v N ) Msg 0 • r N ζ mod N ζ+1 , (2)
output r = r • vMsg 0 -Msg 1 mod N , so that ct = (u t • v) Msg 1 • rN ζ mod N ζ+1 . LOpener(sk, t, ct, Msg 0 , Msg 1 , r): Given sk = (ū, v, K) and t ∈ {0, 1} L , interpret t as an element of Z N ζ . Given Msg 0 , Msg 1 ∈ Z N ζ and r ∈ Z * N such that ct = (u t • v) Msg 0 • r N ζ = (ū t-K • v) N •Msg 0 • r N ζ mod N ζ+1 , ( 3
) output r = r • (ū t-K • v) Msg 0 -Msg 1 mod N , which satisfies ct = (u t • v) Msg 1 • rN ζ mod N ζ+1 .
The scheme enables decryption under injective tags because, with high probability over the randomness of Keygen, the order of u is a multiple of N ζ since u is sampled uniformly in Z * N ζ+1 at step 2. Since t, K ∈ {0, 1} L and p, q > 2 L , we have gcd(t -K, N ζ ) = 1, so that N ζ divides the order of u t-K • vN ζ when t = K. This ensures that h t has order N ζ and gcd(g t , N ζ ) = 1 at step 1 of Decrypt.

We now prove that the scheme satisfies all the properties of Definition 2.22. The first indistinguishability property crucially imposes that lossy and injective keys be indistinguishable even when the equivocation trapdoor tk of Opener is given. This is important for our proof of one-time simulation-soundness, which requires that Opener be able to equivocate lossy ciphertexts given only tk and without knowing the factorization of N (otherwise, we could not meaningfully rely on the DCR assumption to switch from lossy to injective keys).

Theorem 3.2. The above construction is an R NEQ -lossy PKE scheme under the DCR assumption.

Proof. We show that the scheme satisfies all the required properties.

Decryption under injective tags. Let distinct t, K ∈ {0, 1} L and a message

Msg ∈ Z N ζ . Let (pk = (N, ζ, u, v), sk = (p, q, K), tk = (v, K)) ← KeyGen(Γ, K). The encryption algorithm outputs ct = (u t • v) Msg • r N ζ mod N ζ+1 , for some r ∈ Z * N .
The decryption algorithm first computes

h t = (u t-K • vN ζ ) λ(N ) mod N ζ+1 = u (t-K)λ(N ) mod N ζ+1 . (4)
Since u was chosen uniformly in Z * N ζ+1 , its order is a multiple of N ζ with overwhelming probability ϕ(N )/N . In this case, (4) implies that h t has order

N ζ since gcd (t -K)λ(N ), N ζ = 1 (recall that 0 < |t -K| < 2 L < min(p, q), so that gcd(t -K, N ζ ) = 1). It can thus be parsed as h t = 1 + g t N for some g t ∈ Z * N ζ . This implies ct λ(N ) mod N ζ+1 ≡ h Msg t • r N ζ •λ(N ) ≡ (1 + g t N ) Msg ≡ 1 + (Msg • g t mod N ζ ) • N (mod N ζ+1 ).
The output of Decrypt is thus correct as long as gcd(g t , N ζ ) = 1, which is the case with overwhelming probability over the random choice of u in Keygen.

Indistinguishability. We have two properties to verify.

(i) When we consider the distributions of pairs pk = (N, ζ, u, v), tk = (v, K) produced by Keygen and LKeygen, the only difference is the way to sample u.

In the former case, it is sampled from U (Z * N ζ+1 ) while, in the latter case, it is sampled as u = ūN ζ mod N ζ+1 , with ū ← U (Z * N ). The DCR assumption states that these two distributions are computationally indistinguishable and the same holds for the two distributions of pairs (pk, tk).

(ii) We claim that the distributions {pk | (pk, sk, tk) ← LKeygen(Γ, K b )} b=0,1
are perfectly indistinguishable for any

K 0 , K 1 ∈ {0, 1} L since u is an N ζ -th residue. Indeed, (N, u = ūN ζ mod N ζ+1 , (ū -K0 • v) N ζ mod N ζ+1 ) | ū, v ← U (Z * N )) and {(N, u = ūN ζ mod N ζ+1 , (ū -K1 • v) N ζ mod N ζ+1 ) | ū, v ← U (Z * N )
} are identical distributions as their third component is uniform in the subgroup of N ζ -th residues either way.

Lossiness under lossy tags. Let Msg 0 and Msg 1 be two messages and an arbitrary K ∈ K. Let an injective key pk = (N, ζ, u, v), sk = (p, q, K), tk = (v, K) ← Keygen(Γ, K),

where v = u -K • vN ζ mod N ζ+1 . Under the tag t = K, encrypting Msg 0 or Msg 1 leads to identical ciphertext distributions since (u K •v) Msg b = vMsg b •N ζ mod N ζ+1 for each b ∈ {0, 1}. Indeed, the distributions {v Msg 0 •N ζ • r N ζ | r ← U (Z * N )} and {v Msg 1 •N ζ • r N ζ | r ← U (Z *
N )} both coincide with the uniform distribution over the subgroup of N ζ -th residues.

Equivocation under lossy tags. We know that, for any K ∈ K, any injective keys (pk, sk, tk) ← Keygen(Γ, K) and any message Msg

∈ Z N ζ , the distribution {ct = Encrypt(pk, K, Msg; r) | r ← D LPKE R } is equal to {(v Msg • r) N ζ mod N ζ+1 | r ← U (Z N )}, which is nothing but the uniform distribution over the subgroup of N ζ -th residues in Z * N ζ+1 since D LPKE R = U (Z * N ). Since Opener is deterministic, it suffices to observe that any N ζ -th residue ct uniquely determines r ct = ct 1/N ζ mod N ∈ Z * N such that ct = r N ζ ct mod N ζ+1 as its N ζ -th roots are of the form {r i = r ct + i • N | i ∈ Z N ζ }. For any lossy ciphertext ct ∈ Z * N ζ+1 , Opener thus outputs r = r ct • v-Msg mod N , which is the unique r ∈ Z * N such that ct = (u K •v) Msg •r N ζ mod N ζ+1
. Said otherwise, for any Msg ∈ Z N ζ , the support S pk,Msg,ct,K is a singleton and Opener always outputs the correct value.

Equivocation under lossy keys. For any possibly distinct t, K, any lossy keys (pk, sk, tk) ← LKeygen(Γ, K) and any message Msg ∈ Z N ζ , the distribution of lossy ciphertexts {ct = Encrypt(pk, t, Msg; r) | r ← D LPKE R } can be written

{ (ū t-K •v) Msg •r N ζ mod N ζ+1 | r ← U (Z * N )}
, which is the uniform distribution over the subgroup of N ζ -th residues in Z * N ζ+1 . Since LOpener is deterministic, it suffices to note that, for any lossy ciphertext

ct ∈ Z * N ζ+1 , it outputs r = r ct • (ū t-K • v) -Msg mod N , where r ct = ct 1/N ζ mod N is the unique N ζ -th root of ct in Z * N .
For any tag t ∈ {0, 1} L and any message Msg, the support S pk,Msg,ct,t is a singleton and LOpener always outputs the only

r ∈ Z * N such that ct = (u K • v) Msg • r N ζ mod N ζ+1 .
Finally, for the lossy tag t = K, Opener outputs the same result as LOpener.

The Argument System

Our one-time simulation-sound argument is very similar to the one of [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF] which provides unbounded simulation-soundness using a more expensive R-lossy PKE scheme. The construction relies on the following ingredients.

-A trapdoor Σ-protocol Π = (Gen par , Gen L , P , V ) for an NP language L. This protocol should satisfy the properties of Definition 2.21. In addition, the function BadChallenge(τ Σ , crs, x, a) should be computable within time T ∈ poly(λ) for any input (τ, crs, x, a). Let also B ∈ poly(λ) the maximal length of the first prover message sent by P .

-A strongly unforgeable one-time signature scheme OTS = (G, S, V) with verification keys in {0, 1} L , where L ∈ poly(λ). -An R NEQ -lossy PKE scheme Π LPKE = (Par-Gen, Keygen, LKeygen, Encrypt, Decrypt, Opener, LOpener) with space K = T = {0, 1} L . We assume that its decryption algorithm is computable within time T . -A correlation intractable hash family H = (Gen, Hash) for the class R CI of relations that are efficiently searchable within time T .

Gen par (1 λ ): Run par ← Gen par (1 λ ) and output par.

Gen L (par, L): Given public parameters par and a language L, the CRS is generated as follows.

1. Generate a CRS crs L ← Gen L (par, L) for the trapdoor Σ-protocol Π . 2. Choose the description a one-time signature scheme OTS = (G, S, V) with verification keys in {0, 1} L , where L ∈ poly(λ). 3. Choose public parameters Γ ← Π LPKE .Par-Gen(1 λ , 1 L , 1 B ) for an R NEQlossy PKE scheme with tag space K = T = {0, 1} L . Then, generate lossy keys (pk LPKE , sk LPKE , tk LPKE ) ← Π LPKE .LKeygen(Γ, 0 L ). 4. Generate a key k ← Gen(1 λ ) for a correlation intractable hash function with output length κ = Θ(λ).

Output the language-dependent CRS crs L := crs L , pk LPKE , k and the simulation trapdoor τ zk := sk LPKE . The global common reference string consists of crs = (par, crs L , pk LPKE , OTS).

P(crs, x, w, lbl) : To prove a statement x ∈ L for a label lbl ∈ {0, 1} * using the witness w, generate a one-time signature key pair (VK, SK) ← G(1 λ ). Then, 1. Compute (a , st ) ← P (crs L , x, w). Then, sample r ← D LPKE R in the randomness space R LPKE of Π LPKE . Using the tag VK ∈ {0, 1} L , compute a ← Π LPKE .Encrypt(pk LPKE , VK, a ; r). 2. Compute Chall = Hash(k, (x, a, VK)). 3. Compute z = P (crs L , x, w, a , Chall, st ) by executing the prover of Π .

Define z = (z , a , r). 4. Generate sig ← S(SK, (x, a, z, lbl)) and output π = VK, (a, z), sig .

V(crs, x, π, lbl) : Given a statement x, a label lbl as well as a purported proof π = VK, (a, z), sig , return 0 if V(VK, (x, a, z, lbl), sig) = 0. Otherwise, 1. Write z = (z , a , r) and return 0 if any of these does not parse properly or if a = Π LPKE .Encrypt(pk LPKE , VK, a ; r).

Let Chall

= Hash k, (x, a, VK) . If V (crs L , x, a , Chall, z )) = 1, return 1.
Otherwise, return 0. Our construction combines a one-time simulation-sound argument of composite residuosity with a threshold variant of an Elgamal-Paillier combination due to Camenisch and Shoup [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]. As in [START_REF] Miao | Two-sided malicious security for private intersection-sum with cardinality[END_REF], we use a generalization of the Camenisch-Shoup system based on ideas from Damgård and Jurik [START_REF] Damgård | A generalisation, a simplification and some applications of Paillier's probabilistic public-key system[END_REF].

For simplicity, we first present a non-robust version of the scheme. In Supplementary Material C, we will explain how to obtain robustness against malicious adversaries by having each server prove that its decryption share is consistent with some public commitment to its corresponding secret key share.

KeyGen(1 λ , A): The dealer conducts the following steps:

1. Choose a safe-prime product N = pq, of which the prime factors are of the form p = 2p + 1, q = 2q + 1 for some primes primes p , q > 2 l(λ) , where l : N → N is a polynomial. Choose an integer ζ ≥ 1 so as to define the message space as MsgSp = Z N ζ . Then, define the language

L DCR := {x ∈ Z * N ζ+1 | ∃w ∈ Z N : x = w N ζ mod N ζ+1 }
and choose g 0 ← U (Z * N ). 2. Generate a common reference string crs ← Setup(1 λ ) for the one-time simulation-sound argument system Π OTSS = (Setup, P, V) of Section 3.

s d    = M • ρ ∈ Z d ,
where M ∈ Z d×e is the share-generating matrix of Section 2.3, which computes the Boolean formula associated with the threshold access structure A. Then, define the private key shares as

sk i = s j j∈ψ -1 (i) = M j • ρ j∈ψ -1 (i) ∈ Z di ∀i ∈ [ ],
where M j ∈ Z 1×e denotes the j-th row of M while d i stands for the number of rows assigned by the LISS scheme to server i.

Finally, output the public key pk = (N, ζ, g 0 , h, crs) and the vector of secretkey shares (sk 1 , sk 2 , . . . , sk ).

Encrypt(pp, pk, Msg): To encrypt Msg ∈ Z N ζ , choose r ← U ({0, . . . , N/4 }) and compute

C 0 = g 0 2N ζ •r mod N ζ+1 C 1 = (1 + N ) Msg • h r mod N ζ+1
Then, using the witness w = g 2r 0 mod N , compute a simulation-sound NIZK argument π ← P crs, C 0 , g 2r 0 mod N, lbl that C 0 ∈ L DCR using the label lbl = C 1 . Then, return the ciphertext ct := (C 0 , C 1 , π).

PartDec pp, sk i , ct : On input of its share sk i = {s j = M j • ρ} j∈ψ -1 (i) and a ciphertext ct = (C 0 , C 1 , π), the i-th server does the following.

1. If V(crs, C 0 , π, lbl) = 0, return ⊥. 2. For each j ∈ ψ -1 (i) = {j 1 , . . . , j di }, compute µ i,j = C 2•sj 0
mod N ζ+1 and return

µ i = (µ i,j1 , . . . , µ i,j d i ) = C 2•sj 1 0 mod N ζ+1 , . . . , C 2•sj d i 0 mod N ζ+1 ∈ (Z * N ζ+1 ) di .
Combine pp, B = (S ∈ A, {µ i } i∈S ), ct = (C 0 , C 1 , π) : First, parse the set S as S = {j 1 , . . . , j t } and find a vector

λ S = [λ j1 | . . . | λ jt ] ∈ {-1, 0, 1} d S such that λ S • M ψ -1 (S)
= (1, 0, . . . , 0), where d S = i∈S d i and λ ji = (λ ji,1 , . . . , λ ji,dj i ) ∈ {-1, 0, 1} di for all i ∈ [t]. Then, do the following:

1. Compute μ i∈[t] k∈[dj i ] µ λ j i ,k ji,k mod N ζ+1 .
2. Compute Ĉ1 = C 1 /μ mod N ζ+1 and return ⊥ if Ĉ1 = 1 mod N . Otherwise, run the algorithm of [37, Section 3] so as to recover Msg ∈ Z N ζ by extracting the discrete logarithm of Ĉ1 w.r.t. the base (1 + N ).

In the dealing phase, the matrix M ∈ Z d×e has O(log ) non-zero entries for threshold access structures. If we apply the LISS scheme based on the Benaloh-Leichter secret sharing [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF] and the result of Hoory et al. [START_REF] Hoory | Monotone circuits for the majority function[END_REF], M has dimensions d, e = O( 1+ √ 2 ), so that its rows have norm M j = O( √ e log ), which leads to share units of magnitude |s j | = O(σe • log ).

The scheme thus provides compactness in the sense of Definition 2.13 since the size of ciphertexts and public keys only depends on λ. By increasing the exponent ζ > 1, the ratio between ciphertext and plaintext sizes can approach 1, which was not possible in [START_REF] Libert | Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF][START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF]. 11 We now prove security in the sense of Definition 2.16.

Theorem 4.1. The above scheme provides IND-CCA security in the adaptive corruption setting assuming that: (i) The DCR assumption holds; (ii) The argument system Π OTSS provides one-time simulation-soundness.

Proof. We consider a sequence of games where, for each i, we call W i the event that the adversary wins in Game i .

C 0 = z 2 mod N ζ+1 , C 1 = (1 + N ) Msg b • C 0 2x mod N ζ+1 , (5)
before simulating π ← Sim 1 crs, τ zk , C 0 , C 1 as in Game 1 . Since the subgroup of 2N ζ -th residues is a cyclic group of order p q , the distribution of (C 0 , C 1 ) is statistically close to that of Game 1 . Indeed, the distribution of C 0 is now perfectly (instead of statistically) uniform in the subgroup of 2N ζ -th residues. Hence,

| Pr[W 2 ] -Pr[W 1 ]| < 2 -Ω(λ) .
Game 3 : This game is like Game 2 except that, in order to construct the challenge ciphertext, we now sample z ← U (Z N ζ+1 ) uniformly in Z * N ζ+1 instead of sampling it from the subgroup of N ζ -th residues. Then, (C 0 , C 1 ) are still computed as per [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF]. Under the DCR assumption, this change goes unnoticed and a straightforward reduction shows that | Pr

[W 3 ]-Pr[W 2 ]| ≤ Adv DCR (λ).
At this point, we are done with the DCR assumption and we can henceforth use the factorization of N in subsequent games.

Game 4 : In this game, the challenger rejects all pre-challenge partial decryption queries ct = (C 0 , C 1 , π) such that C 0 is not an N ζ -th residue (note that this can be efficiently checked using the factorization of N ). The soundness of the argument system (which is implied by its simulation-soundness) implies that the probability to reject a ciphertext that would not have been rejected in Game 3 is negligible: we have | Pr[W 4 ] -Pr[W 3 ]| ≤ Adv OTSS (λ). Game 5 : We modify the partial decryption oracle and now reject post-challenge

queries ct = (C 0 , C 1 , π) such that (C 0 , C 1 , π) = (C 0 , C 1 , π
) and C 0 is not an N ζ -th residue. By doing so, the challenger does not reject a ciphertext that would not have been rejected in Game 4 until the event F 5 that A queries the partial decryption of a ciphertext ct

= (C 0 , C 1 , π) = (C 0 , C 1 , π ) such that V(crs, C 0 , π, C 1 ) = 1 although C 2p q 0 mod N ζ+1 = 1.
Clearly, event F 5 would contradict the one-time simulation-soundness of the NIZK argument system Π OTSS . We have

| Pr[W 5 ] -Pr[W 4 ]| ≤ Adv OTSS (λ).
C 0 = (1 + N ) αz • g βz mod N ζ+1 , C 1 = (1 + N ) Msg b +2αz•(x mod N ζ ) • g 2βz•(x mod p q ) mod N ζ+1 , with g = g 2N ζ 0 mod N ζ+1 and for uniform α z ∼ U (Z N ζ ), β z ∼ U (Z p q
). Since gcd(2α z , N ζ ) = 1 with overwhelming probability ϕ(N )/N , we only need to show that, from A's view, x mod N ζ is statistically uniform over Z N ζ in order to prove that the distribution of (C 0 , C 1 ) is statistically close to that of Game 6 .

In Game 5 , we note that the challenger rejects all ciphertexts ct = (C 0 , C 1 , π) such that C 0 ∈ L DCR and (C 0 , C 1 , π) = (C 0 , C 1 , π ). For each partial decryption query (i, (C 0 , C 1 , π)) such that C 0 ∈ L DCR , the adversary can only learn the information {M j •ρ mod p q } j∈ψ -1 (i) . As for partial decryption queries involving the challenge ciphertext ct = (C 0 , C 1 , π ), we can handle them as if they were corruption queries since the latter reveal at least as much information as the former. Let C the set of parties for which the adversary made either a corruption query or a decryption query on the challenge ct = (C 0 , C 1 , π ). Let M C to be the sub-matrix of M obtained by stacking up the rows assigned to those parties.

Since C is not authorized in A, there exists κ ∈ Z e such that κ 1 = 1 and M C • κ = 0 d C . Let a matrix L whose rows form a basis of the lattice {m ∈ Z e , m, κ = 0}, where the rows of M C live. Note that (L, L • ρ) reveals at least as much information as (M C , M C • ρ), so that we may condition on (L, L•ρ). When we additionally condition on (M [ ]\C •ρ mod p q ), we condition on something that reveals fewer information than ρ mod p q .

Let an arbitrary vector ρ 0 ∈ Z e satisfying

L • ρ 0 = L • ρ, ρ 0 ≡ ρ (mod p q ).
The conditional distribution of ρ is ρ 0 + D Λ,σ,-ρ0 , where

Λ = {x ∈ Z e | L • x = 0 ∧ x = 0 mod p q } is the lattice Λ = κ • Z ∩ (p q • Z e ) = (p q • Z) • κ. Let us write ρ 0 = y • κ + (ρ ⊥ 0 )
, where y ∈ R and ρ ⊥ 0 ∈ Z e is orthogonal to κ. Conditionally on L • ρ and ρ mod p q , the distribution of ρ can be written

ρ 0 + D Λ,σ,-ρ0 = (ρ ⊥ 0 ) + y • κ + D (p q •Z)•κ,σ,-(ρ ⊥ 0 )-y•κ = (ρ ⊥ 0 ) + y • κ + κ • D (p q •Z),σ/ κ ,-y . Since κ 1 = 1, the conditional distribution of x = (1, 0, . . . , 0), ρ is thus c + D (p q •Z),σ/ κ ,-y ,
where c = y + (1, 0, . . . , 0), ρ ⊥ 0 . We now consider the distribution obtained by reducing the distribution

D (p q •Z),σ/ κ ,-y over Λ 0 = p q • Z modulo its sublattice Λ 0 = (p q ) • (N ζ Z). Since p q • N ζ < N ζ+1 , by Lemma 2.7, choos- ing the standard deviation σ > √ λ • e • N ζ+1 suffices (by [54, Lemma 3.1] which implies η (Λ 0 ) < λ 1/2 N ζ+1 ) to ensure that x mod N ζ is within distance 2 -λ from U (Λ 0 /Λ 0 ) conditionally on A's view. This completes the proof since gcd(p q , N ζ ) = 1 implies Λ 0 /Λ 0 Z N ζ .
In Supplementary Material C, we show how to turn the scheme into a robust TPKE system. This is achieved by using trapdoor Σ-protocols to prove the validity of decryption shares. To this end, we need to first construct a standard Σ-protocol with binary challenges in order to apply the generic trapdoor Σprotocol construction of Ciampi et al. [START_REF] Ciampi | On adaptive security of delayed-input Sigma protocols and Fiat-Shamir NIZKs[END_REF]. The disadvantage of this approach is that parallel repetitions incur a communication overhead Θ(λ). In applications to voting (where "non-malleable" ciphertext components are removed from ciphertexts before homomorphically processing them), this may be acceptable if proofs of correct partial decryptions are computed by trustees with higher computational resources than voters. It remains an interesting open problem to achieve robustness while proving the correctness of partial decryptions without using parallel repetitions.

An Adaptively Secure CCA2-Secure Threshold Encryption Scheme from LWE

We now describe our construction based on the LWE assumption. Our construction combines the standard dual Regev cryptosystem with a LISS scheme and a one-time simulation-sound NIZK argument Π OTSS = (Setup, P, V) for the gap language L = {L zk , L sound } defined as

L zk = {(c 0 , c 1 ) : ∃(s, e) ∈ Z n+L q × Z m+L : e ≤ d ∧ [c 0 |c 1 ] = Bs + e} L sound = {(c 0 , c 1 ) : ∃(s, e) ∈ Z n+L q × Z m+L : e ≤ γ d ∧ [c 0 |c 1 ] = Bs + e}, for some matrix B ∈ Z (m+L)×(n+L) q
, where m, n ∈ poly(λ) while L ∈ poly(λ) defines the message space Z L p for some prime p. Specific constructions of (even unbounded simulation-sound) NIZK arguments for such languages have been recently proposed by Libert et al. in [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF]Section 3] under on the LWE assumption. Our construction goes as follows:

KeyGen(1 λ , A): The trusted dealer proceeds as follows.

1. Choose a LISS scheme L LISS = (M = (M ∈ Z d×e , ψ, ε), A, R, K), as defined in Definition 2.11. Here, M is an ISP for A, R is the reconstruction vector space and K is the sweeping vector space. Define

d i := |ψ -1 (i)| for all i ∈ [ ]. Recall that, in the case A = T t, , we have e = O( 1+ √
2 ). Let also δ = O(log ) the maximal number of non-zero entries on a row of the ISP matrix M. 2. Select public parameters pp = {m, n, q, p, L, L LISS }, consisting of a prime p; a modulus q = p • K, for some K ∈ N * ; dimensions n = Ω(λ 2 ), m = Ω(n log q); a standard deviation σ = Ω( √ e • m); and an integer L ∈ poly(λ). These are chosen so that all prime factors of q are larger than 2 √ mσ. 12 The message space is defined as M = Z L p . 3. Set γ = m 0.5+Ω (1) . Next, pick two Gaussian parameters β, β s ∈ (0, 1) such that

β s > 2 λ (max i∈[ ] d i )δσ 2 γm √ m + L • β and 2p • d S • β s < 1/2 ∀S ∈ A.
Also, choose a real B > 0 such that B < q and such that B and β s satisfy

2 log(d i (m + 1)) • (m + 1) • d 3/2 i • γ 2 d2 + 1 • β s < B /q ∀i ∈ [ ].
Here, B is only relevant in the modified version of the scheme (deferred to Supplementary Material D), which provides consistency.

Then, defining the norm bound d = 2βq • σ m(m + L), the lower bound on β s can be restated as

β s q > 2 λ-1 (max i∈[ ] d i ) • δσ √ m • (γ • d). 4. Sample A ← U (Z n×m q ), R ← D m×L Z,σ
and compute U := AR ∈ Z n×L q .

Define the following matrix B ∈ Z (m+L)×(n+L) q as:

B = A 0 m×L U K • I L
and define the language L = {L zk , L sound }:

L zk = (c 0 , c 1 ) ∈ Z m q × Z L q : ∃s ∈ Z n+L q : [c 0 |c 1 ] -B • s ≤ d L sound = (c 0 , c 1 ) ∈ Z m q × Z L q : ∃s ∈ Z n+L q : [c 0 |c 1 ] -B • s ≤ γ d
Then, generate a common reference string crs ← Setup(1 λ ) for a onetime simulation-sound proof system Π OTSS = (Setup, P, V). Define the public key pk := (A, U, crs) and the centralized secret key sk := R. 5. Share each column of sk = R using the LISS scheme L LISS . To this end, parse

R as R = r 1 | r 2 | • • • | r L ∈ Z m×L
R τ = M • r τ Φτ Φτ ∈ Z d×m ,
where M is the matrix computing the Boolean formula associated with the access structure A. Then, define the private key shares as

sk i = R τ,ψ -1 (i) = M ψ -1 (i) • Φ τ ∈ Z di×m τ ∈[L] ∀i ∈ [ ].
Finally, return (pp, pk, sk 1 , sk 2 , . . . , sk ).

Encrypt(pp, pk, Msg):

To encrypt Msg ∈ Z L p , first sample s ← Z n q , e 0 ← D Z m ,βq , e 1 ← D Z L ,2β• √ mσ•q compute: c 0 = A • s + e 0 ∈ Z m q c 1 = U • s + e 1 + K • Msg ∈ Z L q (6) π ← P crs, (c 0 | c 1 ) , s, ē , using the witnesses s = (s | Msg ) ∈ Z n+L q , ē = (e 0 | e 1 ) ∈ Z m+L and return the ciphertext ct := (c 0 , c 1 , π).
PartDec pp, sk i , ct : Given a ciphertext ct = (c 0 , c 1 , π) and its secret key share

sk i = {R τ,ψ -1 (i) } τ ∈[L]
, the i-th server does the following. 1. If V(crs, (c 0 , c 1 ), π) = 0, return ⊥.

Otherwise, for every

τ ∈ [L], compute μi,τ = R τ,ψ -1 (i) • c 0 ∈ Z di q . Then, for each τ ∈ [L], sample e i,τ ← D Z d i q ,βs•q and return µ i = {µ i,τ } τ ∈[L] { μi,τ + e i,τ } τ ∈[L] . Combine pp, B = (S ∈ A, {µ i = {µ i,τ } τ ∈[L] } i∈S ), (c 0 , c 1 ) : First, find a vector λ S = [λ j1 | . . . | λ jt ] ∈ {-1, 0, 1} d S such that λ S • M ψ -1 (S)
= (1, 0, . . . , 0), where d S = i∈S d i , λ ji ∈ {-1, 0, 1} dj i for all i ∈ [t] and S := {j 1 , . . . , j t }.

Then, do the following:

1. For each τ ∈ [L], compute µ τ i∈S λ i , µ i,τ = r τ , c 0 + i∈S λ i , e i,τ and let [µ 1 | . . . | µ L ] = R c 0 + e , where e ∈ Z L is a short vector with e [τ ] = i∈S λ i , e i,τ . 2. Compute v := c 1 -R c 0 -e = K • Msg + e 1 -R e 0 -e ∈ Z L
q and find and return the vector Msg ∈ Z L p that minimizes the distance

|v[i] -K • Msg[i]| for each i ∈ [L].
To store a public key, n(m + L) log q bits are necessary, plus the size of the common reference string of Π OTSS , which depends on m, n, L and q. Each factor of q is at least 2 √ mσ, where σ = Ω( √ em) and e, d = O( 1+ √ 2 ). We thus have log q = max(λ, c • log m + 0.5 log e) for some constant c. However, we have log e = O(log ) and we can assume log λ. We thus have log q = O(λ), so that the public key is compact in the sense of Definition 2.13. The same goes for ciphertexts. We need (n + m)L log q bits to represent (c 0 , c 1 ), besides the size of the proof which depends on n, m, L, q.

Lemma 5.1. The above TPKE scheme provides correctness.

Proof. For any ciphertext such that (c 0 , c 1 ) ∈ L zk , decryption is correct as long as, for any authorized S ∈ A, we have

i∈S λ i , e i,τ + e 1 [τ ] + r τ , e 0 < K/2, ∀τ ∈ [L]
Note that, according to Lemma 2.3, since we have

σ = ω( √ log m) (recall that σ = Ω( √ e • m)), we have r τ ≤ σ √ m w.h.p. We also know that |e 1 [τ ]| ≤ d and e 0 ≤ d since [e 0 | e 1 ]
≤ d with overwhelming probability. Using the Cauchy-Schwartz inequality, the scheme is thus correct as long as we have

d S • β s q + d(1 + σ √ m) < K/2. With d = 2βqσ m(m + L), this condition can be replaced by d S • β s q + 4βqσ 2 m √ m + L < K/2 or, equivalently, d S • β s + 4βσ 2 m • √ m + L p < 1/2. ( 7
)
Recall that we chose

β s > 2 λ-2 (max i∈[ ] d i )δγ • (4βσ 2 m √ m + L)
, so that the left-hand-side member of ( 7) is indeed smaller than 2pd S • β s < 1/2. Game 4 : We modify again the generation of ct * = (c 0 , c 1 , π ). The challenger first samples c 0 ← U (Z m q ), e ← D Z m ,βq and and sets

ct = (c 0 , c 1 , π ) = c 0 , R (c 0 -e ) + e 1 + Msg b • K, π .
By Lemma 5.3 and our choice of parameters, we obtain that Game 4 is statistically indistinguishable from Game 3 .

Game 5 : We now change the generation of A in the KeyGen. This time, we generate the public matrix via (A, T A ) ← TrapGen(1 n , 1 m , q). The properties of TrapGen ensure that the distribution of A is statistically close to U (Z n×m q ), so that Game 5 and Game 4 are statistically indistinguishable.

Game 6 : This is identical to Game 5 except that the challenger rejects all partial decryption queries ct = (c 0 , c 1 , π) where (c 0 , c 1 , π) = (c 0 , c 1 , π ) and (c 0 , c 1 ) ∈ L sound . Note that the challenger keeps answering partial decryption queries for the challenge ct = (c 0 , c 1 , π ) as long as the combination of corruption queries and partial decryption queries on ct do not allow A to trivially win. In order to apply the new rejection rule and determine whether (c 0 , c 1 ) ∈ L sound or not, the challenger can build a trapdoor for Λ ⊥ (B) by exploiting the special shape of q = p • K and using the trapdoor T A to compute

T B = T A 0 m×L V p • I L ∈ Z (m+L)×(m+L)
where V ∈ Z m×L is a small-norm matrix such that AV = -pU mod q. Note that the choice of a large enough K ensures that p q to make sure that the rows of T B have small norm with respect to the modulus q. 13 Then, if the adversary is able to distinguish between the two games, it is necessarily able to make a valid-looking partial decryption query for a ciphertext outside L sound . By the OTSS property of the argument system, this can only occur with negligible probability. Lemma 5.5 shows this in details.

Game 7 : We modify the decryption oracle and now also reject all ciphertexts ct = (c 0 , c 1 , π) such that c 0 = c 0 and (c 1 , π) = (c 1 , π ) regardless of whether (c 0 , c 1 ) ∈ L sound or not (note that c 0 can be computed at the outset of the game). We call BAD the event that A makes a valid decryption query for a ciphertext (c 0 , c 1 , π) where c 0 = c * 0 . Clearly, Game 7 is identical to Game 6 until BAD occurs. We claim that Pr[BAD] ≤ 2 -Ω(λ) , so that Game 6 and Game 7 are statistically indistinguishable. To prove this claim, we distinguish two cases. First, if c * 0 cannot be written as A s + e for some e ∈ Z m of norm e ≤ γ d, the ciphertext is rejected by the rule introduced in Game 6 13 In order for the challenger to test if (c0, c1) ∈ L sound , we need to have the inequality T B • e ∞ < q for any e ∈ Z m+L such that e ≤ γ d. The trapdoor T A allows sampling V ∈ Z m×L in such a way that the Euclidean norm of the lower rows of

T B is O( m 2 + p). The Cauchy-Schwartz inequality implies T B • e ∞ = O( m 2 + p • (γ d))
. Moreover, we have m 2 + p ≤ 2pm and KeyGen imposes the constraint

2 λ p(max i∈[ ],S∈A didS )δσ √ m(γ • d) < q/2 with σ = Ω( √ e • m).
and the two games are identical. Second, since c * 0 is uniformly sampled in Z m q , the probability that there exist (s, e) ∈ Z n q ×Z m such that c * 0 = A s+e and e ≤ γ d is negligible. Indeed, for a fixed e, the probability that such a pair (s, e) exists is at most q n-m when A has full rank (which is the case w.h.p.). Since there are at most (γ d) m integer vectors of norm ≤ γ d and recalling that γ d ≤ K/2, m ≥ n log q and K/2 = q/2p, we find that

Pr[BAD] ≤ q n (2p) m ≤ q n (2p) n log q ≤ q n q n log 2p ≤ 1 q n(log 2p-1) ,
which is negligible since p ≥ 2 and n = poly(λ). This shows the statistical indistinguishability of Game 7 and Game 6 .

Game 8 : We modify the partial decryption oracle for queries ct = (c 0 , c 1 , π)

where c 0 = c * 0 . Recall that these decryption queries must involve a ciphertext of the form (A s + e, c 1 ), where e ∈ Z m has norm e ≤ γ d. Note that the challenger can use its trapdoor T A to compute s and e. Using these, the challenger now ignores e and handles the query as if it was (c 0 , c 1 ) = (A s, c 1 ). This means that the challenger will return ({sk i,τ

• A s + e i,τ } τ ∈[L] , c 1 ). By noting that sk i,τ • e = R τ,ψ -1 (i) • e ∈ Z di is small compared to β s • q in Game 7
, we can prove that the output distributions of the partial decryption oracle in Game 7 and Game 8 are statistically close. This is formally proved in Lemma 5.6, which shows that Game 7 and Game 8 are statistically close.

In Game 8 , we remark that challenger does no longer answer decryption queries (c 0 , c 1 , π) where (c 0 , c 1 ) ∈ L sound and c 0 = c 0 , nor those where c 0 = c 0 and (c 1 , π) = (c 1 , π ). In the proof of Lemma 5.7, we will show that this prevents the adversary from inferring too much information about R by making partial decryption queries for maliciously generated ciphertexts. Consequently, R still retains a lot of entropy after all corruption and partial decryption queries. By applying the Leftover Hash Lemma, Lemma 5.7 then shows that Game 8 is statistically indistinguishable from Game 9 .

Game 9 : In this game, the challenge ciphertext (c 0 , c 1 , π ) is now generated by choosing c 0 ← U (Z m q ) and c 1 ← U (Z L q ) uniformly at random.

In Game 9 , the challenge ciphertext is independent of the challenger's bit, so that the adversary's advantage is clearly zero.

Lemma 5.5. If the NIZK argument system satisfies the OTSS property then Game 5 and Game 6 are computationally indistinguishable.

Proof. Assuming that an adversary A can distinguish between the two games with non-negligible advantage Adv 56 A , we can build an adversary B that breaks the one-time simulation-soundness of the argument system with the same advantage. We now describe how our adversary B proceeds in the experiment of Definition A.2.

The OTSS challenger first runs (A, T

A ) ← TrapGen(1 n , 1 m , q), samples U ← U (Z n×L q
) and constructs the matrix

B = A 0 m×L U K • I L ∈ Z (m+L)×(n+L)
together with its trapdoor

T B = T A 0 m×L V p • I L ∈ Z (m+L)×(n+L) ,
where V ∈ Z m×L is a small-norm matrix sampled using the trapdoor T A such that AV = -pU. The matrix B and the parameters d, γ define the language L = (L zk , L sound ) and a language-recognition trapdoor τ L := T B . The challenger also runs (crs, τ zk ) ← Sim 0 (1 λ , L). The reduction B is given (crs, τ L , L). The adversary A receives from the reduction the public key pk := (A, U, crs).

Observe that B can deduce a trapdoor T A for A from the knowledge of τ L = T B . It can thus use it to sample R according to the distribution D m×L Z,σ conditionally on AR = U.

To answer decryption queries (c 0 , c 1 , π), B first checks that (c 0 , c 1 ) ∈ L sound , which it can always do using T B . If (c 0 , c 1 ) is not in the language L sound , it returns ⊥. Otherwise, it proceeds as in the real decryption algorithm.

In order to generate the challenge ciphertext, the reduction B samples vectors

c 0 ← U (Z m q ), e 0 ← D Z m ,βq , e 1 ← D Z L ,2β•σ √ mq and computes c 1 = R • (c 0 -e 0 ) + e 1 + K • Msg b ∈ Z L q .
Then, it asks the challenger for a simulated proof π ← Sim 1 (crs, τ zk , (c 0 , c 1 )).

Upon receiving π , it returns the ciphertext ct := (c 0 , c 1 , π ) to A. Observe that the reduction B perfectly simulates the adversary's environment in Game 5 .

We define Out to be the event that the adversary A makes a decryption query (c 0 , c 1 , π) that passes the verification test (i.e., Verify(crs, (c 0 , c 1 , π)) = 1) although (c 0 , c 1 ) / ∈ L sound and (c 0 , c 1 , π) = (c 0 , c 1 , π ). If Out never happens, the environment simulated by B is exactly Game 5 , hence Adv 56 A ≤ Pr[Out]. When Out happens, B can use T B to recognize the decryption query (c 0 , c1 , π) for which it occurs and output (c 0 , c1 ), π , in which case it wins the one-time simulationsoundness experiment. This implies Adv 56 A ≤ Pr[Out] ≤ Adv otss B , as claimed. Lemma 5.6. The distributions of the response to a partial decryption query (c 0 , c 1 ) = (A s + e, c 1 ) in Game 7 and Game 8 are statistically close. Proof. To prove the lemma, we rely on Lemma 2.5. We first need to look at the norm of sk i,τ • e. Recall that sk i,τ = M ψ -1 (i) • Φ τ ∈ Z di×m . Since M ∈ {0, 1} d×e is binary and has at most δ = O(log ) non-zero entries per row, we have

sk i,τ • e ∞ ≤ δ • Φ τ • e ∞ ≤ δ • σ √ m • (γ d)
by applying Lemma 2.3 over the rows of Φ τ and using the Cauchy-Schwartz inequality. In any ciphertext ct = (c 0 , c 1 , π) such that c 0 = c * 0 and which is not rejected by the decryption oracle, we know that c 0 = A s+e 0 for some e 0 ∈ Z m of norm e 0 ≤ γ d. Since d = 2βqσ • m(m + L), Lemma 2.5 implies

∆(sk i,τ • e + e i,τ , e i,τ ) ≤ d i δ • σ √ m • γ d β s • q (8) = d i δβ • σ 2 • m √ m + L • γ β s
as the response to a partial decryption query contains d i times the distribution D Zq,βs•q . The statistical distance [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF] becomes exponentially small as we have set

β s > 2 λ (max i∈[ ] d i )δσ 2 γβm √ m + L.
Lemma 5.7. Game 8 and Game 9 are statistically indistinguishable.

Proof. The proof is inspired from [START_REF] Libert | Adaptively secure distributed PRFs from LWE[END_REF]Lemma 4.4]. We start by computing the min-entropy of R conditionally on A's queries and pk. In the case of the partial decryption queries, we observe that, in Game 8 , the adversary can compute partial decryption by itself if it knows

{sk i,τ • A } τ ∈[L] = R τ,φ -1 (i) • A τ ∈[L] = M ψ -1 (i) • Φ τ • A τ ∈[L] ,
which is completely determined by

Φ τ • A = r τ Φj • A .
To assess the entropy of R, we may condition its distribution on Φ τ • A instead of responses to partial decryption queries. Also, we note that Φj is independent of R. This means that only the first row of the matrix is relevant. This implies that decryption queries on ciphertexts (c 0 , c 1 ) ∈ L sound do not reveal more information about R than the public key pk = (A, U).

In order to prove the lemma, it is sufficient to prove the following fact, where we consider partial decryption queries on the challenge ct = (c 0 , c 1 , π ) as if they were corruption queries. Indeed, the involved secret key shares reveal at least as much information as the corresponding partial decryptions for ct * . Fact 1 Let C the set of parties for which the adversary made either a corruption query or a decryption query on the challenge ct = (c 0 , c 1 , π ). Let M C be the sub-matrix of M obtained by stacking up the rows assigned to those parties. For each τ ∈ [L], conditionally on

A , M [ ]\C • Φ τ • A , M C , M C • Φ τ , (9)
the τ -th column r τ = (1, 0, . . . , 0) • Φ τ of R ∈ Z m×L has min-entropy at least

m • log σ - m 2 • log e -n • log q - m 2 m .
Since the set of corrupted servers is not an authorized subset of A, there exists κ ∈ Z e such that κ 1 = 1 and M C • κ = 0 d C . Let a matrix L ∈ Z (e-1)×e whose rows form a basis of the lattice {m ∈ Z e , m, κ = 0}, where the rows of M C live. Note that (L, L•Φ τ ) reveals at least as much information as (M C , M C •Φ τ ). To obtain a lower bound on the entropy of r τ , we condition on (L, L • Φ τ ). When we additionally condition on (A, M [ ]\C • Φ τ • A ), we condition on something that reveals fewer information than (A, Φ τ • A ).

We can now look at the columns of Φ τ = [ρ τ,1 | . . . | ρ τ,m ] ∈ Z e×m independently because of the way Φ τ is sampled. For each i ∈ [m], let a fixed solution ρ τ,i ∈ Z e of L • x = L • ρ τ,i . We may assume that the adversary knows this specific ρ τ,i as it can be obtained from L • ρ τ,i using de-randomized Gaussian elimination. The conditional distribution of ρ τ,i is ρ τ,i + D Λ,σ,-ρ τ,i , where

Λ = {x ∈ Z e , L • x = 0} is the one-dimensional lattice Λ = κ • Z.
We thus know that each column of Φ τ is Gaussian over an affine line. Using this observation, we will prove that conditioning on (A, Φ τ • A ) is not worse than conditioning on (A, (1, 0, . . . , 0) • Φ τ • A = r τ • A ). More precisely, conditionally on (L, L • Φ τ ), the last e -1 rows of Φ τ • A do not reveal more information than the first row.

We know that, for each column ρ τ,i of Φ τ ∈ Z e×m , there exists some integer ξ τ,i such that

ρ τ,i = ξ τ,i • κ + ρ τ,i .
Letting κ = (κ 1 , . . . , κ e ) , we can thus write the j-th row of Φ τ as

(Φ τ ) j = κ j • (ξ τ,1 , . . . , ξ τ,m ) + (ρ τ,1,j , . . . , ρ τ,m,j ), ∀j ∈ [e],
where ρ τ,i = (ρ τ,i,1 , . . . , ρ τ,i,e ) for each i ∈ This means that we can express the j-th row of Φ τ as (Φ τ ) j = κ j • (r τ -(ρ τ,1,1 , . . . , ρ τ,m,1 )) + (ρ τ,1,j , . . . , ρ τ,m,j ).

From the above, we find that conditioning on (A, r τ • A , L, L • Φ τ ) does not reveal less information than conditioning on (A,

Φ τ • A , L, L • Φ τ ).
We now study r τ,i = (1, 0, . . . , 0) • ρ τ,i . Let us write ρ τ,i = c • κ + (ρ τ,i ) ⊥ , for some c ∈ Z, with κ, (ρ τ,i ) ⊥ = 0. We can express the distribution of ρ τ,i as

ρ τ,i + D κZ,σ,-ρ τ,i = ρ τ,i + D κZ,σ,-c•κ-(ρ τ,i ) ⊥ = ρ τ,i + κ • D Z,σ/ κ ,-c
By taking the inner product with (1, 0, . . . , 0), we obtain that the distribution of r τ,i is (ρ τ,i ) ⊥ 1 + c + D Z,σ/ κ ,-c . Since κ ∈ {-1, 0, 1} e and due to our choice of σ, we have σ/ κ = Ω( √ m). By Lemma 2.4, we can conclude that, for each i ∈ [m],

the min-entropy of each r τ,i is at least log σ √ e -2 -m . When we additionally condition on (A, r τ • A ), we decrease the min-entropy of r τ by at most n • log q.

Putting the above altogether, we obtain

H ∞ r τ | (L, L • Φ τ , A, r τ A ) ≥ m • log(σ) - 1 2 log(e) -n • log q - m 2 m
as a lower bound on the entropy of r τ conditionally on responses to all queries.

Let Q the set of responses to corruption and partial decryption queries. For each τ ∈ [L], we thus have

H ∞ r τ | (Q, pk) ≥ m • log σ - m 2 • log e - m 2 m -n • log q
as an entropy lower bound for the τ -th column of

R = [r 1 | . . . | r L ] ∈ Z m×L .
This completes the proof of Fact 1.

To complete the proof of the lemma, we finally have to show that ∆ (pk, a 0 , R a 0 , Q), (pk, a 0 , U (Z L q ), Q) = negl(λ). Before applying the Leftover Hash Lemma, we first rewrite this distance as

(A,V)∈Z n×m q ×Z n×L q ,Q ∈Q Pr [pk = (A, V) ∩ (Q = Q )] • ∆ (a 0 , R a 0 ), (a 0 , U (Z L q )) | (pk = (A, V)) ∩ Q
, where Q denotes the set of all possible answers to A's queries.

Since a 0 is uniformly sampled at the beginning of the game, we can use the Leftover Hash Lemma (Lemma 5.2), even with conditioning. We can thus write

∆ (a 0 , R a 0 ), (a 0 , U (Z L q )) | (pk = (A, V)) ∩ Q = Q ≤ L 2 q • 2 -H∞(r1|(pk=(A,V))∩Q=Q ) (10)
which holds for any set Q of possible partial decryption/corruption queries and any possible public key. Note that we can apply Lemma 5.2 since the inner product {h a0 : Z m → Z q : r → a 0 , r mod q | a 0 ← U (Z m q )} acts as a universal hash family for sources r ∈ Z m such that 2 r ∞ < p for any prime p dividing q. This is the case here w.h.p. as 2 √ mσ < p for all p |q. In order to bound the statistical distance [START_REF] Bellare | Possibility and impossibility results for encryption and commitment secure under selective opening[END_REF], we have shown before that q • 2 -H∞(r1|(pk=(A,V))∩Q=Q ) ≤ 2 log q-(m log σ-(m/2) log e-n log q-m/2 m ) .

By our choice of σ and m = Ω(n log q), we have log σ - 1 2 log e = Ω(log [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF] since m > 4. Since [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF] is bounded by a negligible function of n(λ), we obtain ∆ (pk, a 0 , R a 0 , Q), (pk, a 0 , U (Z L q ), Q) = negl(λ), which shows that Game 8 and Game 9 are statistically indistinguishable.

√ m). This implies m log(σ/ √ e) ≥ n(log q)(log √ m), so that q • 2 -H∞(r1|(pk=(A,V))∩Q=Q ) ≤ 2 m/2 m • q n+1 q n log √ m < 2 • q n+1 q n log √ m
In Supplementary Material D, we show how to modify the scheme to achieve consistency against malicious adversaries.

• Zero-Knowledge: There is a PPT simulator (Sim 0 , Sim 1 ) such that, for any PPT adversary A, we have

| Pr[crs ← Setup(1 λ , L) : 1 ← A P(crs,•,•) (crs)] -Pr[(crs, τ zk ) ← Sim 0 (1 λ , L) : 1 ← A O(crs,τ zk ,•,•) (crs)]| ≤ negl(λ).
Here, P(crs, •, •) is an oracle that outputs ⊥ on input of (x, w, lbl) ∈ R zk and outputs a valid proof π ← P(crs, x, w, lbl) otherwise; O(crs, τ zk , •, •) is an oracle that outputs ⊥ on input of (x, w, lbl) such that (x, w) / ∈ R zk and outputs a simulated argument π ← Sim 1 (crs, τ zk , x, lbl) on input of (x, w, lbl) such that (x, w) ∈ R zk . Note that this simulated proof π is generated independently of the witness w provided as input. 14The notion of soundness captured by Definition A.1 is non-adaptive in that the statement is given as input to the dishonest prover and chosen independently of the common reference string. The stronger notion of adaptive soundness allows the target statement to be chosen by the adversary after having received the common reference string. It is known (see, e.g., [START_REF] Abe | Perfect NIZK with adaptive soundness[END_REF]) that perfect or statistical NIZK arguments cannot provide adaptive soundness under falsifiable assumptions. The reason stems from the impossibility of detecting when the adversary wins and outputs a proof for a false statement. One way to bypass the impossibility results is to consider trapdoor languages, where a trapdoor can be used to recognize false statements. In the context of CCA security, we will consider a notion of adaptive soundness for trapdoor languages.

Definition A.1 captures a notion of multi-theorem zero-knowledge, which allows the adversary to obtain proofs for multiple statements. Feige et al. [START_REF] Feige | Multiple non-interactive zero-knowledge under general assumptions[END_REF] gave a generic transformation of a multi-theorem NIZK argument system from a single-theorem one (where the adversary can only invoke the oracle once).

Simulation-Soundness. We now recall the definition of simulation-soundness of [START_REF] Sahai | Non-malleable non-interactive zero knowledge and adaptive chosenciphertext security[END_REF][START_REF] Santis | Robust non-interactive zero-knowledge[END_REF], which formalizes the adversary's inability to create a new proof for a false statement x even after having seen simulated proofs for possibly false statements {x i } i of its choice.

In the following, in order to allow a challenger to efficiently check the winning condition (ii) in the security experiment, we restrict ourselves to trapdoor languages, where a language-specific trapdoor τ L makes it possible to determine if a given statement x ∈ {0, 1} N belongs to the language. This restriction has no impact on our applications where we always have a membership testing trapdoor τ L at disposal. Definition A.2 ( [START_REF] Sahai | Non-malleable non-interactive zero knowledge and adaptive chosenciphertext security[END_REF][START_REF] Santis | Robust non-interactive zero-knowledge[END_REF]). Let a language L = (L zk , L sound ). A NIZK argument system for L provides simulation-soundness if no PPT adversary has nonnegligible advantage in this game.

1. The challenger chooses a membership testing trapdoor τ L that allows recognizing elements of L sound . Let Sim = (Sim 0 , Sim 1 ) be an efficient NIZK simulator for L. The challenger runs (crs, τ zk ) ← Sim 0 (1 λ , L) and gives (crs, τ L ) to the adversary A. 2. The adversary A is given oracle access to Sim 1 (crs, τ zk , •, •). At each query, A chooses a statement x ∈ {0, 1} N and a label lbl ∈ {0, 1} * . It obtains a simulated argument π ← Sim 1 (crs, τ zk , x, lbl). 3. A outputs (x , lbl , π ).

Let Q be the set of all queries (x i , lbl i , π i ) to Sim 1 (crs, τ zk , •, •) and their responses. The adversary A wins if: (i) (x , lbl , π ) ∈ Q; (ii) x ∈ L sound ; and (iii) V(crs, x , π , lbl ) = 1. The adversary's advantage Adv uss A (λ) is its probability of success taken over all random choices.

The weaker notion of one-time simulation-soundness (which is sufficient for our purpose of constructing CCA-secure TPKE schemes) is defined identically, except that the adversary is only allowed to make one query at stage 2.

A.2 Consistency Definition for TPKE Schemes

This section recalls the definition of consistency considered in [START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF] for threshold public-key encryption schemes. It informally captures the infeasibility of outputting two distinct sets of valid-looking decryption shares for which the Combine algorithm reconstructs different messages. It can easily be shown that consistency is implied by robustness.

Definition A.3 (Consistency).

A TPKE scheme provides consistency if, for any PPT adversary A, the following experiment Expt consist A,TPKE (1 λ ) outputs 1 with negligible probability.

1. On input the security parameter λ, A chooses an access structure A. 2. The challenger samples (pp, pk, sk 1 , sk 2 , . . . , sk ) ← Keygen(1 λ , A) and provides (pp, pk, sk 1 , sk 2 , . . . , sk ) to A. 3. A eventually outputs a forgery (ct * , {µ 0 i , i ∈ S 0 }, S 0 , {µ 1 j , j ∈ S 0 }, S 1 ) where S 0 ∈ A and S 1 ∈ A. Proof. To prove the result, we describe a simulator (Sim 0 , Sim 1 ) which uses the lossy secret key τ zk = tk LPKE to simulate transcripts (a, Chall, z) without using the witnesses. Namely, on input of par ← Gen par (1 λ ), Sim 0 generates crs L by proceeding identically to Gen L DCR while Sim 1 is described hereunder.

Sim 1 (crs, τ zk , x, lbl): On input a statement x ∈ Z * N 2 , a label lbl and the simulation trapdoor τ zk = sk LPKE , algorithm Sim 1 proceeds as follows.

1. Generate a one-time signature key pair (VK, SK) ← G(1 λ ). Then, sample random coins r ← D LPKE R and compute

a ← Π LPKE .Encrypt(pk LPKE , VK, 0 |a | ; r), (12)
where 0 |a | denotes the all-zeroes string of the same length as the first prover message in Π . 2. Compute Chall = Hash(k, (x, a, VK)).

which satisfy a = Π LPKE .Encrypt(pk LPKE , VK, a ; r).

Then, set z = (z , a , r). 5. Generate a one-time signature sig ← S(SK, (x, a, z, lbl)) and output the proof π = VK, (a, z), sig .

We note that Sim 1 in such a way that, in the DCR-based instantiation, the equivocation (13) of Paillier ciphertexts can be conducted without knowing the factorization of the modulus. This will be crucial in the proof of simulationsoundness.

We now prove that the simulation is statistically indistinguishable from proofs generated by the real prover.

The special zero-knowledge property of Π implies that its simulator produces (a , z ) ← ZKSim(crs L , x, Chall) such that (a , Chall, z ) is indistinguishable from a real transcript with challenge Chall. This implies that the distribution

a, a , r, z | r ← D LPKE R , a ← Π LPKE .Encrypt pk LPKE , VK, 0 |a | ; r , (a , z ) ← ZKSim(crs L , x, Chall), (14) r
← Π LPKE .LOpener(pk LPKE , sk LPKE , VK, a, 0 |a | , a ; r) , is indistinguishable from a, a , r, z | r ← D LPKE R , a ← Π LPKE .Encrypt pk LPKE , VK, 0 |a | ; r , (a , st ) ← P (crs L , x, w), (15)
z = P (crs L , x, w, a , Chall, st ), r ← Π LPKE .LOpener(pk LPKE , sk LPKE , VK, a, 0 |a | , a ; r) ,
By the property of efficient opening under lossy keys, we know that the above is statistically indistinguishable from a, a , r, z | (a , st ) ← P (crs L , x, w),

r ← D LPKE R , a ← Π LPKE .Encrypt pk LPKE , VK, a ; r , z = P (crs L , x, w, a , Chall, st ) , (16)
Clearly, the distribution ( 14) corresponds to proof generated by the simulator while ( 16) is the distribution generated by the real prover. This implies that simulated proofs are perfectly indistinguishable from real proofs if the simulator of Π is perfectly special ZK.

B.2 Proof of Theorem 3.4

Proof. We consider a sequence of games where, for each i, we define a variable W i ∈ {true, false} where W i = true if and only if the adversary wins in Game i .

Game 0 : This is the real game of Definition A.2. Namely, the challenger runs (crs, τ zk ) ← Sim 0 (par) and gives crs = (par, crs L , pk LPKE , OTS) to the adversary A. At the same time, the challenger generates a language description L together with a trapdoor τ L in such a way that it can efficiently test if A's output satisfies the winning condition (ii). The adversary is allowed to make one query to the oracle Sim 1 (crs, τ zk , •, •). After having received crs L , A chooses a statement x with a label lbl and the challenger replies by returning a simulated argument π = VK, (a, z), sig ← Sim 1 (crs, τ zk , x, lbl). When A halts, it outputs a triple (x , π , lbl ), where π = VK , (a , z ), sig . The Boolean variable W 0 is set to W 0 = true under the following conditions: (i) (x , lbl , π ) = (x, lbl, π); (ii) x ∈ L; and (iii) V (crs, x , π , lbl ) = 1. We assume w.l.o.g. that the one-time verification key VK is chosen by Sim 1 at the outset of the game. By definition, we have Adv

, τ Σ ) ← TrapGen (par, L DCR , τ L ) instead of crs L ← Gen L (par, L). We immediately have | Pr[W 5 ] -Pr[W 4 ]| ≤ Adv indist-Σ A (λ).
We note that the trapdoor τ Σ produced by TrapGen in Game 5 can be used in later games to compute the BadChallenge function of the trapdoor Σ-protocol Π . In order to evaluate BadChallenge, we also use the injective decryption key sk LPKE which allows decrypting a for any VK = VK .

Since we are done with the indistinguishability properties of Π LPKE , we are free to use sk LPKE (which contains the factorization of the modulus in our DCRbased instantiation) to decrypt the injective LPKE ciphertext a in π .

Game 6 : We now use the decryption algorithm of the lossy PKE scheme Π DCR .

We know that the adversary's output π = VK , a , z , sig involves a verification key VK such that VK = VK unless W 5 = false in Game 5 . This implies that a is an extractable commitment to some a , so that π uniquely determines the message a obtained by decrypting a . We thus consider the relation R bad defined by

x, a, VK , Chall ∈ R bad ⇔ x ∈ L ∧ (17)
Chall = BadChallenge τ Σ , crs L , x, Π LPKE .Decrypt sk LPKE , VK, a . We now set W 6 = false if Hash k, (x , a , VK ) = BadChallenge τ Σ , crs L , x , Π LPKE .Decrypt sk LPKE , VK , a . (18)
for all i ∈ ψ -1 (i) and b ∈ {0, 1}. However, as long as α = a and 1 = V(crs, x, α) we have γ j = r j + s b j mod p q (because we assume that ord(g 2 1 ) divides p q ) for all j ∈ ψ -1 (i), which means that the last probability can be computed as D Z,β (γ j -s b j )/ Pr rj [r j = γ j -s b j mod p q ]. By definition of (α, c, γ), the condition "a = α" can be replaced with "r j = γ j -s b j mod p q for all j ∈ ψ -1 (i)" and

∆(D 0 , D 1 ) ≤ γ j∈ψ -1 (i) D Z,β,s 0 j (γ) -D Z,β,s 1 j (γ)
Finally, we notice that giving {γ j } j∈ψ -1 (i) is equivalent to giving a full transcript (α, 1, γ) as α can be computed with α j,0 = g

4N ζ (γj -s 0 j ) 0 = g 4N ζ (γj -s 1 j ) 0 and α j,1 = g 2(γj -s 0 j ) 1 = g 2(γj -s 1 j ) 1
. This implies the following bound:

∆(D 0 , D 1 ) ≤ j∈ψ -1 (i) ∆(D Z,β,s 0 j , D Z,β,s 1 j )
Since |s 0 j -s 1 j | ∈ 2B, we get ∆(D 0 , D 1 ) ≤ 2d i B/β ≤ 2 1-λ . In order to obtain a trapdoor version of the above Σ-protocol, we can apply the generic transformation of Ciampi et al. [START_REF] Ciampi | On adaptive security of delayed-input Sigma protocols and Fiat-Shamir NIZKs[END_REF]Section 4.2], which uses a semantically secure public-key encryption scheme. In [START_REF] Ciampi | On adaptive security of delayed-input Sigma protocols and Fiat-Shamir NIZKs[END_REF], they show how to turn any standard Σ-protocol with binary challenges into a trapdoor Σ-protocol by having the prover encrypt the two possible responses and send the resulting ciphertexts along with its first message.

In order for this transformation to preserve statistical WI, we need the underlying PKE scheme to be lossy in order to guarantee that the unopened ciphertext leaks no information on the unopened response at each iteration. More precisely, the underlying public key can be set up in lossy mode when we want to ensure statistical WI and in injective mode when we need to argue soundness. Fortunately, Paillier's cryptosystem can be used for this purpose as it is known [START_REF] Young | Questionable encryption and its applications[END_REF][START_REF] Hemenway | Lossy encryption: Constructions from general assumptions and efficient selective opening chosen ciphertext security[END_REF] to be lossy and it does not introduce any additional assumption in our proof of robustness.

The resulting trapdoor Σ-protocol is denoted Π i log with prover P i log and verifier V i log , for all i = 1 to . However, a single CRS denoted crs log can be used by all the protocols. Finally, we assume that each Π i log already repeats the internal arguments with the binary challenge space κ ∈ O(λ) times, and is made non-interactive using a correlation-intractable hash function for the induced badchallenge relation.

C.2 Achieving Robustness in the DCR/LWE-based Scheme

We use the trapdoor Σ-protocols Π i log , one for each server, to turn the CCAsecure TPKE (KeyGen, Encrypt, PartDec, Combine) of Section 4 into a robust TPKE. To this end, we simply augment KeyGen with the global CRS crs log of the Π i log 's and PartDec with the P i log 's, and add the algorithm PartVerify based on the V i log 's. More precisely, Game 2 : In this game we only add yet another restriction on the success of the adversary. We also reject a forgery that would have been accepted in the previous game if there is some j ∈ ψ -1 (i) such that µ j = C 2sj 0 mod N ζ+1 . Since a forgery that would be rejected in this game but accepted in the previous game implies (C 0 , {v j , µ j } j∈ψ -1 (i) ) ∈ L log i while π i is valid, | Pr[W 2 ] -Pr[W 1 ]| is negligible by the soundness of Π i log . In Game 2 , we do not know whether the adversary uses sk i to compute π i . Indeed, for j ∈ ψ -1 (i) it might be the case that A runs P i log with the witness s j + p q or even manages to build the argument without any explicit witness. However, we know that µ j = C 2[sj mod p q ] 0 holds over Z * N ζ+1 for all these indexes as ord(C 2 0 ) divides p q . But, independently of how the argument π i is performed, µ i is equal to the honest execution of (the deterministic) PartDec. Consequently, so is the output of φ • PartDec . We conclude that Pr[W 2 ] = 0.

D Achieving Consistency for the LWE-Based Construction

In order to achieve consistency, we need a non-interactive argument showing that partial decryptions are consistent with public commitments to the secret key shares. To obtain such an argument, we apply the BadChallenge function paradigm to a trapdoor Σ-protocol showing the validity of partial decryptions. We note that a trapdoor Σ-protocol for the same language can be obtained by applying a generic construction due to Ciampi et al. [START_REF] Ciampi | On adaptive security of delayed-input Sigma protocols and Fiat-Shamir NIZKs[END_REF]. Recall that the construction of [START_REF] Ciampi | On adaptive security of delayed-input Sigma protocols and Fiat-Shamir NIZKs[END_REF] turns any standard Σ-protocol with binary challenges into a trapdoor Σ-protocol by having the prover encrypt the two possible responses and send the encrypted responses along with its first message. Here, we provide a direct construction that avoids the overhead of encrypting the two possible responses. In addition, our application to consistency requires the protocol to be statistically witness indistinguishable (we do not rely on NIZK simulation since it would imply to assume erasures at the servers). In this case, using the transformation of [START_REF] Ciampi | On adaptive security of delayed-input Sigma protocols and Fiat-Shamir NIZKs[END_REF] would require the prover to encrypt its two responses using a lossy encryption scheme in lossy mode to ensure statistical WI. With the protocol in this section, we can avoid the additional encryption layer. The trapdoor Σ-protocol presented in this section makes use of rejection sampling techniques, which rely on a core technical lemma from [START_REF] Lyubashevsky | Fiat-Shamir with aborts: Applications to lattice and factoringbased signatures[END_REF][START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF].

Lemma D.1 [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF]Th. 4.6]). Let V be a subset of Z m in which all elements have norms less than T , let σ be a real number such that σ = ω(T √ log m), and

The Cauchy-Schwartz inequality then implies that no sufficiently short vector z w,0 ∈ Z di(m+1) can satisfy the verification equation ( 29 Special Zero-Knowledge. The special ZK property can be shown by applying Lemma D.1. Given a statement

x = c 0 , V i,τ , µ i,τ ∈ Z m q × Z di×n q × Z di q ,
and a challenge Chall * ∈ {0, 1}, the simulator first samples z * w ← D Z d i (m+1) ,σ dec and computes

a * = A dec • z * w -Chall • vi,τ mod q.
It outputs (a * , Chall * , z * w ) with probability 1/M . By construction, the triple (a * , Chall * , z * w ) satisfies the verification conditions w.h.p. We show that it is statistically indistinguishable from a real transcript. If c 0 , V i,τ , µ i,τ ∈ L dec zk , there exists w i,τ ∈ Z di(m+1) of norm w i,τ ≤ β s q • d i (m + 1) such that vi,τ = A dec • w i,τ mod q. The distribution of z w ∈ Z di(m+1) in a real transcript is thus D Z d i (m+1) ,σ dec ,Chall•wi,τ . Then, by Lemma D.1 and our choice of σ dec ≥ log(d i (m + 1)) • β s q • d i (m + 1), the distribution of the simulated z * w is within statistical distance 2 -100 /M from that of a real non-aborting transcript. Finally, in both the real protocol and the simulation, the statement x, the challenge Chall and the response z w uniquely determine a. Witness-Indistinguishability. As explained in Section C.1, to obtain consistency without assuming erasures on behalf of the servers, we rely on the statistical WI of the protocol. We prove this property in the following lemma.

Lemma D.3. The trapdoor Σ-protocol presented above is statistically witnessindistinguishable, assuming the same bounds as in Lemma D.2, i.e., σ dec ≥ log(d i (m + 1)) • β s q • d i (m + 1) and B * > 2σ dec d i (γ 2 d2 + 1)(m + 1).

Proof. Let x = (c 0 , V i,τ , µ i,τ ) ∈ Z m q × Z di×n q × Z di q be a statement interpreted as vi,τ ∈ Z di(n+1) q , and let w

i,τ ∈ Z di(m+1) be two different witnesses for x, i.e., we have: vi,τ = A dec • w

i,τ ≤ β s q • d i (m + 1).

D.2 Modifying the LWE-Based Scheme to Achieve Consistency

Let (KeyGen, Encrypt, PartDec, Combine) be the Dual-Regev-based CCA2-secure TPKE scheme from Section 5. We use the • L protocols Π lwe i,τ , to transform the scheme into a consistent TPKE. To this end, we augment Keygen with the global CRS crs lwe of the Π lwe i,τ 's, augment PartDec with the P lwe i,τ 's, and add algorithm PartVerify based on the V lwe i,τ 's. More concretely, the modifications are as follows.

Keygen (1 λ , A): Run (pp, pk, sk 1 , . . . , sk ) ← Keygen(1 λ , A). Define the language L i lwe = (L i zk , L i sound ) for every i ∈ [ ] using pp and pk 15 , and let crs lwe be their global CRS. Update the public key to pk = (A, U, crs, crs lwe , {V i,τ = A • R τ,ψ -1 (i) , (i, τ ) ∈ [ ] × [L]}), and return (pp, pk , sk 1 , . . . sk ). PartDec (pp, sk i , ct = (c 0 , c 1 , π)): Run µ i = {µ i,τ } τ ∈[L] ← PartDec(pp, sk i , ct), then, for each τ ∈ [L], generate π i,τ = P lwe i,τ (crs lwe , µ i,τ , R τ,ψ -1 (i) ).

Return µ i = {µ i,τ , π i,τ } τ ∈[L] . PartVerify(pp, pk, ct, µ i = {µ i,τ , π i,τ } τ ∈[L] ): First, check that ct = (c 0 , c 1 , π) is a valid ciphertext by running V(crs, (c 0 , c 1 ), π). If it is not, return 0. For every τ ∈ [L], if V lwe i,τ (crs lwe , µ i,τ , π i,τ ) = 0, then return 0. If all the L arguments are valid, return 1.

The CCA security of the TPKE scheme is not affected by the above augmentation, as the additional NIZK arguments are always run honestly or simulated on true statements in the reductions. However, as discussed in Section C.2, for the indistinguishable transition to hold under adaptive corruption, we would need to assume reliable erasure of the decryption-servers' tape. Instead of relying on this additional assumption, we use the statistical WI property established in Lemma D.3. It is sufficient for the reductions to go through, as none of the bits of the key share sk i is revealed in partial decryptions, except for a negligible probability.

Theorem D.4. Let TPKE = (KeyGen , Encrypt, PartDec , PartVerify, Combine) be the augmented scheme, Then, TPKE satisfies the consistency requirement in the sense of Definition A.3.

Proof. Let A be a PPT adversary against the consistency of TPKE . We will show that the advantage of A in the experiment Expt consist A,TPKE (1 λ ) from Definition A.3 is negligible, based on the soundness of Π OTSS and of Π lwe i,τ , for (i, τ ) ∈ [ ] × [L]. To this end, we consider a sequence of games where, for each j, we call W j the event that the adversary wins in Game j . , respectively.

Note that, since (C 1 , C 2 ) ∈ L eq-dcr , we have m 1 = m 2 . Moreover, a valid transcript must contain (Chall, z) ∈ {0, . . . , 2 λ -1}×[0, R] satisfying the following equations over Z:

a 1 = z -m 1 • Chall + k 1 • N 1 ( 30
)
a 2 = z -m 2 • Chall + k 2 • N 2 ,
for some k 1 , k 2 ∈ Z. We remark that valid solutions (z, Chall, k 1 , k 2 ) ∈ Z 4 of the system (30) live in a coset of the two-dimensional lattice

Λ =        (z 1 , z 2 , z 3 , z 4 ) ∈ Z 4 : 1 -m 1 N 1 0 1 -m 2 0 N 2 •     z 1 z 2 z 3 z 4     = 0       
.

Lemma 2 . 3 (

 23 [START_REF] Micciancio | Worst-case to average-case reductions based on gaussian measures[END_REF],Lemma 4.4). For σ = ω( √ log n), there exists a negligible function

Definition 2 .

 2 [START_REF] Boneh | Chosen ciphertext secure public key threshold encryption without random oracles[END_REF] (Adaptive-CCA security for TPKE). A TPKE scheme provides chosen-ciphertext security under adaptive corruptions if no PPT adversary A has non-negligible advantage in the following game.1. On input the the security parameter λ, A chooses an access structure A. 2. The challenger generates (pp, pk, sk 1 , sk 2 , . . . , sk ) ← Keygen(1 λ , A). It sends (pp, pk) to A and initializes an empty set C = ∅. 3. A can adaptively interleave the following queries: -Corruption: A sends the challenger an index i ∈ [ ]. The challenger replies by returning the share sk i and updating the set C = C ∪ {i}. -Partial Decryption: A chooses an index i ∈ [ ] and a ciphertext ct and the challenger returns a partial decryption µ i ← PartDec(pk, sk i , ct). 4. A chooses Msg 0 , Msg 1 ∈ M. The challenger replies with a challenge ciphertext ct * ← Encrypt(pk, Msg b ), where b ← U ({0, 1}) is a random bit. 5. A makes more corruption and partial decryption queries subject to the following condition which must be satisfied at any time. Let C ⊂ [ ] the set of corrupted servers and let C * the subset of indexes j ∈ [ ] such that A made a decryption query of the form (j, ct * ). Then, it is required that C ∪ C * / ∈ A. 6. The experiment ends with A outputting a bit b ∈ {0, 1}. The advantage of A is defined as Adv ind-cca (A) := Pr[b = b] -1 2 .

  (i) For any K ∈ K, the distributions D inj = {(pk, tk) | (pk, sk, tk) ← Keygen(Γ, K)} and D loss = {(pk, tk) | (pk, sk, tk) ← LKeygen(Γ, K)} are computationally indistinguishable. Namely, for any PPT adversary A, we have Adv indist-LPKE A (λ) ≤ negl(λ), where Adv indist-LPKE A (λ) := | Pr[(pk, tk) ← D inj : A(pk, tk) = 1] -Pr[(pk, tk) ← D loss : A(pk, tk) = 1]| .

Definition 3 . 1 .

 31 Let K = {0, 1} and T = {0, 1} , for some ∈ poly(λ). The inequality relation R NEQ : K×T → {0, 1} is the relation where R NEQ (K, t) = 1 if and only if K = t. 3.1 An R NEQ -Lossy PKE Scheme from DCR Our DCR-based R NEQ -lossy PKE scheme goes as follows.

3 .

 3 Let σ > √ λ • e • N ζ be a Gaussian parameter, where e = Ω( (1+ √ 2)/2 ) is the dimension of the matrix M in Section 2.3. Sample a secret key x ← D Z,σ and compute h = g 4N ζ •x 0 mod N ζ+1 . Define the public key pk := (N, ζ, g 0 , h, crs) whereas the centralized secret key sk := x ∈ Z. 4. Share sk using a LISS scheme. To this end, sample ρ = (ρ 2 , . . . , ρ e ) ← (D Z,σ ) (e-1) , define ρ = [x | ρ ] ∈ Z e and compute

Game 0 :

 0 This is the real IND-CCA game. The challenger faithfully answers all queries. In the challenge phase, the adversary A chooses two messages Msg 0 , Msg 1 ∈ Z N ζ . The challenger flips a coin b ← U ({0, 1}) and computes the challenge ciphertext ct * = (C * 0 , C * 1 , π ) by running the real encryption algorithm. When A halts, it outputs b ∈ {0, 1} and we denote by W 0 the event that b = b. By definition, Adv ind-cca (A) := | Pr[W 0 ] -1/2|.

Game 1 : 2 :

 12 This game is identical to Game 0 except that we change the generation of the common reference string and the generation of π in the challenge ciphertext. In the key generation phase, the challenger runs (crs, τ zk ) ← Sim 0 (1 λ , L DCR ). In the challenge ciphertext ct = (C 0 , C 1 , π ), the NIZK argument π is simulated as π ← Sim 1 crs, τ zk , C 0 , C 1 without using the witness. From the perfect zero-knowledge property of Π OTSS , Game 1 is indistinguishable from Game 0 and Pr[W 1 ] = Pr[W 0 ]. Game This game is identical to Game 1 except that we change the generation of the challenge ciphertext ct = (C 0 , C 1 , π ). Now, the challenger first samples z 0 ← U (Z * N ), which is used to compute z = z N ζ 0 mod N ζ+1 and then

Game 6 :

 6 We finally modify the challenge ciphertext and now compute (C 0 , C 1 ) by sampling C 0 ← QR N ζ+1 as a random quadratic residue in Z * N ζ+1 and computingC 1 = (1+N ) Msg •C 0 2x mod N ζ+1 for a random Msg ← U (Z N ζ). Lemma 4.2 shows that Game 6 and Game 5 are negligibly far apart in terms of statistical distance, so that | Pr[W 6 ] -Pr[W 5 ]| ≤ 2 -λ .In Game 6 , we have Pr[W 6 ] = 1/2 since ct is completely independent of the challenger's bit b ∼ U ({0, 1}).

Lemma 4 . 2 .

 42 Game 6 and Game 5 are statistically indistinguishable. Proof. The proof uses similar arguments to [6, Theorem 5]. In Game 5 , the challenge ciphertext has components (C 0 , C 1 ) of the form

  and share each column independently. Namely, for each τ ∈ [L], sample Φτ ← (D Z,σ ) (e-1)×m and set

  [m]. Since κ 1 = 1, this gives us an explicit expression of the ξ τ,i 's:(ξ τ,1 , . . . , ξ τ,m ) = (Φ τ ) 1 -(ρ τ,1,1 , . . . , ρ τ,m,1 ) = r τ -(ρ τ,1,1 , . . . , ρ τ,m,1 ).

4 . 3 B. 1

 431 Outputs 1 only if PartVerify(pk, ct * , µ b i ) = 1 for all b ∈ {0, 1} and i ∈ S b and Combine(pk, (S 0 , {φ(µ * i )} i∈S0 ), ct) = Combine(pk, (S 1 , {φ(µ * j )} j∈S1 ), ct). Note that φ is the identity function for non-robust TPKE. B Deferred Proofs for the NIZK Argument of Section Proof of Theorem 3.3

D. 1 A

 1 Trapdoor Σ-Protocol Showing Correctness of Partial Decryptions of the LWE-Based TPKE Scheme

  ) for the challenge b = 0 since B * /2 > σ dec d i (γ 2 d2 + 1)(m + 1). Hence, if a bad challenge exists at all, it can only be b = 1.For the same reason, the condition∃k ∈ [d i ] : ([-s | 1] ⊗ e k ) • (a + vi,τ ) mod q > B * /2,is incompatible with the existence of a valid response z w,1 ∈ Z di(m+1) satisfying (29) for the challenge b = 1.

( 1 )

 1 i,τ = A dec • w

  The above construction provides one-time simulation-soundness if: (i) OTS is a strongly unforgeable one-time signature; (ii) Π LPKE is an R NEQlossy PKE scheme; (iii) The hash function family H is correlation-intractable for all relations that are searchable within time T , where T denotes the maximal running time of algorithms BadChallenge(•, •, •, •) and Π LPKE .Decrypt(•, •, •).

	Theorem 3.4. (The
	proof is given in Supplementary Material B.2.)
	4 An Adaptively Secure CCA2-Secure Threshold
	Encryption Scheme Based on Paillier and LWE
	Theorem 3.3. The above argument is statistically (resp. computationally) zero-
	knowledge if: (i) Π LPKE is statistically equivocable under lossy keys; (ii) The trap-
	door Σ-protocol Π is statistically (resp. computationally) special zero-knowledge.
	(The proof is given in Supplementary Material B.1.)

  3. Run the ZK simulator (a , z ) ← ZKSim(crs L , x, Chall) of Π to obtain a simulated transcript (a , Chall, z ) of Π for the challenge Chall. 4. Using the trapdoor key tk LPKE , compute random coins r ∼ D pk LPKE ,a ,a,VK which explain a as a lossy encryption of a under the tag VK. Namely, compute r ← Π LPKE .LOpener(pk LPKE , sk LPKE , VK, a, 0 |a | , a ; r)

  Game 1 : This is like Game 0 except that the challenger sets W 1 = false if A out-The strong unforgeability of OTS implies that Pr[W 1 ] cannot significantly differ from Pr[W 0 ] as B readily implies a forger such that| Pr[W 1 ] -Pr[W 0 ]| ≤ Adv ots B (λ).Game 2 : We modify the generation of crs. Namely, we now generate the lossy keys of Π LPKE as (pk LPKE , sk LPKE , tk LPKE ) ← Π LPKE .LKeygen(Γ, VK) instead of (pk LPKE , sk LPKE , tk LPKE ) ← Π LPKE .LKeygen(Γ, 0 L ). By the second indistinguishability property of Π LPKE , we know that changing the initialization value does not significantly affect A's view as the two distributions of pk LPKE are statistically close. It follows that | Pr[W 2 ] -Pr[W 1 ]| ≤ 2 -Ω(λ) . Game 3 : We modify the oracle Sim 1 (crs, τ zk , •, •) and by using the equivocation property of Π LPKE for lossy tags (instead of lossy keys). To simulate an argument for (x, lbl) to Sim 1 (crs, τ zk , •, •) uses the lossy tag VK (recall that lossy keys are generated as (pk LPKE , sk LPKE , tk LPKE ) ← Π LPKE .LKeygen(Γ, VK)) to equivocate a using the trapdoor key tk LPKE instead of the lossy secret key sk LPKE of Π LPKE . Namely, at step 4 of Sim 1 , the modified Sim 1 (crs, τ zk , •, •) computes random coins r ← Π LPKE .Opener(pk LPKE , tk LPKE , VK, a, 0 |a | , a , r) instead of running LOpener using sk LPKE . We define the Boolean variable W 3 exactly as W 2 . Since Opener and LOpener sample from the same distribution D LPKE R over R LPKE , we have | Pr[W 3 ] -Pr[W 2 ]| ≤ 2 -Ω(λ) . Game 4 : We change the distribution of pk LPKE in the common reference string crs. At step 3 of Gen L , we generate the keys for Π LPKE as injective keys (pk LPKE , sk LPKE , tk LPKE ) ← Π LPKE .Keygen(Γ, VK) instead of generating them as lossy keys (pk LPKE , sk LPKE , tk LPKE ) ← Π LPKE .LKeygen(Γ, VK). The indistinguishability property (i) of Π LPKE ensures that Pr[W 4 ] and Pr[W 3 ] are negligibly far apart. Recall that this indistinguishability property ensures that the distributions of pairs (pk LPKE , tk LPKE ) produced by Keygen and LKeygen are computationally indistinguishable. We can thus easily build a distinguisher B against Π LPKE that transitions from Game 4 to Game 5 (in particular, the reduction has tk LPKE at disposal to simulate Sim 1 (crs, τ zk , •, •)). It comes that | Pr[W 4 ] -Pr[W 3 ]| ≤ Adv indist-LPKE-1 Game 5 : We change again the distribution of crs = (par, crs L , pk LPKE , OTS) by relying on the CRS indistinguishability property of the trapdoor Σ-protocol Π . Namely, we use the TrapGen algorithm of Definition 2.21 to generate crs L as (crs L

1-ss A (λ) = Pr[W 0 ]. puts a fake proof (x , π , lbl ), where π = VK , (a , z ), sig recycles the one-time verification key used by Sim 1 (i.e., VK = VK). B (λ).

An alternative approach, suggested in[START_REF] Rabin | A simplified approach to threshold and proactive rsa[END_REF][START_REF] Almansa | Simplified threshold RSA with adaptive and proactive security[END_REF], requires each participant to store backup shares of other participant's shares in such a way that the missing contributions of faulty servers can be reconstructed. However, it still requires additional interaction.

When t, = O(log λ), statically secure schemes can be proven adaptively secure by guessing the set of corrupted servers upfront.

Faust et al.[START_REF] Faust | On the non-malleability of the Fiat-Shamir transform[END_REF] showed that Fiat-Shamir provides simulation-soundness "for free" in the ROM. However, their proof crucially relies on the random oracle modeling of hash functions and it is not known to immediately carry over to the standard model.

Note that a threshold-t function can be obtained from the majority function by fixing the desired number of input bits, so that we need a majority function of size ≤ 2 to construct a threshold function T t, .

It helps defining robustness. For non-robust TPKE, φ is the identity function.

While the rate can be optimized via hybrid encryption, this would ruin the votingfriendly property of the scheme[START_REF] Bernhard | Adapting helios for provable ballot privacy[END_REF]. Moreover, the KEM/DEM framework does not immediately work in the threshold setting (see, e.g.,[START_REF] Abe | Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of kurosawa-desmedt KEM[END_REF]).

In particular, this implies that all prime factors of q are Ω( √ e • λ 2 • log q). In the case of threshold access structures A = T t, , this becomes Ω( (1+ √ 2)/2 • λ 2 • log q).

In particular, Sim1 can be run on any statement x, even x / ∈ L sound .

Note that L i lwe is the same for all L sub-protocols corresponding to the i-th server.

Acknowledgements

Part of this research was funded by the French ANR ALAMBIC project (ANR-16-CE39-0006). This work was also supported in part by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701). Khoa Nguyen was supported in part by the Gopalakrishnan -NTU PPF 2018, by A*STAR, Singapore under research grant SERC A19E3b0099, and by Vietnam National University HoChiMinh City (VNU-HCM) under grant number NCM2019-18-01.

In our proof of CCA2-security under adaptive corruptions, we will use the following lemmas. Lemma 5.2 ( [START_REF] Agrawal | Efficient lattice (H)IBE in the standard model[END_REF]). Let H = {h : X → Y } h∈H be a family of universal hash functions, for countable sets X, Y . For any random variable T taking values in X, we have ∆ (h, h(T )), (h, U (Y )) ≤ 1 2 • 2 -H∞(T ) • |Y |. More generally, let (T i ) i≤k be independent random variables with values in X, for some k > 0. We have ∆ (h, (h(T i )) i≤k ), (h, (U (Y ) Lemma 1]). Let q, m, be positive integers and r a positive real satisfying r > max(ω( √ log m), ω( √ log )). Let b ∈ Z m q and x ← D Z m ,r . Then, for any V ∈ Z m× and any positive real σ > V , there exists a PPT algorithm ReRand(V, b + x, r, σ) that outputs b = V b + x ∈ Z q where x is distributed statistically close to D Z ,2rσ .

Theorem 5.4. Under the LWE n,q,β,m assumption, the above scheme provides IND-CCA security under adaptive corruptions in the standard model.

Proof. We are going to prove the theorem by proving that all the following games are computationally indistinguishable for a fixed b ∈ {0, 1}.

Game 0 : This is the real experiment Expt CCA A,TPKE,b (1 λ ), where the challenger's bit is b ∈ {0, 1}. In this game, the challenger faithfully answers all queries (partial decryption and/or corruption). It also computes the challenge ciphertexts ct * = (c * 1 , c * 0 ) by running the real encryption algorithm. Game 1 : This game is identical to Game 0 except that we change the generation of the common reference string and the generation of the proof of the challenge ciphertext. In the key generation phase, the challenger runs (crs, τ zk ) ← Sim 0 (1 λ , L). In the challenge ciphertext ct * = (c * 0 , c * 1 , π * ), the NIZK argument π * is simulated as π * ← Sim 1 crs, τ zk , (c * 0 , c * 1 ) without using the witnesses. By the zero-knowledge property of the argument system, Game 1 is indistinguishable from Game 0 .

Game 2 : We modify the generation of ct * = (c * 0 , c * 1 , π * ). When the adversary declares the challenge messages (Msg * 0 , Msg * 1 ), the challenger first defines c * 0 = A • s + e, where s ← U (Z n q ), e ← D Z m ,βq . Then, it uses the ReRand algorithm of Lemma 5.3 to compute

Lemma 5.3 implies that A's view remains statistically unchanged since we have

Game 2 is thus statistically indistinguishable from Game 1 .

Game 3 : We change again the construction of ct * = (c 0 , c 1 , π ) in the challenge phase. Instead of sampling c 0 from the LWE distribution, we now sample it uniformly as c 0 ← U (Z m q ). Under the LWE n,q,β,m assumption, this game is computationally indistinguishable from Game 2 .

Supplementary Material

A Other Definitions for Cryptographic Primitives

A.1 Non-Interactive Zero-Knowledge and Simulation-Sound Arguments

We recall the definitions of NIZK proofs. Since it is sufficient for our applications, we allow the common reference string to be generated as a function of the language L (analogously to quasi-adaptive NIZK proofs [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF]). We actually give a slightly different definition than the standard ones, defining NIZK for gap languages. That is, a language is defined by a pair of language L zk ⊆ L sound , and completeness is guaranteed for statements in L zk while soundness is guaranteed for statement outside L sound . This is sufficient for our purpose.

In addition, we consider NIZK argument systems where each argument comes with a label lbl taken as input by both the prover and the verifier. Labels will only be useful when we consider simulation-soundness, which is necessary in our CCA-secure encryption schemes.

Definition A.1. A non-interactive zero-knowledge (NIZK) argument system Π for a language L = (L zk , L sound ) associated to two NP relations (R zk , R sound ) consists of four PPT algorithms (Gen par , Gen L , P, V) with the following syntax:

• Gen par (1 λ ) takes as input a security parameter λ and outputs public parameters par. • Gen L (1 λ , L, τ L ) takes as input a security parameter λ, the description of L which specifies a statement length N , and a membership testing trapdoor τ L for L. It outputs the language-dependent part crs L of the common reference string crs = (par, crs L ). • P(crs, x, w, lbl) is a proving algorithm taking as input the common reference string crs, a statement x ∈ {0, 1} N , a witness w such that (x, w) ∈ R zk and a label lbl. It outputs a proof π. • V(crs, x, π, lbl) is a verification algorithm taking as input a common reference string crs, a statement x ∈ {0, 1} N , and a proof π. It outputs 1 or 0.

Moreover, Π should satisfy the following properties. For simplification we denote below by Setup an algorithm that runs successively Gen par and Gen L to generate a common reference string.

• Completeness: For any (x, w) ∈ R zk and any lbl ∈ {0, 1} * , we have

• Soundness: For any x ∈ {0, 1} N \ L sound and any PPT prover P * , we have

Otherwise, we set W 6 = W 5 . If x ∈ L, we note that, unless Π LPKE fails to correctly decrypt under injective tags, π cannot be accepted by the verifier if inequality (18) holds. By the statistical decryption correctness of Π LPKE , we have

In Game 6 , we have Pr[W 6 ] ≤ Adv CI A (λ) because, if the adversary outputs a valid π = VK , a , z , sig for x ∈ L, we necessarily have

which breaks the correlation intractability of H for the relation R bad .

Putting the above altogether, we obtain

which completes the proof.

C Achieving Robustness in the TPKE of Section 4

In this section, we show how to obtain robustness against malicious adversaries using trapdoor Σ-protocols and correlation-intractable hash functions.

C.1 A Σ-Protocol Showing Equality of Two Discrete Logarithms in the DCR Setting

In order to achieve robustness in the DCR-based scheme of Section 4, we need to prove equalities between discrete logarithms in a group of hidden order. To do this, we adapt a standard Σ-protocol due to Chaum and Pedersen in [START_REF] Chaum | Wallet databases with observers[END_REF] for the language

, where d i is the size of the set ψ -1 (i) ⊂ {1, . . . , d}. This language can be described by crs L := (g 0 , N = pq, ζ, (M, ψ), B, B * ) with p, q two primes chosen as in the KeyGen algorithm of the TPKE scheme and g 0 , g 1 ∈ Z N ζ+1 , and B ∈ N is a guaranteed upper bound on the magnitude of witnesses when they actually have magnitude B < B * . In the scheme of Section 4, witnesses are share units

, where we may set e = O( 1+ √ 2 ) using the LISS scheme of Benaloh and Leichter [START_REF] Benaloh | Generalized secret sharing and monotone functions[END_REF]. Membership of the language L log i thus only guarantees a looser upper bound on |s j |, but it does not affect robustness.

The Σ-protocol is described as follows:

Gen(1 λ ): This algorithm sets crs L = (g 0 , N = pq, ζ, (M, ψ), B, B * ) by choosing β > 2 λ dB, where d is the number of rows of M ∈ Z d×e , and B * = 2β. It returns crs := (crs L , β).

P(crs, x, w) ↔V(crs, x): Given a crs describing a language L log i and a statement x = g 1 , {h i,j , µ i,j } j∈ψ -1 (i)

P and V write ψ -1 (i) = {j 1 , . . . , j di } and define h i = (h i,j1 , . . . , h i,j d i ), µ i = (µ i,j1 , . . . , µ i,j d i ). Then, they proceed as follows:

1. P samples r ← D Z d i ,β and sends

as a first message to V. 2. V chooses a challenge Chall ∈ {0, 1} and returns it to P. 3. P using the witness w = {s j } j∈ψ -1 (i) to define w = (s j1 , . . . , s

Otherwise, it returns 0.

Assuming that P and V follow the protocol, it is easy to see that V will always accept but with negligible probability. We now prove other properties.

Special Zero-Knowledge: On input a tuple (crs, x, Chall), where the state-

The final transcript is (a 0 , a 1 ), Chall, z . The difference between the simulated distribution of z its distribution in a real transcript is the center of the Gaussian: In the former case the center is 0 di whereas, in the latter case, the center is Chall • w. From Lemma 2.5, we can bound the distance between the two distributions as

We also note that, if g 1 is an N ζ -th residue and x ∈ L log i , (a 0 , a 1 ) is uniquely determined by Chall ∈ {0, 1} and the statement since g 4N ζ 0 and g 2 1 both generate the subgroup of 2N ζ -th residues in Z * N ζ+1 . We conclude that (20) also bounds the distance between the distribution of a real transcript (for fixed Chall) and the distribution of a transcript produced by ZKSim.

Special Soundness: Let us assume that g 1 is an N ζ -th residue in Z * N ζ+1 . Let us assume that two valid transcripts (a 0 , a 1 ), 0, z , (a 0 , a 1 ), 1, z exist for the challenges 0 and 1 with z , z ≤ B * /2. Then, the following holds:

Hence, there can be at most one bad challenge if x ∈ L log i . Witness-indistinguishability: We rely on Lemma C.1 which shows that the Σ-protocol provides statistical witness-indistinguishability.

In order to obtain robustness without assuming erasures on behalf of the servers, we rely on the statistical WI property of the scheme. The reason is that, if we were to use the NIZK simulator in the proof of CCA security under adaptive corruptions, the simulator would have to explain simulated proofs as if they had been honestly generated. Instead of relying on erasures as a loophole, we exploit the statistical WI property to argue that, even if WI proofs of correct partial decryptions are faithfully generated by the challenger, they do not decrease the entropy of shares from the adversary's view.

Lemma C.1. The above Σ-protocol for the language L log i is statistically witnessindistinguishable assuming that the order of g 2 1 modulo N ζ+1 divides p q . Proof.

|p q be a statement such that sk 0 i = {s 0 j } j∈ψ -1 (i) and sk 1 i = {s 1 j } j∈ψ -1 (i) are two witnesses for x. In particular, for all j ∈ ψ -1 (i), h i,j = g

and then s 0 j -s 1 j ∈ p q Z. We define the following probability distributions, for b = 0, 1, where V is an adversary that chooses challenges.

To prove witness-indistinguishability, we need to prove that D 1 is indistinguishable from D 2 . Since the distributions restricted to a are equal, Chall is independent of the witness. Therefore, it is easy to see that if Chall = 0, the distributions are the same and we have

KeyGen (1 λ , A): Run (pp, pk, sk 1 , . . . , sk ) ← KeyGen(1 λ , A), where the secret key shares are contained in the components of s = M • ρ = (s 1 , . . . , s d ) .

Compute the verification key vk

Define the language L log i for every 1 ≤ i ≤ using pp and pk, and let crs log be their global CRS. Update the public key pk = (pk, vk, crs log ) and return pp, pk , sk 1 , . . . , sk

to prove that the partial decryption was honestly computed. In that case, return µ i = (µ i , π i ).

PartVerify(pp, pk , ct = (C 0 , C 1 , π), µ i = (µ i , π i )): Given a partial decryption µ i from server i, verify it by running V i log (crs log , (C 0 , {v j , µ j } j∈ψ -1 (i) ), π i ) and V(crs, C 0 , π, lbl). Return 1 if both returned 1, and 0 otherwise.

The CCA security of the TPKE is not affected by this augmentation as the additional arguments of membership for the languages L log i are always run honestly or simulated on true statements in the reductions. Nevertheless, such a strategy would require assuming reliable erasure of the decryption-servers' tape for the indistinguishable transition to hold under adaptive corruption. However, by relying on lemma C.1, the statistical witness indistinguishability is enough as none of the uncorrupted decryption parties' bits of s j mod N ζ is revealed in partial decryptions but with negligible probability. Therefore, we can still rely on the fact that the secret key x keeps its entropy until x mod N ζ is used to emulate the challenge ciphertext in Equation ( 5) of the security proof.

Theorem C.2. Let TPKE = (KeyGen , Encrypt, PartDec , PartVerify, Combine) with φ(µ i , π i ) := µ i . Then, TPKE is robust (according to definition 2.17).

Proof. Let A be a PPT adversary against the robustness of TPKE'. Given (pp, pk , sk 1 , . . . , sk ) ← KeyGen (1 λ , A), the goal of the adversary is to build of forgery (ct = (C 0 , C 1 , π), (µ i , π i ), i), which means that µ i is not in the range of PartDec(pp, sk i , ct := (C 0 , C 1 , π)) (since φ • PartDec = PartDec) while we also have PartVerify(pp, pk , ct, (µ i , π i )) = 1.

We consider a sequence of games where, for each i, we call W i the event that the adversary wins in Game i .

Game 0 : This is the real game of robustness as recalled above. More precisely,

This game is like the previous game except that we keep the factorization of N during the generation of pk. Moreover, we no more consider A to be successful if it outputs a forgery such that C 2p q

since producing a valid ciphertext such that C 0 ∈ L DCR would contradict the soundness (and thus the one-time simulation-soundness) of the NIZK argument system Π OTSS . h : V → R be a probability distribution. Then, there exists a real number M such that the distribution of the following algorithm A:

M from the distribution of the following algorithm F:

Moreover, the probability that A outputs something is at least 1-2 -ω(log m)

M

. More concretely, if σ = αT for any positive α, then M = e 12/α+1/(2α 2 ) , the output of A is within statistical distance 2 -100 /M of the output of F, and the probability that A outputs something is at least 1-2 -100 M .

In order to achieve consistency in the LWE-based scheme of Section 5, the Setup algorithm additionally computes

so that each server i ∈ [ ] is assigned a verification key vk i = {V i,τ } τ ∈[L] , which will serve as a commitment to the secret key share

In order to enforce consistency, each partial decryption will come with a NIZK argument of consistency with the matrices {R τ,ψ -1 (i) } τ ∈[L] hidden in vk i . Such a NIZK/NIWI argument can be obtained from the trapdoor Σ-protocol described hereafter.

Consider a ciphertext ct = (c 0 , c 1 , π). We will give a trapdoor Σ-protocol for the language

where B r < B e ≤ β s q √ d i . To ease the description, let us define matrices

55

Then, let

We also define

for each k ∈ [d i ], as well as

To prove membership of L dec zk , a natural idea is to prove the existence of a smallnorm

We now observe that, if the pair (c 0 , c 1 ) belongs to the language L sound of Section 5 (i.e., if there exist vectors s ∈ Z n q and e 0 ∈ Z m such that e 0 ≤ γ d and c 0 = A • s + e 0 ), then L dec zk is contained in the language

and where e k ∈ Z di stands for the k-th

defined in ( 23)- [START_REF] Canetti | Adaptive security for threshold cryptosystems[END_REF].

Gen par (1 λ ) : On input of a security parameter λ ∈ N, choose moduli q, p with q = p • K, dimensions n, m, and error rate α > 0 and a Gaussian parameter

. Define public parameters par = {λ, q, p, n, m, α, σ dec }. Gen L (par, L dec ) : Takes in global parameters par and the description of a language L dec = (L dec zk , L dec sound ) specifying a real B * > 0 such that B * > 2σ dec d i (γ 2 d2 + 1)(m + 1), and a matrix A dec from the distribution [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF]. It defines the language-dependent crs L = {A dec , B * }. The global CRS is crs = {λ, q, p, n, m, α, σ dec }, {A dec , B * } .

TrapGen(par, L, τ L ) : Given par and a language description L dec that specifies B * > 0 satisfying the same constraint as in Gen L , a matrix A dec sampled from the distribution [START_REF] Camenisch | Practical verifiable encryption and decryption of discrete logarithms[END_REF], as well as a membership-testing trapdoor τ L = T A ∈ Z m×m for L dec sound , output crs L = {A dec , B * }. The global CRS is crs = {λ, q, p, n, m, α, σ dec }, {A dec , B * } and the trapdoor τ Σ = T A ∈ Z m×m .

P crs, x, w ↔ V(crs, x) : Given crs and a statement

of the form described in ( 23)- [START_REF] Canetti | Adaptive security for threshold cryptosystems[END_REF]. Then, they conduct the following steps. m+1) satisfying [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen-ciphertext attacks[END_REF]. Then, it samples a Gaussian vector r w ← D Z d i (m+1) ,σ dec . It computes the following which is sent to V :

P encodes the witness w

2. V sends a random challenge Chall ∈ {0, 1} to P .

P computes z

(zw) , 1 , where M = e 12/ log(di(m+1))+1/(2 log 2 (di(m+1))) .

With probability 1 -θ, P aborts. 4. Given z w ∈ Z di(m+1) , V checks if z w ≤ σ dec d i (m + 1) and

If these conditions do not both hold, V halts and returns ⊥.

BadChallenge par, τ Σ , crs, x, a : Given the trapdoor

, parse the first prover message as a ∈ Z di(n+1) q and conduct the following steps.

Using T

then return Chall = 1 -d. Otherwise, return Chall =⊥.

Lemma D.2. The above construction is a trapdoor Σ-protocol for L dec if we set

Proof. By construction, the protocol has completeness with probability negligibly close to θ. We now prove that it satisfies special soundness, correctness of BadChallenge and special zero-knowledge.

Special Soundness. Let us assume that (c 0 , c 1 ) ∈ L sound (so that there exists s ∈ Z n q such that c 0 -A s ≤ γ d) and, for a given a ∈ Z di(n+1) q

, there exist two valid responses

Subtracting them yields vi,τ = A dec • (z w,1 -z w,0 ) mod q, where z w,1 -z w,0 ≤ 2σ dec • d i (m + 1). Moreover, we also have

which implies that (c 0 , V i,τ , µ i,τ ) ∈ L dec sound since we assumed (c 0 , c 1 ) ∈ L sound and

Correctness of BadChallenge. We now show that BadChallenge provides the correct output. Assuming that (c 0 , c 1 ) ∈ L sound , the trapdoor T A allows computing the vector s ∈ Z n q such that c 0 -A s ≤ γ d. We also assume (c 0 , V i,τ , µ i,τ ) ∈ L dec sound . For a given a ∈ Z di(n+1) q

, we cannot simultaneously have

as this would imply

If the statement is false and (c 0 , V i,τ , µ i,τ ) ∈ L dec sound , there must exist k ∈ [d i ] and d ∈ {0, 1} such that inequality (28) holds. Now, let us first assume that

To prove statistical WI, we will demonstrate that if no abort occurs, then the following 2 distributions are statistically indistinguishable:

Since the distributions are restricted to the same a, the distribution of Chall is independent of the witnesses. Therefore, it can be seen that when Chall = 0, the 2 distributions are identical, and we have ∆(D 1 , D 2 ) = ∆(D 1 , D 2 ), where distributions D 1 , D 2 are defined as

To this end, let us consider the following distribution:

By Lemma D.1, in the non-aborting case, for a pair (a, z

w ) from D 1 , the distribution of z By the same argument, we also have ∆(D 2 , D) ≤ negl(λ) and thus

which proves the claim.

Parallel repetitions and non-interactive versions. We note that the trapdoor Σ-protocol presented in this section works with binary challenge, and hence, admits a soundness error of 1/2. This error can be made negligibly small via O(λ) parallel repetitions. Then, using the transformation suggested in [START_REF] Libert | Simulation-sound arguments for LWE and applications to KDM-CCA2 security[END_REF], we can obtain a non-interactive protocol in the standard model. For each i ∈ [ ] and each τ ∈ [L], we will denote the resulting protocol as Π lwe i,τ , with prover P lwe i,τ and verifier V lwe i,τ . A global CRS, denoted by crs lwe , can be used for all • L protocols. We will use these notations in the next section. ), we generate it together with a trapdoor T A via (A, T A ) ← TrapGen(1 n , 1 m , q). The properties of TrapGen ensure that the distribution of A is statistically close to U (Z n×m q ). Therefore, we have

Game 2 : In this game, we use the trapdoor T A to test whether there exists s ∈ Z n q satisfying c * 0 -A s ≤ γ d, and if this is not the case, we no longer consider A to be successful. Clearly,

∈ L sound would contradict the soundness of the NIZK argument system Π OTSS . Game 3 : Recall that, in the previous games, for all i ∈ S 0 and j ∈ S 1 , we have

such that all the pairs (µ 0 i,τ , π 0 i,τ ), (µ 1 j,τ , π 1 j,τ ) pass the verifications of algorithm PartVerify. In particular, we have

In this game we add yet another restriction on the success of the adversary. We also reject a forgery that would have been accepted in the previous game if there exists s ∈ Z n q satisfying c * 0 -A s ≤ γ d, but -Either there exists a pair (i, τ ) ∈ S 0 × [L], for which there does not exist

-Or there exists a pair (j, τ ) ∈ S 1 × [L], for which there does not exist y j,τ ∈ Z dj satisfying

Note that, the existence of such a pair (i, τ ) (resp., (j, τ )) would contradict the soundness of the argument system Π lwe i,τ (resp., Π lwe j,τ ) , since it would imply that (c * 0 , V i,τ , µ 0 i,τ ) ∈ L i sound (resp., (c * 0 , V j,τ , µ 1 j,τ ) ∈ L j sound ), yet V lwe i,τ (crs lwe , µ 0 i,τ , π 0 i,τ ) = 1 (resp., V lwe j,τ (crs lwe , µ 1 j,τ , π 1 j,τ ) = 1) at the same time. Therefore, by the soundness of Π lwe i,τ (resp., Π lwe j,τ ), we have

We now demonstrate that the adversary cannot win in Game 3 . Indeed, since S 0 and S 1 are authorized sets, by construction, there must exist coefficients

Then, based on the norm bounds of y i,τ , y j,τ , we obtain that This concludes the lemma.

E On the Soundness of a Σ-Protocol Proving Plaintext Equalities Between Paillier Ciphertexts

In this section, we analyze the soundness of a Fiat-Shamir-based non-interactive proof system showing plaintext equalities between Paillier ciphertexts generated for distinct moduli. This proof system was used in a Paillier-based threshold cryptosystem proposed by Fouque and Pointcheval [START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF]Section 4.2].

Let us further assume that m 1 = N 1 -1 and m 2 = N 2 -1 (in which case (C 1 , C 2 ) ∈ L eq-dcr since N 1 = N 2 ). Then, z (z 1 , z 2 , z 3 , z 4 ) = (-1, 1, 1, 1) belongs to Λ.

A cheating prover can thus initially encrypt C 1 = g m1 1

• w N1 1 mod N 2 1 and C 2 = g m2 2 •w N2 2 mod N 2 2 , with w 1 ← U (Z * N1 ), w 2 ← U (Z * N2 ). Then, it can run the HVZK simulator by choosing Chall = 2 λ -1, z ← U ([0, R -2 λ ]), z1 ← U (Z * N1 ), z2 ← U (Z * N2 ) and computing

which implicitly yields a solution (z, Chall, k1 , k2 ) ∈ Z 4 to the system [START_REF] Cramer | Modular design of secure, yet practical cryptographic protocols[END_REF] • g m1

), while we obtain

2 ) in the same way.

This invalidates the soundness of the Σ-protocol and the proof that the Paillier-based threshold cryptosystem from [START_REF] Fouque | Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks[END_REF] provides IND-CCA2 security in the random oracle model. We insist that we did not find a concrete chosenciphertext attack against the scheme. Still, the security proof cannot apply a Naor-Yung-based strategy since, in a sequence of hybrid games, the adversary can always distinguish which one of the secret keys sk 1 = (p 1 , q 1 ), sk 2 = (p 2 , q 2 ) is used to answer decryption queries. A simple solution to this problem is to add a range proof showing that the plaintext is smaller than min(N 1 , N 2 ).