Deniable Fully Homomorphic Encryption from Learning with Errors

Abstract

We define and construct Deniable Fully Homomorphic Encryption based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption.

Our constructions achieve compactness independently of the level of deniability- both the size of the public key and the size of the ciphertexts are bounded by a fixed polynomial, independent of the detection probability achieved by the scheme. This is in contrast to all previous constructions of deniable encryption schemes (even without requiring homomorphisms) which are based on polynomial hardness assumptions, originating with the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) in which the ciphertext size grows with the inverse of the detection probability. Canetti et al. argued that this dependence “seems inherent”, but our constructions illustrate this is not the case. We note that the Sahai-Waters (STOC 2014) construction of deniable encryption from indistinguishability obfuscation achieves compactness and can be easily modified to achieve deniable FHE as well, but it requires multiple, stronger sub-exponential hardness assumptions, which are furthermore not post-quantum secure. In contrast, our constructions rely only on the LWE polynomial hardness assumption, as currently required for FHE even without deniability.

The running time of our encryption algorithm depends on the inverse of the detection probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability probability and polynomial encryption time. Yet, we believe that achieving compactness is a fundamental step on the way to achieving all properties simultaneously as has been the historical journey for other primitives such as functional encryption. Our constructions support large message spaces, whereas previous constructions were bit by bit, and can be run in online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. This results in an efficient online phase whose running time is independent of the detection probability. At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.

1 Introduction

Deniable (public-key) encryption, which was introduced in a seminal work by Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) [13], is a seemingly paradoxical primitive that enables a user, who may be coerced to reveal the plaintexts corresponding to her public ciphertexts, to successfully lie about which messages she encrypted.

In particular, suppose Alice encrypted a message m with ciphertext $\mathsf{{ct}}$ which she deposits in the cloud for the purpose of cloud computing, and is later forced by the government to reveal the randomness she used and the message encrypted. Deniable encryption allows her to chose a different message $m'$ at coercion time and reveal fake random coins, which convincingly explain $\mathsf{{ct}}$ as the encryption of $m'$. Clearly, deniability is a property which may be highly desirable when one uses a public resource such as cloud computing which expose him to possible coercion. Another use case is preventing vote buying in electronic elections: if the voter encrypts her vote using deniable encryption, then she can claim she encrypted an alternate message when forced to reveal her vote, deeming vote selling ineffective and encouraging honest voting since the voter cannot be forced to reveal her choice.

In this work, we introduce the notion of deniable fully homomorphic encryption (FHE) and provide the first constructions based on the Learning With Errors polynomial hardness assumption. In deniable FHE, the encryptor can produce ciphertexts that can be opened to fake messages under coercion, and additionally support fully homomorphic computations and achieve security as in (by now) classical FHE. We emphasize that for all the applications of deniable public key encryption mentioned above, the capability of homomorphism is an important implicit requirement – indeed, several modern e-voting protocols use FHE [15, 27], and present-day encrypted data is often stored on a cloud server which assists the data owner with computing “blind-folded” via FHE [21].

We proceed to describe important prior work before we proceeding to describe our results in detail.

1.1 Prior Work on Deniability

Canetti et al. ($\mathsf{{CDNO}}$) [13] provided elegant constructions of deniable encryption based on the construct of so called “translucent sets”, which in turn can be constructed from trapdoor permutations. A major disadvantage of the $\mathsf{{CDNO}}$ construction was lack of compactness – the ciphertext size grows with the inverse of the detection probability achieved by the scheme. Furthermore, it encodes large messages bit by bit, where the ciphertext for each bit grows inversely with the detection probability. $\mathsf{{CDNO}}$ provided a lower bound that shows that their construction is in some sense optimal. They identified a structural property of encryption, which they term as separability and argued that as long as a construction is separable, the dependence of the ciphertext size with the inverse of the detection probability “seems inherent” [13].

A significant step forward in our understanding of deniable encryption and compactness was achieved via the work of Sahai and Waters in 2014 [29] which provided the first construction achieving negligible deniability assuming indistinguishability obfuscation ($\mathsf{iO}$) and one way functions. However, $\mathsf{iO}$ seems to be an inherently sub-exponential assumption [19, 20], and while exciting as a feasibility result, does not provide a satisfying solution to the question of deniable encryption from standard polynomial hardness assumptions.

$\mathsf{{CDNO}}$ also suggested the notion of weak deniability where the encryptor can lie not only about the random coins used to generate the ciphertext, but also the algorithm used to encrypt the message and the notion of receiver deniability, where the receiver can also produce a fake secret key that decrypts the message to an alternate one. In the weak model, [13] showed that compact public key and ciphertext as well as negligible deniability are possible. However, whether the weak model is meaningful for practical applications has been the subject of some debate – as discussed in [28], a common objection to the weak model is “since there are alternative deniable algorithms that are strictly more powerful than the normal ones, why would anyone ever run the normal algorithms? And given this situation, why would a coercer ever accept a transcript corresponding to the normal algorithms?”. We refer the reader to [28] for a detailed discussion.

Other extensions to deniable encryption were also explored – O’Neill, Peikert and Waters [28] provided the first constructions of non-interactive bi$\text{- }$deniable encryption schemes where both the sender and the receiver can fake simultaneously as well as the first construction of identity based bi-deniable encryption. Apon, Fan and Liu [4] extended their results to provide the first construction deniable attribute based encryption. However, in the full model, both works [4, 28] inherit the detection probability of $\mathsf{{CDNO}}$, which is inverse polynomial. Additional prior work not directly related to the current work is discussed in Sect. 1.5.

Summarizing, barring the $\mathsf{iO}$ based construction which seems to require a sub-exponential hardness assumption, all proposals for (fully) sender deniable encryption schemes from standard assumptions suffer from ciphertext size that is inversely proportional to the detection probability. This implies a prohibitively large blow on efficiency. For a primitive as fundamental and interesting as deniable encryption, this state of affairs is very dissatisfying.

1.2 Our Results

In this work, we introduce the notion of deniable fully homomorphic encryption (FHE) and provide the first constructions of deniable FHE based on the Learning With Errors ($\mathsf {LWE}$) assumption. Our constructions enjoy deniability compactness - the public key as well as the ciphertext of our schemes have size that can be bounded by a fixed polynomial, and are, in particular, independent of the level of deniability (or detection probability) achieved by the scheme. Our constructions support large messages paces, whereas all prior constructions encoded large messages bit by bit. On the down side, our encryption time depends on the inverse of the detection probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability and polynomial encryption time. Luckily, the scheme can be run in online-offline model of encryption, where the bulk of computation, which grows with the inverse of the detection probability, is independent of the message and may be performed in an offline pre-processing phase. The running time of the online phase, is independent of the detection probability.

We believe that achieving compact ciphertext even at the price of large encryption time is a fundamental step forward – indeed, note that for the related primitive of functional encryption (FE), compact ciphertext was later found to imply compact running time [26] by additionally assuming LWE via the “succinct” FE of Goldwasser et al. [24]. While this implication does not hold true for our work at present, it is a tantalizing possibility for future work.

We now proceed to on expound on the particulars of our results.

Deniable FHE. A (public key, sender) deniable fully homomorphic encryption consists of a tuple of algorithms $\mathsf {DFhe}=(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval},\mathsf {Dec},\mathsf {Fake})$ where $\mathsf {Gen}$, $\mathsf {Enc}$ and $\mathsf {Dec}$ are the standard key-generation, encryption and decryption algorithms, $\mathsf {Eval}$ is an algorithm that takes as input the public key, a circuit $\mathcal{C}$ and a tuple of ciphertexts $\mathsf{{ct}}_1,\ldots ,\mathsf{{ct}}_n$ encrypting $x_1,\ldots , x_n$ respectively, and outputs a ciphertext $\mathsf{{ct}}^*$ which encrypts $\mathcal{C}(x_1,\ldots ,x_n)$, and $\mathsf {Fake}$ is a faking algorithm, which takes as input the public key, an original message m, randomness r, and a fake message $m^*$ and outputs a fake randomness $r^*$ so that the encryption of message m using randomness r produces the same ciphertext as the encryption of message $m^*$ using randomness $r^*$, i.e. $\mathsf {Enc}({\mathsf{pk}},m;r)=\mathsf {Enc}({\mathsf{pk}},m^*;r^*)$. The detection probability is the probability with which an adversary can distinguish r from $r^*$, and we denote it by $1/\delta =1/\delta (\lambda )$ where $\lambda$ is the security parameter. Our notion of deniable FHE is formalized in Definition 2.8.

We naturally extend this definition to the weak model (Definition 2.11) – a weakly deniable FHE is defined as $\mathsf {wDFhe}=(\mathsf {Gen}, \mathsf {DEnc}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec}, \mathsf {Fake})$ which is distinct from “fully” deniable FHE in that there are two distinct algorithms for encryption, namely $\mathsf {Enc}$ and $\mathsf {DEnc}$. Here, as in [13], leveraging the additional secret “deniable” encryption algorithm $\mathsf {DEnc}$, allows for better constructions as discussed below (in particular, those that achieve negligible deniability in polynomial time).

In more detail, $\mathsf {Enc}$ is an “honest” encryption algorithm and is used by the encryptor when it does not wish to fake a ciphertext, and $\mathsf {DEnc}$ is a “deniable” encryption algorithm, which is used when the encryptor wishes to retain the ability of faking a ciphertext in the future. Let us say the encryptor wishes to compute an encryption of m which it may later want to explain differently. Then it produces a ciphertext $\mathsf{{ct}}^*$ by running the algorithm $\mathsf {DEnc}$ with message m using randomness r. To explain $\mathsf{{ct}}^*$ as encrypting an arbitrary fake message $m^*$ at a later time, the encryptor produces random coins $r^*$ using the $\mathsf {Fake}$ algorithm, so that the ciphertext output by the honest encryption algorithm $\mathsf {Enc}$ on $m^*$ using $r^*$ equals the ciphertext $\mathsf{{ct}}^*$ which was produced using the deniable encryption algorithm $\mathsf {DEnc}$, i.e. $\mathsf {DEnc}({\mathsf{pk}}, m;r)=\mathsf {Enc}({\mathsf{pk}},m^*;r^*)$.

Next, we describe our constructions. We provide:

• 1. A weakly deniable FHE scheme for bits with negligible detection probability (Sect. 4.1). We extend this scheme to support larger (polynomial sized) message spaces (Sect. 5).

• 2. A fully deniable FHE scheme for bits with inverse polynomial detection probability (Sect. 4.2). We also extend this scheme to support larger (polynomial sized) message spaces (see the full version [1]). Both our fully deniable FHE schemes have compact public key and ciphertext, i.e. with size independent of the detection probability, but with encryption running time that grows with the inverse of the detection probability.

• 3. Plan-ahead deniable FHE schemes which support exponentially large message spaces (see the full version [1]). Plan-ahead deniable encryption [13] requires the encryptor to choose all (polynomially many) possible fake messages at the time of encryption. Later, when the encryptor desires to explain a ciphertext, it can only provide convincing fake randomness for one of the fake messages chosen during encryption.

Fake Evaluation. We note that our notions of deniable FHE also allow, in some cases, to explain evaluated ciphertexts as encoding a fake message. For instance, in the case that $\mathsf {Eval}$ is a deterministic algorithm, suppose that $\mathsf{{ct}}^*$ was computed by homomorphically evaluating a polynomial sized circuit $\mathcal{C}$ on ciphertexts $\mathsf{{ct}}_1,\ldots ,\mathsf{{ct}}_n$ which encode messages $x_1,\ldots ,x_n$ respectively. Suppose an encryptor wishes to explain $\mathsf{{ct}}^*$ as an encryption of an arbitrary message $m^* \ne \mathcal{C}(x_1,\ldots ,x_n)$, and $\mathcal{C}$ supports inversion, i.e. given a value $m^*$, it is possible to efficiently sample $x'_1,\ldots x'_n$ such that $\mathcal{C}(x'_1,\ldots ,x'_n) = m^*$. Then, the encryptor may simply explain $\mathsf{{ct}}_i$ as an encryption of $x'_i$ for $i \in [n]$ and exhibit that the homomorphic evaluation procedure for $\mathcal{C}$ results in $\mathsf{{ct}}^*$. This convinces the adversary that $\mathsf{{ct}}^*$ encodes $m^*$, as desired. We note that for several applications of interest, the circuit $\mathcal{C}$ can indeed be invertible – for instance, $\mathcal{C}$ may represent the vote counting circuit, which is simply addition and hence easily invertible.

On the Underlying Assumptions. We remark that the Sahai-Waters construction of public key deniable encryption from indistinguishability obfuscation (iO) [29] can be modified in a natural way to construct deniable fully homomorphic encryption. This provides an appealing feasibility result for deniable fully homomorphic encryption with negligible deniability, but rely on the strong hammer of indistinguishability obfuscation. While (concurrent) exciting recent work [25] has based indistinguishability obfuscation on well-founded assumptions, this construction relies on the subexponential hardness of four different assumptions, including assumptions on bilinear maps which are known to be insecure in the post-quantum regime. It is also well known that existing reductions to indistinguishability obfuscation [29] run into subexponential barrier due to the number of hybrids used in the security reductions – this results a subexponential assumption, please see [20] for a discussion.

The focus of our work is to rely on minimal assumptions. The primitive of levelled (respectively, pure) fully homomorphic encryption may be based on the polynomial hardness of the Learning With Errors (respectively, with circular security) assumption, with polynomial approximation factors [12]. Our constructions show that we can achieve (polynomially) deniable FHE without making any additional assumptions.

Compact Deniable PKE from FHE. Homomorphism aside, as discussed above, our construction implies, as a special case, a compact deniable public key encryption scheme, where the size of the public key and ciphertext are independent of the detection probability, which can be made an arbitrarily small inverse polynomial. However, as discussed above, the running time of our encryption algorithm does grow linearly with the inverse of the detection probability. This dependence again seems inherent, since our constructions can be shown to be separable in the sense of $\mathsf{{CDNO}}$ and hence subject to the lower bound (see the full version [1]). We discuss in Sect. 1.4 the technical barriers in circumventing this lower bound from non-obfuscation assumptions.

Online-Offline Encryption. Our constructions of deniable FHE also enjoy a desirable online-offline property, which allows the encryptor to do the bulk of the work in an offline phase that is independent of the message to be encrypted. In more detail, our encryption algorithm can be divided into two parts – an offline, message independent part which runs in time $O(\delta )$ (recall that $\frac{1}{\delta }$ is the detection probability), and an online phase which is efficient and independent of $\delta$. We believe this feature makes these schemes especially attractive for practice since it mitigates the disadvantage of the large running time of encryption.

1.3 Our Techniques

The primary technical challenge in (full) deniable encryption is satisfying the many constraints imposed by the faking algorithm: the adversary knows the encryption algorithm and must be shown correctly distributed randomness that explains a given challenge ciphertext to a fake message. Excepting the construction based on obfuscation [29], all prior work addressed this challenge by setting the ciphertext to be a long sequence of elements that are either random or pseudorandom, and encoding the message bit in the parity of the number of pseudorandom elements. To fake, the encryptor pretends that one of the pseudorandom elements is in fact random, thus flipping the parity of the number of pseudorandom elements, and hence the encoded message. To construct a deniable fully homomorphic encryption scheme, the first challenge that arises is that an FHE ciphertext is highly structured, and this is necessary if it has to support homomorphic evaluation. Moreover, valid FHE ciphertexts are sparse in the ciphertext space, so randomly sampled elements are unlikely to be well-formed ciphertexts. Hence, if the encryptor for deniable FHE constructs all components of the ciphertext by running the FHE encryption algorithm i.e. $\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},m;r)$, then it is forced to open the FHE ciphertexts to provide r honestly – the structure of ciphertexts does not support lying about any of the encoded bits. The encryptor is thus faced with the incongruous task of producing highly structured ciphertexts without running the FHE encryption algorithm.

The Magic of Bootstrapping. To overcome this hurdle, we leverage the clever idea of “bootstrapping” proposed by Gentry [21]. At a high level, bootstrapping is the procedure of homomorphically computing the decryption circuit of a given scheme, say $\mathsf {Fhe}$, on a ciphertext of the same scheme, using an encryption of the scheme’s secret key, denoted by $\mathsf{{ct}}_\mathsf{{sk}}$. This procedure assumes circular security, namely that semantic security of $\mathsf {Fhe}$ holds even when the adversary is provided an encryption of the scheme’s own secret key. The original motivation for bootstrapping was to reduce the “noise” level in FHE ciphertext – since the decryption circuit of an FHE scheme is quite shallow, running the decryption circuit homomorphically on some FHE ciphertext $\mathsf{{ct}}$ using the encryption of the FHE secret key $\mathsf{{ct}}_\mathsf{{sk}}$, removes the noise contained in $\mathsf{{ct}}$ via decryption, and the noise in output ciphertext $\mathsf{{ct}}'$ can be bound depending on the depth of the decryption circuit and the noise in $\mathsf{{ct}}_\mathsf{{sk}}$. To date, all constructions of “pure” FHE, namely, FHE that supports unbounded depth circuits, must assume circular security of the underlying “somewhat homomomorphic” encryption scheme, and hence of the underlying Learning With Errors (LWE) assumption. Since circular security is required anyway for the construction of pure FHE, we assume it in our construction of deniable (pure) FHE, and in the exposition below for simplicity. For the case of “levelled” FHE, which assumes a bound on the depth of supported circuits, and which can be built from standard LWE, this requirement can be removed as discussed in the full version [1].

Aside from noise reduction, an additional attractive feature of bootstrapping is that it suggests a way to obliviously generate FHE ciphertexts. Suppose our FHE scheme’s decryption algorithm always outputs a valid message regardless of whether the ciphertext is well-formed or not. Then, by running the bootstrapping procedure on a random element from the ciphertext space, we obtain a well formed, valid FHE ciphertext for an unknown bit, by correctness of FHE evaluation. Moreover, if we run the bootstrapping procedure on a valid FHE ciphertext of any bit, the ciphertext output by bootstrapping still encodes the same bit, by correctness of FHE decryption and evaluation. If FHE ciphertexts are indistinguishable from random (which they usually are), then the encryptor may cheat about which of the two types of inputs was provided to the bootstrapping procedure and thereby lie about the encoded bit in the bootstrapped ciphertext.

While this feels like progress, it is still unclear how to encrypt a single bit of one’s choosing using obliviously generated ciphertexts of unknown bits and honestly generated ciphertexts of known bits.

Deniable FHE in the Weak Model. As a warm-up, let us consider the weak model of deniability, where the encryptor can lie not only about the randomness used in encryption but also the algorithm used. Let us suppose for the moment that we may engineer the bootstrapping procedure so that an obliviously generated FHE ciphertext is biased and encodes the bit 0 with overwhelming probability (we will weaken this assumption later). Then, an approach to encrypt in the weak model is as follows.

Let the bootstrapping procedure be denoted by $\mathsf{boot}$. In the honest mode, the encryptor encrypts bit 0 by choosing $R_1$ and $R_2$ randomly from the ciphertext space, converting these to well formed FHE ciphertexts via the bootstrapping procedure, and finally computing the homomorphic XOR operation (denoted by $\oplus _2$) on these FHE ciphertexts. Thus, we have:

$$\mathsf{{ct}}_0={{\mathsf{boot}}}{({R_1})} \oplus _2 \mathsf{boot}(R_2)$$

Since we assumed that random elements are bootstrapped to encode 0 with overwhelming probability, the ciphertext $\mathsf{{ct}}_0$ encodes 0 due to correctness of the FHE evaluation procedure. To encrypt bit 1, the encryptor chooses $R_3$ randomly from the ciphertext space, and computes $R_4$ as an honest encryption of 1 using the FHE encryption algorithm. It then sets:

$$\mathsf{{ct}}_1=\mathsf{boot}(R_3) \oplus _2 \mathsf{boot}(R_4)$$

It is easy to see that correctness is preserved by the same arguments as above.

In the deniable or fake encryption algorithm, the sender changes the way it encrypts 0. Instead of choosing $R_1$ and $R_2$ uniformly at random, it now computes both $R_1$ and $R_2$ as well formed FHE ciphertexts of 1. Bootstrapping preserves the message bit and homomorphic evaluation of addition modulo 2 ensures that $\mathsf{{ct}}_0$ is a valid encryption of 0. The bit 1 is encrypted as before. However, if asked to explain, the encryptor can pretend that $\mathsf{{ct}}_0$ is in fact an encryption of 1 by claiming that $R_1$ is chosen uniformly and by explaining $R_2$ as an encryption of 1. Since $R_1$ is an FHE ciphertext, the adversary cannot tell the difference as long as FHE ciphertext is pseudorandom. Similarly, if asked to explain $\mathsf{{ct}}_1$ as an encryption of 0, she explains $R_4$ as a randomly chosen element in the ciphertext space. Thus, we obtain a construction of weakly deniable FHE for bits which achieves negligible detection probability. For more details, please see Sect. 4.1.

Deniable FHE in the Full Model. In the full model, the encryptor is not allowed to cheat about the algorithm it used for encryption, hence we may not take advantage of different ways of sampling randomness in the real and deniable encryption algorithms – there is only one encryption algorithm. In this model, we obtain FHE with polynomial deniability but with compact public key and ciphertext, that is, the size of the public key and ciphertext are independent of the detection probability. We proceed to describe the main ideas in the construction.

Let $\delta$ be the inverse of the desired detection probability. To encrypt a bit b, the encryptor samples uniform random bits $x_1,\dots ,x_\delta$ such that $\sum _{i\in [\delta ]}x_i=b\pmod 2$. It then computes $\delta$ elements $R_1,\dots ,R_\delta$ of which, $R_i$ is computed as an FHE encryption of 1 when $x_i=1$, and $R_i$ is sampled uniformly at random when $x_i=0$. Finally, it outputs

$$\mathsf{{ct}}=\mathsf{boot}(R_1)\; {\oplus _2}\; \mathsf{boot}(R_2) \;{\oplus _2}\; \dots \; {\oplus _2} \;\mathsf{boot}(R_\delta )$$

To fake, it samples a random $j\in [\delta ]$ such that $x_j=1$, sets $x^*_j=0$, and $x^*_i=x_i$ for every $i\ne j, i\in [\delta ].$ It pretends that $R_j$ is chosen uniformly at random, implying that $\mathsf{boot}(R_j)$ encodes 0 with overwhelming probability. It is easy to see that this flips the message bit that was chosen during encryption. Moreover, the statistical distance between honest randomness and fake randomness is $O(\frac{1}{\delta })$ and we achieve polynomial deniability, so long as the encryption time is polynomial. Please see Sect. 4.2 for more details.

Special FHE. The above informal description brushes several important details under the rug. For instance, we assumed various properties about the underlying FHE scheme which are not true in general. The most problematic assumption we made is that the FHE bootstrapping procedure can be engineered so that it outputs an encryption of 0 for a random input with overwhelming probability.

Some thought reveals that existing FHE schemes do not satisfy this property. Fortunately however, we show that some constructions can be modified to do so. For concreteness, we describe how to modify the FHE scheme by Brakerski, Gentry and Vaikuntanathan [10] to get the “special FHE” that we require. At a high level, decryption in the BGV cryptosystem is a two step procedure, where the first step computes the inner product of the ciphertext and the secret key over the ambient ring, and the second step computes the least significant bit of the result, which is then output. One can check that for any well formed ciphertext in this scheme, regardless of whether it encodes 0 or 1, the first step of the decryption procedure always yields a “small” element. On the other hand, for a random element in the ciphertext space, the first step of decryption yields a random element, i.e. it is small with low probability. Thus, we may modify the BGV decryption algorithm so that after computing the inner product in the first step, it checks whether the output is small, and outputs 0 if not. This does not change decryption for well formed ciphertexts but by a suitable setting of parameters, it biases the output of decryption to 0 for random inputs. In fact, we can make do with a weaker requirement on bias, namely that the bootstrapping procedure outputs an encryption of 0 for a random input with only non-negligible (not overwhelming) probability. However this makes the scheme more complicated, so we do not discuss it here. Please see the full version [1] for details. We also require some additional properties from our special FHE, which we define and establish in Sect. 3.

Large Messages. In all prior constructions of deniable encryption, larger messages were encoded bit by bit, where the ciphertext for a single bit is itself quite substantial $(O(\delta ))$ as discussed above. To further improve efficiency, we again leverage the power of FHE. This enables our schemes to support large message spaces natively, thereby inheriting the significant advances in FHE schemes with large information rate [9, 10, 22, 30], and bringing deniable FHE closer to practice.

Let $\mathcal{M}$ be the message space of an FHE scheme $\mathsf {Fhe}$ such that $|\mathcal{M}| = \mathrm {poly}(\lambda )$. Further, let us assume that $\mathsf {Fhe}$ satisfies the special properties discussed above (formalized in Sect. 3). Then, to compute a ciphertext for a message $m_k \in \mathcal{M}$, we express $m_k$ as the output of a “selector” function which computes the inner product of the $k^{th}$ unit vector with a vector of all messages in $\mathcal{M}$. In more detail, we express

$$m_k = 1 \cdot m_k + \sum _{m_i \in \mathcal{M}, i \ne k} \; 0 \cdot m_i$$

Here, the bits 0 or 1 are referred to as “selector” bits for obvious reasons. Our main observation is that the deniable encryption scheme for bits can now be used to add deniability to ciphertexts of selector bits and thereby to the overall ciphertext.

In more detail, assume that the sender selects message $m_k$ at the time of encryption. To compute a ciphertext of $m_k$, she computes FHE ciphertexts $\mathsf{{ct}}_i$ for all $m_i \in \mathcal{M}$ and selector bit ciphertexts $\mathsf{{ct}}^{\mathsf{{sel}}}_i$ for $i \in [|\mathcal{M}|]$ where $\mathsf{{ct}}^{\mathsf{{sel}}}_i$ encodes 0 if $i \ne k$ and 1 otherwise. We use deniable encryption to compute the ciphertexts of selector bits as described above; thus, each selector bit is computed using multiple elements $\{R_i\}$ where $i \in [\delta ]$. She then homomorphically computes the selector function described above to obtain a ciphertext $\mathsf{{ct}}^*$ encoding $m_k$. Under coercion, she may explain $\mathsf{{ct}}^*$ as encoding of any message $m_i$, even for $i \ne k$, by explaining the corresponding selector bits differently, i.e. by explaining $\mathsf{{ct}}^{\mathsf{{sel}}}_i$ as an encryption of 1 and $\mathsf{{ct}}^{\mathsf{{sel}}}_k$ as an encryption of 0.

We note that the above description is oversimplified and glosses over many technical details – for instance, the deniable FHE scheme for bits assumes that decryption of a random element in the ciphertext space is biased to 0 with overwhelming probability, which is no longer the case for FHE with large message spaces. However, this and other issues can be addressed, and we get schemes in both the weak and full models – please see Sect. 5 and the full version [1] for details.

Plan-Ahead Deniability. Plan-ahead deniable encryption [13] requires the sender to choose all possible fake messages at the time of encryption itself. For plan-ahead fully homomorphic encryption, it becomes possible to instantiate the underlying FHE to have super-polynomial message space. Intuitively, without the plan-ahead restriction, the construction discussed above fails for exponentially large message spaces, since it is not possible to “select” between exponentially many options in polynomial time. However, if the number of possible fake messages is fixed to some polynomial in advance, as is the case for plan-ahead deniability, then the same construction as above works, as long as we can establish the “special” properties of the FHE. We discuss how this can be achieved, please see the full version [1] for details.

Online-Offline Encryption. We now describe how our encryption algorithms lend themselves naturally to the online-offline model, where a bulk of the computation required for encryption is performed before the message is available. Consider the encryption algorithm for bits in the full model. Observe that sampling $\delta$ random bits $x_1,\dots , x_\delta$ such that $\sum _{i\in [\delta ]}x_i=b\pmod 2$ is the same as sampling $\delta -1$ random bits $x_1,\dots ,x_{\delta -1}$ and setting $x_\delta =b+ \sum _{i\in [\delta -1]} x_i \pmod 2$. In the offline phase, we may select $\delta -1$ bits $x_1,\dots ,x_{\delta -1}$ at random as well as the corresponding $\delta -1$ elements $R_i$ based on the bit $x_i$ as specified in the encryption algorithm. Next, we homomorphically evaluate the bootstrapping circuit on the $\delta -1$ random elements, i.e. $\mathsf{boot}(R_i)$ for $i \in [\delta -1]$ and then compute:

$$\mathsf{{ct}}_{\mathsf {offline}}=\mathsf{boot}(R_1)\;\oplus _2\; \mathsf{boot}(R_{2}) \;\oplus _2\; \dots \; \oplus _2\;\mathsf{boot}(R_{\delta -1}).$$

Now, in the online phase we can simply select the last bit and corresponding randomness $R_\delta$ according to the message b being encrypted, compute the homomorphic bootstrapping algorithm on $R_\delta$, and evaluate the homomorphic addition mod 2 as: $\mathsf{{ct}}=\mathsf{{ct}}_{\mathsf {offline}}\oplus _2\mathsf{boot}(R_\delta )$. Thus, the online encryption time is independent of $\delta$.

Next, consider the encryption scheme for large message spaces. Even here, note that the dependence of the encryption running time on the detection probability comes from the construction of selector bits. Since the construction of any ciphertext involves $|\mathcal{M}|-1$ encryptions of 0 and a single encryption of 1, the encryptions of these selector bits can be computed in an offline pre-processing phase. The encryptions of all possible messages in the message space can also be performed offline. Then, in the online phase, given message $m_k$, the encryptor needs only to perform the homomorphic evaluation of the selector function to compute the final ciphertext. This leads to an online encryption time which grows with $|\mathcal{M}|$ but not with the inverse of the detection probability.

The online processing time may be optimized further as follows – now, additionally in the offline phase, let the encryptor perform the homomorphic evaluation of the selector function with all the selector bits set to 0, i.e. $\sum _{m_i \in \mathcal{M}} \; 0 \cdot m_i$. It stores the ciphertexts for all possible messages $m \in \mathcal{M}$, the ciphertexts of the computed selector bits which are set to 0 as well as a ciphertext $\mathsf{{ct}}^1$ for an extra selector bit which is set to 1. In the online phase, when $m_k$ is known, it subtracts the “wrong” term $\mathsf{{ct}}^{0}_k \cdot \mathsf{{ct}}_k$ and adds the term $\mathsf{{ct}}^{1} \cdot \mathsf{{ct}}_k$ to the evaluated ciphertext to obtain the correct ciphertext. Thus, the online phase can be performed in time independent of both $|\mathcal{M}|$ as well as $\delta$.

Removing the Circularity Assumption for Levelled FHE. Above, our usage of the bootstrapping procedure implies the assumption of circular secure homomorphic encryption, hence circular secure LWE. Since circular security is required anyway for all known constructions of pure FHE (we refer the reader to [8] for a discussion), this assumption currently comes “for free” in the construction of deniable pure FHE. However, for levelled FHE, which only supports circuits of bounded depth and can be constructed from standard LWE [10, 11, 23], the assumption of circularity is not implied. In this setting, our construction can be easily adapted to make do without the circularity assumption, as observed by [3]. The idea is simple – instead of assuming that the encryption of a scheme’s secret key under it’s own public key is secure, we can instead rely on two encryption schemes and assume that the secret key of first scheme $\mathsf{{sk}}_1$ can be securely encrypted using the public key of the second scheme ${\mathsf{pk}}_2$. Let us denote this ciphertext by $\mathsf{{ct}}_{\mathsf{{sk}}_1}$. Now, the obliviously sampled ciphertexts can be seen as encrypted under ${\mathsf{pk}}_1$ and the ciphertext $\mathsf{{ct}}_{\mathsf{{sk}}_1}$ may be used to translate these to valid ciphertexts under ${\mathsf{pk}}_2$ via a variant of the bootstrapping procedure discussed above. In more detail, the modified bootstrapping procedure computes the homomomorphic evaluation procedure of the second scheme using as inputs the ciphertext $\mathsf{{ct}}_{\mathsf{{sk}}_1}$ and the decryption circuit of the first scheme to produce valid ciphertexts under the second scheme. We refer the reader to the full version [1] for more details.

1.4 Perspective: FHE as a Tool

As discussed above, bootstrapping enables us to obliviously sample FHE ciphertexts, and homomorphic evaluation enables us to “compactify” the final ciphertext – this makes FHE a useful tool even in the context of deniable public key encryption (PKE). One of the main insights of our work is that evaluation compactness in FHE can be leveraged to achieve deniability compactness in PKE. All constructions of non-interactive sender deniable encryption in the full model known from 1997 to date (excepting the one based on $\mathsf{iO}$ [29]), must provide multiple elements in the ciphertext, both pseudorandom and random, and encode the message bit in the parity of the number of pseudorandom elements leading to ciphertext size that grows inversely with detection probability. We can avoid this dependence using FHE.

Can FHE also help achieve compact runtime of encryption? If so, this would lead to negligibly deniable PKE from LWE, resolving the long-standing open problem of deniable PKE from a standard, polynomial hardness assumption, with the post-quantum advantage as the “icing on the cake”. While this exciting possibility cannot be ruled out, a thorny technical barrier that arises is the hardness of inverting the bootstrapping procedure. Intuitively, deniable encryption requires invertible biased oblivious sampling – the encryption procedure must obliviously sample a ciphertext (biased to encoding 0, say) and the faking procedure must invert a given ciphertext, encoding either 0 or 1, to produce a well distributed randomness. In hindsight, even the $\mathsf{iO}$ based construction of Sahai and Waters [29] can be viewed as a construction of invertible oblivious sampling – indeed, similar techniques have been used to construct invertible sampling [17].

Using our current techniques, bootstrapping enables us to perform oblivious sampling, but not inversion. Due to this limitation, we are restricted to cheating only in one direction – we can pretend that a ciphertext of 1 encodes 0 but not the other way around. This leads to the attack discussed in the full version [1], which curtails the scheme to polynomial deniability. However if, given $y = \mathsf{boot}(R)$, we could compute well-distributed $R'$ such that $\mathsf{boot}(R')=y\oplus _2 1$, where $\oplus _2 1$ denotes homomorphic XOR of the bit 1, then we would gain the ability to cheat in both directions and obtain negligibly deniable PKE. We remark that while $\mathsf{boot}$ is a one way function, infeasibility of inversion does not apply since we have potentially useful side information about the preimage – we must find the preimage of $y \oplus _2 1$ and know the preimage to y. Unfortunately, we currently do not know how to leverage this information. Nevertheless, we view ciphertext compactness as a useful stepping stone to full runtime compactness from LWE, and hope it can lead to progress towards a full solution. Please see the full version [1] for a more in-depth discussion on the barriers in achieving negligible deniability.

In the full version [1], we discuss the notion of receiver deniable FHE.

1.5 Other Related Work

De Caro, Iovino and O’Neill [18] studied the notion of receiver deniable functional encryption, but instantiating these constructions requires the assumption of full fledged functional encryption, which in turn is known to imply indistinguishability obfuscation ($\mathsf{iO}$) [2, 6].

Aside from work extending the functionality of deniable encryption, there was also progress in lower bounds – for receiver deniability, [5] showed that a non-interactive public-key scheme having key size $\delta$ can be fully receiver-deniable only with non-negligible $\varOmega (\frac{1}{\delta })$ detection probability while for sender deniability, Dachman-Soled [16] showed that there is no black-box construction of sender-deniable public key encryption with super-polynomial deniability from simulatable public key encryption. There has also been work on interactive deniable encryption where the sender and receiver are allowed to participate in an interactive protocol – in this setting, negligible bi-deniability in the full model has been achieved based on subexponentially secure indistinguishability obfuscation and one-way functions [14]. Our focus in this work is the non-interactive setting.

2 Preliminaries

In this section, we define the notation and preliminaries that we require in this work. Some standard notions are moved to the full version [1] due to space constraints.

2.1 Fully Homomorphic Encryption

Definition 2.1

(Fully Homomorphic Encryption). A public-key fully homomorphic encryption scheme for a message space $\mathcal{M}$ consists of PPT algorithms $\mathsf {Fhe}=(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec})$ with the following syntax:

• $\mathsf {Gen}(1^\lambda )\rightarrow ({\mathsf{pk}},\mathsf{{sk}})$: on input the unary representation of the security parameter $\lambda$, generates a public-key ${\mathsf{pk}}$ and a secret-key $\mathsf{{sk}}$.

• $\mathsf {Enc}({\mathsf{pk}},m)\rightarrow \mathsf{{ct}}$: on input a public-key ${\mathsf{pk}}$ and a message $m\in \mathcal{M}$, outputs a ciphertext $\mathsf{{ct}}$.

• $\mathsf {Eval}({\mathsf{pk}}, \mathcal{C}, \mathsf{{ct}}_1,\dots , \mathsf{{ct}}_k)\rightarrow \mathsf{{ct}}$: on input a public-key ${\mathsf{pk}}$, a circuit $\mathcal{C}:\mathcal{M}^k\rightarrow \mathcal{M}$, and a tuple of ciphertexts $\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k$, outputs a ciphertext $\mathsf{{ct}}$.

• $\mathsf {Dec}(\mathsf{{sk}},\mathsf{{ct}})\rightarrow m$: on input a secret-key $\mathsf{{sk}}$ and a ciphertext $\mathsf{{ct}}$, outputs a message $m\in \mathcal{M}$.

The scheme should satisfies the following properties:

• Correctness. A scheme $\mathsf {Fhe}$ is correct if for every security parameter $\lambda$, polynomial-time circuit $\mathcal{C}:\mathcal{M}^k\rightarrow \mathcal{M}$, and messages $m_i\in \mathcal{M}$ for $i\in [k]$:

  $$\Pr [\mathsf {Dec}(\mathsf{{sk}},\mathsf {Eval}({\mathsf{pk}},\mathcal{C},\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k))=\mathcal{C}(m_1,\dots ,m_k)]=1-\mathsf {negl}(\lambda )$$

  where $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Gen}(1^\lambda ),$ and $\mathsf{{ct}}_i\leftarrow \mathsf {Enc}({\mathsf{pk}},m_i)$ for $i\in [k].$

• Compactness. A scheme $\mathsf {Fhe}$ is compact if there exists a polynomial $\mathrm {poly}(\cdot )$ such that for all security parameter $\lambda$, polynomial-time circuit $\mathcal{C}:\mathcal{M}^k\rightarrow \mathcal{M}$, and messages $m_i\in \mathcal{M}$ for $i\in [k]$:

  $$\Pr \left[ \left|\mathsf {Eval}\left( {\mathsf{pk}},\mathcal{C},\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k\right) \right|\le \mathrm {poly}(\lambda )\right] =1$$

  where $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Gen}(1^\lambda ),$ and $\mathsf{{ct}}_i\leftarrow \mathsf {Enc}({\mathsf{pk}},m_i)$ for $i\in [k].$

• CPA Security. A scheme $\mathsf {Fhe}$ is IND-CPA secure if for all PPT adversary $\mathcal{A}$:

  $$\left|\Pr \left[ \mathsf {FheGame}^0_\mathcal{A}(\lambda )=1\right] -\Pr \left[ \mathsf {FheGame}^1_\mathcal{A}(\lambda )=1\right] \right|\le \mathsf {negl}(\lambda )$$

  where $\mathsf {FheGame}^b_\mathcal{A}(\lambda )$ is a game between an adversary and a challenger with a challenge bit b defined as follows:

  • Sample $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Gen}(1^\lambda )$, and send ${\mathsf{pk}}$ to $\mathcal{A}$.

  • The adversary chooses $m_0,m_1\in \mathcal{M}$.

  • Compute $\mathsf{{ct}}\leftarrow \mathsf {Enc}({\mathsf{pk}}, m_b)$, and send $\mathsf{{ct}}$ to $\mathcal{A}$.

  • The adversary $\mathcal{A}$ outputs a bit $b'$ which we define as the output of the game.

Definition 2.2

(Circular Security). A public-key encryption scheme with key generation algorithm $\mathsf {Gen}$ and encryption algorithm $\mathsf {Enc}$ is circular secure if for every PPT adversary $\mathcal{A}$:

$$\left|\Pr \left[ \mathsf {CircGame}^0_\mathcal{A}(\lambda )=1\right] -\Pr \left[ \mathsf {CircGame}^1_\mathcal{A}(\lambda )=1\right] \right|\le \mathsf {negl}(\lambda )$$

where $\mathsf {CircGame}^b_\mathcal{A}(\lambda )$ is a game between an adversary and a challenger with a challenge bit b defined as follows:

• Sample $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Gen}(1^\lambda )$, compute $\mathsf{{ct}}_\mathsf{{sk}}\leftarrow \mathsf {Enc}({\mathsf{pk}},\mathsf{{sk}})$, and give $({\mathsf{pk}},\mathsf{{ct}}_\mathsf{{sk}})$ to $\mathcal{A}$.

• The adversary chooses $m_0,m_1\in \mathcal{M}$.

• Compute $\mathsf{{ct}}\leftarrow \mathsf {Enc}({\mathsf{pk}}, m_b)$, and give $\mathsf{{ct}}$ to $\mathcal{A}$.

• The adversary $\mathcal{A}$ outputs a bit $b'$ which we define as the output of the game.

Definition 2.3

(Bootstrapping Procedure).[21] Let $\mathsf {Fhe}=(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec})$ be a public-key FHE scheme for a message space $\mathcal{M}$ with ciphertext space $\mathcal{R}^{\ell _c}$. We define the bootstrapping procedure, denoted by $\mathsf{boot}:\mathcal{R}^{\ell _c}\rightarrow \mathcal{R}^{\ell _c}$, as

$$\mathsf{boot}(x)=\mathsf {Fhe}.\mathsf {Eval}({\mathsf{pk}},\mathsf {Dec}_x, \mathsf{{ct}}_\mathsf{{sk}})$$

where $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$, $\mathsf{{ct}}_\mathsf{{sk}}\leftarrow \mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},\mathsf{{sk}})$, and $\mathsf {Dec}_x(\mathsf{{sk}})=\mathsf {Fhe}.\mathsf {Dec}(\mathsf{{sk}}, x)$. Above, when $\mathsf{{sk}}\notin \mathcal{M}$, we assume that $\mathsf{{sk}}$ may be represented as a vector of elements in $\mathcal{M}$, which would make $\mathsf{{ct}}_\mathsf{{sk}}$ a vector of ciphertexts.

Definition 2.4

(Valid Ciphertext). We say that an $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}$ is a valid ciphertext of m, if either

$$\mathsf{{ct}}\leftarrow \mathsf {Enc}({\mathsf{pk}}, m),$$

or for any polynomial-sized circuit $\mathcal{C}$, we have that:

$$\Pr [\mathsf {Dec}(\mathsf{{sk}},\mathsf {Eval}({\mathsf{pk}},\mathcal{C}, \mathsf{{ct}}))=\mathcal{C}(m)]=1-\mathsf {negl}(\lambda ),$$

where $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Gen}(1^\lambda )$ and $\lambda$ is the security parameter.

Some Useful Functions. In this paragraph, we define notation for some functions that will prove useful in our constructions.

Definition 2.5

(Addition Modulo 2). We denote by $\oplus _2$ the homomorphic evaluation of addition modulo 2 circuit, that is for $k\ge 2$, $\oplus _2(\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k)=\mathsf{{ct}}$, $\mathsf{{ct}}$ is a valid encryption of $\sum _{i=1}^k x_i \pmod {2}$ where $x_i\in \{0,1\}$ and $\mathsf{{ct}}_i$ is a valid encryption of $x_i$ for $i\in [k]$.

For ease of readability, we will often denote $\oplus _2(\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k)$ by $\mathsf{{ct}}_1 \oplus _2 \mathsf{{ct}}_2 \ldots \oplus _2 \mathsf{{ct}}_k$.

Definition 2.6

(Selector). Let $b_i\in \{0,1\}$ such that for all $i\in [k], i\ne j$, $b_i=0$, and $b_j=1$ for some fixed $j\in [k]$. For all $i\in [k]$, let $x_i\in \mathcal{M}$. We define a selector function as $\sum _{i\in [k]}b_i x_i=x_j$.

We denote the homomorphic evaluation of this function by

$$\sum _{i\in [k]}\mathsf{{ct}}_i^\mathsf{{sel}}\otimes \mathsf{{ct}}_i=\mathsf{{ct}},$$

where $\mathsf{{ct}}$ is a valid encryption of the selected message $x_j$, $\mathsf{{ct}}^\mathsf{{sel}}_i$ is a valid encryption of $b_i$ and $\mathsf{{ct}}_i$ is a valid encryption of $x_i$ for all $i\in [k].$

Definition 2.7

(Indicator Function). The indicator function for the set $\mathcal{X}$, denoted by ${\mathbf {1}}_{\mathcal{X}}(\cdot )$, defined as

$${\mathbf {1}}_{\mathcal{X}}(x)= {\left\{ \begin{array}{ll} 1 &{} x\in \mathcal{X}\\ 0 &{} x\notin \mathcal{X}\end{array}\right. }.$$

2.2 Deniable Homomorphic Encryption

Definition 2.8

(Compact Deniable FHE.). A compact public-key deniable fully homomorphic encryption scheme for message space $\mathcal{M}$ consists of PPT algorithms $\mathsf {DFhe}=(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval},\mathsf {Dec},\mathsf {Fake})$ with the following syntax:

• $\mathsf {Gen}(1^\lambda )\rightarrow ({\mathsf{dpk}},{\mathsf{dsk}})$: on input the unary representation of the security parameter $\lambda$, generates a public-key ${\mathsf{dpk}}$ and a secret-key ${\mathsf{dsk}}$.

• $\mathsf {Enc}({\mathsf{dpk}},m; r)\rightarrow \mathsf{{ct}}$: on input a public-key ${\mathsf{dpk}}$ and a message $m\in \mathcal{M}$, uses $\ell$-bit string randomness r, outputs a ciphertexts ${\mathsf{dct}}$.

• $\mathsf {Eval}({\mathsf{dpk}}, \mathcal{C}, {\mathsf{dct}}_1,\dots , {\mathsf{dct}}_k)\rightarrow {\mathsf{dct}}$: on input a public-key ${\mathsf{dpk}}$, a circuit $\mathcal{C}:\mathcal{M}^k\rightarrow \mathcal{M}$, and a tuple of ciphertexts ${\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k$, outputs a ciphertext ${\mathsf{dct}}$.

• $\mathsf {Dec}({\mathsf{dsk}},{\mathsf{dct}})\rightarrow m$: on input a secret-key ${\mathsf{dsk}}$ and a ciphertext ${\mathsf{dct}}$, outputs a message $m\in \mathcal{M}$.

• $\mathsf {Fake}({\mathsf{dpk}}, m, r, m^*)\rightarrow r^*$: on input a public-key ${\mathsf{dpk}}$, an original message $m\in \mathcal{M}$, an $\ell$-bit string randomness r, and a fake message $m^*\in \mathcal{M}$, output an $\ell$-bit string randomness $r^*$.

The scheme should satisfies the following properties:

• Correctness, Compactness & CPA Security. A scheme $\mathsf {DFhe}$ is correct, compact and secure if the scheme $(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec})$ satisfies the standard notions of correctness, compactness and IND-CPA security properties of fully homomorphic encryption, as in Definition 2.1. We remark that a scheme cannot simultaneously satisfy perfect correctness and deniability, so negligible decryption error in correctness is inherent.

• Deniability. A scheme $\mathsf {DFhe}$ is $\delta (\lambda )$-deniable if for all PPT adversary $\mathcal{A}$:

  $$\left|\Pr \left[ \mathsf {DnblGame}^0_\mathcal{A}(\lambda )=1\right] -\Pr \left[ \mathsf {DnblGame}^1_\mathcal{A}(\lambda )=1\right] \right|\le \delta (\lambda )$$

  where $\mathsf {DnblGame}^b_\mathcal{A}(\lambda )$ is a game between an adversary and a challenger with a challenge bit b defined as follows:

  • Sample $({\mathsf{dpk}},{\mathsf{dsk}})\leftarrow \mathsf {Gen}(1^\lambda )$, and send ${\mathsf{dpk}}$ to $\mathcal{A}$.

  • The adversary chooses $m,m^*\in \mathcal{M}$.

  • Sample $r\leftarrow \{0,1\}^\ell$, and $r^*\leftarrow \mathsf {Fake}({\mathsf{dpk}}, m, r, m^*)$; if $b=0$ give $(m^*, r, \mathsf {Enc}({\mathsf{dpk}}, m^*; r))$ to $\mathcal{A}$, else if $b=1$, give $(m^*, r^*, \mathsf {Enc}({\mathsf{dpk}}, m; r))$ to $\mathcal{A}$.

  • The adversary $\mathcal{A}$ outputs a bit $b'$ which we define as the output of the game.

Remark 2.9

We note that in our constructions, the length of randomness used during encryption may depend on the message being encrypted. This does not affect deniability, because the length of the randomness is only revealed together with the encrypted message. For ease of exposition, we do not introduce additional notation to capture this nuance.

• Deniability Compactness. A $\delta (\lambda )$-deniable scheme $\mathsf {DFhe}$ is deniability compact if there exists a a polynomial $\mathrm {poly}(\cdot )$ such that for all security parameters $\lambda$, and message $m\in \mathcal{M}$:

  $$\Pr [|\mathsf {Enc}({\mathsf{dpk}},m)|\le \mathrm {poly}(\lambda )]=1$$

  where $({\mathsf{dpk}},{\mathsf{dsk}})\leftarrow \mathsf {Gen}(1^\lambda ),$ regardless of the encryption running time.

Remark 2.10

The above definition can be modified to capture a compact deniable public key encryption scheme by removing the evaluation algorithm required by FHE.

Definition 2.11

(Weak Deniable FHE). A public-key weak deniable fully homomorphic encryption scheme for message space $\mathcal{M}$ consists of PPT algorithms $\mathsf {wDFhe}=(\mathsf {Gen}, \mathsf {DEnc}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec}, \mathsf {Fake})$ where $\mathsf {Gen}, \mathsf {Eval},$ and $\mathsf {Dec}$ have the same syntax as in Definition 2.8, and $\mathsf {DEnc}, \mathsf {Enc}$ and $\mathsf {Fake}$ have the following syntax:

• $\mathsf {DEnc}({\mathsf{dpk}},m; r)\rightarrow \mathsf{{ct}}$: on input a public-key ${\mathsf{dpk}}$ and a message $m\in \mathcal{M}$, uses $\ell$-bit string randomness r, outputs a ciphertexts ${\mathsf{dct}}$.

• $\mathsf {Enc}({\mathsf{dpk}},m; r)\rightarrow \mathsf{{ct}}$: on input a public-key ${\mathsf{dpk}}$ and a message $m\in \mathcal{M}$, uses $\ell ^*$-bit string randomness r, outputs a ciphertexts ${\mathsf{dct}}$.

• $\mathsf {Fake}({\mathsf{dpk}}, m, r, m^*)\rightarrow r^*$: on input a public-key ${\mathsf{dpk}}$, an original message $m\in \mathcal{M}$, an $\ell$-bit string randomness r, and a faking message $m^*\in \mathcal{M}$, output an $\ell ^*$-bit string randomness $r^*$.

The scheme should satisfies the following properties:

• Correctness, Compactness & CPA Security. A scheme $\mathsf {wDFhe}$ is correct, compact and secure if both schemes $(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec})$, and $(\mathsf {Gen}, \mathsf {DEnc}, \mathsf {Eval}, \mathsf {Dec})$ satisfy the standard notions of correctness, compactness and IND-CPA security properties of fully homomorphic encryption, as in Definition 2.1.

• Weak Deniability. A scheme $\mathsf {wDFhe}$ is weakly-deniable if for all PPT adversaries $\mathcal{A}$:

  $$\left|\Pr \left[ \mathsf {wDnblGame}^0_\mathcal{A}(\lambda )=1\right] -\Pr \left[ \mathsf {wDnblGame}^1_\mathcal{A}(\lambda )=1\right] \right|\le \mathsf {negl}(\lambda )$$

  where $\mathsf {wDnblGame}^b_\mathcal{A}(\lambda )$ is a game between an adversary and a challenger with a challenge bit b defined as follows:

  • Sample $({\mathsf{dpk}},{\mathsf{dsk}})\leftarrow \mathsf {Gen}(1^\lambda )$, and send ${\mathsf{dpk}}$ to $\mathcal{A}$.

  • The adversary $\mathcal{A}$ chooses $m,m^*\in \mathcal{M}$.

  • Sample $r\leftarrow \{0,1\}^{\ell ^*}$, $r'\leftarrow \{0,1\}^\ell$, and $r^*\leftarrow \mathsf {Fake}({\mathsf{dpk}}, m, r', m^*)$; if $b=0$ return $(m^*, r, \mathsf {Enc}({\mathsf{dpk}}, m^*; r))$ else if $b=1$ return $(m^*,r^*, \mathsf {DEnc}({\mathsf{dpk}}, m; r'))$ to $\mathcal{A}$.

  • The adversary $\mathcal{A}$ outputs a bit $b'$ which we define as the output of the game.

3 Special Homomorphic Encryption

Our constructions rely on a fully homomorphic encryption scheme which satisfies some special properties. We define these and instantiate it below.

Definition 3.1

(Special FHE). A special public-key FHE scheme for a message space $\mathcal{M}$ with ciphertext space $\mathcal{R}^{\ell _c}$ is a public-key FHE scheme, $\mathsf {Fhe}=(\mathsf {Gen},\mathsf {Enc},\mathsf {Eval},\mathsf {Dec})$, with the following additional properties:

• 1. Deterministic Algorithms. The evaluation and decryption algorithms, $\mathsf {Eval}$ and $\mathsf {Dec}$ respectively, are deterministic. In particular, this implies the bootstrapping procedure $\mathsf{boot}$, defined in 2.3, is deterministic.

• 2. Pseudorandom Ciphertext. The distribution $\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, m; U^\ell )$ is computationally indistinguishable from $\mathcal{R}^{\ell _c}$, where $U^\ell$ is the uniform distribution over $\ell$-bit strings, $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$, and $m\in \mathcal{M}$. Moreover, the distribution $\mathsf{boot}(\mathcal{R}^{\ell _c})$ is computationally indistinguishable from $\mathcal{R}^{\ell _c}$, where $\mathsf{boot}$ is the bootstrapping procedure as in Definition 2.3.

• 3. Decryption Outputs Valid Message. The decryption algorithm, $\mathsf {Fhe}.\mathsf {Dec}$, always outputs a message from the message space $\mathcal{M}$. Namely, for any $x\in \mathcal{R}^{\ell _c}$, $\mathsf {Fhe}.\mathsf {Dec}(\mathsf{{sk}},x)\in \mathcal{M}$ where $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$. In particular, this implies that the output of the bootstrapping procedure $\mathsf{boot}$ is always a valid ciphertext (Definition 2.4).

• 4. Biased Decryption on Random Input (Strong Version). The decryption algorithm $\mathsf {Fhe}.\mathsf {Dec}$, when invoked with a random element in the ciphertext space $x\leftarrow \mathcal{R}^{\ell _c}$, outputs a message from a fixed (strict) subset of the message space $\mathcal{S}\subset \mathcal{M}$ with overwhelming probability. Formally, we require that there exists a strict subset of the message space, $\mathcal{S}\subset \mathcal{M}$, such that

  $$P(\mathcal{S}):=\sum _{m\in S}P(m)\ge 1 - \mathsf {negl}(\lambda )$$

  where $P:\mathcal{M}\rightarrow \mathbb {R}$ is defined as $P(m):=\Pr \left[ \mathsf {Fhe}.\mathsf {Dec}\left( \mathsf{{sk}},x\right) =m\right]$ where $x\leftarrow \mathcal{R}^{\ell _c}$ and $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$. Moreover, we require that $0\in \mathcal{S}$. Thus, if the message space is binary, then $\mathcal{S}=\{0\}$. We remark that the above property, while sufficient, is not strictly necessary for our constructions. However, for ease of exposition, our constructions assume the “strong version” stated above. In the full version [1] we describe how to modify our constructions to instead use the weaker version below. Biased Decryption on Random Input (Weak Version). This version weakens overwhelming to noticeable in the above definition, i.e. using the notation above, we require:

  $$P(\mathcal{S}):=\sum _{m\in S}P(m)\ge 1/\mathrm {poly}(\lambda ) $$

  As before, we require that $0\in \mathcal{S}$.

• 5. Circular Secure. The scheme $\mathsf {Fhe}$ is circular secure as in Definition 2.2. As discussed in Sect. 1, this condition may be removed at the cost of making the construction more complicated, please see the full version [1] for details. Since this condition is anyway required for the construction of pure FHE, we assume it for ease of exposition.

3.1 Instantiation

For concreteness, we instantiate our special FHE scheme with (a modified version of) the scheme by Brakerski, Gentry and Vaikuntanathan [10] (henceforth $\mathsf{BGV}$), which is based on the hardness of the learning with errors ($\mathsf {LWE}$) problem. To begin, note that $\mathsf{BGV}$ already satisfies the property that the algorithms for evaluation and decryption are deterministic (property 1), the property that the ciphertext is pseudorandom (property 2) as well as the property that decryption always outputs valid message (property 3). The property of circular security (property 5) does not provably hold in $\mathsf{BGV}$, or indeed any existing FHE scheme, but is widely assumed to hold for $\mathsf{BGV}$. In particular, the authors already assume it for optimized versions of their main construction (which does not require this assumption)– please see [10, Section 5] for a discussion. We also remark that circular security is assumed by all “pure” FHE schemes, namely, schemes that can support homomorphic evaluation of circuits of arbitrary polynomial depth. We require circular security for a different reason – to support the bootstrapping operation, which allows us to obliviously sample FHE ciphertexts. Thus, it remains to establish the property that decryption of a (truly) random element from the ciphertext space outputs a biased message from the message space (property 4). Establishing this property requires slight modifications to the $\mathsf{BGV}$ scheme¹. Next, we describe these modifications for the case when the $\mathcal{M}$ is binary, of polynomial size and of super-polynomial size.

Recap of $\mathsf{BGV}$. Let us consider the $\mathsf{BGV}$ construction for binary messages [10, Section 4]. We begin by providing a brief recap of the features of $\mathsf{BGV}$ that we require. We use the same notation as in their paper for ease of verification. Let $\mathcal{R}$ be a ring and $|\mathcal{R}|=q$. Recall that the key generation algorithm of $\mathsf{BGV}$ samples a vector $\mathbf {s}' \in \mathcal{R}^{n}$ such that all the entries of $\mathbf {s}'$ are “small” with high probability (details of the distribution are not relevant here) and outputs $\mathsf{{sk}}= \mathbf {s}=(1, \mathbf {s}')$. The public key is constructed by sampling a uniform random matrix $\mathbf {A}' \leftarrow \mathcal{R}^{N \times n}$, an error vector $\mathbf {e}\in \mathcal{R}^N$ from a special “error” distribution, and setting $\mathbf {b}= \mathbf {A}' \mathbf {s}' + 2\cdot \mathbf {e}$. Denote by $\mathbf {A}$ the $(n + 1)$ column matrix consisting of $\mathbf {b}$ followed by the n columns of $- \mathbf {A}'$. Observe that $\mathbf {A}\cdot \mathbf {s}= 2 \mathbf {e}$. The public key contains $\mathbf {A}$ in addition to some other elements which are not relevant for our discussion². To encrypt a message bit m, set $\mathbf {m}= (m, 0, 0,\ldots ,0) \in \{0,1\}^{n+1}$, sample $\mathbf {r}\leftarrow \{0,1\}^{N}$ and output $\mathsf{{ct}}= \mathbf {m}+ \mathbf {A}^\top \;\mathbf {r}$. To decrypt, compute and output $[[\langle \mathsf{{ct}}, \;\mathsf{{sk}}\rangle ]_q]_2$, where $\langle \cdot \;,\; \cdot \rangle$ denotes inner product over the ring, and $[\cdot ]_p$ denotes reduction modulo p. The above construction can be adapted to support larger message spaces. A simple extension is to choose the message from $\mathbb {Z}_p$ for a polynomial sized prime p and multiply the error with p instead of 2. This, and other extensions are discussed in detail in [10, Section 5].

Creating a Bias. Observe that the decryption algorithm, given a ciphertext $\mathsf{{ct}}$ and secret $\mathsf{{sk}}$, outputs the decrypted message bit as $[[\langle \mathsf{{ct}}, \;\mathsf{{sk}}\rangle ]_q]_2$ regardless of the distribution of $\mathsf{{ct}}$. Thus, even if $\mathsf{{ct}}$ is a random element from the ciphertext space $\mathcal{R}^{n+1}$ which may not be well formed, it still outputs a valid message from the message space. However, it is easy to see that for a random element $R \leftarrow \mathcal{R}^{n+1}$, the output of $[[\langle R, \;\mathsf{{sk}}\rangle ]_q]_2$ is a uniformly distributed random bit, whereas we require the decryption algorithm to output a biased bit to satisfy property 4. Below, we will describe the modification to $\mathsf{BGV}$ to achieve the strong version of property 4. In the full version [1], we describe how we can instead rely on the weak version of the property, which is satisfied by $\mathsf{BGV}$ unmodified.

To create a bias, an idea is to build in an additional step in the decryption algorithm, which first checks whether the input ciphertext $\mathsf{{ct}}$ is well-formed. If so, it proceeds with legitimate decryption, i.e. computes $[[\langle \mathsf{{ct}}, \;\mathsf{{sk}}\rangle ]_q]_2$. If not, it simply outputs 0. Since well-formed ciphertexts in the $\mathsf{BGV}$ FHE are sparse in the ciphertext space $\mathcal{R}^{n+1}$, this ensures that a randomly chosen element from the ciphertext space is decrypted to 0 with high probability.

It remains to identify an efficient check for the well-formedness of the ciphertext. Towards this, we observe that for any valid ciphertext (Definition 2.4), the inner product $[\langle \mathsf{{ct}}, \;\mathsf{{sk}}\rangle ]_q = m + 2e$ where m is the encrypted bit and e is some error whose norm may be bounded using bounds on the norms of the secret key $\mathbf {s}$, the randomness $\mathbf {r}$, the error term in the public key $\mathbf {e}$ and the depth of the circuit – of which the norms of all aforementioned elements were chosen to be sufficiently “small” and the depth of the circuit can be bounded by the depth of the bootstrapping circuit [21].

Let us assume that the decryption error is bounded above by $B-1$, for some $B = \mathrm {poly}(\lambda )$. We note that this bound holds true for the current setting of parameters in [10]. Then, it follows that the output of step 1 of decryption can be bounded from above by B (for any well formed ciphertext). On the other hand, the output of $[\langle R, \;\mathsf{{sk}}\rangle ]_q$ for a random element R will also be uniformly distributed, and hence will have norm $\le B$ only with probability $O(\frac{B}{q})$. If we set q to be super-polynomial in the security parameter, then this term is negligible. Thus, we may modify the $\mathsf{BGV}$ decryption algorithm so that after computing $[\langle \mathsf{{ct}}, \;\mathsf{{sk}}\rangle ]_q$, it checks whether the output is $\le B$, and outputs 0 if not. This biases the output of decryption to 0 for random inputs – in more detail, decryption of a random element yields 0 with probability $1 - \mathsf {negl}(\lambda )$ as desired. With this modification, we ensured that $\mathsf{BGV}$ satisfies all the properties required by special FHE. We refer the reader to [10] for more details about the full construction of FHE.

In the above description, we chose the ring modulus q to be super-polynomial in the security parameter to obtain the desired bias. However, this large modulus is unnecessary and affects the efficiency of the scheme negatively. In the full version [1], we describe how to relax this requirement.

Next, we discuss how to modify the $\mathsf{BGV}$ scheme supporting larger (polynomial) message spaces, as discussed in [10, Section 5]. As in the case of binary messages (discussed above), we have that without performing any modifications, the $\mathsf{BGV}$ decryption algorithm, if executed on a random element in the ciphertext space, outputs a uniformly distributed message from the message space.

It remains to establish property 4 which requires that there exists a strict subset of the message space, $\mathcal{S}\subset \mathcal{M}$, such that

$$P(\mathcal{S}):=\sum _{m\in S}P(m)\ge 1 - \mathsf {negl}(\lambda )$$

where $P:\mathcal{M}\rightarrow \mathbb {R}$ is defined as $P(m):=\Pr \left[ \mathsf {Fhe}.\mathsf {Dec}\left( \mathsf{{sk}},x\right) =m\right]$ where $x\leftarrow \mathcal{R}^{\ell _c}$ and $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$.

Let $\mathcal{S}$ be an arbitrary subset of $\mathcal{M}$ that contains 0. For the binary message case above, we described a trick that ensures that random elements are decrypted to 0 with overwhelming probability. The same trick may be generalized to larger message spaces. If the modulus q is superpolynomial, and the message space is polynomial (say of size p), then the first step of decryption yields $[\langle \mathsf{{ct}},\mathsf{{sk}}\rangle ]_q = m + p \cdot e$ for well-formed ciphertexts, and a random element in $\mathcal{R}$ otherwise. Again, this term can be bounded by some polynomial B and the decryption procedure can be modified to output 0 (or any element from the set $\mathcal{S}$) if the output of step 1 is greater than B. By the same reasoning as above, this biases the output to $\mathcal{S}$ with overwhelming probability as long as q is super-polynomial. Please see the full version [1] to avoid the restriction of super-polynomial q.

Finally, we remark that $\mathsf{BGV}$ also includes variants where the message space is super-polynomial in size [10, Section 5.4]. In this case, biasing the output to a fixed set $\mathcal{S}$ is simple: we can just set $\mathcal{S}=\mathcal{M}\setminus \{1\}$. Moreover $\mathcal{S}$ has efficient representation since it can simply be represented by its complement, which is of small size and it is clear that the decryption output of a random element is biased to $\mathcal{S}$ with overwhelming probability.

4 Deniable Encryption for Bits

In this section, we provide our constructions for weak deniable FHE, as in Definition 2.11, and compact deniable FHE, as in Definition 2.8. Let $\mathsf {Fhe}=(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec})$ be a special public-key FHE scheme for the message space $\mathcal{M}=\{0,1\}$ with ciphertext space $\mathcal{R}^{\ell _c}$, as in Definition 3.1. For reading convenience, we denote by lowercase r, the $\ell$-bit string randomness that is input to an $\mathsf {Fhe}.\mathsf {Enc}$ algorithm, and by uppercase R, the elements in $\mathcal{R}^{\ell _c}$, where $\mathcal{R}^{\ell _c}$ is the co-domain of the algorithm $\mathsf {Fhe}.\mathsf {Enc}$. We denote by ${\ell '_c}$ the bit length of elements in $\mathcal{R}^{\ell _c}$ (that is, ${\ell '_c}=\lceil {\ell _c}\log _2(|\mathcal{R}|)\rceil$). Recall that $\mathsf{boot}$ denotes the bootstrapping procedure described in Definition 2.3 and $\oplus _2$ denotes the homomorphic evaluation of addition mod 2 described in Definition 2.5.

4.1 Weakly Deniable FHE for Bits

Our public-key weak deniable fully homomorphic encryption scheme for message space $\mathcal{M}=\{0,1\}$, $\mathsf {wDFhe}=(\mathsf {Gen},\mathsf {DEnc},\mathsf {Enc},\mathsf {Eval},\mathsf {Dec},\mathsf {Fake})$, is described as follows:

• $\mathsf {wDFhe}.\mathsf {Gen}(1^\lambda ):$ Upon input the unary representation of the security parameter $\lambda$, do the following:

  • 1. Sample $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$, and $\mathsf{{ct}}_{\mathsf{{sk}}}\leftarrow \mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, \mathsf{{sk}})$.

  • 2. Outputs ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}}), {\mathsf{dsk}}:= \mathsf{{sk}}$

• $\mathsf {wDFhe}.\mathsf {DEnc}({\mathsf{dpk}}, m; \mathsf{{r}})$: Upon input the public key ${\mathsf{dpk}}$, a message bit m and $(3\ell +{\ell '_c})$-bit string randomness $\mathsf{{r}}$, do the following:

  • 1. Parse ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}})$ and $\mathsf{{r}}=(r_1, r_2, r_3, R_4)$, where $|r_i|=\ell$ for $i\in [3]$ and $|R_4|={{\ell '_c}}$.

  • 2. For $i\in [3],$ set $R_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;r_i).$

  • 3. Let $\mathsf{{ct}}_0=\mathsf{boot}(R_1) \oplus _2 \mathsf{boot}(R_2)$ and $\mathsf{{ct}}_1=\mathsf{boot}(R_4) \oplus _2 \mathsf{boot}(R_3)$.

  • 4. Output ${\mathsf{dct}}=\mathsf{{ct}}_m$.

• $\mathsf {wDFhe}.\mathsf {Enc}({\mathsf{dpk}}, m ; \mathsf{{r}}):$ Upon input the public-key ${\mathsf{dpk}}$, the message bit m, and the $({\ell +3{\ell '_c}})$-bit string randomness $\mathsf{{r}}$, do the following:

  • 1. Parse ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}})$ and $\mathsf{{r}}=(R_1, R_2, R_3, r_4)$, where $|R_i|={{\ell '_c}}$ for $i\in [3]$ and $|r_4|=\ell$.

  • 2. Set $R_4=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;r_4)$.

  • 3. Let $\mathsf{{ct}}_0=\mathsf{boot}(R_1) \oplus _2 \mathsf{boot}(R_2)$ and $\mathsf{{ct}}_1=\mathsf{boot}(R_3) \oplus _2 \mathsf{boot}(R_4)$.

  • 4. Output ${\mathsf{dct}}= \mathsf{{ct}}_m$.

• $\mathsf {wDFhe}.\mathsf {Eval}({\mathsf{dpk}}, \mathcal{C}, {\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k)$: Upon input the public key ${\mathsf{dpk}}= ({\mathsf{pk}}, \mathsf{{ct}}_\mathsf{{sk}})$, the circuit $\mathcal{C}$ and the ciphertexts ${\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k$, interpret ${\mathsf{dct}}_i$ as $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}_i$ for $i \in [k]$, and output ${\mathsf{dct}}= \mathsf {Fhe}.\mathsf {Eval}({\mathsf{pk}}, \mathcal{C}, \mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k)$.

• $\mathsf {wDFhe}.\mathsf {Dec}({\mathsf{dsk}}, {\mathsf{dct}})$: Upon input the secret key ${\mathsf{dsk}}$ and the ciphertext ${\mathsf{dct}}$, interpret ${\mathsf{dsk}}$ and ${\mathsf{dct}}$ as $\mathsf {Fhe}$ secret key $\mathsf{{sk}}$ and $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}$ and output $\mathsf {Fhe}.\mathsf {Dec}(\mathsf{{sk}}, \mathsf{{ct}})$.

• $\mathsf {wDFhe}.\mathsf {Fake}({\mathsf{dpk}}, m, \mathsf{{r}}, m^*)$: Upon input the public key ${\mathsf{dpk}}$, the original message bit m, $(3\ell +{\ell '_c})$-bit string randomness $\mathsf{{r}}$, and the faking message bit $m^*$, do the following:

  • 1. Parse ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}})$ and $\mathsf{{r}}=(r_1, r_2, r_3, R_4)$, where $|r_i|=\ell$ for $i\in [3]$ and $|R_4|={{\ell '_c}}$.

  • 2. For $i\in [3]$, set $R_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, 1; r_i).$

  • 3. If $m = m^*$, then set $R^*_1=R_1$, $R_2^*=R_2$, $R^*_3=R_4$, and $r^*_4=r_3$.

  • 4. Else if $m \ne m^*$, then set $R^*_1=R_4$, $R_2^*=R_3$, $R^*_3=R_1$, and $r^*_4=r_2$.

  • 5. Output $\mathsf{{r}}^*=(R^*_1, R^*_2, R^*_3, r^*_4)$

We now prove the scheme satisfies correctness, compactness, CPA security and weak deniability.

xmlcommandpara Compactness and Security. Observe that the output of both $\mathsf {wDFhe}.\mathsf {DEnc}$ and $\mathsf {wDFhe}.\mathsf {Enc}$ is a valid ciphertext of the underlying $\mathsf {Fhe}$ scheme. This is due to property 3 of the special FHE which states that the FHE decryption algorithm always outputs a valid bit, and due to the correctness of FHE evaluation which implies correctness of bootstrapping. Together, these two properties ensure that $\mathsf{boot}$ always outputs a valid ciphertext. Moreover, correctness of homomorphic evaluation implies that the addition mod 2 operation is performed correctly, so that the output of $\mathsf {wDFhe}.\mathsf {DEnc}$ and $\mathsf {wDFhe}.\mathsf {Enc}$ is a valid ciphertext of FHE.

Since the underlying FHE scheme satisfies compactness, it holds that the ciphertext output by $\mathsf {wDFhe}.\mathsf {DEnc}$ and $\mathsf {wDFhe}.\mathsf {Enc}$ is also compact. Similarly, due to property 5 which states that the scheme is circular secure, and since the ciphertext of the underlying FHE satisfies semantic security, so does the ciphertext output by $\mathsf {wDFhe}.\mathsf {DEnc}$ and $\mathsf {wDFhe}.\mathsf {Enc}$. Thus, both schemes are compact and secure as the underlying FHE scheme is.

Correctness. We start by proving correctness of the deniable encryption algorithm $\mathsf {wDFhe}.\mathsf {DEnc}$. Parse $\mathsf{{r}}\in \{0,1\}^{3\ell + {\ell '_c}}$ as $\mathsf{{r}}=(r_1, r_2, r_3, R_4)$. Observe that:

• 1. Since $R_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;r_i)$ for $i\in [3]$, we have by correctness of the underlying $\mathsf {Fhe}$, that $R_1,R_2$ and $R_3$ are valid encryptions of 1.

• 2. By properties 3 and 4 which state that FHE decryption always outputs a bit and this bit is biased to 0 with overwhelming probability when decryption is invoked with a truly random input, we have that $\mathsf{boot}(R_4)$ is a valid encryption of 0 with overwhelming probability.

Now, by correctness of FHE evaluation, we have that $\mathsf{{ct}}_0=\mathsf{boot}(R_1) \oplus _2 \mathsf{boot}(R_2)$ is a valid encryption of 0 and $\mathsf{{ct}}_1=\mathsf{boot}(R_4)\oplus _2 \mathsf{boot}(R_3)$ is a valid encryption of 1.

Next we prove correctness of $\mathsf {wDFhe}.\mathsf {Enc}$. Parse $\mathsf{{r}}\in \{0,1\}^{\ell +3{\ell '_c}}$ as $\mathsf{{r}}=(R_1, R_2, R_3, r_4)$. Observe that:

• 1. Since $R_4=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;r_4)$, we have that $R_4$ is a valid encryption of 1.

• 2. As above, we have by properties 3 and 4 that $\mathsf{boot}({R_i})$ for $i \in [3]$ are valid encryptions of 0 with overwhelming probability.

Thus, again by correctness of FHE evaluation, we have that $\mathsf{{ct}}_0=\mathsf{boot}(R_1) \oplus _2 \mathsf{boot}(R_2)$ is a valid encryption of 0 and $\mathsf{{ct}}_1=\mathsf{boot}(R_3)\oplus _2 \mathsf{boot}(R_4)$ is a valid encryption of 1.

Weak-Deniability. Next, we prove weak deniability of the construction. Fix a security parameter $\lambda$, an original message $m\in \{0,1\},$ and a faking message $m^*\in \{0,1\}.$ Let $({\mathsf{dpk}},{\mathsf{dsk}})\leftarrow \mathsf {wDFhe}.\mathsf {Gen}(1^\lambda )$, and parse ${\mathsf{dpk}}:=({\mathsf{pk}},\mathsf{{ct}}_\mathsf{{sk}}), {\mathsf{dsk}}:=\mathsf{{sk}}$.

• Faking Case. First consider the distribution of $({\mathsf{dpk}}, m^*, \mathsf{{r}}, \mathsf {DEnc}({\mathsf{dpk}}, m; \mathsf{{r}}'))$ in the case of faking.

  • 1. Select uniformly at random $\mathsf{{r}}'\leftarrow \{0,1\}^{3\ell }\times \mathcal{R}^{\ell _c}$.

  • 2. Parse $\mathsf{{r}}':=(r_1, r_2, r_3, R_4)$, where $|r_i|=\ell$ for $i\in [3]$ and $|R_4|={{\ell '_c}}$.

  • 3. For $i\in [3]$, set $R_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, 1; r_i)$.

  • 4. Let $\mathsf{{r}}^*=\mathsf {wDFhe}.\mathsf {Fake}({\mathsf{dpk}},m, \mathsf{{r}}', {m^*})$.

  • 5. By the faking algorithm $\mathsf{{r}}^*= \big (R_1^*, R_2^*, R_3^*, r_4^*)$ which is computed as follows:

    • (a) Case $m = m^*$:

      $$R^*_1=R_1,\quad R_2^*=R_2,\quad R^*_3=R_4,\quad r^*_4=r_3.$$

      By property 2 which asserts that ciphertexts are pseudorandom, we can explain $R_1^*$ and $R_2^*$ as uniform from the ciphertexts space $\mathcal{R}^{\ell _c}$. Here, $R^*_3=R_4$ is already a uniform element in $\mathcal{R}^{\ell _c}$, and $r^*_4=r_3$ is a uniform $\ell$ bit string.

    • (b) Case $m \ne m^*$:

      $$R^*_1=R_4,\quad R_2^*=R_3,\quad R^*_3=R_1,\quad r^*_4=r_2.$$

      As above, we can explain $R_2^*$ and $R_3^*$ as uniform elements in $\mathcal{R}^{\ell _c}$, and $R_1^*=R_4$ and $r^*_4=r_2$ are already uniform.

  • 6. The output of this hybrid is:

    $$\big (\;{\mathsf{dpk}}, m^*, \mathsf{{r}}^*=\left( R_1^*, R_2^*, R_3^*, r_4^*\right) , \mathsf{{ct}}^*=\mathsf {wDFhe}.\mathsf {DEnc}({\mathsf{dpk}}, m; \mathsf{{r}}')\big )$$

    where $\mathsf{{ct}}^*:=\mathsf{{ct}}_m$, $\mathsf{{ct}}_0=\mathsf{boot}(R_1)\oplus _2\mathsf{boot}(R_2)$ and $\mathsf{{ct}}_1=\mathsf{boot}(R_4)\oplus _2\mathsf{boot}(R_3).$ Observe that $\mathsf{{ct}}^*=\mathsf {wDFhe}.\mathsf {Enc}({\mathsf{dpk}}, m^*; \mathsf{{r}}^*)$. Thus, the output of this hybrid can be written as:

    $$\big (\;{\mathsf{dpk}}, m^*, \mathsf{{r}}^*=\left( R_1^*, R_2^*, R_3^*, r_4^*\right) , \mathsf{{ct}}^*=\mathsf {wDFhe}.\mathsf {Enc}({\mathsf{dpk}}, m^*; \mathsf{{r}}^*)\big )$$

    where $\mathsf{{ct}}^*:=\mathsf{{ct}}_{m^*}$, $\mathsf{{ct}}_0=\mathsf{boot}(R^*_1)\;\oplus _2\;\mathsf{boot}(R^*_2)$, $\mathsf{{ct}}_1=\mathsf{boot}(R^*_3)\;\oplus _2\;\mathsf{boot}(R^*_4)$ and $R^*_1, R^*_2, R^*_3$ and $r_4^*$ are explained as uniform in $\mathcal{R}^{3{\ell _c}}\times \{0,1\}^\ell$.

• Honest Case. Next, note that in the honest case $\mathsf{{r}}\leftarrow \mathcal{R}^{3{\ell _c}}\times \{0,1\}^{\ell }$, so the output distribution is:

  $$\big (\;{\mathsf{dpk}}, m^*, \mathsf{{r}}=\left( R_1, R_2, R_3, r_4\right) , \mathsf{{ct}}^*=\mathsf {wDFhe}.\mathsf {Enc}({\mathsf{dpk}}, m^*; \mathsf{{r}}) \big )$$

  where $\mathsf{{ct}}^*:=\mathsf{{ct}}_{m^*}$, $\mathsf{{ct}}_0=\mathsf{boot}(R_1)\oplus _2\mathsf{boot}(R_2)$, $\mathsf{{ct}}_1=\mathsf{boot}(R_3)\oplus _2\mathsf{boot}(R_4)$ and $R_1,R_2,R_3$ and $r_4$ are sampled uniformly. Hence, the two distributions are indistinguishable.

4.2 Fully Deniable FHE for Bits

Our compact public-key $1/\delta$-deniable³ fully homomorphic encryption scheme for message space $\mathcal{M}=\{0,1\}$, $\mathsf {DFhe}=(\mathsf {Gen},\mathsf {DEnc},\mathsf {Enc},\mathsf {Eval},\mathsf {Dec},\mathsf {Fake})$, is described below. We also provide an alternate construction with slightly different parameters in the full version [1]. Recall that $\mathsf{boot}$ denotes the bootstrapping procedure described in Definition 2.3 and $\oplus _2$ denotes the homomorphic evaluation of addition mod 2 described in Definition 2.5). We let $n = \delta ^2$.

• $\mathsf {DFhe}.\mathsf {Gen}(1^\lambda ):$ Upon input the unary representation of the security parameter $\lambda$, do the following:

  • 1. Sample $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$, and $\mathsf{{ct}}_{\mathsf{{sk}}}\leftarrow \mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, \mathsf{{sk}})$.

  • 2. Outputs ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}}), {\mathsf{dsk}}:= \mathsf{{sk}}.$

• $\mathsf {DFhe}.\mathsf {Enc}({\mathsf{dpk}}, m):$ Upon input the public-key ${\mathsf{dpk}}$, the message bit m, do the following:

  • 1. Parse ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}})$

  • 2. Select $\mathsf{{r}}$ as follows:

    • (a) Select uniformly $x_1,\dots ,x_n\in \{0,1\}$ such that $\sum _{i=1}^n{x_i}=m\pmod 2$.

    • (b) For $i\in [n]$: if $x_i=1$, then select $r_i\leftarrow \{0,1\}^\ell$; else if $x_i=0$, select $R_i\leftarrow \mathcal{R}^{\ell _c}.$

  • 3. For $i\in [n]$ such that $x_i=1$, set $R_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, 1;r_i)$.

  • 4. Output ${\mathsf{dct}}={\oplus _2}(\mathsf{boot}(R_1),\dots ,\mathsf{boot}(R_n))$

• $\mathsf {DFhe}.\mathsf {Eval}({\mathsf{dpk}}, \mathcal{C}, {\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k)$: Upon input the public key ${\mathsf{dpk}}= ({\mathsf{pk}}, \mathsf{{ct}}_\mathsf{{sk}})$, the circuit $\mathcal{C}$ and the ciphertexts ${\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k$, interpret ${\mathsf{dct}}_i$ as $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}_i$ for $i \in [k]$, and output ${\mathsf{dct}}= \mathsf {Fhe}.\mathsf {Eval}({\mathsf{pk}}, \mathcal{C}, \mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k)$.

• $\mathsf {DFhe}.\mathsf {Dec}({\mathsf{dsk}}, {\mathsf{dct}})$: Upon input the secret key ${\mathsf{dsk}}$ and the ciphertext ${\mathsf{dct}}$, interpret ${\mathsf{dsk}}$ and ${\mathsf{dct}}$ as $\mathsf {Fhe}$ secret key $\mathsf{{sk}}$ and $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}$ and output $\mathsf {Fhe}.\mathsf {Dec}(\mathsf{{sk}}, \mathsf{{ct}})$.

• $\mathsf {DFhe}.\mathsf {Fake}({\mathsf{dpk}}, m, \mathsf{{r}}, m^*)$: Upon input the public key ${\mathsf{dpk}}$, the original message bit m, randomness $\mathsf{{r}}$, and the fake message $m^*$ do the following:

  • 1. If $m=m^*$, output $\mathsf{{r}}^*=\mathsf{{r}}$.

  • 2. Parse ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}})$ and $\mathsf{{r}}=(x_1,\dots ,x_n, \rho _1,\dots ,\rho _n)$, where $x_1,\dots ,x_n\in \{0,1\}$, and for each $i\in [n],$ if $x_i=1$, then $|\rho _i|=\ell$; else if $x_i=0,$ $|\rho _i|={\ell '_c}$.

  • 3. Select uniform $i^*\in [n]$ such that $x_{i^*}=1$. If there is no such $i^*$, output “cheating impossible”; else:

    • (a) Set $x^*_{i^*}=0$ and $\rho ^*_{i^*}=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, 1; \rho _{i^*})$;

    • (b) For $i\in [n]\setminus \{i^*\}$, set $x^*_i=x_i$ and $\rho ^*_i=\rho _i$.

  • 4. Output $\mathsf{{r}}^*=(x_1^*,\dots ,x_n^*, \rho _1^*,\dots ,\rho _n^*).$

We now prove the scheme satisfies correctness, compactness, CPA security and poly deniability. Compactness and security follow exactly as in Sect. 4.1.

Correctness. To argue correctness, we note that:

• 1. Since $R_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;r_i)$ for i such that $x_i=1$, we have by correctness of the underlying $\mathsf {Fhe}$ that $R_i$, and hence $\mathsf{boot}(R_i)$ are valid encryptions of 1 for all $i\in [n]$ such that $x_i=1$.

• 2. By properties 3 and 4 which state that FHE decryption always outputs a bit and this bit is biased to 0 with overwhelming probability when decryption is invoked with a truly random input, we have that $\mathsf{boot}(R_{i})$ for i such that $x_i=0$ is valid encryption of 0 with overwhelming probability.

Hence, since $\sum _{i=1}^n{x_i}=m \pmod 2$, the (FHE evaluation of) addition mod 2 of $\mathsf{boot}(R_i)$ for $i \in [n]$ yields an encryption of m. Hence, the scheme encodes the message bit correctly.

Deniability. Next, we prove $1/\delta$-deniability of the construction. Fix a security parameter $\lambda$, an original message $m\in \{0,1\},$ and a faking message $m^*\in \{0,1\}.$ Let $({\mathsf{dpk}},{\mathsf{dsk}})\leftarrow \mathsf {DFhe}.\mathsf {Gen}(1^\lambda )$, and parse ${\mathsf{dpk}}:=({\mathsf{pk}},\mathsf{{ct}}_\mathsf{{sk}}), {\mathsf{dsk}}:=\mathsf{{sk}}$. When the original message m and the fake message $m^*$ are the same, the faked randomness $\mathsf{{r}}^*$ is equal to the original randomness $\mathsf{{r}}$. Thus in this case, $m=m^*$, the distributions are identical:

$$({\mathsf{dpk}}, m^*, \mathsf{{r}}, \mathsf {DFhe}.\mathsf {Enc}({\mathsf{dpk}}, m^*;\mathsf{{r}}))=({\mathsf{dpk}}, m^*, \mathsf{{r}}^*, \mathsf {DFhe}.\mathsf {Enc}({\mathsf{dpk}}, m;\mathsf{{r}})).$$

When the original message m and the fake message $m^*$ are not the same, observe that “cheating impossible” will be output only in case that $x_i=0$ for all $i\in [n]$, which occurs with probability $2^{-n}$. Assuming we are not in this case, the output distribution is:

• Faking Case. First consider the distribution of $({\mathsf{dpk}}, m^*, \mathsf{{r}}^*, \mathsf {DFhe}.\mathsf {Enc}({\mathsf{dpk}},m;\mathsf{{r}}))$ in the case of faking, where $\mathsf{{r}}^*\leftarrow \mathsf {DFhe}.\mathsf {Fake}({\mathsf{dpk}}, m, \mathsf{{r}}; m^*)$.

  • 1. Select uniform $\mathsf{{r}}:=(x_1,\dots ,x_n,\rho _1, \dots , \rho _n)$, by,

    • (a) Select $x_i\leftarrow \{0,1\}$ for $i\in [n]$ such that $\sum _{i\in [n]}x_i=m\pmod 2$

    • (b) For $i\in [n]$, if $x_i=1$, select $\rho _i\leftarrow \{0,1\}^\ell$

    • (c) For $i\in [n]$, if $x_i=0$, select $\rho _i\leftarrow \mathcal{R}^{\ell _c}$

  • 2. Let $\mathsf{{r}}^*=\mathsf {DFhe}.\mathsf {Fake}({\mathsf{dpk}},m, \mathsf{{r}}, {m^*})$, that is $\mathsf{{r}}^*= (x^*_1,\dots ,x^*_n,\rho ^*_1, \dots , \rho ^*_n)$ which is computed as follows:

    • (a) Select a uniform index $i^*\in [n]$ such that $x_{i^*}=1$, i.e. $i^*\leftarrow \{i| x_i=1\}$.

    • (b) For $i\in [n], i\ne i^*$, set $x_i^*=x_i$ and $\rho ^*_i=\rho _i$.

    • (c) Set $x_{i^*}=0$, and $\rho ^*_{i^*}=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;\rho _{i^*}).$

• Intermediate Case. By property 2 of the special FHE, which asserts that ciphertexts are pseudorandom, we can explain $\rho ^*_{i^*}=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},1;\rho _{i^*})$ as uniform element from the ciphertexts space $\mathcal{R}^{\ell _c}$. The distribution of this hybrid is $({\mathsf{dpk}}, m^*, \mathsf{{r}}', \mathsf {DFhe}.\mathsf {Enc}({\mathsf{dpk}},m;\mathsf{{r}}))$, where $\mathsf{{r}}'=(x'_1,\dots ,x'_n,\rho '_1, \dots , \rho '_n)$ is sampled as follows:

  • 1. Select $x_i\leftarrow \{0,1\}$ for $i\in [n]$ such that $\sum _{i\in [n]}x_i=m\pmod 2$

  • 2. Select a uniform index $i'\in [n]$ such that $x_{i'}=1$ (i.e. $i'\leftarrow \{i| x_i=1\}$), and set $x'_{i'}=0$, and for all $i\in [n]\setminus \{i'\}$ set $x'_i=x_i$.

  • 3. For $i\in [n]$, if $x'_i=1$, select $\rho '_i\leftarrow \{0,1\}^\ell$

  • 4. For $i\in [n]$, if $x'_i=0$, select $\rho '_i\leftarrow \mathcal{R}^{\ell _c}$

• Honest Case. Note that in the honest case the distribution is $({\mathsf{dpk}}, m^*, \mathsf{{r}}, \mathsf {DFhe}.\mathsf {Enc}({\mathsf{dpk}},m^*;\mathsf{{r}}))$, where $\mathsf{{r}}=(x_1,\dots ,x_n,\rho _1, \dots , \rho _n)$ is sampled as follows:

  • 1. Select $x_i\leftarrow \{0,1\}$ for $i\in [n]$ such that $\sum _{i\in [n]}x_i=m^*\pmod 2$.

  • 2. For $i\in [n]$, if $x_i=1$, select $\rho '_i\leftarrow \{0,1\}^\ell$

  • 3. For $i\in [n]$, if $x_i=0$, select $\rho '_i\leftarrow \mathcal{R}^{\ell _c}$

The statistical distance between the two distributions used to sample $(x_1,\dots ,x_n)$, in the honest case and in the intermediate/faking case, is $\frac{1}{\sqrt{n}}$. Hence, any PPT adversary $\mathcal{A}$ can win the $\mathsf {DnblGame}^b_\mathcal{A}(\lambda )$ game with probability at most $\frac{1}{\sqrt{n}}$, which is $\frac{1}{\delta }$ by our choice of n.

5 Weakly Deniable FHE with Large Message Space

In this section, we provide our construction for weak deniable FHE for polynomial size⁴ message space $\mathcal{M}$, as in Definition 2.11. Let $\mathsf {Fhe}=(\mathsf {Gen},\mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec})$ be a special public-key fully homomorphic encryption for the message space $\mathcal{M}$ with ciphertext space $\mathcal{R}^{\ell _c}$, as in Definition 3.1, and $\mathsf{boot}(x)$ be the bootstrapping procedure, described in Definition 2.3. We denote by $\mathcal{S}$ a strict subset of the message space to which decryption of random elements is biased,⁵ by ${\mathbf {1}_{\overline{\mathcal{S}}}}$ the indicator function for the set $\overline{\mathcal{S}}=\mathcal{M}\setminus \mathcal{S}$, described in Definition 2.7, and by s a fixed element in $\overline{\mathcal{S}}$. Recall that $\oplus _2$ denotes the homomorphic evaluation of addition mod 2 described in Definition 2.5 and $\mathsf {select}$ denotes the selector circuit described in Definition 2.6.

For reading convenience, we denote by lowercase r, the $\ell$-bit string randomness that is input to an $\mathsf {Fhe}.\mathsf {Enc}$ algorithm, and by upper case R, the elements in $\mathcal{R}^{\ell _c}$, where $\mathcal{R}^{\ell _c}$ is the co-domain of the FHE encryption algorithm. We denote by ${\ell '_c}$ the bit length of elements in $\mathcal{R}^{\ell _c}$ (that is, ${\ell '_c}=\lceil {\ell _c}\log _2(|R|)\rceil$). We index the messages in the message space as $\mathcal{M}=\{m_0,\dots ,m_\mu \}$.

Our (public-key) weakly deniable fully homomorphic encryption scheme for message space $\mathcal{M}$ $\mathsf {wDFhe}=(\mathsf {Gen},\mathsf {DEnc}, \mathsf {Enc}, \mathsf {Eval}, \mathsf {Dec}, \mathsf {Fake})$ is described as follows:

• $\mathsf {wDFhe}.\mathsf {Gen}(1^\lambda ):$ Upon input the unary representation of the security parameter $\lambda$, do the following:

  • 1. Sample $({\mathsf{pk}},\mathsf{{sk}})\leftarrow \mathsf {Fhe}.\mathsf {Gen}(1^\lambda )$, and $\mathsf{{ct}}_{\mathsf{{sk}}}\leftarrow \mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, \mathsf{{sk}})$.

  • 2. Outputs ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}}), {\mathsf{dsk}}:= \mathsf{{sk}}$

• $\mathsf {wDFhe}.\mathsf {DEnc}({\mathsf{dpk}}, m_k; \mathsf{{r}})$: Upon input the public key ${\mathsf{dpk}}$, a message $m_k\in \mathcal{M}$ and $((4\ell +{\ell '_c})\mu )$-bit string randomness $\mathsf{{r}}$, do the following:

  • 1. Parse the input. ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}}),\ \mathsf{{r}}=(r_1,\dots ,r_{\mu }, (r_{1,1}, r_{1,2}, r_{1,3}, {\hat{R}}_{1,4}), \dots , (r_{\mu ,1},r_{\mu ,2}, r_{\mu ,3}, {\hat{R}}_{\mu ,4}))$ where $|r_i|=|r_{i,j}|=\ell$ and $|{\hat{R}}_{i,4}|={{\ell '_c}}$ for $i\in [\mu ], j\in [3]$.

  • 2. Generate ciphertexts for every possible message. For $i\in [\mu ]$, set $\mathsf{{ct}}_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, m_i; r_i)$.

  • 3. Generate ciphertexts for “selector” bits.

    • (a) For every $i\in [\mu ], j\in [3]$, set ${\hat{R}}_{i,j}=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},s;r_{i,j})$.

    • (b) For every $i\in [\mu ], j\in [4]$, set $R_{i,j}=\mathsf {Fhe}.\mathsf {Eval}({\mathsf{pk}}, {\mathbf {1}}_{\overline{\mathcal{S}}}, {\hat{R}}_{i,j})$.

    • (c) We compute ciphertexts for selector bits 0 and 1 for every index as follows. For $i\in [\mu ]$, compute

      $$\mathsf{{ct}}^i_0=\mathsf{boot}(R_{i,1}) \oplus _2 \mathsf{boot}(R_{i,2}),\;\;\; \mathsf{{ct}}^i_1= \mathsf{boot}(R_{i,4}) \oplus _2 \mathsf{boot}(R_{i,3})$$

    • (d) We let the $k^{th}$ message to be selected by setting it’s selector bit to 1, and all others to 0 as follows. For every $i \in [\mu ]$ if $i\ne k$, set $\mathsf{{ct}}^{\mathsf{{sel}}}_i=\mathsf{{ct}}^i_0$; else if $i=k$, set $\mathsf{{ct}}^{\mathsf{{sel}}}_i=\mathsf{{ct}}^i_1.$

  • 4. Evaluate selector circuit on ciphertexts. Compute and output ${\mathsf{dct}}= \mathsf {select}(\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_\mu ,\mathsf{{ct}}^{\mathsf{{sel}}}_1,\dots ,\mathsf{{ct}}^{\mathsf{{sel}}}_\mu )$, that is ${\mathsf{dct}}=\sum _{i\in [\mu ]} \left( \mathsf{{ct}}^{\mathsf{{sel}}}_i \otimes \mathsf{{ct}}_i \right)$.

• $\mathsf {wDFhe}.\mathsf {Enc}({\mathsf{dpk}}, m_k ; \mathsf{{r}}):$ Upon input public-key ${\mathsf{dpk}}$, a message $m_k\in \mathcal{M}$, and $(({2\ell +3{\ell '_c}})\mu )$-bit string randomness $\mathsf{{r}}$, do the following:

  • 1. Parse the input. ${\mathsf{dpk}}:= ({\mathsf{pk}},\mathsf{{ct}}_{\mathsf{{sk}}}),\ \mathsf{{r}}=(r_1,\dots ,r_{\mu }, ({\hat{R}}_{1,1}, {\hat{R}}_{1,2}, {\hat{R}}_{1,3}, r_{1,4}), \dots , ({\hat{R}}_{\mu ,1},{\hat{R}}_{\mu , 2}, {\hat{R}}_{\mu ,3}, r_{\mu ,4}))$ where $|r_i|=|r_{i,4}|=\ell$ and $|{\hat{R}}_{i,j}|={{\ell '_c}}$ for $i\in [\mu ], j\in [3]$.

  • 2. Generate ciphertexts for every possible message. For $i\in [\mu ]$, set $\mathsf{{ct}}_i=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}}, m_i; r_i)$.

  • 3. Generate ciphertexts for “selector” bits.

    • (a) For every $i\in [\mu ]$, set ${\hat{R}}_{i,4}=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},s;r_{i,4}).$

    • (b) For every $i\in [\mu ], j\in [4]$, set $R_{i,j}=\mathsf {Fhe}.\mathsf {Eval}({\mathsf{pk}}, {\mathbf {1}}_{\overline{\mathcal{S}}}, {\hat{R}}_{i,j})$.

    • (c) We compute ciphertexts for selector bits 0 and 1 for every index as follows. For $i\in [\mu ]$, compute

      $$\mathsf{{ct}}^i_0=\mathsf{boot}(R_{i,1}) \oplus _2 \mathsf{boot}(R_{i,2}),\;\;\; \mathsf{{ct}}^i_1= \mathsf{boot}(R_{i,3}) \oplus _2 \mathsf{boot}(R_{i,4}).$$

    • (d) We let the $k^{th}$ message to be selected by setting it’s selector bit to 1, and all others to 0 as follows. For every $i \in [\mu ]$ if $i\ne k$, set $\mathsf{{ct}}^{\mathsf{{sel}}}_i=\mathsf{{ct}}^i_0$; else if $i=k$, set $\mathsf{{ct}}^{\mathsf{{sel}}}_i=\mathsf{{ct}}^i_1.$

  • 4. Evaluate selector circuit on ciphertexts. Compute and output ${\mathsf{dct}}= \mathsf {select}(\mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_\mu ,\mathsf{{ct}}^{\mathsf{{sel}}}_1,\dots ,\mathsf{{ct}}^{\mathsf{{sel}}}_\mu )$, that is $\sum _{i\in [\mu ]} \left( \mathsf{{ct}}^{\mathsf{{sel}}}_i \otimes \mathsf{{ct}}_i \right)$.

• $\mathsf {wDFhe}.\mathsf {Eval}({\mathsf{dpk}}, \mathcal{C}, {\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k)$: Upon input the public key ${\mathsf{dpk}}= ({\mathsf{pk}}, \mathsf{{ct}}_\mathsf{{sk}})$, the circuit $\mathcal{C}$ and the ciphertexts ${\mathsf{dct}}_1,\dots ,{\mathsf{dct}}_k$, interpret ${\mathsf{dct}}_i$ as $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}_i$ for $i \in [k]$, and output ${\mathsf{dct}}= \mathsf {Fhe}.\mathsf {Eval}({\mathsf{pk}}, \mathcal{C}, \mathsf{{ct}}_1,\dots ,\mathsf{{ct}}_k)$.

• $\mathsf {wDFhe}.\mathsf {Dec}({\mathsf{dsk}}, {\mathsf{dct}})$: Upon input the secret key ${\mathsf{dsk}}$ and the ciphertext ${\mathsf{dct}}$, interpret ${\mathsf{dsk}}$ and ${\mathsf{dct}}$ as $\mathsf {Fhe}$ secret key $\mathsf{{sk}}$ and $\mathsf {Fhe}$ ciphertext $\mathsf{{ct}}$ and output $\mathsf {Fhe}.\mathsf {Dec}(\mathsf{{sk}}, \mathsf{{ct}})$.

• $\mathsf {wDFhe}.\mathsf {Fake}({\mathsf{dpk}}, m_k, \mathsf{{r}}, m_{k^*})$: Upon input the public key ${\mathsf{dpk}}$, the original message $m_k\in \mathcal{M}$, $((4\ell +{\ell _c})\mu )$-bit string randomness $\mathsf{{r}}$ and the fake message $m_{k^*}$, do the following:

  • 1. Parse ${\mathsf{dpk}}:=({\mathsf{pk}},\mathsf{{ct}}_\mathsf{{sk}})$, and $\mathsf{{r}}:=(r_1,\dots ,r_{\mu }, (r_{1,1}, r_{1,2}, r_{1,3}, {\hat{R}}_{1,4}), \dots , (r_{\mu , 1},r_{\mu ,2}, r_{\mu ,3}, {\hat{R}}_{\mu ,4})),$ where $|r_i|=|r_{i,j}|=\ell$ and $|{\hat{R}}_{i,4}|={{\ell '_c}}$ for $i\in [\mu ], j\in [3]$.

  • 2. For all $i\in [\mu ],$ set $r_i^*= r_i.$

  • 3. For every $i\in [\mu ], j\in [3]$, set ${\hat{R}}_{i,j}=\mathsf {Fhe}.\mathsf {Enc}({\mathsf{pk}},s;r_{i,j})$.

  • 4. For every $i\in [\mu ]\setminus \{k,k^*\}$ set

    $${\hat{R}}^*_{i,1}={\hat{R}}_{i,1},\quad {\hat{R}}_{i,2}^*={\hat{R}}_{i,2},\quad {\hat{R}}^*_{i,3}={\hat{R}}_{i,3}, \quad r^*_{i,4}=r_{i,4}.$$

  • 5. If $k= k^*$, then set

    $${\hat{R}}^*_{k,1}={\hat{R}}_{k,1},\quad {\hat{R}}_{k,2}^*={\hat{R}}_{k,2},\quad {\hat{R}}^*_{k,3}={\hat{R}}_{k,4}, \quad r^*_{k,4}=r_{k,3};$$

    Else if $k\ne k^*$, for every $i\in \{k,k^*\}$ set

    $${\hat{R}}^*_{i,1}={\hat{R}}_{i,4},\quad {\hat{R}}_{i,2}^*={\hat{R}}_{i,3},\quad {\hat{R}}^*_{i,3}={\hat{R}}_{i,1}, \quad r^*_{i,4}=r_{i,2}.$$

  • 6. Output $\mathsf{{r}}^*=(r^*_1,\dots ,r^*_{\mu }, ({\hat{R}}^*_{1,1}, {\hat{R}}^*_{1,2}, {\hat{R}}^*_{1,3}, {r}^*_{1,4}),\dots , ({\hat{R}}^*_{\mu ,1}, {\hat{R}}^*_{\mu ,2}, {\hat{R}}^*_{\mu ,3}, {r}^*_{\mu ,4}))$

Remark 5.1

We observe that by using the circuit $\mathsf{{Mux}}$ instead of the circuit $\mathsf {select}$, we can use smaller randomness – in particular, we can achieve $|\mathsf{{r}}|=\mu \ell +2\log _2(\mu ){\ell '_c}$.

In the full version [1], we prove the scheme satisfies correctness, compactness, CPA security and weak deniability. Due to space constraints, we provide our construction of compact public-key $1/\delta$-deniable fully homomorphic encryption scheme for polynomial sized message space in the full model in the full version of this paper [1].