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

Abstract

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 ($\mathsf {DCR}$) and Learning-With-Errors ($\mathsf {LWE}_{}$) assumptions.

1 Introduction

Threshold cryptography [17, 36, 38, 39] avoids a single point of failure by splitting the secret key into $\ell >1$ shares and handing them over to different servers. This is done in such a way that any set of size at least $t\le \ell$ 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 [69, 74] 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 non-interactive. 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 [78], 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 [62, 65] 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 [46, 77] of ciphertext well-formedness in the random oracle model. In the standard model, Canetti and Goldwasser [23] thresholdized the Cramer-Shoup cryptosystem [31] 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 [28] a non-interactive distributed randomization technique but it only supports a small number of servers. Boneh et al. [16] 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 [14, 15, 42, 81]. Boneh, Boyen and Halevi [14] 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 applications of the Canetti-Halevi-Katz [24] methodology to threshold cryptography were considered in [18, 58]. Wee [81] 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. [15] 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) [50] and notably implies CCA2-secure non-interactive threshold encryption schemes in the static corruption setting.

Adaptive Corruptions. Most threshold cryptosystems (e.g., [14, 23, 42, 46, 77]) 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. [22] 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 [47, 48] independently showed different methods to achieve adaptive security. Their techniques were extended [5] to obtain proactive [70] RSA signatures.

The constructions of [22, 47, 48] inherently require interaction as they rely on the so-called “single inconsistent player” (SIP) technique. The latter consists of transforming a t-out-of-$\ell$ 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 $\ell$ severs) has an inconsistent internal state that causes the simulation to fail if it gets corrupted. Since this occurs with probability $\approx 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 [47, 48] thus proceed by switching from a $(t,\ell )$ 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.¹ Jarecki and Lysyanskaya [55] extended the SIP technique to eliminate the need for erasures and described an adaptively secure variant of the Canetti-Goldwasser scheme [23]. Abe and Fehr [2] removed zero-knowledge proofs from the Jarecki-Lysyanskaya construction and proved it secure in (a variant of) the universal composability framework. However, [2, 55] 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 pre-shared secrets. As argued in [78], none of the schemes in [1, 2, 23, 55] is a simple, non-interactive, client/server protocol.

An adaptively secure extension of the Boneh-Boyen-Halevi construction [14] was proposed by Libert and Yung [64] using bilinear maps in composite order groups. It was subsequently shown [62, 65] that pairing-based NIWI/NIZK arguments [53, 56] 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 [71] ($\mathsf {DCR}$) and the Learning-With-Errors ($\mathsf {LWE}_{}$) assumption [75].

Our first construction relies on both assumptions and features ciphertexts that are about as short as in standard (i.e., non-threshold) $\mathsf {DCR}$-based CCA2-secure encryption schemes based on the Cramer-Shoup paradigm [20, 32]. Indeed, ciphertexts are only roughly 3 times as large as those of [20]. Our scheme offers at least two advantages over the $\mathsf {DCR}$-based system obtained by applying universal thresholdizers [15] to, e.g., the Camenisch-Shoup cryptosystem [20, Section 3.2]. First, in line with our goal, we can prove adaptive security under a polynomial reduction for $t,\ell =\mathsf {poly}(\lambda )$ without relying on complexity leveraging.² Indeed, universal thresholdizers are not known to enable adaptive security under our definition. Second, the scheme implies a more efficient voting-friendly threshold cryptosystem [12] 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 [15, 20]. The reason is that the shared decryption algorithm of [15] would proceed by homomorphically evaluating the decryption circuit of the standard Paillier-based scheme [20] over FHE-encrypted Paillier secret keys.

Our second construction relies on the sole $\mathsf {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 $\mathsf {LWE}_{}$-based threshold cryptosystems, it relies on an $\mathsf {LWE}_{}$ assumption with super-polynomial approximation factor. The reason is that, as in all earlier threshold $\mathsf {LWE}_{}$-based constructions [10, 15], 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 $\mathsf {LWE}_{}$ assumption with polynomial approximation factor.

Technical Overview. Our schemes build on hash proof systems [32] and can be seen as pairing-free adaptation of constructions proposed by Libert and Yung [65]. In [65], 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 [41] 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, [62, 65] replaced the designated-verifier NIZK proofs of ciphertext validity [31, 32] by publicly verifiable pairing-based NIZK arguments. This eliminates the need for randomized decryption – which was the culprit of interaction in [23, 55] – 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 [31, 32]) 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 [76].

Our first scheme is a threshold version of (a variant of) an Elgamal-Paillier combination proposed in [20]. The public key contains $h =g^{4N \cdot x} \bmod N^2$, where N is a safe-prime product and $x \in \mathbb {Z}$ is the secret key. Messages $\mathsf {Msg} \in \mathbb {Z}_N$ are encrypted as $(C_0,C_1)=(g^{2 N \cdot r} ,(1+N)^{\mathsf {Msg}} \cdot h^r ) \in (\mathbb {Z}_{N^2}^*)^2$ and can be decrypted using x. The security proof of [20] involves a hybrid game where $C_0$ is sampled as a random quadratic residue (instead of a 2N-th residue) in $\mathbb {Z}_{N^2}^*$ before computing $C_1= (1+N)^{\mathsf {Msg}} \cdot C_0^{2x} \bmod N^2$. In order to exploit the entropy of $x \bmod 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 $\mathbb {Z}_{N^2}^*$.

This NIZK component can be realized from recent results [21, 25, 72] on the standard-model instantiability of the Fiat-Shamir paradigm [45]. In our setting, we can use an argument of composite residuosity described by Libert et al. [61], 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 simulation-soundness in the context of threshold CCA2 security. We, thus, construct an optimized version of the NIZK argument of [61], where the common reference string (CRS) only contains O(1) Paillier ciphertexts, instead of $O(\lambda )$ in [61]. This new optimized NIZK argument suffices for all applications that only need one-time simulation soundness.³

Like its unbounded counterpart [61], our one-time simulation-sound argument adapts a compiler from [60], which builds USS arguments from trapdoor $\varSigma$-protocols. In short, these are $\varSigma$-protocols in the CRS model where an efficiently computable function $\mathsf {BadChallenge}$ uses a trapdoor to compute the only challenge $\mathsf {Chall}$ admitting a valid response z for a given false statement $x \not \in \mathcal {L}$ and a given first prover message a. The USS argument of [60] uses a technique due to Damgård [33] that consists of having the prover first send an equivocable commitment to its first $\varSigma$-protocol message before opening the commitment in the response z. In [60], the equivocable commitment was replaced by a strengthened version of the $\mathcal {R}$-lossy encryption primitive of Boyle et al. [19]. In a nutshell, an $\mathcal {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 $\mathsf {BadChallenge}$ function (in order to ensure soundness via the techniques of [25]), 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. [49] in the context of the $\mathsf {BadChallenge}$ function methodology [25].

In [60], it was shown that the underlying equivocable $\mathcal {R}$-lossy PKE scheme can be instantiated from the $\mathsf {DCR}$ assumption using public keys comprised of $O(\lambda )$ Paillier ciphertexts. In Sect. 3, we show that, if we only need to simulate one argument of a false statement, we can use a more efficient $\mathcal {R}$-lossy PKE scheme for a different relation allowing for constant-size public keys. While [61] uses the bit-matching relation of [19] which incurs long public keys as it must be combined with admissible hash functions [13], we can simply use the inequality relation where $R(K,t)=1$ if and only if $K \ne t$. In our $\mathsf {DCR}$-based instantiation, we can thus encrypt/commit to $\mathsf {Msg} \in \mathbb {Z}_{N}$ under the tag t by computing $\mathsf {ct}= (u^t \cdot v)^{\mathsf {Msg}} \cdot r^N \bmod N^2$, which can be decrypted as a standard Paillier ciphertext when N divides the order of $u^t \cdot v$. When $u^t \cdot v$ is an N-th residue, we can equivocate $\mathsf {ct}$ by finding $r \in \mathbb {Z}_N^*$ that explains $\mathsf {ct}$ as an encryption of an arbitrary plaintext. By suitably programming $u,v \in \mathbb {Z}_{N^2}^*$, we can make sure that $u^t \cdot 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 $\mathsf {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 $\mathbb {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_0^2$ lives in the subgroup of 2N-th residues before releasing decryption shares $C_0^{2 \cdot \mathsf {sk}_i}$.

Our $\mathsf {LWE}_{}$-based construction relies on the dual Regev cryptosystem [51], where public keys contain random matrices $\mathbf {A} \in \mathbb {Z}_q^{ n \times m}$ and $\mathbf {U} = \mathbf {A} \cdot \mathbf {R} \in \mathbb {Z}_q^{n \times L}$, for some $n,m,L \in \mathsf {poly}(\lambda )$ such that $n<m$, and secret keys are small-norm integer matrices $\mathbf {R} \in \mathbb {Z}^{m \times L}$. Since the columns of $\mathbf {R}$ have a lot of entropy conditionally on $(\mathbf {A},\mathbf {U})$, it is tempting to adapt the approach of our $\mathsf {DCR}$-based system and use $\mathsf {LWE}_{}$ in an hash-proof-like fashion (as previously done in, e.g., [6]). However, this requires preventing the adversary from inferring information on $\mathbf {R}$ by making decryption queries on ill-formed ciphertexts. This cannot be achieved via designated-verifier NIZK proofs [32] since known $\mathsf {LWE}_{}$-based hash proof systems (e.g., [57, 82]) do not provide smoothness in the worst-case. Namely, nothing is guaranteed on the unpredictability of $\mathbf {R}^\top \mathbf {c}_0$ when $\mathbf {c}_0$ is neither a vector of $\mathsf {LWE}_{}$ samples for $\mathbf {A} \in \mathbb {Z}_q^{n \times m}$ nor a uniform vector over $\mathbb {Z}_q^m$, but something in between (e.g., a vector $\mathbf {c}_0=\mathbf {A}^\top \cdot \mathbf {s} + \mathbf {e}_0$ where $\mathbf {e}_0 \in \mathbb {Z}^m$ is slightly too large).

To address the problem of showing that $\mathbf {c}_0$ is well-formed (i.e., of the form $\mathbf {c}_0=\mathbf {A}^\top \cdot \mathbf {s} + \mathbf {e}_0$ for a small enough $\mathbf {e}_0 \in \mathbb {Z}^m$), we replace the designated-verifier NIZK proof by a Fiat-Shamir-based [45] publicly verifiable NIZK argument, which is known to provide soundness in the standard model under the $\mathsf {LWE}_{}$ assumption [72]. To avoid relying on a generic Karp reduction to the Graph Hamiltonicity language used in [25], we rely on the simulation-sound NIZK argument of Libert et al. [60, Appendix G] which allows showing that a vector $\mathbf {c}_0$ is indeed of the form $\mathbf {c}_0=\mathbf {A}^\top \cdot \mathbf {s} + \mathbf {e}_0$ for a small $\mathbf {e}_0 \in \mathbb {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 $\mathbf {c}_0=\mathbf {A}^\top \cdot \mathbf {s} + \mathbf {e}_0$ where $\mathbf {e}_0$ is only slightly too large, which preserves the entropy of the centralized secret key $\mathbf {R} \in \mathbb {Z}^{m \times \ell }$.

In the threshold setting, both schemes share their secret keys using the linear integer secret sharing (LISS) primitive of Damgård and Thorbek [35], which are similar to linear secret sharing schemes except that they work over $\mathbb {Z}$. In our $\mathsf {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 [59]) as in [15]. However, as observed in [63] 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 $\mathsf {DCR}$-based TPKE bears similarities to the inner product functional encryption scheme of Agrawal et al. [4] in that it samples secret keys $x \in \mathbb {Z}$ from a Gaussian distribution over the integers. By sharing them with a LISS, we can adapt arguments used in [4, 63] in order to assess the entropy of secret keys after all queries.

Related Work. Back in 2001, Fouque and Pointcheval [46] used the Naor-Yung paradigm [69] to construct a CCA2-secure threshold cryptosystem under the $\mathsf {DCR}$ assumption in the random oracle model. In the full version of the paper, we show, as a comment, that the proof of IND-CCA security of [46] 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 $\mathsf {LWE}_{}$-based threshold encryption scheme was proposed by Bendlin and Damgård [10] who showed a threshold version of Regev’s cryptosystem [75]. Xie et al. [83] 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 [15] that turns any IND-CCA secure into a non-interactive threshold variant thereof using fully homomorphic encryption. Bendlin et al. [11] 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. [63] described non-interactive threshold pseudorandom functions from $\mathsf {LWE}_{}$. Our $\mathsf {LWE}_{}$-based TPKE and its security proof are actually inspired by their use of LISS schemes.

Organization. In Sect. 2, we first recall some definitions and tools that will be used in our constructions. Section 3 then presents our one-time simulation-sound NIZK arguments, which builds on our $\mathsf {DCR}$-based $\mathcal {R}$-lossy PKE scheme described in Sect. 3.1. Our $\mathsf {DCR}$-based threshold cryptosystem is explained in Sect. 4. Its variant based on the sole $\mathsf {LWE}_{}$ assumption is given in the full version of the paper. For simplicity, we first present non-robust variants of both schemes. In the full version of the paper [40], we show that standard techniques can be applied to achieve robustness against malicious adversaries.

2 Background and Definitions

2.1 Lattices

For any $q\ge 2$, $\mathbb {Z}_q$ denotes the ring of integers with addition and multiplication modulo q. If $\mathbf {x} \in \mathbb {R}^n$ is a vector, $\Vert \mathbf {x}\Vert =\sqrt{\sum _{i=1}^n x_i^2 }$ denotes its Euclidean norm and $\Vert \mathbf {x}\Vert _{\infty }=\max _{i}|x_i|$ its infinity norm. If $\mathbf {M}$ is a matrix over $\mathbb {R}$, then $\Vert \mathbf {M}\Vert :=\sup _{\mathbf {x}\ne 0}\frac{\Vert \mathbf {Mx}\Vert }{\Vert \mathbf {x}\Vert }$ and $\Vert \mathbf {M}\Vert _{\infty }:=\sup _{\mathbf {x}\ne 0}\frac{\Vert \mathbf {Mx}\Vert _{\infty }}{\Vert \mathbf {x}\Vert _{\infty }}$ 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, $\varDelta (X,Y)$ denotes their statistical distance.

Let $\mathbf {\Sigma } \in \mathbb {R}^{n\times n}$ be a symmetric positive-definite matrix, and $\mathbf {c} \in \mathbb {R}^n$. We define the Gaussian function on $\mathbb {R}^n$ by $\rho _{\mathbf {\Sigma },\mathbf {c}}(\mathbf {x})=\exp (-\pi (\mathbf {x}-\mathbf {c})^\top \mathbf {\Sigma }^{-1} (\mathbf {x}-\mathbf {c}))$ and if $\mathbf {\Sigma }=\sigma ^2 \cdot \mathbf {I}_n$ and $\mathbf {c}=\mathbf {0}$ we denote it by $\rho _{\sigma }$. For an n dimensional lattice $\varLambda \subset \mathbb {R}^n$ and for any lattice vector $\mathbf {x} \in \varLambda$ the discrete Gaussian is defined by $\rho _{\varLambda ,\mathbf {\Sigma },\mathbf {c}}(\mathbf {x})=\frac{\rho _{\mathbf {\Sigma },\mathbf {c}}}{\rho _{\mathbf {\Sigma },\mathbf {c}}(\varLambda )}$.

For an n-dimensional lattice $\varLambda$, we define $\eta _{\varepsilon }(\varLambda )$ as the smallest $r>0$ such that $\rho _{1/r} (\widehat{\varLambda } \setminus \mathbf {0}) \le \varepsilon$ with $\widehat{\varLambda }$ denoting the dual of $\varLambda$, for any $\varepsilon \in (0,1)$.

For a matrix $\mathbf {A} \in \mathbb {Z}_q^{n \times m}$, we define $\varLambda ^\perp (\mathbf {A}) = \{\mathbf {x}\in \mathbb {Z}^m: \mathbf {A} \cdot \mathbf {x} = \mathbf {0} \bmod q\}$ and $\varLambda (\mathbf {A}) = \mathbf {A}^\top \cdot \mathbb {Z}^n + q\mathbb {Z}^m$. For an arbitrary vector $\mathbf {u} \in \mathbb {Z}_q^{n}$, we also define the shifted lattice $\varLambda ^{\mathbf {u}}(\mathbf {A}) = \{\mathbf {x}\in \mathbb {Z}^m: \mathbf {A} \cdot \mathbf {x} = \mathbf {u} \bmod q\}$.

We now recall the definition of the Learning-With-Errors ($\mathsf {LWE}_{}$) assumption introduced by Regev [75].

Definition 2.1

($\mathsf {LWE}$ assumption). Let $m\ge n \ge 1$, $q\ge 2$ and $\alpha \in (0,1)$ be functions of a security parameter $\lambda$. The $\mathsf {LWE}_{}$ problem consists in distinguishing between the distributions $(\mathbf{A}, \mathbf{A} \mathbf{s} + \mathbf{e})$ and $U(\mathbb {Z}_q^{m \times n}\times \mathbb {Z}_q^m)$, where $\mathbf{A} \sim U(\mathbb {Z}_q^{m \times n})$, $\mathbf{s} \sim U(\mathbb {Z}_q^n)$ and $\mathbf{e} \sim D_{\mathbb {Z}^m, \alpha q}$.

Lemma 2.2

([51, Theorem 4.1]). There is a PPT algorithm that, given a basis $\mathbf {B}$ of an n-dimensional $\varLambda =\varLambda (\mathbf {B})$, a parameter $s > \Vert \tilde{\mathbf {B}} \Vert \cdot \omega ( \sqrt{\log n} )$, and a center $\mathbf {c} \in \mathbb {R}^n$, outputs a sample from a distribution statistically close to $D_{\varLambda ,s,\mathbf {c}}$.

Lemma 2.3

([68], Lemma 4.4). For $\sigma =\omega (\sqrt{\log n})$, there exists a negligible function $\epsilon =\epsilon (n)$ such that $\Pr _{\mathbf {x}\hookleftarrow D_{\mathbb {Z}^n, \sigma }} \left[ \Vert \mathbf {x}\Vert >\sigma \sqrt{n} \right] \le \frac{1+\epsilon }{1-\epsilon }\cdot 2^{-n} .$

Lemma 2.4

([63, Lemma 2.6]). Let $\epsilon \in (0,1),c\in \mathbb {R}$ and $\sigma >0$, such that $\sigma \ge \sqrt{\ln 2(1+1/\epsilon )/\pi }$. Then $H_\infty (D_{\mathbb {Z},\sigma ,c})\ge \log \sigma -\log \left( 1+\frac{2\epsilon }{1-\epsilon }\right) .$ For $\sigma =\varOmega (\sqrt{n})$, we get $H_\infty (D_{\mathbb {Z},\sigma ,c})\ge \log (\sigma )-2^{-n}$.

Lemma 2.5

([44]). Let $\beta >0,q\in \mathbb {Z}$ and $y\in \mathbb {Z}$. Then, the following holds: $\varDelta (D_{\mathbb {Z}_q,\beta \cdot q,0},D_{\mathbb {Z}_q,\beta \cdot q,y})\le \frac{|y|}{\beta q}.$

Lemma 2.6

([67, Theorem 2]). There exists an efficient randomized algorithm $\mathsf {TrapGen}(1^n,1^m,q)$ that given any integers $n\ge 1$,$q\ge 2$ and sufficiently large $m=O(n\log q)$ outputs a matrix $\mathbf {A}\in \mathbb {Z}_q^{n\times m}$ and a trapdoor $\mathbf {T}_{\mathbf {A}}$ such that the distribution of $\mathbf {A}$ is statistically close to uniform.

Lemma 2.7

(Adapted from [51, corollary 2.8]). Let $\varLambda ' \subseteq \varLambda \subseteq \mathbb {R}^n$ be two lattices with the same dimension. Let $\epsilon \in (0,1/2)$. Then, for any $c \in \mathbb {R}^n$ and any $\sigma \ge \eta _{\epsilon }(\varLambda ')$, the distribution $D_{\varLambda ,\sigma ,c} \bmod \varLambda '$ is within statistical distance $2\epsilon$ from the uniform distribution over $\varLambda / \varLambda '$.

2.2 Composite Residuosity Assumption

We now recall Paillier’s Composite Residuosity assumption and its variant considered by Damgård and Jurik.

Definition 2.8

([34, 71]). Let integers $N=pq$ and $s>1$ for primes p, q. The s-Decision Composite Residuosity $(s\text {-}\mathsf {DCR})$ assumption states that the distributions $\{x=w^{N^s} \bmod N^{s+1} \mid w \leftarrow U(\mathbb {Z}_{N}^\star ) \}$ and $\{x \mid x\leftarrow U(\mathbb {Z}_{N^{s+1}}^\star ) \}$ are computationally indistinguishable.

It is known [34] that the $s\text {-}\mathsf {DCR}$ assumption is equivalent to the standard $1\text {-}\mathsf {DCR}$ of [71] for any $s>1$.

2.3 Linear Integer Secret Sharing

This section recalls the concept of linear integer secret sharing (LISS), as defined by Damgård and Thorbek [35]. Definitions below are taken from [79] where the secret to be shared lives in an interval $[-2^l,2^l]$ centered in 0, for some $l \in \mathbb {N}$.

Definition 2.9

A monotone access structure on $[\ell ]$ is a non-empty collection $\mathbb {A}$ of sets $A \subseteq [\ell ]$ such that $\emptyset \not \in \mathbb {A}$ and, for all $A \in \mathbb {A}$ and all sets B such that $A \subseteq B \subseteq [\ell ]$, we have $B \in \mathbb {A}$. For an integer $t \in [\ell ]$, the threshold-t access structure $T_{t,\ell }$ is the collection of sets $A \subseteq [\ell ]$ such that $|A|\ge t$. Sets $A\in \mathbb {A}$ are called qualified and sets $B\notin \mathbb {A}$ are called forbidden.

Let $P= [\ell ]$ 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 $\mathbf {M} \in \mathbb {Z}^{d \times e}$ and a random vector $\varvec{\rho } = (s,\rho _2,\ldots ,\rho _e)^\top$, where s is the secret to be shared and $\{\rho _i\}_{i=2}^e$ are randomly sampled in $[-2^{l_0+\lambda },2^{l_0+\lambda }]^{e-1}$, for some $l_0\ge l \in \mathbb {\ell }$. Usually, the distribution of the $\rho _i$ is uniform but, in the following, we will set $l_0=l$ and $\rho _i\hookleftarrow D_{\mathbb {Z},\sigma }$. The dealer D computes a vector $\varvec{s}=(s_1,\ldots ,s_d)^\top$ of share units as $\varvec{s}= (s_1,\ldots ,s_d)^\top = \mathbf {M} \cdot \varvec{\rho } \in \mathbb {Z}^d.$ Each party in $P = \{1,\ldots ,\ell \}$ is assigned a set of share units. Letting $\psi : \{1,\ldots ,d\} \rightarrow P$ be a surjective function, the i-th share unit $s_i$ is assigned to the shareholder $\psi (i) \in P$, in which case player $\psi (i)$ is said to own the i-th row of $\mathbf {M}$. If $A \subseteq P$ is a set of shareholders, $\mathbf {M}_A \in \mathbb {Z}^{d_A \times e}$ denotes the set of rows jointly owned by A. Likewise, $\varvec{s}_A \in \mathbb {Z}^{d_A}$ denotes the restriction of $\varvec{s} \in \mathbb {Z}^d$ to the coordinates jointly owned by the parties in A. The j-th shareholder’s share consists of $\varvec{s}_{\psi ^{-1}(j)} \in \mathbb {Z}^{d_j}$, so that it receives $d_j=| \psi ^{-1} (j) |$ out of the $d=\sum _{j=1}^\ell d_j$ share units. The expansion rate $\mu =d/\ell$ 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 [35] used integer span programs [30].

Definition 2.10

([30]). An integer span program (ISP) is a tuple formed by three elements $\mathcal {M}=(\mathbf {M},\psi ,\varvec{\varepsilon })$, where $\mathbf {M} \in \mathbb {Z}^{d \times e}$ is an integer matrix whose rows are labeled by a surjective function $\psi : \{1,\ldots ,d\} \rightarrow \{1,\ldots , \ell \}$ and $\varvec{\varepsilon }=(1,0,\ldots ,0)$ is called target vector. The size of $\mathcal {M}$ is the number of rows d in $\mathbf {M}$.

Definition 2.11

Let $\varGamma$ be a monotone access structure and let $\mathcal {M}=(\mathbf {M},\psi ,\varvec{\varepsilon })$ an integer span program. Then, $\mathcal {M}$ is an ISP for $\varGamma$ if it computes $\varGamma$: namely, for all $A \subseteq \{1,\ldots ,\ell \}$, the following conditions hold:

• 1. If $A \in \varGamma$, there is a reconstruction vector $\varvec{\lambda } \in \mathbb {Z}^{d_A}$ such that $\varvec{\lambda }^\top \cdot \mathbf {M}_A = \varvec{\varepsilon }^\top$.

• 2. If $A \not \in \varGamma$, there exists $\varvec{\kappa }=(\kappa _1,\ldots ,\kappa _e)^\top \in \mathbb {Z}^e$ such that $\mathbf {M}_A \cdot \varvec{\kappa } = \varvec{0} \in \mathbb {Z}^d$ and $\varvec{\kappa }^\top \cdot \varvec{\varepsilon }=1$. In this case, $\varvec{\kappa }$ is called a sweeping vector for A.

We also define $\kappa _{\max }=\max \{|a| \mid a \text { is an entry in some sweeping vector} \}$.

Damgård and Thorbek [35] observed that a LISS can be built by setting the share generating matrix to be the matrix $\mathbf {M}$ of an ISP $\mathcal {M}=(\mathbf {M},\psi ,\varvec{\varepsilon })$ that computes the access structure $\varGamma$. We may then specify a LISS scheme $\mathcal {L}=(\mathcal {M}=(\mathbf {M},\psi ,\varvec{\varepsilon }),\varGamma ,\mathcal {R},\mathcal {K})$ by an ISP for the access structure $\varGamma$, a space $\mathcal {R}$ of reconstruction vectors satisfying Condition 1 of Definition 2.11, and a space $\mathcal {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 [35] that LISS schemes can be obtained from [9, 30]. While the Benaloh-Leichter (BL) secret sharing [9] was designed to work over finite groups, it was generalized in [35] 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 [52, 80]. Their LISS scheme built upon Benaloh-Leichter [9] satisfies what we want: as can be observed from [35, Lemma 4], every coefficient of any reconstruction vector $\varvec{\lambda }$ lives in $\{-1,0,1\}$ and [35, Lemma 5] shows that $\kappa _{\max }=1$. Let a monotone Boolean formula f, then the BL-based technique allows us to build binary share distribution matrices $\mathbf {M} \in \{0,1\}^{d \times e}$ such that $d,e=O(\mathrm {size}(f))$. Moreover they have at most $\mathrm {depth}(f)+1$ non-zero entries, so that each share unit $s_i$ has magnitude $O(2^{l_0+\lambda } \cdot \mathrm {depth}(f))$.

Finally, Valiant’s result [80] implies the existence of a monotone Boolean formula of the threshold-t function $T_{t,\ell }$, which has size $d = O(\ell ^{5.3})$ and depth $O(\log \ell )$. Recall that each player will receive about $d/\ell$ rows of $\mathbf {M}$ on average, then the average share size is $O(\ell ^{4.3} \cdot (l_0+\lambda + \log \log \ell ))$ bits. Valiant’s construction was improved by Hoory et al. [54] who gave a monotone formula of size $O(\ell ^{1+\sqrt{2}})$ and depth $O(\log \ell )$ for the majority function.⁴ This in turn reduces the average share size to $O(\ell ^{\sqrt{2}} \cdot (l_0+\lambda + \log \log \ell ))$ bits.

2.4 Threshold PKE

In this section, we recall the TPKE syntax defined by Boneh et al. [15].

Definition 2.12

(Threshold PKE). Let P be a party of $\ell$ servers and $\mathbb {S}$ be a class of efficient monotone access structure on P. A Threshold PKE scheme (TPKE) for some message space $\mathcal {M}$ is then a tuple of efficient $\mathsf {PPT}$ algorithms $(\mathsf {Keygen}, \mathsf {Encrypt}, \mathsf {PartDec}, \mathsf {PartVerify}, \mathsf {Combine})$ with the following specifications:

• $\mathsf {Keygen}(1^\lambda ,\mathbb {A})\rightarrow (\mathsf {pp},\mathsf {ek},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )$: On input a security parameter $\lambda$, $\mathbb {A}\in \mathbb {S}$ an access structure, the algorithm outputs a set of public parameters $\mathsf {pp}$ (which are implicit in the inputs of all other algorithms), a public key $\mathsf {pk}$ and a set of secret key shares $\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell$.

• $\mathsf {Encrypt}(\mathsf {pk},\mathsf {Msg})\rightarrow \mathsf {ct}$: On input the public parameters $\mathsf {pp}$, the encryption key $\mathsf {ek}$ and a message $\mathsf {Msg} \in \mathcal {M}$, the algorithm outputs a ciphertext $\mathsf {ct}$.

• $\mathsf {PartDec}(\mathsf {pk},\mathsf {ct},\mathsf {sk}_i)\rightarrow \mu _i$: Given public parameters $\mathsf {pp}$, a ciphertext $\mathsf {ct}$ and a secret key share $\mathsf {sk}_i$, this algorithm outputs a partial decryption $\mu _i$.

• $\mathsf {PartVerify}(\mathsf {pk}, \mathsf {ct}, \mu _i)\rightarrow \mathsf {b}\in \{0,1\}$: On input of public parameters $\mathsf {pp}$, a ciphertext $\mathsf {ct}$ and a partial decryption $\mu _i$, this algorithm outputs a bit $\mathsf {b}$.

• $\mathsf {Combine}\left( \mathsf {pk}, B=(\mathcal {S}, \{\phi (\mu _i)\}_{i\in \mathcal {S}}) ,\mathsf {ct}\right) \rightarrow \mathsf {Msg}'$: Given public parameters and a set of images of $\phi$ of partial decryptions, the algorithm outputs a message $\mathsf {Msg} '\in \mathcal {M}$. The function $\phi$ is public and deterministic.⁵

The goal is now to construct a TPKE scheme that satisfies the following compactness, correctness and requirements.

Definition 2.13

(Compactness [15]). A TPKE scheme satisfies compactness if there exist polynomials P and Q such that $\forall \lambda ,\forall \mathbb {A}\in \mathbb {S},|\mathsf {pk}|\le P(\lambda )\wedge |\mathsf {ct}|\le Q(\lambda ) ,$ where $(\mathsf {pp},\mathsf {pk},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )\leftarrow \mathsf {Keygen}(1^\lambda ,\mathbb {A})$ and the ciphertext is generated with $\mathsf {ct}\leftarrow \mathsf {Encrypt}(\mathsf {pk},\mathsf {Msg})$ for any $\mathsf {Msg} \in \mathcal {M}$.

Definition 2.14

(Decryption Correctness). A TPKE provides decryption correctness if the following holds. For any $\lambda \in \mathbb {N}$, any access structure $\mathbb {A}\in \mathbb {S}$, any set $\mathcal {S}\in \mathbb {A}$ and any message $\mathsf {Msg} \in \mathcal {M}$, if we run $(\mathsf {pp},\mathsf {pk},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )\leftarrow \mathsf {Keygen}(1^\lambda ,\mathbb {A})$, $\mathsf {ct}\leftarrow \mathsf {Encrypt}(\mathsf {pk},\mathsf {Msg})$ and then $\mu _i\leftarrow \mathsf {PartDec}(\mathsf {pp},\mathsf {sk}_i,\mathsf {ct}),\forall i\in \mathcal {S}$, we have $\Pr [\mathsf {Combine}\left( \mathsf {pk},\left( \mathcal {S},\{\phi (\mu _i)\}_{i\in \mathcal {S}}\right) , \mathsf {ct}\right) =\mathsf {Msg} ]=1-\text {negl}(\lambda ).$

Definition 2.15

(Partial Verification Correctness). A TPKE provides partial verification correctness if the following holds. For any $\lambda \in \mathbb {N}$, any $\mathbb {A}\in \mathbb {S}$, any $\mathcal {S}\in \mathbb {A}$ and any message $\mathsf {Msg} \in \mathcal {M}$, if we run $(\mathsf {pp},\mathsf {pk},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )\leftarrow \mathsf {Keygen}(1^\lambda ,\mathbb {A})$, $\mathsf {ct}\leftarrow \mathsf {Encrypt}(\mathsf {pk},\mathsf {Msg})$ and $\mu _i\leftarrow \mathsf {PartDec}(\mathsf {pp},\mathsf {sk}_i,\mathsf {ct}),\forall i\in \mathcal {S}$, then $\Pr [ \mathsf {PartVerify}(\mathsf {pk},\mathsf {ct},\mu _i)=1 ]=1-\text {negl}(\lambda ).$

We can now define chosen-ciphertext security in a model allowing the adversary to adaptively corrupt decryption servers.

Definition 2.16

(Adaptive-CCA security for TPKE). A TPKE scheme provides chosen-ciphertext security under adaptive corruptions if no PPT adversary $\mathcal {A}$ has non-negligible advantage in the following game.

• 1. On input the the security parameter $\lambda$, $\mathcal {A}$ chooses an access structure $\mathbb {A}$.

• 2. The challenger generates $(\mathsf {pp},\mathsf {pk},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )\leftarrow \mathsf {Keygen}(1^\lambda ,\mathbb {A})$. It sends $(\mathsf {pp},\mathsf {pk})$ to $\mathcal {A}$ and initializes an empty set $\mathcal {C}=\emptyset$.

• 3. $\mathcal {A}$ can adaptively interleave the following queries:

  • Corruption: $\mathcal {A}$ sends the challenger an index $i \in [\ell ]$. The challenger replies by returning the share $\mathsf {sk}_i$ and updating the set $\mathcal {C} = \mathcal {C} \cup \{ i \}$.

  • Partial Decryption: $\mathcal {A}$ chooses an index $i \in [\ell ]$ and a ciphertext $\mathsf {ct}$ and the challenger returns a partial decryption $\mu _i\leftarrow \mathsf {PartDec}(\mathsf {pk},\mathsf {sk}_i,\mathsf {ct})$.

• 4. $\mathcal {A}$ chooses $\mathsf {Msg}_0^\star ,\mathsf {Msg}_1^\star \in \mathcal {M}$. The challenger replies with a challenge ciphertext $\mathsf {ct}^* \leftarrow \mathsf {Encrypt}(\mathsf {pk},\mathsf {Msg}_b^\star )$, where $b \hookleftarrow U(\{0,1\})$ is a random bit.

• 5. $\mathcal {A}$ makes more corruption and partial decryption queries subject to the following condition which must be satisfied at any time. Let $\mathcal {C} \subset [\ell ]$ the set of corrupted servers and let $\mathcal {C}^*$ the subset of indexes $j \in [\ell ]$ such that $\mathcal {A}$ made a decryption query of the form $(j,\mathsf {ct}^*)$. Then, it is required that $\mathcal {C} \cup \mathcal {C}^*\notin \mathbb {A}$.

• 6. The experiment ends with $\mathcal {A}$ outputting a bit $b' \in \{0,1\}$.

The advantage of $\mathcal {A}$ is defined as $\mathbf {Adv}^{\mathrm {ind}\hbox {-}\mathrm {cca}}(\mathcal {A}) := \big | \Pr [ b'= b ]- \frac{1}{2} \big |.$

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

([15]). A TPKE scheme satisfies robustness if no PPT adversary $\mathcal {A}$ can cause the following experiment $\mathsf {Expt}_{\mathcal {A}, \mathsf {TPKE}}^{\mathrm {robust}}(1^\lambda )$ to output 1 with non-negligible probability.

• 1. On input the security parameter $\lambda$, $\mathcal {A}$ chooses an access structure $\mathbb {A}$.

• 2. The challenger samples $(\mathsf {pp},\mathsf {pk},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )\leftarrow \mathsf {Keygen}(1^\lambda ,\mathbb {A})$ and provides $(\mathsf {pp},\mathsf {pk},\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )$ to $\mathcal {A}$.

• 3. $\mathcal {A}$ outputs a partial decryption forgery $\big (\mathsf {ct}^\star ,\mu _i^\star ,i \big )$, where $i \in [\ell ]$.

• 4. The experiment outputs 1 if we have $\phi (\hat{\mu }_i^\star )\ne \phi (\mathsf {PartDec}(\mathsf {pk},\mathsf {sk}_i,\mathsf {ct}^\star ))$ while $\mathsf {PartVerify}(\mathsf {pk},\mathsf {ct}^\star ,\mu _i^\star )=1$.

We note that the function $\phi$ allows considering as robust a TPKE such that $\mu _i^\star =(\hat{\mu }_i^\star ,\pi _i^\star )$ and where $\mathsf {Combine}$ only runs on $\hat{\mu }_i^\star$ and not on $\pi _i^\star$. While, given $(\hat{\mu }_i^\star ,\pi _i^\star )$, $\mathsf {Combine}$ could have simply striped $\pi _i^\star$, such formalization would prevent showing as robust a TPKE where $\hat{\mu }_i^\star$ is a word in an admissible language and $\pi _i^\star$ is a probabilistic membership argument whose validity, moreover, does not necessarily ensure that $\pi _i^\star$ is in the range of honestly computed arguments. Thanks to $\phi$, such case will not be artificially discarded.

A weaker robustness notion, a.k.a. consistency [14], captures the robustness of schemes where the word $\hat{\mu }_i^\star$ itself is probabilistic and whose validity tolerates a gap with respect to honestly computed statements. Here, we will focus on the (stronger) notion of robustness.

2.5 Correlation Intractable Hash Functions

We consider unique-output efficiently searchable relations [21].

Definition 2.18

A relation $R \subseteq \mathcal {X} \times \mathcal {Y}$ is searchable in time T if there exists a function $f :\mathcal {X} \rightarrow \mathcal {Y}$ which is computable in time T and such that, if there exists y such that $(x,y) \in R$, then $f(x) = y$.

Let $\lambda \in \mathbb {N}$ a security parameter. A hash family with input length $n(\lambda )$ and output length $m(\lambda )$ is a collection $\mathcal {H}=\{ h_\lambda : \{0,1\}^{s(\lambda )} \times \{0,1\}^{n(\lambda )} \rightarrow \{0,1\}^{m(\lambda )} \}$ of keyed functions induced by efficient algorithms $(\mathsf {Gen},\mathsf {Hash})$, where $\mathsf {Gen}(1^\lambda )$ outputs a key $k \in \{0,1\}^{s(\lambda )}$ and $\mathsf {Hash}(k,x)$ computes $h_\lambda (k,x) \in \{0,1\}^{m(\lambda )}$.

Definition 2.19

For a relation ensemble $\{ R_\lambda \subseteq \{0,1\}^{n(\lambda )} \times \{0,1\}^{m (\lambda )} \}$, a hash function family $\mathcal {H}=\{ h_\lambda : \{0,1\}^{s(\lambda )} \times \{0,1\}^{n(\lambda )} \rightarrow \{0,1\}^{m(\lambda )} \}$ is R -correlation intractable if, for any probabilistic polynomial time (PPT) adversary $\mathbb {A}$, we have $\Pr \left[ k \leftarrow \mathsf {Gen}(1^\lambda ) ), ~x \leftarrow \mathcal {A}(k) : (x,h_\lambda (k,x)) \in R \right] = \mathsf {negl}(\lambda ).$

Peikert and Shiehian [72] 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 $\mathsf {SIS}$ assumption with polynomial approximation factors. Under the $\mathsf {LWE}_{}$ assumption with polynomial approximation factors, their bootstrapping theorem allows handling arbitrary bounded-depth functions.

2.6 Trapdoor $\varSigma$-protocols

Canetti et al. [25] considered a definition of $\varSigma$-protocols that slightly differs from the usual formulation [27, 29].

Definition 2.20

(Adapted from [7, 25]). Let a language $\mathcal {L}= (\mathcal {L}_\mathsf {zk},\mathcal {L}_\mathsf {sound})$ associated with two NP relations $R_\mathsf {zk},R_\mathsf {sound}$. A 3-move interactive proof system $\mathsf {\varPi }=(\mathsf {Gen}_\mathsf {par},\mathsf {Gen}_\mathcal {L},\mathsf {P},\mathsf {V})$ in the common reference string model is a Gap $\varSigma$-protocol for $\mathcal {L}$ if it satisfies the following conditions:

• 3-Move Form: $\mathsf {P}$ and $\mathsf {V}$ both take as input $\mathsf {crs}= (\mathsf {par},\mathsf {crs}_\mathcal {L})$, with $\mathsf {par}\leftarrow \mathsf {Gen}_\mathsf {par}(1^\lambda )$ and $\mathsf {crs}_\mathcal {L}\leftarrow \mathsf {Gen}_\mathcal {L}(\mathsf {par},\mathcal {L})$, and a statement x and proceed as follows: (i) $\mathsf {P}$ takes in $w \in R_\mathsf {zk}(x)$, computes $(\mathbf {a},st) \leftarrow \mathsf {P}(\mathsf {crs},x,w)$ and sends $\mathbf {a}$ to the verifier; (ii) $\mathsf {V}$ sends back a random challenge $\mathsf {Chall}$ from the challenge space $\mathcal {C}$; (iii) $\mathsf {P}$ finally sends a response $\mathbf {z}=\mathsf {P}(\mathsf {crs},x,w,\mathbf {a},\mathsf {Chall},st)$ to $\mathsf {V}$; (iv) On input of $(\mathbf {a},\mathsf {Chall},\mathbf {z})$, $\mathsf {V}$ outputs 1 or 0.

• Completeness: If $(x,w)\in R_\mathsf {zk}$ and $\mathsf {P}$ honestly computes $(\mathbf {a},\mathbf {z})$ for a challenge $\mathsf {Chall}$, $\mathsf {V}(\mathsf {crs},x,(\mathbf {a},\mathsf {Chall},\mathbf {z}))$ outputs 1 with probability $1-\mathsf {negl}(\lambda )$.

• Special zero-knowledge: There is a PPT simulator $\mathsf {ZKSim}$ that inputs $\mathsf {crs}$, $x \in \mathcal {L}_\mathsf {zk}$ and a challenge $\mathsf {Chall} \in \mathcal {C}$. It outputs $(\mathbf {a},\mathbf {z}) \leftarrow \mathsf {ZKSim}(\mathsf {crs},x,\mathsf {Chall})$ such that $(\mathbf {a},\mathsf {Chall},\mathbf {z})$ is computationally indistinguishable from a real transcript with challenge $\mathsf {Chall}$ (for $w \in R_{zk}(x)$).

• Special soundness: For any CRS $\mathsf {crs}= (\mathsf {par},\mathsf {crs}_\mathcal {L})$ obtained as $\mathsf {par}\leftarrow \mathsf {Gen}_\mathsf {par}(1^\lambda )$, $\mathsf {crs}_\mathcal {L}\leftarrow \mathsf {Gen}_\mathcal {L}(\mathsf {par},\mathcal {L})$, any $x \not \in \mathcal {L}_\mathsf {sound}$, and any first message $\mathbf {a}$ sent by $\mathsf {P}$, there is at most one challenge $\mathsf {Chall}=f(\mathsf {crs},x,\mathbf {a})$ for which an accepting transcript $(\mathsf {crs},x,\mathbf {a},\mathsf {Chall},\mathbf {z})$ exists for some third message $\mathbf {z}$. The function f is called the “bad challenge function” of $\mathsf {\varPi }$. That is, if $x \not \in \mathcal {L}_\mathsf {sound}$ and the challenge differs from the bad challenge, the verifier never accepts.

Definition 2.20 is taken from [25] 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. [25] define trapdoor $\varSigma$-protocols as $\varSigma$-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 $\mathsf {crs}=(\mathsf {par},\mathsf {crs}_\mathcal {L})$ consists of a fixed part $\mathsf {par}$ and a language-dependent part $\mathsf {crs}_\mathcal {L}$ which is generated as a function of $\mathsf {par}$ and a language parameter $\mathcal {L}=(\mathcal {L}_\mathsf {zk},\mathcal {L}_\mathsf {sound})$.

Definition 2.21

(Adapted from [25]). A $\varSigma$-protocol $\mathsf {\varPi }=(\mathsf {Gen}_\mathsf {par},\mathsf {Gen}_\mathcal {L},\mathsf {P},\mathsf {V})$ with bad challenge function f for a trapdoor language $\mathcal {L}=(\mathcal {L}_\mathsf {zk},\mathcal {L}_\mathsf {sound})$ is a trapdoor $\varSigma$-protocol if it satisfies the properties of Definition 2.20 and there exist PPT algorithms $(\mathsf {TrapGen},\mathsf {BadChallenge})$ with the following properties.

• $\mathsf {Gen}_\mathsf {par}$ inputs $\lambda \in \mathbb {N}$ and outputs public parameters $\mathsf {par}\leftarrow \mathsf {Gen}_\mathsf {par}(1^\lambda )$.

• $\mathsf {Gen}_\mathcal {L}$ is a randomized algorithm that, on input of public parameters $\mathsf {par}$, outputs the language-dependent part $\mathsf {crs}_\mathcal {L}\leftarrow \mathsf {Gen}_\mathcal {L}(\mathsf {par},\mathcal {L})$ of $\mathsf {crs}= (\mathsf {par},\mathsf {crs}_\mathcal {L})$.

• $\mathsf {TrapGen}(\mathsf {par},\mathcal {L},\tau _\mathcal {L})$ takes as input public parameters $\mathsf {par}$ and a membership-testing trapdoor $\tau _\mathcal {L}$ for the language $\mathcal {L}_\mathsf {sound}$. It outputs a common reference string $\mathsf {crs}_\mathcal {L}$ and a trapdoor $\tau _\varSigma \in \{0,1\}^{\ell _\tau }$, for some $\ell _\tau (\lambda )$.

• $\mathsf {BadChallenge}(\tau _\varSigma ,\mathsf {crs},x,\mathbf {a})$ takes in a trapdoor $\tau _\varSigma$, a CRS $\mathsf {crs}=(\mathsf {par},\mathsf {crs}_\mathcal {L})$, an instance x, and a first prover message $\mathbf {a}$. It outputs a challenge $\mathsf {Chall}$.

In addition, the following properties are required.

• CRS indistinguishability: For any $\mathsf {par}\leftarrow \mathsf {Gen}_\mathsf {par}(1^\lambda )$, and any trapdoor $\tau _\mathcal {L}$ for the language $\mathcal {L}$, an honestly generated $\mathsf {crs}_\mathcal {L}$ is computationally indistinguishable from a CRS produced by $\mathsf {TrapGen}(\mathsf {par},\mathcal {L},\tau _\mathcal {L})$. Namely, for any $\mathsf {aux}$ and any PPT distinguisher $\mathcal {A}$, we have

  $$\begin{aligned}&\mathbf {Adv}^{\mathrm {indist}\text {-}\varSigma }_\mathcal {A}(\lambda ) := | \Pr [ \mathsf {crs}_\mathcal {L}\leftarrow \mathsf {Gen}_\mathcal {L}(\mathsf {par},\mathcal {L}) : \mathcal {A}(\mathsf {par},\mathsf {crs}_\mathcal {L}) = 1] \\&\qquad - \Pr [ (\mathsf {crs}_\mathcal {L},\tau _\varSigma ) \leftarrow \mathsf {TrapGen}(\mathsf {par},\mathcal {L},\tau _\mathcal {L}) : \mathcal {A}(\mathsf {par},\mathsf {crs}_\mathcal {L}) = 1 ] | \le \mathsf {negl}(\lambda ). \end{aligned}$$

• Correctness: There exists a language-specific trapdoor $\tau _\mathcal {L}$ such that, for any instance $x \not \in \mathcal {L}_\mathsf {sound}$ and all pairs $(\mathsf {crs}_\mathcal {L},\tau _\varSigma ) \leftarrow \mathsf {TrapGen}(\mathsf {par},\mathcal {L},\tau _\mathcal {L})$, we have $\mathsf {BadChallenge}(\tau _\varSigma ,\mathsf {crs},x,\mathbf {a})=f(\mathsf {crs},x,\mathbf {a}).$

Note that the $\mathsf {TrapGen}$ algorithm does not take a specific statement x as input, but only a trapdoor $\tau _\mathcal {L}$ allowing to recognize elements of $\mathcal {L}_\mathsf {sound}$.

2.7 $\mathcal {R}$-Lossy Public-Key Encryption with Efficient Opening

In [60], Libert et al. formalized a generalization of the notion of $\mathcal {R}$-lossy encryption introduced by Boyle et al. [19]. The primitive is a tag-based encryption scheme [58] where the tag space $\mathcal {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 $\mathcal {R}$-lossy PKE schemes, the tag space is partitioned according to a binary relation $\mathcal {R} \subseteq \mathcal {K} \times \mathcal {T}$. The key generation algorithm takes as input an initialization value $K \in \mathcal {K}$ and partitions $\mathcal {T}$ in such a way that injective tags $t \in \mathcal {T}$ are exactly those for which $(K,t) \in \mathcal {R}$ (i.e., all tags t for which $(K,t) \not \in \mathcal {R}$ are lossy).

From a security standpoint, the definitions of [19] require the initialization value K to be computationally hidden by the public key. The definition of [60] requires the existence of a lossy key generation algorithm $\mathsf {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) \not \in \mathcal {R}$). In addition, [60] also asks that the secret key allows equivocating lossy ciphertexts (a property called efficient opening by Bellare et al. [8]) using an algorithm called $\mathsf {Opener}$. For the purpose of constructing simulation-sound arguments, [60] uses two distinct opening algorithms $\mathsf {Opener}$ and $\mathsf {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 $\mathcal {R} \subseteq \mathcal {K}_\lambda \times \mathcal {T}_\lambda$ be an efficiently computable binary relation. An $\mathcal {R}$-lossy PKE scheme with efficient opening is a 7-uple of PPT algorithms $(\mathsf {Par}\text {-}\mathsf {Gen}, \mathsf {Keygen},\mathsf {LKeygen},\mathsf {Encrypt},\mathsf {Decrypt},\mathsf {Opener},\mathsf {LOpener})$ such that:

• Parameter generation: On input of a security parameter $\lambda$, a desired length of of initialization values $L \in \mathsf {poly}(\lambda )$ and a lower bound $B \in \mathsf {poly}(\lambda )$ on the message length, $\mathsf {Par}\text {-}\mathsf {Gen}(1^\lambda ,1^L,1^B)$ outputs public parameters $\varGamma$ that specify a tag space $\mathcal {T}$, a space of initialization values $\mathcal {K}$, a public key space $\mathcal {PK}$, a secret key space $\mathcal {SK}$ and a trapdoor space $\mathcal {TK}$.

• Key generation: For an initialization value $K \in \mathcal {K}$ and public parameters $\varGamma$, algorithm $\mathsf {Keygen}(\varGamma ,K)$ outputs an injective public key $\mathsf {pk}\in \mathcal {PK}$, a decryption key $\mathsf {sk}\in \mathcal {SK}$ and a trapdoor key $\mathsf {tk}\in \mathcal {TK}$. The public key specifies a ciphertext space $\mathsf {CtSp}$ and a randomness space $R^{\mathsf {LPKE}}$.

• Lossy Key generation: Given an initialization value $K \in \mathcal {K}$ and public parameters $\varGamma$, the lossy key generation algorithm $\mathsf {LKeygen}(\varGamma ,K)$ outputs a lossy public key $\mathsf {pk}\in \mathcal {PK}$, a lossy secret key $\mathsf {sk}\in \mathcal {SK}$ and a trapdoor key $\mathsf {tk}\in \mathcal {TK}$.

• Decryption under injective tags: For any $\varGamma \leftarrow \mathsf {Par}\text {-}\mathsf {Gen}(1^\lambda ,1^L,1^B)$, any initialization value $K \in \mathcal {K}$, any tag $t \in \mathcal {T}$ such that $(K,t) \in \mathcal {R}$, and any message $\mathsf {Msg} \in \mathsf {MsgSp}$, we have

  $$ \Pr \left[ \exists r \in R^{\mathsf {LPKE}} : \mathsf {Decrypt} \big (\mathsf {sk},t,\mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg};r) \big ) \ne \mathsf {Msg} \right] < \nu (\lambda ), $$

  for some negligible function $\nu (\lambda )$, where $(\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {Keygen}(\varGamma ,K)$ and the probability is taken over the randomness of $\mathsf {Keygen}$.

• Indistinguishability: For any $\varGamma \leftarrow \mathsf {Par}\text {-}\mathsf {Gen}(1^\lambda ,1^L,1^B)$, the key generation algorithms $\mathsf {LKeygen}$ and $\mathsf {Keygen}$ satisfy the following:

  • (i) For any $K \in \mathcal {K}$, the distributions $D_{\mathrm {inj}}=\{(\mathsf {pk},\mathsf {tk}) \mid (\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {Keygen}(\varGamma ,K) \}$ and $D_{\mathrm {loss}}=\{(\mathsf {pk},\mathsf {tk}) \mid (\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {LKeygen}(\varGamma ,K) \}$ are computationally indistinguishable. Namely, for any PPT adversary $\mathcal {A}$, we have $\mathbf {Adv}^{\mathsf {indist}\text {-}\mathsf {LPKE}}_\mathcal {A}(\lambda ) \le \mathsf {negl}(\lambda )$, where

    $$\begin{aligned} \mathbf {Adv}_\mathcal {A}^{\mathsf {indist}\text {-}\mathsf {LPKE}}(\lambda ) : =&| \Pr [ (\mathsf {pk},\mathsf {tk}) \hookleftarrow D_{\mathrm {inj}} : \mathcal {A}(\mathsf {pk},\mathsf {tk}) = 1 ] \\&\qquad \quad - \Pr [ (\mathsf {pk},\mathsf {tk}) \hookleftarrow D_{\mathrm {loss}} : \mathcal {A}(\mathsf {pk},\mathsf {tk}) = 1] | . \end{aligned}$$

  • (ii) For any initialization values $K,K' \in \mathcal {K}$, the two distributions $\{ \mathsf {pk}\mid (\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {LKeygen}(\varGamma ,K) \}$ and $\{ \mathsf {pk}\mid (\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {LKeygen}(\varGamma ,K') \}$ are statistically indistinguishable. We require them to be $2^{-\varOmega (\lambda )}$-close in terms of statistical distance.

• Lossiness: For any $\varGamma \leftarrow \mathsf {Par}\text {-}\mathsf {Gen}(1^\lambda ,1^L,1^B)$, any initialization value $K \in \mathcal {K}$ and tag $t \in \mathcal {T}$ such that $(K,t) \not \in \mathcal {R}$, any $(\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {Keygen}(\varGamma ,K)$, and any $\mathsf {Msg}_0,\mathsf {Msg}_1 \in \mathsf {MsgSp}$, the following distributions are statistically close:

  $$\{C \mid C \leftarrow \mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg}_0 ) \} \quad ~ \approx _s ~\quad \{C \mid C \leftarrow \mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg}_1 ) \}. $$

  For any $(\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {LKeygen}(\varGamma ,K)$, the above holds for any tag t (and not only those for which $(K,t) \not \in \mathcal {R}$).

• Equivocation under lossy tags: For any $\varGamma \leftarrow \mathsf {Par}\text {-}\mathsf {Gen}(1^\lambda ,1^L,1^B)$, any $K \in \mathcal {K}$, any keys $(\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {Keygen}(\varGamma ,K)$ let $D_{R}$ denote the distribution, defined over the randomness space $R^\mathsf {LPKE}$, from which the random coins used by $\mathsf {Encrypt}$ are sampled. For any message $\mathsf {Msg} \in \mathsf {MsgSp}$ and ciphertext C, let $D_{\mathsf {pk},\mathsf {Msg},C,t}$ denote the probability distribution on $R^{\mathsf {LPKE}}$ with support

  $$S_{\mathsf {pk},\mathsf {Msg},C,t} = \{ \overline{r} \in R^\mathsf {LPKE}~|~\mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg},\overline{r})=C \},$$

  and such that, for each $\overline{r} \in S_{PK,\mathsf {Msg},C,t}$, we have

  $$\begin{aligned} D_{\mathsf {pk},\mathsf {Msg},C,t}(\overline{r}) = \Pr _{r' \hookleftarrow D_R}[r'=\overline{r} \mid \mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg},r') = C]. \end{aligned}$$

  (1)

  For any random coins $r \hookleftarrow D_R$, any tag $t \in \mathcal {T}_\lambda$ such that $(K,t) \not \in \mathcal {R}$, and any messages $\mathsf {Msg}_0,\mathsf {Msg}_1 \in \mathsf {MsgSp}$, algorithm $\mathsf {Opener}$ takes as inputs $\mathsf {pk}, C=\mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg}_0, r )$, r t, and $\mathsf {tk}$. It outputs a sample $\overline{r}$ from a distribution statistically close to $D_{\mathsf {pk},\mathsf {Msg}_1,C,t}$.

• Equivocation under lossy keys: For any initialization value $K \in \mathcal {K}_\lambda$, any keys $(\mathsf {pk},\mathsf {sk},\mathsf {tk}) \leftarrow \mathsf {LKeygen}(\varGamma ,K)$, any random coins $r \hookleftarrow D_R$, any tag $t \in \mathcal {T}_\lambda$, and any distinct messages $\mathsf {Msg}_0,\mathsf {Msg}_1 \in \mathsf {MsgSp}$, algorithm $\mathsf {LOpener}$ takes as input $C =\mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg}_0, r )$, r, t and $\mathsf {sk}$. It outputs $\overline{r} \in R^{\mathsf {LPKE}}$ such that $C =\mathsf {Encrypt}(\mathsf {pk},t,\mathsf {Msg}_1, \bar{r} )$. We require that, for any $t \in \mathcal {T}_\lambda$ such that $(K,t) \not \in \mathcal {R}$, the distributions

  $$ \{ \bar{r} \leftarrow \mathsf {LOpener}( \mathsf {pk},\mathsf {sk},t,\mathsf {ct},\mathsf {Msg}_0,\mathsf {Msg}_1,r) \mid r \hookleftarrow D_{R} \} $$

  and $\{ \bar{r} \leftarrow \mathsf {Opener}( \mathsf {pk},\mathsf {tk},t,\mathsf {ct},\mathsf {Msg}_0,\mathsf {Msg}_1,r) \mid r \hookleftarrow D_{R} \}$ be statistically close.

The above definition is slightly weaker than the one of [60] in the property of equivocation under lossy keys. Here, we do not require that the outputs of $\mathsf {Opener}$ and $\mathsf {LOpener}$ be statistically close to $D_{\mathsf {pk},\mathsf {Msg}_1,C,t}$ as defined in (1): We only require that, on lossy keys and lossy tags, $\mathsf {Opener}$ and $\mathsf {LOpener}$ sample random coins from statistically close distributions. In fact, the first indistinguishability property implies (since the distinguisher is given $\mathsf {tk}$) that the outputs of both algorithms will be computationally indistinguishable from $D_{\mathsf {pk},\mathsf {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 $\mathsf {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 pre-defined set $R^{\mathsf {LPKE}}$.

2.8 Trapdoor $\varSigma$-Protocol Showing Composite Residuosity

We recall the trapdoor $\varSigma$-protocols of [61], which allows proving that an element of $\mathbb {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 $\zeta >1$. We describe a trapdoor $\varSigma$-protocol for the language

$$\begin{aligned} \mathcal {L}^{\mathsf {DCR}} := \{ x \in \mathbb {Z}_{N^{\zeta +1}}^*\mid \exists w \in \mathbb {Z}_{N}^\star : x = w^{N^\zeta } \bmod N^{\zeta +1} \}. \end{aligned}$$

We assume that the challenge space is $\{0,\ldots ,2^{\lambda }-1\}$ and that $p,q >2^{l(\lambda ) }$, for some polynomial $l :\mathbb {N}\rightarrow \mathbb {N}$ such that $l(\lambda )>\lambda$ for any sufficiently large $\lambda \in \mathbb {N}$. The condition $p,q>2^\lambda$ will ensure that the difference between any two challenges be co-prime with N.

In order to obtain a $\mathsf {BadChallenge}$ function that identifies bad challenges for elements $x \not \in \mathcal {L}^{\mathsf {DCR}}$, one difficulty is the case of elements $x \in \mathbb {Z}_{N^{\zeta +1}}^*$ that are encryptions of an element $\alpha _x \in \mathbb {Z}_N$ such that $1<\gcd (\alpha _x,N^\zeta ) <N^\zeta$. Indeed, we cannot immediately identify a unique bad challenge by inverting $\alpha _x$ in $\mathbb {Z}_{N^\zeta }$. However, a closer analysis shows that, even when $\zeta >1$ and $\gcd (\alpha _x,N^\zeta ) >1$, at most one bad challenge can exist in the set $\{0,1,\ldots ,2^\lambda -1\}$.

• Gen$_\mathsf {par}(1^\lambda ):$ Given the security parameter $\lambda$, define $\mathsf {par}= \{ \lambda \}$.

• Gen$_\mathcal {L}(\mathsf {par},\mathcal {L}^{\mathsf {DCR}}):$ Given public parameters $\mathsf {par}$ as well as a description of a language $\mathcal {L}^{\mathsf {DCR}}$, consisting of an RSA modulus $N = pq$ with p and q prime satisfying $p,q >2^{l(\lambda ) }$, for some polynomial $l :\mathbb {N}\rightarrow \mathbb {N}$ such that $l(\lambda )>\lambda$, define the language-dependent $\mathsf {crs}_\mathcal {L}= \{N \}$. The global CRS is

  $$\begin{aligned} \mathsf {crs}= (\{\lambda \}, \mathsf {crs}_\mathcal {L}). \end{aligned}$$

• TrapGen$(\mathsf {par},\mathcal {L}^{\mathsf {DCR}},\tau _\mathcal {L}):$ Given $\mathsf {par}$, the description of a language $\mathcal {L}^{\mathsf {DCR}}$ that specifies an RSA modulus N and a membership-testing trapdoor $\tau _\mathcal {L}=(p,q)$ consisting of the factorization of $N=pq$, output the language-dependent $\mathsf {crs}_\mathcal {L}= \{ N \}$ which defines $\mathsf {crs}= (\{\lambda \}, \mathsf {crs}_\mathcal {L})$ and the trapdoor $\tau _\varSigma = (p,q)$.

• P$\big (\mathsf {crs}, {x}, {w} \big ) \leftrightarrow$ V$(\mathsf {crs}, {x}):$ Given a $\mathsf {crs}$, a statement $x = w^{N^\zeta } \bmod N^{\zeta +1}$, P (who has the witness $w \in \mathbb {Z}_{N}^\star$) and V interact as follows:

  • 1. P chooses a random $r \hookleftarrow U(\mathbb {Z}_{N}^*)$ and sends $a = r^{N^\zeta } \bmod N^{\zeta +1}$ to V.

  • 2. V sends a random challenge $\mathsf {Chall} \hookleftarrow U(\{0,\ldots ,2^\lambda -1\})$ to P.

  • 3. P computes the response $z = r \cdot w^\mathsf {Chall}\bmod N$ and sends it to V.

  • 4. V checks if $a \cdot x^\mathsf {Chall}\equiv z^{N^\zeta } \pmod { N^{\zeta +1} }$ and returns 0 if this condition is not satisfied.

• BadChallenge$\big (\mathsf {par}, \tau _\varSigma ,\mathsf {crs}, {x}, {a} \big ):$ Given $\tau _\varSigma = (p,q)$, decrypt x and a to obtain $\alpha _x = \mathcal D_{\tau _\varSigma }(x) \in \mathbb {Z}_{N^\zeta }$, $\alpha _a = \mathcal D_{\tau _\varSigma }(a) \in \mathbb {Z}_{N^\zeta }$.

  • 1. If $\alpha _a = 0$, return $\mathsf {Chall}= 0$.

  • 2. If $\alpha _a \ne 0$, let $d_x=\gcd (\alpha _x,N^\zeta )$, which lives in the set

    $$ \{ p^iq^j \mid 0 \le i< \zeta , ~0 \le j<\zeta \} \cup \{ p^i q^\zeta \mid 0 \le i<\zeta \} \cup \{ p^s q^j \mid 0 \le j <\zeta \} .$$

    Then, do the following:

    • a. If $1< d_x <N^\zeta$, return $\perp$ if $d_x$ does not divide $N^\zeta -\alpha _a$.

    • b. Otherwise, the congruence $\alpha _a + \mathsf {Chall} \cdot \alpha _x \equiv 0 \pmod {\frac{N^\zeta }{d_x}}$ has a unique solution $\mathsf {Chall}'= - \alpha _x^{-1} \cdot \alpha _a \in \mathbb {Z}_{N^\zeta /d_x}$ since $\gcd (\alpha _x,N^\zeta /d_x)=1$. If $\mathsf {Chall}' \in \mathbb {Z}_{N^\zeta /d_x} \setminus \{0,\ldots ,2^\lambda -1\}$, return $\perp$. Else, return $\mathsf {Chall}=\mathsf {Chall}'$.

In [61], it is shown that the above construction is a trapdoor $\varSigma$-protocol with large challenge space. By applying [72], this implies compact NIZK arguments (i.e., without using parallel repetitions to achieve negligible soundness error) for the language $\mathcal {L}^{\mathsf {DCR}}$ assuming that the $\mathsf {LWE}$ assumption holds.

Lemma 2.23

([61]). The above protocol is a trapdoor $\varSigma$-protocol for the language $\mathcal {L}^{\mathsf {DCR}}$.

3 NIZK Arguments with One-Time Simulation-Soundness

Libert et al. [60] gave a method that directly compiles (i.e., without relying on generic NIZK techniques [37]) any trapdoor $\varSigma$-protocol for a trapdoor language into an unbounded simulation-sound NIZK argument for the same language. As a building block, their construction uses an $\mathsf {LWE}_{}$-based equivocable $\mathcal {R}$-lossy PKE scheme for the bit-matching relation. Under the $\mathsf {DCR}$ assumption, a more efficient $\mathcal {R}$-lossy PKE scheme was described in [61]. In this section, we show that, in applications that only require one-time simulation-soundness, we can use an $\mathcal {R}$-lossy PKE scheme with a constant-size public key. In contrast, the $\mathcal {R}$-lossy PKE system of [61] has a large public key comprised of $\varTheta (\lambda )$ Paillier ciphertexts.

In our one-time simulation-sound arguments, we use an $\mathcal {R}$-lossy PKE scheme for the inequality relation.

Definition 3.1

Let $\mathcal {K}=\{0,1\}^{\ell }$ and $\mathcal {T}=\{0,1\}^{\ell }$, for some ${\ell }\in \mathsf {poly}(\lambda )$. The inequality relation $\mathcal {R}_\mathsf {NEQ}: \mathcal {K } \times \mathcal {T} \rightarrow \{0,1\}$ is the relation where $\mathcal {R}_\mathsf {NEQ}(K,t)=1$ if and only if $K \ne t$.

3.1 An $\mathcal {R}_\mathsf {NEQ}$-Lossy PKE Scheme from $\mathsf {DCR}$

Our $\mathsf {DCR}$-based $\mathcal {R}_\mathsf {NEQ}$-lossy PKE scheme goes as follows.

• ${\mathbf {\mathsf{{Par}}}}\text {-}{\mathbf {\mathsf{{Gen}}}}(1^\lambda ,1^L,1^B)$: Define $\mathcal {K}=\mathcal {T}=\{0,1\}^L$, so that the tag and initialization value spaces coincide. Define public parameters as $\varGamma = (1^\lambda ,1^L,1^B)$.

• ${\mathbf {\mathsf{{Keygen}}}}(\varGamma ,K)$: On input of public parameters $\varGamma$ and $K \in \mathcal {K}$, generate a key pair as follows.

  • 1. Choose an RSA modulus $N=pq$ such that $p,q >2^{l (\lambda )}$, for some polynomial $l : \mathbb {N} \rightarrow \mathbb {N}$ such that $l(\lambda )>L(\lambda )$ for any sufficiently large $\lambda$, and an integer $\zeta \in \mathsf {poly}(\lambda )$ such that $N^\zeta >2^B$.

  • 2. Pick $u \hookleftarrow U(\mathbb {Z}_{N^{\zeta +1}}^*)$, $\bar{v} \hookleftarrow U(\mathbb {Z}_N^*)$ and compute $v = u^{-K} \cdot \bar{v}^{N^\zeta } \bmod N^{\zeta +1}$, where K is interpreted as an element of $\mathbb {Z}_{N^\zeta }$.

  Define $R^{\mathsf {LPKE}} = \mathbb {Z}_{N}^*$ and output $\mathsf {sk}= (p,q,K)$ as well as

  $$\mathsf {pk}:= \Bigl ( N,\zeta ,u,v \Bigr ), \quad \quad \mathsf {tk}=( \bar{v},K) . $$

• LKeygen$(\varGamma ,K)$: On input of public parameters $\varGamma$ and an initialization value $K \in \mathcal {K}$, generate a key pair as follows.

  • 1. Choose an RSA modulus $N=pq$ such that $p,q >2^{l (\lambda )}$, for some polynomial $l : \mathbb {N} \rightarrow \mathbb {N}$ such that $l(\lambda )>L(\lambda )$ for any sufficiently large $\lambda$, and an integer $\zeta \in \mathsf {poly}(\lambda )$ such that $N^\zeta >2^B$.

  • 2. Choose $\bar{u} ,\bar{v} \hookleftarrow U(\mathbb {Z}_{N}^*)$ uniformly. Compute $u = \bar{u}^{N^\zeta } \bmod N^{\zeta +1}$ and $v = u^{-K} \cdot \bar{v}^{N^\zeta } \bmod N^{\zeta +1}$, where K is interpreted as an element of $\mathbb {Z}_{N^\zeta }$.

  Define $R^{\mathsf {LPKE}} = \mathbb {Z}_{N}^*$ and output $\mathsf {sk}= (\bar{u},\bar{v},K)$ as well as $\mathsf {pk}:= \bigl ( N,\zeta ,u,v \bigr )$ and $\mathsf {tk}=( \bar{v},K) .$

• Encrypt$(\mathsf {pk},t,\mathsf {Msg})$: To encrypt $\mathsf {Msg} \in \mathbb {Z}_{N^\zeta }$ for the tag $t \in \{0,1\}^L$, interpret t as an element of $\mathbb {Z}_{N^\zeta }$. Pick $r \hookleftarrow U(\mathbb {Z}_N^*)$ and compute

  $$ \mathsf {ct}= (u^t \cdot v)^{\mathsf {Msg}} \cdot r^{N^\zeta } \bmod N^{\zeta +1}. $$

• Decrypt$(\mathsf {sk},t,\mathsf {ct})$: Given $sk= (p,q,t^\star )$ and the tag $t \in \{0,1\}^L$, interpret t as an element of $\mathbb {Z}_{N^\zeta }$. Then, do the following:

  • 1. Letting $\lambda (N)= \mathrm {lcm}(p-1,q-1)$, compute $h_t = (u^t \cdot v)^{\lambda (N)} \bmod N^{\zeta +1}$, which can be written $h_t= 1+ g_t N \bmod N^{\zeta +1}$, for some $g_t \in \mathbb {Z}_{N^\zeta }$, since its order is at most $N^\zeta$. Return $\perp$ if $g_t=0$ or $\gcd (g_t,N^\zeta )>1$.

  • 2. Otherwise, compute $\mathsf {Msg} = \frac{ (\mathsf {ct}^{\lambda (N)} \bmod N^{\zeta +1}) -1}{N} \cdot g_t^{-1} \bmod N^\zeta ,$ where the division is computed over $\mathbb {Z}$, and output $\mathsf {Msg} \in \mathbb {Z}_{N^\zeta }$.

• Opener$(\mathsf {pk},\mathsf {tk},t,\mathsf {ct},\mathsf {Msg}_0,\mathsf {Msg}_1,r)$: Given $\mathsf {tk}= (\bar{v},K)$ and $t \in \{0,1\}^L$, return $\perp$ if $t \ne K$ when they are interpreted as elements of $\mathbb {Z}_{N^\zeta }$. Otherwise, given $\mathsf {Msg}_0, \mathsf {Msg}_1 \in \mathbb {Z}_{N^\zeta }$ and $r \in \mathbb {Z}_N^*$ such that

  $$\begin{aligned} \mathsf {ct}= (u^t \cdot v)^{\mathsf {Msg}_0} \cdot r^{N^\zeta } = (\bar{v}^N)^{\mathsf {Msg}_0} \cdot r^{N^\zeta } \bmod N^{\zeta +1}, \end{aligned}$$

  (2)

  output $\bar{r} = r \cdot \bar{v}^{\mathsf {Msg}_0 - \mathsf {Msg}_1} \bmod N$, so that $\mathsf {ct}= (u^t \cdot v)^{\mathsf {Msg}_1} \cdot \bar{r}^{N^\zeta } \bmod N^{\zeta +1}.$

• LOpener$(\mathsf {sk},t, \mathsf {ct},\mathsf {Msg}_0,\mathsf {Msg}_1,r)$: Given $\mathsf {sk}= (\bar{u},\bar{v},K)$ and $t \in \{0,1\}^L$, interpret t as an element of $\mathbb {Z}_{N^\zeta }$. Given $\mathsf {Msg}_0,\mathsf {Msg}_1 \in \mathbb {Z}_{N^\zeta }$ and $r \in \mathbb {Z}_N^*$ such that

  $$\begin{aligned} \mathsf {ct}= (u^t \cdot v)^{\mathsf {Msg}_0} \cdot r^{N^\zeta } = (\bar{u}^{t-K} \cdot \bar{v} )^{N \cdot \mathsf {Msg}_0} \cdot r^{N^\zeta } \bmod N^{\zeta +1}, \end{aligned}$$

  (3)

  output $\bar{r} = r \cdot (\bar{u}^{t-K} \cdot \bar{v} )^{\mathsf {Msg}_0 - \mathsf {Msg}_1} \bmod N$, which satisfies

  $$ \mathsf {ct}= (u^t \cdot v)^{\mathsf {Msg}_1} \cdot \bar{r}^{N^\zeta } \bmod N^{\zeta +1}.$$

The scheme enables decryption under injective tags because, with high probability over the randomness of $\mathsf {Keygen}$, the order of u is a multiple of $N^\zeta$ since u is sampled uniformly in $\mathbb {Z}_{N^{\zeta +1}}^*$ at step 2. Since $t,K \in \{0,1\}^L$ and $p,q>2^L$, we have $\gcd (t-K,N^\zeta )=1$, so that $N^\zeta$ divides the order of $u^{t-K} \cdot \bar{v}^{N^\zeta }$ when $t \ne K$. This ensures that $h_t$ has order $N^\zeta$ and $\gcd (g_t,N^\zeta )=1$ at step 1 of $\mathsf {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 $\mathsf {tk}$ of $\mathsf {Opener}$ is given. This is important for our proof of one-time simulation-soundness, which requires that $\mathsf {Opener}$ be able to equivocate lossy ciphertexts given only $\mathsf {tk}$ and without knowing the factorization of N (otherwise, we could not meaningfully rely on the $\mathsf {DCR}$ assumption to switch from lossy to injective keys).

Theorem 3.2

The above construction is an $\mathcal {R}_\mathsf {NEQ}$-lossy PKE scheme under the $\mathsf {DCR}$ assumption. (The proof is available in the full version of the paper [40]).

3.2 The Argument System

Our one-time simulation-sound argument is very similar to the one of [60] which provides unbounded simulation-soundness using a more expensive $\mathcal {R}$-lossy PKE scheme. The construction relies on the following ingredients.

• A trapdoor $\varSigma$-protocol $\mathsf {\varPi }'=(\mathsf {Gen}_\mathsf {par}',\mathsf {Gen}_\mathcal {L}',\mathsf {P}',\mathsf {V}')$ for an NP language $\mathcal {L}$. This protocol should satisfy the properties of Definition 2.21. In addition, the function $\mathsf {BadChallenge}(\tau _\varSigma ,\mathsf {crs},x, {a})$ should be computable within time $T \in \mathsf {poly}(\lambda )$ for any input $(\tau ,\mathsf {crs},x,{a})$. Let also $B \in \mathsf {poly}(\lambda )$ the maximal length of the first prover message sent by $\mathsf {P}'$.

• A strongly unforgeable one-time signature scheme $\mathsf {OTS}=(\mathcal {G},\mathcal {S},\mathcal {V})$ with verification keys in $\{0,1\}^L$, where $L \in \mathsf {poly}(\lambda )$.

• An $\mathcal {R}_\mathsf {NEQ}$-lossy PKE scheme $\varPi ^{\mathsf {LPKE}}=(\mathsf {Par}\text {-}\mathsf {Gen}, \mathsf {Keygen},\mathsf {LKeygen},\mathsf {Encrypt},$ $\mathsf {Decrypt},\mathsf {Opener},\mathsf {LOpener})$ with space $\mathcal {K}=\mathcal {T}=\{0,1\}^L$. We assume that its decryption algorithm is computable within time T.

• A correlation intractable hash family $\mathcal {H}=(\mathsf {Gen},\mathsf {Hash})$ for the class $\mathcal {R}_{\mathsf {CI}}$ of relations that are efficiently searchable within time T.

• Gen$_\mathsf {par}(1^\lambda )$: Run $\mathsf {par}\leftarrow \mathsf {Gen}_\mathsf {par}'(1^\lambda )$ and output $\mathsf {par}$.

• Gen$_\mathcal {L}(\mathsf {par},\mathcal {L})$: Given public parameters $\mathsf {par}$ and a language $\mathcal {L}$, the CRS is generated as follows.

  • 1. Generate a CRS $\mathsf {crs}_\mathcal {L}' \leftarrow \mathsf {Gen}_\mathcal {L}'(\mathsf {par},\mathcal {L})$ for the trapdoor $\varSigma$-protocol $\mathsf {\varPi }'$.

  • 2. Choose the description a one-time signature scheme $\mathsf {OTS}=(\mathcal {G},\mathcal {S},\mathcal {V})$ with verification keys in $\{0,1\}^L$, where $L \in \mathsf {poly}(\lambda )$.

  • 3. Choose public parameters $\varGamma \leftarrow \varPi ^{\mathsf {LPKE}}.\mathsf {Par}\text {-}\mathsf {Gen}(1^\lambda ,1^L,1^B)$ for an $\mathcal {R}_\mathsf {NEQ}$-lossy PKE scheme with tag space $\mathcal {K}=\mathcal {T}=\{0,1\}^L$. Then, generate lossy keys $(\mathsf {pk}_\mathsf {LPKE},\mathsf {sk}_\mathsf {LPKE},\mathsf {tk}_\mathsf {LPKE}) \leftarrow \varPi ^{\mathsf {LPKE}}. \mathsf {LKeygen}(\varGamma ,0^L)$.

  • 4. Generate a key $k \leftarrow \mathsf {Gen}(1^\lambda )$ for a correlation intractable hash function with output length $\kappa = \varTheta (\lambda )$.

  Output the language-dependent CRS $\mathsf {crs}_\mathcal {L}:= \big ( \mathsf {crs}_\mathcal {L}',\mathsf {pk}_\mathsf {LPKE},k \big )$ and the simulation trapdoor $\tau _{\mathsf {zk}}:=\mathsf {sk}_\mathsf {LPKE}$. The global common reference string consists of $\mathsf {crs}=(\mathsf {par},\mathsf {crs}_\mathcal {L},\mathsf {pk}_\mathsf {LPKE},\mathsf {OTS})$.

• P$(\mathsf {crs},x,w,\mathsf {lbl}):$ To prove a statement $x \in \mathcal {L}$ for a label $\mathsf {lbl}\in \{0,1\}^*$ using the witness w, generate a one-time signature key pair $(\mathsf {VK},\mathsf {SK}) \leftarrow \mathcal {G}(1^\lambda )$. Then,

  • 1. Compute $( {a}' ,st' ) \leftarrow \mathsf {P}'(\mathsf {crs}_\mathcal {L}',x,w)$. Then, sample $r \hookleftarrow D_R^\mathsf {LPKE}$ in the randomness space $R^{\mathsf {LPKE}}$ of $\varPi ^{\mathsf {LPKE}}$. Using the tag $\mathsf {VK}\in \{0,1\}^L$, compute $a \leftarrow \varPi ^{\mathsf {LPKE}}.\mathsf {Encrypt}(\mathsf {pk}_\mathsf {LPKE}, \mathsf {VK}, a';r ) .$

  • 2. Compute $\mathsf {Chall}=\mathsf {Hash}(k,(x, {a},\mathsf {VK}))$.

  • 3. Compute ${z}' =\mathsf {P}'(\mathsf {crs}_\mathcal {L}',x,w, {a}',\mathsf {Chall},st')$ by executing the prover of $\mathsf {\varPi }'$. Define ${z}=({z}',{a}',r)$.

  • 4. Generate $sig\leftarrow \mathcal {S}(\mathsf {SK},(x, {a}, {z},\mathsf {lbl}))$ and output $\varvec{\pi } = \big (\mathsf {VK}, ( {a}, {z}), sig \big ).$

• V$(\mathsf {crs},x,\varvec{\pi },\mathsf {lbl}):$ Given a statement x, a label $\mathsf {lbl}$ as well as a purported proof $\varvec{\pi } = \big (\mathsf {VK}, ( {a}, {z}), sig \big )$, return 0 if $\mathcal {V}(\mathsf {VK},(x, {a} , {z},\mathsf {lbl}),sig)=0$. Otherwise,

  • 1. Write ${z}= ({z}',{a}',{r})$ and return 0 if any of these does not parse properly or if $a \ne \varPi ^{\mathsf {LPKE}}.\mathsf {Encrypt}(\mathsf {pk}_\mathsf {LPKE}, \mathsf {VK}, a';r )$.

  • 2. Let $\mathsf {Chall}=\mathsf {Hash}\big (k,(x, {a},\mathsf {VK}) \big )$. If $\mathsf {V}'(\mathsf {crs}_\mathcal {L}',x,{a}',\mathsf {Chall},{z}'))=1$, return 1. Otherwise, return 0.

Theorem 3.3

The above argument is statistically (resp. computationally) zero-knowledge if: (i) $\varPi ^\mathsf {LPKE}$ is statistically equivocable under lossy keys; (ii) The trapdoor $\varSigma$-protocol $\varPi '$ is statistically (resp. computationally) special zero-knowledge. (The proof is given in the full version of the paper.)

Theorem 3.4

The above construction provides one-time simulation-soundness if: (i) $\mathsf {OTS}$ is a strongly unforgeable one-time signature; (ii) $\varPi ^\mathsf {LPKE}$ is an $\mathcal {R}_\mathsf {NEQ}$-lossy PKE scheme; (iii) The hash function family $\mathcal {H}$ is correlation-intractable for all relations that are searchable within time T, where T denotes the maximal running time of algorithms $\mathsf {BadChallenge}(\cdot ,\cdot ,\cdot ,\cdot )$ and $\varPi ^\mathsf {LPKE}.\mathsf {Decrypt}(\cdot ,\cdot ,\cdot )$. (The proof is given in the full version of the paper.)

4 An Adaptively Secure CCA2-Secure Threshold Encryption Scheme Based on Paillier and $\mathsf {LWE}$

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 [20]. As in [66], we use a generalization of the Camenisch-Shoup system based on ideas from Damgård and Jurik [34].

For simplicity, we first present a non-robust version of the scheme. In the full version of the paper, we 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^\lambda ,\mathbb {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(\lambda )}$, where $l : \mathbb {N} \rightarrow \mathbb {N}$ is a polynomial. Choose an integer $\zeta \ge 1$ so as to define the message space as $\mathsf {MsgSp}= \mathbb {Z}_{N^\zeta }$. Then, define the language

    $$\begin{aligned} \mathcal {L}^{\mathsf {DCR}} := \{ x \in \mathbb {Z}_{N^{\zeta +1}}^*\mid \exists w \in \mathbb {Z}_{N}^\star : x = w^{N^\zeta } \bmod N^{\zeta +1} \} \end{aligned}$$

    and choose $g_0 \hookleftarrow U(\mathbb {Z}_{N}^*)$.

  • 2. Generate a common reference string $\mathsf {crs}\leftarrow \mathsf {Setup}(1^\lambda )$ for the one-time simulation-sound argument system $\mathsf {\varPi ^{OTSS}} = (\mathsf {Setup}, \mathsf {P}, \mathsf {V})$ of Sect. 3.

  • 3. Let $\sigma > \sqrt{\lambda \cdot e} \cdot N^\zeta$ be a Gaussian parameter, where $e = \varOmega (\ell ^{(1+ \sqrt{2})/2})$ is the dimension of the matrix $\mathbf {M}$ in Sect. 2.3. Sample a secret key $x \hookleftarrow D_{\mathbb {Z}, \sigma }$ and compute $h=g_0^{4N^\zeta \cdot x} \bmod N^{\zeta +1}$. Define the public key $\mathsf {pk}:=(N,\zeta ,g_0,\mathsf {crs})$ whereas the centralized secret key $\mathsf {sk}:=x \in \mathbb {Z}$.

  • 4. Share $\mathsf {sk}$ using a LISS scheme. To this end, sample $\bar{\varvec{\rho }}=(\rho _2,\ldots ,\rho _e)^\top \hookleftarrow (D_{\mathbb {Z},\sigma })^{(e-1) }$, define $\varvec{\rho } =[x \mid \bar{\varvec{\rho }}^\top ]^\top \in \mathbb {Z}^e$ and compute

    $$ \varvec{s}= \begin{bmatrix} s_1 \\ \vdots \\ s_d \end{bmatrix} =\mathbf {M}\cdot \varvec{\rho } \in \mathbb {Z}^{d} ,$$

    where $\mathbf {M} \in \mathbb {Z}^{d \times e}$ is the share-generating matrix of Sect. 2.3, which computes the Boolean formula associated with the threshold access structure $\mathbb {A}$. Then, define the private key shares as

    $$\mathsf {sk}_i= \big (s_{ j} \big )_{ j \in \psi ^{-1}(i) } =\big ( \mathbf {M}_{j} \cdot \varvec{\rho } \big )_{ j \in \psi ^{-1}(i) } \in \mathbb {Z}^{d_i } \qquad \quad \forall i \in [\ell ], $$

    where $\mathbf {M}_{j} \in \mathbb {Z}^{1 \times e}$ denotes the j-th row of $\mathbf {M}$ while $d_i$ stands for the number of rows assigned by the LISS scheme to server i.

  Finally, output the public key $\mathsf {pk}=(N,\zeta ,g_0,\mathsf {crs})$ and the vector of secret-key shares $(\mathsf {sk}_1,\mathsf {sk}_2,\dots ,\mathsf {sk}_\ell )$.

• Encrypt$(\mathsf {pp},\mathsf {pk},\mathsf {Msg})$: To encrypt $\mathsf {Msg} \in \mathbb {Z}_{N^\zeta }$, choose $r \hookleftarrow U(\{0,\ldots , \lfloor N/4 \rfloor \})$ and compute

  $$\begin{aligned} C_{0}= & {} {g_0}^{2N^\zeta \cdot r} \bmod N^{\zeta +1} \qquad \quad C_1 = (1+N)^{\mathsf {Msg}} \cdot h^r \bmod N^{\zeta +1} \end{aligned}$$

  Then, using the witness $w=g_0^{2r} \bmod N$, compute a simulation-sound NIZK argument $\varvec{\pi } \leftarrow \mathsf {P}\big (\mathsf {crs}, C_0,g_0^{2r} \bmod N ,\mathsf {lbl}\big )$ that $C_0 \in \mathcal {L}^{\mathsf {DCR}}$ using the label $\mathsf {lbl}=C_1$. Then, return the ciphertext $\mathsf {ct}:=(C_0,C_1,\varvec{\pi })$.

• PartDec$\big (\mathsf {pp},\mathsf {sk}_i ,\mathsf {ct}\big )$: On input of its share $\mathsf {sk}_i=\left\{ s_{ j} = \mathbf {M}_{j} \cdot \varvec{\rho } \right\} _{ j \in \psi ^{-1}(i) }$ and a ciphertext $\mathsf {ct}=(C_0,C_1,\varvec{\pi })$, the i-th server does the following.

  • 1. If $\mathsf {V}(\mathsf {crs},{C}_0,\varvec{\pi },\mathsf {lbl})=0$, return $\perp$.

  • 2. For each $j \in \psi ^{-1}(i)=\{j_1,\ldots ,j_{d_i}\}$, compute $\mu _{i,j} = C_0^{2 \cdot s_j } \bmod N^{\zeta +1}$ and return

    $$\begin{aligned} \varvec{\mu }_i= & {} ( \mu _{i,j_1}, \ldots ,\mu _{i,j_{d_i}} ) \\= & {} \big ( C_0^{ 2 \cdot s_{j_1} } \bmod N^{\zeta +1} ,~ \ldots ,~C_0^{2 \cdot s_{j_{d_i}}} \bmod N^{\zeta +1} \big ) ~\in (\mathbb {Z}_{N^{\zeta +1}}^*)^{d_i}. \end{aligned}$$

• Combine$\big (\mathsf {pp},\mathcal {B}=(\mathcal {S}\in \mathbb {A}, \{\varvec{\mu }_i \}_{i\in \mathcal {S}}) ,\mathsf {ct}=(C_0,C_1,\varvec{\pi }) \big )$: First, parse the set $\mathcal {S}$ as $\mathcal {S}=\{j_1,\dots ,j_t\}$ and find a vector $\varvec{\lambda }_\mathcal {S}= [\varvec{\lambda }_{j_1}^\top \mid \ldots \mid \varvec{\lambda }_{j_t}^\top ]^\top \in \{-1,0,1\}^{d_\mathcal {S}}$ such that $\varvec{\lambda }_\mathcal {S}\cdot \mathbf {M}_{\psi ^{-1}(\mathcal {S})}=(1,0,\ldots ,0)$, where $d_\mathcal {S}=\sum _{i\in \mathcal {S}}d_{i}$ and $\varvec{\lambda }_{j_i} =( \lambda _{j_i,1}, \ldots ,\lambda _{j_i,d_{j_i}} ) \in \{-1,0,1\}^{d_{i}}$ for all $i \in [t]$. Then, do the following:

  • 1. Compute

    $$ \hat{\mu } \triangleq \prod _{i\in [t]} \prod _{k \in [d_{j_i}]} \mu _{j_i,k}^{ \lambda _{j_i,k}} \bmod N^{\zeta +1}. $$

  • 2. Compute $\hat{C}_1 = C_1 / \hat{\mu } \bmod N^{\zeta +1}$ and return $\perp$ if $\hat{C}_1\not \equiv 1 \pmod N$. Otherwise, return $\mathsf {Msg} = ({\hat{C}_1-1})/{N} \in \mathbb {Z}_{N^\zeta }$.

In the dealing phase, the matrix $\mathbf {M} \in \mathbb {Z}^{d \times e}$ has $O(\log \ell )$ non-zero entries for threshold access structures. If we apply the LISS scheme based on the Benaloh-Leichter secret sharing [9] and the result of Hoory et al. [54], $\mathbf {M}$ has dimensions $d,e=O(\ell ^{1+\sqrt{2}})$, so that its rows have norm $\Vert \mathbf {M}_j \Vert =O(\sqrt{e} \log \ell )$, which leads to share units of magnitude $| s_j| = O(\sigma e \cdot \log \ell )$.

The scheme thus provides compactness in the sense of Definition 2.13 since the size of ciphertexts and public keys only depends on $\lambda$. By increasing the exponent $\zeta >1$, the ratio between ciphertext and plaintext sizes can approach 1, which was not possible in [62, 65].⁶ 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 $\mathsf {DCR}$ assumption holds; (ii) The argument system $\mathsf {\varPi ^{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 $\mathsf {Game}_i$.

• Game$_0$: This is the real IND-CCA game. The challenger faithfully answers all queries. In the challenge phase, the adversary $\mathcal {A}$ chooses two messages $\mathsf {Msg}_0,\mathsf {Msg}_1 \in \mathbb {Z}_{N^\zeta }$. The challenger flips a coin $b \hookleftarrow U(\{0,1\})$ and computes the challenge ciphertext $\mathsf {ct}^*=(C_0^*,C_1^*,\varvec{\pi }^\star )$ by running the real encryption algorithm. When $\mathcal {A}$ halts, it outputs $b' \in \{0,1\}$ and we denote by $W_0$ the event that $b'=b$. By definition $\mathbf {Adv}^{\mathrm {ind}\text {-}\mathrm {cca}}(\mathcal {A}):=|\Pr [W_0]-1/2|$.

• Game$_1$: This game is identical to $\mathsf {Game}_0$ except that we change the generation of the common reference string and the generation of $\varvec{\pi }^\star$ in the challenge ciphertext. In the key generation phase, the challenger runs $(\mathsf {crs},\tau _{\mathsf {zk}})\leftarrow \mathsf {Sim}_0(1^\lambda ,\mathcal {L}^{\mathsf {DCR}})$. In the challenge ciphertext $\mathsf {ct}^\star =(C_0^\star ,C_1^\star ,\varvec{\pi }^\star )$, the NIZK argument $\varvec{\pi }^\star$ is simulated as $\varvec{\pi }^\star \leftarrow \mathsf {Sim}_1 \big (\mathsf {crs},\tau _{\mathsf {zk}}, {C}_0^\star , {C}_1^\star \big )$ without using the witness. From the perfect zero-knowledge property of $\mathsf {\varPi ^{OTSS}}$, $\mathsf {Game}_1$ is indistinguishable from $\mathsf {Game}_0$ and $\Pr [W_1]=\Pr [W_0]$.

• Game$_2$: This game is identical to $\mathsf {Game}_1$ except that we change the generation of the challenge ciphertext $\mathsf {ct}^\star =(C_0^\star ,C_1^\star ,\varvec{\pi }^\star )$. Now, the challenger first samples $z_0 \hookleftarrow U(\mathbb {Z}_N^*)$, which is used to compute $z = z_0^{N^\zeta } \bmod N^{\zeta +1}$ and then

  $$\begin{aligned} C_0^\star= & {} z^2 \bmod N^{\zeta +1} , \qquad C_1^\star =(1+N)^{\mathsf {Msg}_b} \cdot {C_0^\star }^{2 x} \bmod N^{\zeta +1} , \end{aligned}$$

  (4)

  before simulating $\varvec{\pi }^\star \leftarrow \mathsf {Sim}_1 \big (\mathsf {crs},\tau _{\mathsf {zk}}, {C}_0^\star , {C}_1^\star \big )$ as in $\mathsf {Game}_1$. Since the subgroup of $2N^\zeta$-th residues is a cyclic group of order $p'q'$, the distribution of $(C_0^\star ,C_1^\star )$ is statistically close to that of $\mathsf {Game}_1$. Indeed, the distribution of $C_0^\star$ is now perfectly (instead of statistically) uniform in the subgroup of $2N^\zeta$-th residues. Hence, $|\Pr [W_2]-\Pr [W_1]| < 2^{-\varOmega (\lambda )}$.

• Game$_3$: This game is like $\mathsf {Game}_2$ except that, in order to construct the challenge ciphertext, we now sample $z \hookleftarrow U(\mathbb {Z}_{N^{\zeta +1}}^\star )$ uniformly in $\mathbb {Z}_{N^{\zeta +1}}^*$ instead of sampling it from the subgroup of $N^\zeta$-th residues. Then, $(C_0^\star ,C_1^\star )$ are still computed as per (4). Under the $\mathsf {DCR}$ assumption, this change goes unnoticed and a straightforward reduction shows that $| \Pr [W_3] - \Pr [W_2] | \le \mathbf {Adv}^{\mathsf {DCR}}(\lambda )$.

At this point, we are done with the $\mathsf {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 $\mathsf {ct}=(C_0,C_1,\varvec{\pi })$ such that $C_0$ is not an $N^\zeta$-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 $\mathsf {Game}_3$ is negligible: we have $|\Pr [W_4]-\Pr [W_3]| \le \mathbf {Adv}^{\mathsf {OTSS}}(\lambda )$.

• Game$_5$: We modify the partial decryption oracle and now reject post-challenge queries $\mathsf {ct}=(C_0,C_1,\varvec{\pi })$ such that $(C_0,C_1,\varvec{\pi }) \ne (C_0^\star ,C_1^\star ,\varvec{\pi }^\star )$ and $C_0$ is not an $N^\zeta$-th residue. By doing so, the challenger does not reject a ciphertext that would not have been rejected in $\mathsf {Game}_4$ until the event $F_5$ that $\mathcal {A}$ queries the partial decryption of a ciphertext $\mathsf {ct}=(C_0,C_1,\varvec{\pi })\ne (C_0^\star ,C_1^\star ,\varvec{\pi }^\star )$ such that $\mathsf {V}(\mathsf {crs},{C}_0,\varvec{\pi },C_1)=1$ although $C_0^{2p'q'} \bmod N^{\zeta +1} \ne 1$. Clearly, event $F_5$ would contradict the one-time simulation-soundness of the NIZK argument system $\varPi ^{\mathsf {OTSS}}$. We have $| \Pr [W_5] - \Pr [W_4] | \le \mathbf {Adv}^{\mathsf {OTSS}}(\lambda )$.

• Game$_6$: We finally modify the challenge ciphertext and now compute $(C_0^\star ,C_1^\star )$ by sampling $C_0^\star \hookleftarrow \mathbb {QR}_{N^{\zeta +1}}$ as a random quadratic residue in $\mathbb {Z}_{N^{\zeta +1}}^*$ and computing $C_1^\star =(1+N)^{\mathsf {Msg}^\star } \cdot {C_0^\star }^{2 x} \bmod N^{\zeta +1}$ for a random $\mathsf {Msg}^\star \hookleftarrow U(\mathbb {Z}_{N^\zeta })$. Lemma 4.2 shows that $\mathsf {Game}_6$ and $\mathsf {Game}_5$ are negligibly far apart in terms of statistical distance, so that $| \Pr [W_6]-\Pr [W_5]| \le 2^{-\lambda }$.

In Game$_6$, we have $\Pr [W_6]=1/2$ since $\mathsf {ct}^\star$ is completely independent of the challenger’s bit $b \sim U(\{0,1\})$.    $\square$

Lemma 4.2

$\mathsf {Game}_6$ and $\mathsf {Game}_5$ are statistically indistinguishable.

Proof

The proof uses similar arguments to [4, Theorem 5]. In $\mathsf {Game}_5$, the challenge ciphertext has components $(C_0^\star ,C_1^\star )$ of the form

$$\begin{aligned} C_0^\star= & {} (1+N)^{\alpha _z} \cdot g^{\beta _z} \bmod N^{\zeta +1}, \\ C_1^\star= & {} (1+N)^{ \mathsf {Msg}_b+ 2\alpha _z \cdot (x \bmod N^\zeta ) } \cdot g^{2\beta _z \cdot (x \bmod p'q')} \bmod N^{\zeta +1} , \end{aligned}$$

with $g=g_0^{2N^\zeta } \bmod N^{\zeta +1}$ and for uniform $\alpha _z \sim U(\mathbb {Z}_{N^\zeta })$, $\beta _z \sim U(\mathbb {Z}_{p'q'})$. Since $\gcd (2 \alpha _z ,N^\zeta )=1$ with overwhelming probability $\varphi (N)/N$, we only need to show that, from $\mathcal {A}$’s view, $x \bmod N^\zeta$ is statistically uniform over $\mathbb {Z}_{N^\zeta }$ in order to prove that the distribution of $(C_0^\star ,C_1^\star )$ is statistically close to that of $\mathsf {Game}_6$.

In $\mathsf {Game}_5$, we note that the challenger rejects all ciphertexts $\mathsf {ct}=(C_0,C_1,\varvec{\pi })$ such that $C_0 \not \in \mathcal {L}^{\mathsf {DCR}}$ and $(C_0,C_1,\varvec{\pi })\ne (C_0^\star ,C_1^\star ,\varvec{\pi }^\star )$. For each partial decryption query $(i,(C_0,C_1,\varvec{\pi }))$ such that $C_0 \in \mathcal {L}^{\mathsf {DCR}}$, the adversary can only learn the information $\{\mathbf {M}_{j} \cdot \varvec{\rho } \bmod p'q' \}_{j \in \psi ^{-1}(i)}$. As for partial decryption queries involving the challenge ciphertext $\mathsf {ct}^\star =(C_0^\star ,C_1^\star ,\varvec{\pi }^\star )$, we can handle them as if they were corruption queries since the latter reveal at least as much information as the former. Let $\mathcal {C}^\star$ the set of parties for which the adversary made either a corruption query or a decryption query on the challenge $\mathsf {ct}^\star =({C}_0^\star ,{C}_1^\star ,\varvec{\pi }^\star )$. Let $\mathbf {M}_{\mathcal {C}^\star }$ to be the sub-matrix of $\mathbf {M}$ obtained by stacking up the rows assigned to those parties.

Since $\mathcal {C}^\star$ is not authorized in $\mathbb {A}$, there exists $\varvec{\kappa } \in \mathbb {Z}^e$ such that $\kappa _1=1$ and $\mathbf {M}_{\mathcal {C}^\star }\cdot \varvec{\kappa }=\mathbf {0}^{d_{\mathcal {C}^\star }}$. Let a matrix $\mathbf {L}$ whose rows form a basis of the lattice $\{\mathbf {m}\in \mathbb {Z}^e,\langle \mathbf {m},\varvec{\kappa }\rangle =0\}$, where the rows of $\mathbf {M}_{\mathcal {C}^\star }$ live. Note that $(\mathbf {L},\mathbf {L}\cdot \varvec{\rho } )$ reveals at least as much information as $(\mathbf {M}_{\mathcal {C}^\star },\mathbf {M}_{\mathcal {C}^\star }\cdot \varvec{\rho })$, so that we may condition on $(\mathbf {L},\mathbf {L}\cdot \varvec{\rho })$. When we additionally condition on $( \mathbf {M}_{[\ell ]\setminus \mathcal {C}^\star }\cdot \varvec{\rho } \bmod p'q')$, we condition on something that reveals fewer information than $\varvec{\rho } \bmod p'q'$.

Let an arbitrary vector $\varvec{\rho }_0 \in \mathbb {Z}^e$ satisfying

$$\mathbf {L} \cdot \varvec{\rho }_0=\mathbf {L} \cdot \varvec{\rho } , \qquad \qquad \varvec{\rho }_0 \equiv \varvec{\rho } \pmod {p'q'}.$$

The conditional distribution of $\varvec{\rho }$ is $\varvec{\rho }_{0} +D_{\varLambda ,\sigma ,-\varvec{\rho }_{0}}$, where

$$\varLambda = \left\{ \varvec{x}\in \mathbb {Z}^e ~\mid ~ \mathbf {L}\cdot \varvec{x}=0 \quad \wedge \quad \varvec{x}= \mathbf {0} \bmod p'q' \right\} $$

is the lattice $\varLambda = \varvec{\kappa } \cdot \mathbb {Z}\cap (p'q' \cdot \mathbb {Z}^e) = ( p'q' \cdot \mathbb {Z}) \cdot \varvec{\kappa }$. Let us write $\varvec{\rho }_0 = y \cdot \varvec{\kappa } + (\varvec{\rho }_0^\perp )$, where $y \in \mathbb {R}$ and $\varvec{\rho }_0^\perp \in \mathbb {Z}^e$ is orthogonal to $\varvec{\kappa }$. Conditionally on $\mathbf {L} \cdot \varvec{\rho }$ and $\varvec{\rho } \bmod {p'q'}$, the distribution of $\varvec{\rho }$ can be written

$$\begin{aligned} \varvec{\rho }_{0} +D_{\varLambda ,\sigma ,-\varvec{\rho }_{0}}= & {} (\varvec{\rho }_0^\perp ) + y \cdot \varvec{\kappa } + D_{( p'q' \cdot \mathbb {Z}) \cdot \varvec{\kappa },\sigma ,- (\varvec{\rho }_0^\perp ) - y \cdot \varvec{\kappa }} \\= & {} (\varvec{\rho }_0^\perp ) + y \cdot \varvec{\kappa } + \varvec{\kappa } \cdot D_{( p'q' \cdot \mathbb {Z}) ,\sigma / \Vert \varvec{\kappa } \Vert ,- y } . \end{aligned}$$

Since $\kappa _1=1$, the conditional distribution of $x = \langle (1,0,\ldots ,0) , \varvec{\rho } \rangle$ is thus

$$ c + D_{ (p'q' \cdot \mathbb {Z}),\sigma / \Vert \varvec{\kappa } \Vert ,-y} ,$$

where $c= y+ \langle (1,0,\ldots ,0),\varvec{\rho }_0^\perp \rangle$. We now consider the distribution obtained by reducing the distribution $D_{ (p'q' \cdot \mathbb {Z}),\sigma / \Vert \varvec{\kappa } \Vert ,-y}$ over $\varLambda _0=p'q' \cdot \mathbb {Z}$ modulo its sublattice $\varLambda _0'=(p'q') \cdot (N^\zeta \mathbb {Z})$. Since $p'q' \cdot N^\zeta < N^{\zeta +1}$, by Lemma 2.7, choosing the standard deviation $\sigma > \sqrt{\lambda \cdot e} \cdot N^{\zeta +1}$ suffices (by [51, Lemma 3.1] which implies $\eta _{\epsilon }(\varLambda _0')< \lambda ^{1/2} N^{\zeta +1}$) to ensure that $x \bmod N^\zeta$ is within distance $2^{-\lambda }$ from $U(\varLambda _0 / \varLambda _0')$ conditionally on $\mathcal {A}$’s view. This completes the proof since $\gcd (p'q',N^\zeta )=1$ implies $\varLambda _0/\varLambda _0' \simeq \mathbb {Z}_{N^\zeta }$.    $\square$

In the full version of the paper, we show how to turn the scheme into a robust TPKE system. This is achieved by using trapdoor $\varSigma$-protocols to prove the validity of decryption shares. To this end, we need to first construct a standard $\varSigma$-protocol with binary challenges in order to apply the generic trapdoor $\varSigma$-protocol construction of Ciampi et al. [26]. The disadvantage of this approach is that parallel repetitions incur a communication overhead $\varTheta (\lambda )$. 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 without parallel repetitions.