FHE Circuit Privacy Almost for Free

Abstract

Circuit privacy is an important property for many applications of fully homomorphic encryption. Prior approaches for achieving circuit privacy rely on superpolynomial noise flooding or on bootstrapping. In this work, we present a conceptually different approach to circuit privacy based on a novel characterization of the noise growth amidst homomorphic evaluation. In particular, we show that a variant of the GSW FHE for branching programs already achieves circuit privacy; this immediately yields a circuit-private FHE for NC$^1$ circuits under the standard LWE assumption with polynomial modulus-to-noise ratio. Our analysis relies on a variant of the discrete Gaussian leftover hash lemma which states that $\mathbf {e}^\intercal \mathbf {G}^{-1}(\mathbf {v})+small$ noise does not depend on $\mathbf {v}$. We believe that this result is of independent interest.

F. Bourse—Supported by the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 CryptoCloud)

R. Del Pino—Supported by SAFEcrypto (H2020 ICT-644729)

M. Minelli was supported by European Union’s Horizon 2020 research and innovation programme under grant agreement No H2020-MSCA-ITN-2014-643161 ECRYPT-NET.

H. Wee—Columbia University and CQT, NUS. Supported in part by the ERC Project aSCEND (H2020 639554) and NSF Award CNS-1445424.

1 Introduction

A fully homomorphic encryption (FHE) scheme is an encryption scheme which supports computation on encrypted data: given a ciphertext that encrypts some data $\mu$, one can compute a ciphertext that encrypts $f(\mu )$ for any efficiently computable function f, without ever needing to decrypt the data or know the decryption key. FHE has numerous theoretical and practical applications, the canonical one being to the problem of outsourcing computation to a remote server without compromising one’s privacy. In 2009, Gentry put forth the first candidate construction of FHE based on ideal lattices [Gen09]. Since then, substantial progress has been made [vDGHV10, SS10, SV10, BV11a, BV11b, BGV12, GHS12, GSW13, BV14, AP14], offering various improvements in conceptual and technical simplicity, efficiency, security guarantees, assumptions, etc.; in particular, Gentry, Sahai and Waters presented a very simple FHE (hereafter called the GSW cryptosystem) based on the standard learning with errors (LWE) assumption.

Circuit Privacy. An additional requirement in many FHE applications is that the evaluated ciphertext should also hide the function f, apart from what is inevitably leaked through the outcome of the computation $f(\mu )$; we refer to this requirement as circuit privacy [SYY99, IP07]. In the context of outsourcing computation, a server may wish to hide its proprietary algorithm from the client. Circuit privacy is also a requirement when we use FHE for low-communication secure two-party computation. In all existing FHE schemes, there is a “noise” term in the ciphertext, which is necessary for security. The noise grows and changes as a result of performing homomorphic operations and, in particular, could leak information about the function f. The main challenge for achieving FHE circuit privacy lies precisely in avoiding the leakage from the noise term in the evaluated ciphertext.

Prior Works. Prior works achieve circuit privacy by essentially canceling out the noise term in the evaluated ciphertext. There are two main approaches for achieving this. The first is “noise flooding” introduced in Gentry’s thesis, where we add a much larger noise at the end of the computation; in particular, the noise that is added needs to be super-polynomially larger than the noise that accumulates amidst homomorphic operations, which in turn requires that we start with a super-polynomial modulus-to-noise ratio.¹ This is a fairly mild assumption for the early constructions of FHE schemes, which required a quasi-polynomial modulus-to-noise ratio just to support homomorphic operations for circuits in $\mathsf {NC}^1$ (i.e., circuits of logarithmic depth). The second is to decrypt and re-encrypt the evaluated ciphertext, also known as bootstrapping in the FHE literature. This can be achieved securely without having to know the secret key in the clear in one of two ways: (i) with the use of garbled circuits [OPP14, GHV10], and (ii) via homomorphic evaluation of the decryption circuit given an encryption of the secret key under itself [DS16], which requires the additional assumption of circular security.

Both of the prior approaches have some theoretical and practical draw-backs, if we consider FHE for $\mathsf {NC}^1$ circuits (the rest of the discussion also applies to leveled FHE for general circuits). First, recall that we now have FHE for $\mathsf {NC}^1$ circuits under the LWE assumption with a polynomial modulus-to-noise ratio [BV14, AP14], and we would ideally like to achieve circuit privacy under the same assumption. Relying on noise flooding for circuit privacy would require quantitatively stronger assumptions with a super-polynomial modulus-to-noise ratio, which in turn impacts practical efficiency due to the use of larger parameters. Similarly, the use of bootstrapping for circuit privacy can also be computationally expensive (indeed, the bootstrapping operation is the computational bottleneck in existing FHE schemes, cf. [DM15, HS15]). Moreover, realizing bootstrapping via an encryption of the secret key requires an additional circular security assumption, which could in turn also entail the use of larger parameters in order to account for potential weaknesses introduced by circular security. Realizing bootstrapping via garbled circuits avoids the additional assumption, but is theoretically and practically unsatisfying as it requires encoding the algebraic structure in existing FHEs as boolean computation, and sacrifices the multi-hop property in that we can no longer perform further homomorphic computation on the evaluated ciphertexts.

1.1 Our Results

Our main result is a circuit-private FHE for $\mathsf {NC}^1$ circuits – and a circuit-private leveled FHE for general circuits – under the LWE assumption with a polynomial modulus-to-noise ratio, and whose efficiency essentially matches that of existing variants of the GSW cryptosystem in [BV14, AP14]; in other words, we avoid noise flooding or bootstrapping and obtain circuit privacy almost for free!

We obtain our main result via a conceptually different approach from prior works: instead of canceling out the noise term in the evaluated ciphertext, we directly analyze the distribution of the noise term (prior works on FHE merely gave a bound on the noise term). Concretely, we show that adding a small noise in each step of homomorphic evaluation in the GSW cryptosystem already hides the computation itself which yields circuit privacy. Along the way, we gain better insights into the algebraic structure and the noise distribution in GSW scheme and provide new tools for analyzing noise randomization which we believe could be of independent interest.

As an immediate corollary, we obtain a two-party protocol for secure function evaluation where Alice holds x, Bob holds a branching program f, and we want Alice to learn f(x) while protecting the privacy of x and f to the largest extent possible, that is, Bob learns nothing about x and Alice learns nothing about f (apart from a bound on the size of f). Our protocol achieves semi-honest security under the standard LWE assumption with polynomial hardness, and where the total communication complexity and Alice’s computation are poly-logarithmic in the size of f.

The core of our analysis is a variant of the Gaussian leftover hash lemma [AGHS13, AR13]: given a “small” vector $\mathbf {e}$ and any vector $\mathbf {v}$, we have

$$\begin{aligned} \mathbf {e}^\intercal \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right) + y \approx _{s}e' \end{aligned}$$

where

• $\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right)$ outputs a random short vector $\mathbf {x}$ satisfying $\mathbf {G}\mathbf {x}=\mathbf {v}\mod q$ according to a discrete Gaussian with parameter $r= \tilde{O}(1)$;

• both y and $e'$ are drawn from discrete Gaussians with parameter $O(r \cdot \Vert \mathbf {e} \Vert )$ (the norm of $e'$ will be slightly larger than that of y).

We stress that the distribution of $e'$ is independent of $\mathbf {v}$ and that the norm of $y,e'$ are polynomially related to that of $\Vert \mathbf {e} \Vert$. Indeed, a similar statement is true via noise flooding, where we pick $y,e'$ to have norm super-polynomially larger than that of $\Vert \mathbf {e} \Vert$. Using this leftover hash lemma to hide the argument of $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ is new to this work and will be crucial in proving circuit privacy. In Table 1 we show a comparison with previous works on how to perform a step of computation for branching program evaluation.

1.2 Technical Overview

We proceed with a technical overview of our construction. We build up to our main construction in three steps.

Generating Fresh LWE Samples. How do we generate a fresh LWE sample from a large but bounded number of samples? That is, we need to randomize $(\mathbf {A}, \mathbf {s}^\intercal \mathbf {A}+ \mathbf {e}^\intercal )$. The first idea, going back to [Reg05, GPV08, ACPS09] is to choose $\mathbf {x}$ according to a discrete Gaussian with parameter $r = \tilde{O}(1)$ and a small “smoothing” noise y from a discrete Gaussian with parameter $O(r \cdot \Vert \mathbf {e} \Vert )$ and output

$$\begin{aligned} \mathbf {A}\mathbf {x}, (\mathbf {s}^\intercal \mathbf {A}+ \mathbf {e}^\intercal ) \mathbf {x}+ y \end{aligned}$$

The vector $\mathbf {A}\mathbf {x}$ is statistically close to uniform (by leftover hash lemma), and the error $\mathbf {e}^\intercal \mathbf {x}+ y$ in the resulting sample is statistically close to a discrete Gaussian with parameter $O(r \cdot \Vert \mathbf {e} \Vert )$. We stress that the norm of y is polynomially related to that of $\mathbf {e}$, which is better than naive noise flooding. One draw-back compared to noise flooding is that the error in the new sample leaks $\Vert \mathbf {e} \Vert$. In the case of generating fresh LWE samples, we just need to repeat the process to generate many more samples than what we started out with.

Randomizing GSW Ciphertexts. Next, we note that the above idea can also be used to randomize GSW ciphertexts. Recall that a GSW encryption of a message $\mu$ is of the form

$$ \mathbf {C}= \begin{pmatrix}\mathbf {A}\\ \mathbf {s}^\intercal \mathbf {A}+ \mathbf {e}^\intercal \end{pmatrix} + \mu \mathbf {G}\in \mathbb {Z}_q^{n \times {(n \log q)}}$$

where $\mathbf {s}\in \mathbb {Z}_q^n$ is the secret key and $\mathbf {G}$ is the “powers of 2” gadget matrix. We can randomize $\mathbf {C}$ to be a fresh encryption of $\mu$ by computing

$$\begin{aligned} \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {G}\right) + \begin{pmatrix}\mathbf {0} \\ {\mathbf {y}}^\intercal \end{pmatrix} \end{aligned}$$

where $\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {G}\right)$ is chosen according to a discrete Gaussian of parameter $r$ satisfying $\mathbf {G}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {G}\right) = \mathbf {G}$ and $\mathbf {y}$ is again a small smoothing noise vector. Here, we need an extension of the previous lemma showing that each coordinate in $\mathbf {e}^\intercal \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {G}\right) + {\mathbf {y}}^\intercal$ is statistically close to a discrete Gaussian; this in turn follows from an extension of the previous lemma where the vector $\mathbf {x}$ is drawn from discrete Gaussian over the coset of a lattice (cf. Lemma 3.6). And again, the norm of $\mathbf {y}$ is polynomially related to that in $\mathbf {e}$, which is better than naive noise flooding.

Table 1. The first row of the table shows the plaintext computation that happens at each step of the computation for evaluating a branching program (cf. Sect. 5.1). The next three rows describe how this computation is carried out homomorphically on ciphertexts $\mathbf {V}_0, \mathbf {V}_1, \mathbf {C}$ corresponding to encryptions of the input bits $v_0, v_1, x$. In the [GSW13, BV14] FHE schemes, homomorphic evaluation is deterministic, whereas in [AP14] and this work, homomorphic evaluation is randomized. In particular, our construction introduces an additional small Gaussian shift on top of [AP14].

Scaling GSW Ciphertexts. More interesting, given a constant $a \in \{0,1\}$, we can scale a GSW encryption of $\mu$ to obtain a fresh encryption of $a \cdot \mu$ while revealing no information about a beyond what is leaked in $a \cdot \mu$. In particular, if $\mu = 0$, then the resulting ciphertext should completely hide a. To achieve this, we simply proceed as before, except we use $\mathbf {G}^{-1}_{\text {rand}}\left( a \cdot \mathbf {G}\right)$ so that $\mathbf {G}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( a \cdot \mathbf {G}\right) = a \cdot \mathbf {G}$. Here, we crucially rely on the fact that the error $\mathbf {e}^\intercal \cdot \mathbf {G}^{-1}_{\text {rand}}\left( a \cdot \mathbf {G}\right) + {\mathbf {y}}^\intercal$ in the resulting ciphertext is independent of a.

Circuit-Private Homomorphic Evaluation. The preceding construction extends to the setting where we are given a GSW encryption $\mathbf {C}'$ of a instead of a itself, so that we output

$$\begin{aligned} \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}'\right) + \begin{pmatrix}\mathbf {0} \\ {\mathbf {y}}^\intercal \end{pmatrix} \end{aligned}$$

We can handle homomorphic encryption as in GSW; this then readily extends to a circuit-private homomorphic evaluation for branching programs, following [BV14, AP14].

Branching programs are a relatively powerful representation model. In particular, any logarithmic space or $\mathsf {NC}^1$ computation can be carried out by a family of polynomial-size branching programs. Branching programs can also directly capture several representation models often used in practice such as decision trees, OBDDs, and deterministic finite automaton.

The key insight from Brakerski and Vaikuntanathan [BV14] is that when homomorphically evaluating a branching program, we will only need to perform homomorphic additions along with homomorphic multiplications of ciphertexts $\mathbf {V}_j,\mathbf {C}_i$ where $\mathbf {V}_j$ is the encryption of an intermediate computation and $\mathbf {C}_i$ is an encryption of the input variable $x_i$. To obtain decryption correctness with polynomial noise growth, they computed the product as

$$\begin{aligned} \mathbf {C}_i \cdot \mathbf {G}^{-1}_{\text {det}}(\mathbf {V}_j), \end{aligned}$$

where $\mathbf {G}^{-1}_{\text {det}}\left( \cdot \right)$ denotes the deterministic binary decomposition, cleverly exploiting the asymmetric noise growth in GSW ciphertexts and the fact that the noise in $\mathbf {C}_i$ is smaller than that in $\mathbf {V}_j$. To obtain circuit privacy, we will compute the product as

$$ \mathbf {C}_i \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_j\right) + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}^\intercal _j\end{pmatrix}.$$

Note that we made two modifications:

• First, we switched to a randomized $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$. The use of a randomized $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ for homomorphic evaluation was first introduced in [AP14], but for the very different purpose of a mild improvement in the noise growth (i.e. efficiency); here, we crucially exploit randomization for privacy.

• Next, we introduced an additional Gaussian shift $\mathbf {\mathbf {y}}^\intercal _j$.

Interestingly, it turns out that computing the product as $\mathbf {C}_i \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_j\right)$ instead of $\mathbf {V}_j \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}_i\right)$ is useful not only for polynomial noise growth, but also useful for circuit privacy. Roughly speaking, the former hides which $\mathbf {V}_j$ is used, which corresponds to hiding the intermediate states that lead to the final output state, which in turn hides the branching program.

We highlight a subtlety in the analysis: $\mathbf {V}_j$ could in principle encode information about $\mathbf {C}_i$, if the variable $x_i$ has been read prior to reaching the intermediate state encoded in $\mathbf {V}_j$, whereas to apply our randomization lemma, we crucially rely on independence between $\mathbf {C}_i$ and $\mathbf {V}_j$. The analysis proceeds by a careful induction argument showing that $\mathbf {V}_j$ looks like a fresh GSW ciphertext independent of input ciphertexts $\mathbf {C}_1,\ldots ,\mathbf {C}_\ell$ apart from some dependencies on the norm of the noise terms in the input ciphertexts (see Lemma 5.4 for a precise statement). These dependencies mean that homomorphic evaluation leaks the number of times each variable appears in the branching program, but that can be easily fixed by padding the branching program.

1.3 Discussions

One draw-back of our approach is that it is specific to the GSW cryptosystem and variants there-of, whereas previous approaches based on noise flooding and bootstrapping are fairly generic; another is that we need to pad the branching program so that each variable appears the same number of times. Nonetheless, we stress that the GSW cryptosystem turns out to be ubiquitous in many applications outside of FHE, including attribute-based encryption and fully homomorphic signatures [BGG+14, GVW15]. We are optimistic that the additional insights we gained into the noise distributions of GSW ciphertexts in this work will find applications outside of FHE.

We conclude with several open problems pertaining to FHE circuit privacy. The first is to achieve circuit privacy against malicious adversaries [OPP14]: namely, the result of a homomorphic evaluation should leak no information about the circuit f, even if the input ciphertexts are maliciously generated. Our analysis breaks down in this setting as it crucially uses fresh uniform randomness in the input ciphertexts for left-over hash lemma, and the fact that the noise in the input ciphertexts are small (but does not need to be discrete Gaussian). Another is to achieve circuit-private CCA1-secure FHE [LMSV12]; here, the technique that [DS16] uses to achieve circuit privacy cannot obtain such a result since giving out an encryption of the secret key violates CCA1-security. A third open problem is to extend the techniques in this work to other FHE schemes, such as those in [BV11a, DM15, HS15].

2 Preliminaries

In this section we clarify our notation and recall some definitions, problems and lemmas that we are going to use throughout the paper.

Notation. We denote the real numbers by $\mathbb {R}$, the integers by $\mathbb {Z}$, the integers modulo some q by $\mathbb {Z}_q$, and let $\left[ N\right]$ indicate the integer numbers $\left\{ 1, \ldots , N\right\}$. Throughout the paper we use $\lambda$ to denote the security parameter. We say that a function is negligible in $\lambda$, and we denote it by ${{\mathrm{negl}}}\left( \lambda \right)$, if it is a $f\left( \lambda \right) = o\left( \lambda ^{-c}\right)$ for every fixed constant c. We also say that a probability is overwhelming if it is $1 - {{\mathrm{negl}}}\left( \lambda \right)$.

Vectors are denoted by lower-case bold letters (e.g., $\mathbf {v}$) and are always in column form ($\mathbf {v}^{\intercal }$ is a row vector), while matrices are indicated by upper-case bold letters. We let $\left( \mathbf {a}, \mathbf {b}\right)$ denote the vector obtained by concatenating the two vectors, i.e. $\begin{pmatrix} \mathbf {a}\\ \mathbf {b}\end{pmatrix}$. We also write $\left( \mathbf {v}_1 \mid \mathbf {v}_2 \mid \ldots \mid \mathbf {v}_k\right)$ to denote the matrix whose columns are the vectors $\mathbf {v}_i$. Unless otherwise stated, the norm $\Vert \cdot \Vert$ considered in this paper is the $\ell _2$ norm and $\log$ denotes the base-2 logarithm, while $\ln$ denotes the natural logarithm.

Given two distributions X, Y over a finite or countable domain D, their statistical distance is defined as $\varDelta \left( X,Y\right) = \frac{1}{2}\sum _{v \in D} \left| X\left( v\right) - Y\left( v\right) \right|$. We say that two distributions are statistically close (denoted by $\approx _{s}$) if their statistical distance is ${{\mathrm{negl}}}\left( \lambda \right)$. Given a set A, we will write $a \mathop {\leftarrow }\limits ^{\$}A$ to indicate that a is sampled from A uniformly at random. If $\mathcal {D}$ is a probability distribution, we will write $d \leftarrow \mathcal {D}$ to indicate that d is sampled according to the distribution $\mathcal {D}$. Following [MP12], we denote by $\mathbf {G}$ the gadget matrix, i.e. $\mathbf {G}= \mathbf {g}^{\intercal } \otimes \mathbf {I}_n$, where $\mathbf {g}$ is the vector $\left( 1,2,4,\ldots ,2^{\lceil \log q\rceil - 1}\right)$, for given parameters n, q.

Lattices. A m-dimensional lattice $\varLambda$ is a discrete additive subgroup of $\mathbb {R}^m$. For an integer $k < m$ and a rank k matrix $\mathbf {B}\in \mathbb {R}^{m\times k}$, $\varLambda \left( \mathbf {B}\right) = \left\{ \mathbf {B}\mathbf {x}\in \mathbb {R}^m \mid \mathbf {x}\in \mathbb {Z}^k\right\}$ is the lattice generated by the columns of $\mathbf {B}$. We will let $\varLambda _q^{\perp }\left( \mathbf {B}\right)$ denote $\left\{ \mathbf {v}\in \mathbb {Z}^m \mid \mathbf {B}^\intercal \mathbf {v}= \mathbf {0}\mod q\right\}$.

Gaussian Function. For any $\alpha >0$, the spherical Gaussian function with parameter $\alpha$ (omitted if 1) is defined as $\rho _\alpha \left( \mathbf {x}\right) = \exp \left( -\pi \Vert \mathbf {x} \Vert ^2/\alpha ^2\right)$, for any $\mathbf {x}\in \mathbb {R}^m$. Given a lattice $\varLambda \subseteq \mathbb {R}^m$, a parameter $r\in \mathbb {R}$ and a vector $\mathbf {c}\in \mathbb {R}^m$ the spherical Gaussian distribution with parameter $r$ and support $\varLambda + \mathbf {c}$ is defined as

$$ \mathcal {D}_{\varLambda + \mathbf {c}, r}\left( \mathbf {x}\right) = \frac{\rho _r\left( \mathbf {x}\right) }{\rho _r\left( \varLambda + \mathbf {c}\right) }, \quad \forall \mathbf {x}\in \varLambda + \mathbf {c}$$

where $\rho _r\left( \varLambda + \mathbf {c}\right)$ denotes $\sum _{\mathbf {x}\in \varLambda + \mathbf {c}} \rho _r\left( \mathbf {x}\right)$. Note that $\rho _r\left( \mathbf {x}\right) = \rho \left( r^{-1} \mathbf {x}\right)$.

We now give an algorithm for the randomized bit decomposition $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$.

Definition 2.1

(The $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ algorithm, adapted from [MP12], [AP14, Claim 3.1]). There is a randomized, efficiently computable function $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right) : \mathbb {Z}_q^n\rightarrow \mathbb {Z}^m$, where $m = n \lceil \log q\rceil$ such that $\mathbf {x}\leftarrow \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right)$ is drawn from a distribution close to a Gaussian with parameter $r= \tilde{O}(1)$ conditioned on $\mathbf {G}\mathbf {x}= \mathbf {v}\mod q$, i.e. $\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right)$ outputs a sample from the distribution $\mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) + \mathbf {G}^{-1}_{\text {det}}\left( \mathbf {v}\right) , r}$ where $\mathbf {G}^{-1}_{\text {det}}\left( \cdot \right)$ denotes (deterministic) bit decomposition. We will also write $\mathbf {X}\leftarrow \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {M}\right)$ to denote that the columns of the matrix $\mathbf {X}\in \mathbb {Z}^{m \times p}$ are obtained by applying the algorithm separately to each column of a matrix $\mathbf {M}\in \mathbb {Z}_q^{n \times p}$.

In particular, using the exact sampler in [BLP+13, Sect. 5] (which is a variant of the algorithm presented in [GPV08]), $\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right)$ outputs a sample from the discrete Gaussian

$$ \mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) + \mathbf {G}^{-1}_{\text {det}}\left( \mathbf {v}\right) , r} $$

Next, we recall the definition of the smoothing parameter of a lattice from [MR04]. Intuitively, this parameter provides the width beyond which the discrete Gaussian measure on a lattice behaves like a continuous one.

Definition 2.2

(Smoothing parameter). For a lattice $\varLambda \subseteq \mathbb {Z}^m$ and positive real $\varepsilon > 0$, the smoothing parameter $\eta _{\varepsilon }\left( \varLambda \right)$ is the smallest real $r> 0$ such that $\rho _{1/r} \left( \varLambda ^{*}\setminus \left\{ \mathbf {0}\right\} \right) \le \varepsilon$, where $\varLambda ^{*}:=\left\{ \mathbf {x}\in \mathbb {R}^m\mid \mathbf {x}^\intercal \varLambda \subseteq \mathbb {Z}\right\}$.

We will also need the following probability results.

Lemma 2.3

(Simplified version of [Pei10, Theorem 3.1]). Let $\varepsilon >0$, $r_1,r_2>0$ be two Gaussian parameters, and $\varLambda \subseteq \mathbb {Z}^m$ be a lattice. If $\frac{r_1r_2}{\sqrt{ r_1^2+r_2^2}}\ge \eta _{\varepsilon }\left( \varLambda \right)$, then

$$\begin{aligned} \varDelta \left( \mathbf {y}_1+\mathbf {y}_2,\mathbf {y}'\right) \le 8\varepsilon \end{aligned}$$

where $\mathbf {y}_1\leftarrow \mathcal {D}_{\varLambda ,r_1}$, $\mathbf {y}_2\leftarrow \mathcal {D}_{\varLambda ,r_2}$, and $\mathbf {y}'\leftarrow \mathcal {D}_{\varLambda ,\sqrt{ r_1^2+r_2^2}}$.

Lemma 2.4

[AP14, Lemma 2.1]. There exists a universal constant $C>0$, such that

$$\begin{aligned} \Pr {\left[ \Vert \mathbf {x} \Vert >Cr\sqrt{m}\right] }\le 2^{-\varOmega (m)} \end{aligned}$$

where $\mathbf {x}\leftarrow \mathcal {D}_{\mathbb {Z}^m,r}$.

Next, we recall the LWE problem and its hardness assumption.

The LWE Problem and Assumption. The learning with errors (LWE) problem was introduced by Regev in [Reg05] as a generalization of “learning parity with noise”. Let $q \ge 2$, n and $m = {{\mathrm{poly}}}(n)$ be positive integers, and let $\chi$ be a probability distribution over $\mathbb {Z}_q$. We define the following advantage function for an adversary $\mathcal {A}$:

$$ \mathsf {Adv}_{\mathcal {A}}^{{\mathsf {LWE}}_{n,q,\chi }} :=\left| \Pr \left[ \mathcal {A}\left( \mathbf {A}, \mathbf {s}^\intercal \mathbf {A}+ \mathbf {e}^\intercal \right) = 1\right] - \Pr \left[ \mathcal {A}\left( \mathbf {A}, \mathbf {u}\right) = 1\right] \right| $$

where $\mathbf {A}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{n \times m}$, $\mathbf {s}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^n$, $\mathbf {e}\leftarrow \chi$ and $\mathbf {u}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^m$. The LWE assumption asserts that for any PPT adversary $\mathcal {A}$, the advantage $\mathsf {Adv}_{\mathcal {A}}^{{\mathsf {LWE}}_{n,q,\chi }}$ is ${{\mathrm{negl}}}\left( n\right)$.

Finally, we recall the definition of a homomorphic encryption scheme, evaluation correctness and semantic security.

Homomorphic Encryption Scheme. A homomorphic (secret-key) encryption scheme $\mathcal {E}= (\mathcal {E}.\mathsf {Setup}, \mathcal {E}.\mathsf {Encrypt}, \mathcal {E}.\mathsf {Decrypt}, \mathcal {E}.\mathsf {Eval})$ is a quadruple of PPT algorithms as follows:

• $\mathcal {E}.\mathsf {Setup}\left( 1^\lambda \right)$: given the security parameter $\lambda$, outputs a secret key sk and an evaluation key evk

• $\mathcal {E}.\mathsf {Encrypt}\left( sk, \mu \right)$: using the secret key sk, encrypts a message $\mu \in \left\{ 0,1\right\}$ into a ciphertext c and outputs c

• $\mathcal {E}.\mathsf {Decrypt}\left( sk, c\right)$: using the secret key sk, decrypts a ciphertext c to recover a message $\mu \in \left\{ 0,1\right\}$

• $\mathcal {E}.\mathsf {Eval}\left( evk, f, c_1, \ldots , c_\ell \right)$: using the evaluation key evk, applies a function $f : \left\{ 0,1\right\} ^{\ell }\rightarrow \left\{ 0,1\right\}$ to ciphertexts $c_1, \ldots , c_\ell$ and outputs a ciphertext $c_f$

Evaluation Correctness. We say that the $\mathcal {E}.\mathsf {Eval}$ algorithm correctly evaluates all functions in $\mathcal {F}$ if, for any function $f \in \mathcal {F}: \left\{ 0,1\right\} ^{\ell } \rightarrow \left\{ 0,1\right\}$ and respective inputs $x_1, \ldots , x_\ell \in \left\{ 0,1\right\}$ it holds that

$$ \Pr \left[ \mathcal {E}.\mathsf {Decrypt}\left( sk, \mathcal {E}.\mathsf {Eval}\left( evk, f, c_1, \ldots , c_\ell \right) \right) = f\left( x_1, \ldots , x_\ell \right) \right] = 1 - {{\mathrm{negl}}}\left( \lambda \right) $$

where $sk \leftarrow \mathcal {E}.\mathsf {Setup}\left( 1^\lambda \right)$ and $c_i \leftarrow \mathcal {E}.\mathsf {Encrypt} \left( sk, x_i\right)$.

Semantic Security. A secret key encryption scheme $\mathcal {E}$ is said to be semantically secure (or IND-CPA secure) if any PPT adversary $\mathcal {A}$ cannot distinguish between encryptions of two known plaintexts. More formally, let $sk\leftarrow \mathcal {E}.\mathsf {Setup}(1^\lambda )$ and $\mathcal {O}_b\left( \mu _0,\mu _1\right) = \mathcal {E}.\mathsf {Encrypt}\left( sk, \mu _b\right)$ for $b\in \left\{ 0,1\right\}$. Then $\mathcal {E}$ is IND-CPA secure if

$$ \left| \Pr \left[ \mathcal {A}^{\mathcal {O}_0}\left( 1^\lambda \right) =1\right] -\Pr \left[ \mathcal {A}^{\mathcal {O}_1}\left( 1^\lambda \right) =1\right] \right| = {{\mathrm{negl}}}\left( \lambda \right) $$

where the probability is taken over the internal coins of $\mathcal {E}.\mathsf {Setup}$, $\mathcal {E}.\mathsf {Encrypt}$ and $\mathcal {A}$.

3 Core Randomization Lemma

Note that throughout the rest of the paper we set q to be a power of 2, and $m=n\log q$. We discuss the use of a modulus q that is not a power of 2 in Sect. 5.4.

The goal of this Section is to establish the following lemma:

Lemma 3.1

(Core randomization lemma). Let $\varepsilon ,\varepsilon '>0$, $r> \eta _{\varepsilon }(\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) )$ be a Gaussian parameter. For any $\mathbf {e}\in \mathbb {Z}_q^m$, $\mathbf {v}\in \mathbb {Z}_q^n$, if $r\ge \max \left( 4\left( {(1-\varepsilon )\left( 2\varepsilon '\right) ^2}\right) ^ {-\frac{1}{m}},\sqrt{5}(1+\Vert \mathbf {e} \Vert ) \sqrt{\frac{\ln \left( 2m\left( 1+1/\varepsilon \right) \right) }{\pi }}\right)$, then

$$ \varDelta \left( \left( \mathbf {A}, \mathbf {A}\mathbf {x}, \mathbf {e}^\intercal \mathbf {x}+ y \right) ,\left( \mathbf {A},\mathbf {u},e'\right) \right) < \varepsilon '+2\varepsilon $$

where $\mathbf {x}\leftarrow \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right)$, $\mathbf {A}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{(n-1)\times m}$, $\mathbf {u}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{n-1}$, $y\leftarrow \mathcal {D}_{\mathbb {Z},r}$ and $e'\leftarrow \mathcal {D}_{\mathbb {Z},r\sqrt{1+\Vert \mathbf {e} \Vert ^2}}$.

Asymptotically, $r=\tilde{\varTheta }(\Vert \mathbf {e} \Vert \sqrt{\lambda })$ is enough to obtain negligible statistical distance.

Remark 1

(on the necessity of randomization). We note here that the use of randomization in $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ and the shift are both necessary.

First, the shift is necessary for both distributions to have the same support. For example, $\mathbf {e}^\intercal \mathbf {G}^{-1}_{\text {rand}}\left( (1,0,\ldots ,0)\right)$ and $\mathbf {e}^\intercal \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right)$ might lie in two different cosets of the lattice $\mathbf {e}^\intercal \varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right)$, depending on the value of $\mathbf {e}$: if the first coordinate of $\mathbf {e}$ is odd and all the others are even, then $\mathbf {e}^\intercal \mathbf {G}^{-1}_{\text {rand}}\left( (1,0,\ldots ,0)\right)$ will be odd, while $\mathbf {e}^\intercal \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right)$ will be even, for a q even. The shift by a Gaussian over $\mathbb {Z}$ ensures that the support of the two distributions is $\mathbb {Z}$. Proving that $\mathbf {e}^\intercal \varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) =\mathbb {Z}$ with overwhelming probability over the choice of $\mathbf {e}$ is still an open question that would remove the necessity of the shift, thus proving circuit privacy for standard GSW only using randomized $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$.

Finally, the randomization of $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ is necessary for both distributions to have the same center. Using the same example, $\mathbf {e}^\intercal \mathbf {G}^{-1}_{\text {det}}\left( (1,0,\ldots ,0)\right) +y$ and $\mathbf {e}^\intercal \mathbf {G}^{-1}_{\text {det}}\left( \mathbf {0}\right) +y$ would be two Gaussians, centered respectively on $e_1$ (the first coordinate of $\mathbf {e}$) and on 0. Instead, using the randomized algorithm $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$, the center of both distributions will be 0.

3.1 Additional Preliminaries

Before proving Lemma 3.1, we need to recall some additional results.

Lemma 3.2

[MR07, Lemma 3.3]. Let $\varLambda$ be any rank-m lattice and $\varepsilon$ be any positive real. Then

$$ \eta _{\varepsilon }\left( \varLambda \right) \le \lambda _m\left( \varLambda \right) \cdot \sqrt{\frac{ \ln \left( 2m\left( 1+1/\varepsilon \right) \right) }{\pi }} $$

where $\lambda _m\left( \varLambda \right)$ is the smallest R such that the ball $\mathcal {B}_R$ centered in the origin and with radius R contains m linearly independent vectors of $\varLambda$.

Lemma 3.3

[GPV08, Corollary 2.8]. Let $\varLambda \subseteq \mathbb {Z}^m$ be a lattice, $0< \varepsilon < 1$, $r>0$. For any vector $\mathbf {c}\in \mathbb {R}^m$, if $r\ge \eta _{\varepsilon }\left( \varLambda \right)$, then we have

$$ \rho _r\left( \varLambda + \mathbf {c}\right) \in \left[ \frac{1-\varepsilon }{1+ \varepsilon },\ 1\right] \cdot \rho _r\left( \varLambda \right) . $$

Lemma 3.4

[Reg05, Claim 3.8]. Let $\varLambda \subseteq \mathbb {Z}^m$ be any lattice, $\mathbf {c}\in \mathbb {R}^m$, $\varepsilon > 0$ and $r \ge \eta _{\varepsilon }{\left( \varLambda \right) }$. Then

$$ \rho _r\left( \varLambda +\mathbf {c}\right) \in \frac{r^m}{\det \left( \varLambda \right) } \left( 1 \pm \varepsilon \right) .$$

Generalized Leftover Hash Lemma. We state here a simplified version of the generalized leftover hash lemma which is sufficient for our use. The min-entropy of a random variable X is defined as

$$ H_{\infty }\left( X\right) = -\log \left( \max _x \Pr \left[ X=x\right] \right) . $$

Lemma 3.5

(Generalized leftover hash lemma [DRS04]). Let $\mathbf {e}$ be any random variable over $\mathbb {Z}_q^m$ and $f : \mathbb {Z}_q^m \rightarrow \mathbb {Z}_q^k$. Then

$$\varDelta ((\mathbf {X}\mathbf {e},\mathbf {X},f(\mathbf {e})), (\mathbf {r},\mathbf {X},f(\mathbf {e})))\le \frac{1}{2}\sqrt{q^{n+k} \cdot 2^{-H_{\infty }\left( \mathbf {e}\right) }}\,.$$

where $\mathbf {X}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{n\times m}$ and $\mathbf {r}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^n$.

3.2 Proof of Lemma 3.1

We first prove that given $\mathbf {e}$, the new error term $\mathbf {e}^\intercal \mathbf {x}+y$ is indeed a Gaussian with parameter $r\sqrt{1+\Vert \mathbf {e} \Vert ^2}$. This proof is inspired by [AR13], which in turn is an improvement of [AGHS13], but it is different in two aspects: on one hand, in [AR13] the proof is done for the specific case where $\mathbf {x}$ is drawn from a Gaussian over a coset of $\mathbb {Z}^m$; on the other hand, they consider the more general case of an ellipsoidal Gaussian distribution.

Lemma 3.6

(adapted from [AR13, Lemma 3.3]). Let $\varepsilon , r> 0$. For any $\mathbf {e}\in \mathbb {Z}^m$, $\mathbf {c}\in \mathbb {R}^m$, if $r\ge \sqrt{5}(1+\Vert \mathbf {e} \Vert )\cdot \sqrt{\frac{\ln \left( 2m\left( 1+1/\varepsilon \right) \right) }{\pi }}$, then

$$ \varDelta \left( \mathbf {e}^\intercal \mathbf {x}+y,e'\right) < 2 \varepsilon $$

where $\mathbf {x}\leftarrow \mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) + \mathbf {c},r}$, $y\leftarrow \mathcal {D}_{\mathbb {Z},r}$, and $e'\leftarrow \mathcal {D}_{\mathbb {Z},r\sqrt{1+\Vert \mathbf {e} \Vert ^2}}$.

Asymptotically, $r=\tilde{\varTheta }(\Vert \mathbf {e} \Vert \sqrt{\lambda })$ is enough to obtain negligible statistical distance. We stress that the distribution of $e'$ does not depend on the coset $\mathbf {c}$.

Proof

Let $\widehat{\mathbf {e}}=\left( \mathbf {e},1\right) \in \mathbb {Z}^{m+1},\widehat{\mathbf {c}}=\left( \mathbf {c},0\right) \in \mathbb {Z}^{m+1}$ and $\widehat{\varLambda }=\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) \times \mathbb {Z}$, we want to show that

$$\varDelta \left( {\widehat{\mathbf {e}}^\intercal \mathcal {D}_{\widehat{\varLambda }+ \widehat{\mathbf {c}},r},\mathcal {D}_{\mathbb {Z}, \Vert \widehat{\mathbf {e}} \Vert r}}\right) \le 2\varepsilon $$

The support of $\widehat{\mathbf {e}}^\intercal \mathcal {D}_{\widehat{\varLambda }+\widehat{\mathbf {c}},r}$ is $\widehat{\mathbf {e}}^\intercal \widehat{\varLambda }+\widehat{\mathbf {e}}^\intercal \widehat{\mathbf {c}}= \mathbf {e}^\intercal \varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) + \mathbb {Z}+ \mathbf {e}^ \intercal \mathbf {c}=\mathbb {Z}$. Fix some $z \in \mathbb {Z}$. The probability mass assigned to z by $\widehat{\mathbf {e}}^\intercal \mathcal {D}_{\widehat{\varLambda }+ \widehat{\mathbf {c}},r}$ is proportional to $\rho _r(\mathcal {L}_z)$, where

$$\begin{aligned} \mathcal {L}_z=\left\{ \mathbf {v}\in \widehat{\varLambda }+\widehat{\mathbf {c}}: \widehat{\mathbf {e}}^\intercal \mathbf {v}=z\right\} \end{aligned}$$

We define the lattice $\mathcal {L}=\left\{ \mathbf {v}\in \widehat{\varLambda }: \widehat{\mathbf {e}}^\intercal \mathbf {v}=0\right\}$; note that $\mathcal {L}_z=\mathcal {L}+\mathbf {w}_z$ for any $\mathbf {w}_z\in \mathcal {L}_z$. Let $\mathbf {u}_z=\frac{z}{\Vert \widehat{\mathbf {e}} \Vert ^2r} \widehat{\mathbf {e}}$, then $\mathbf {u}_z$ is clearly proportional to $\widehat{\mathbf {e}}$. Observe that $\mathbf {u}_z$ is orthogonal to $r^{-1}\mathcal {L}_z- \mathbf {u}_z$, indeed for any $\mathbf {t}\in r^{-1}\mathcal {L}_z$ we have $\widehat{\mathbf {e}}^\intercal \left( \mathbf {t}-\mathbf {u}_z\right) =0$. From this we have $\rho (\mathbf {t})=\rho (\mathbf {u}_z)\cdot \rho (\mathbf {t}-\mathbf {u}_z)$, and by summing for $\mathbf {t}\in r^{-1}\mathcal {L}_z$:

$$\begin{aligned} \rho (r^{-1}\mathcal {L}_z)=\rho (\mathbf {u}_z)\cdot \rho (r^{-1}\mathcal {L}_z-\mathbf {u}_z) \end{aligned}$$

Observe that we have $r^{-1}\mathcal {L}_z-\mathbf {u}_z=r^{-1}(\mathcal {L}-\mathbf {c}')$ for some $\mathbf {c}'$ in the vector span of the lattice $\mathcal {L}$ (because $\mathcal {L}_z-r\mathbf {u}_z=\mathcal {L}+\mathbf {w}_z-r\mathbf {u}_z$ and $\widehat{\mathbf {e}}^\intercal (\mathbf {w}_z- r\mathbf {u}_z)=0$). Thus using Lemmas 3.3 and 3.7 with $r\ge \sqrt{5}(1+\Vert \mathbf {e} \Vert )\cdot \sqrt{\frac{\ln \left( 2m \left( 1+1/\varepsilon \right) \right) }{\pi }} \ge \eta _{\varepsilon }(\mathcal {L})$, we obtain

$$\begin{aligned} \rho (r^{-1}\mathcal {L}_z)&=\rho (\mathbf {u}_z)\cdot \rho _{r}(\mathcal {L}-\mathbf {c}')\\&\in \left[ \frac{1-\varepsilon }{1+\varepsilon },\ 1\right] \cdot \rho _{r}(\mathcal {L})\cdot \rho (\mathbf {u}_z)\\&= \left[ \frac{1-\varepsilon }{1+\varepsilon },\ 1\right] \cdot \rho _{r}(\mathcal {L})\cdot \rho \left( \frac{z}{\Vert \widehat{\mathbf {e}} \Vert ^2r}\widehat{\mathbf {e}}\right) \\&= \left[ \frac{1-\varepsilon }{1+\varepsilon },\ 1\right] \cdot \rho _{r}(\mathcal {L})\cdot \rho _{\Vert \widehat{\mathbf {e}} \Vert r}(z) \end{aligned}$$

This implies that the statistical distance between $\widehat{\mathbf {e}}^\intercal \mathcal {D}_{\widehat{\varLambda }+ \widehat{\mathbf {c}},r}$ and $\mathcal {D}_{\mathbb {Z},\Vert \widehat{\mathbf {e}} \Vert r}$ is at most $1- \frac{1-\varepsilon }{1+\varepsilon }\le 2\varepsilon$.    $\square$

In order to conclude the previous proof, we now give a bound on the smoothing parameter of the lattice $\mathcal {L}$.

Lemma 3.7

Let $\varepsilon >0$. For any $\mathbf {e}\in \mathbb {Z}^{m}$, let $\mathcal {L}$ be as defined in Lemma 3.6. Then we have:

$$\eta _{\varepsilon }(\mathcal {L})\le \sqrt{5}(1+\Vert \mathbf {e} \Vert )\cdot \sqrt{\frac{\ln \left( 2m\left( 1+1/\varepsilon \right) \right) }{\pi }}.$$

Proof

We use Lemma 3.2 to bound the smoothing parameter of $\mathcal {L}$. Since $\widehat{\varLambda }=\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) \times \mathbb {Z}$ is of dimension $m+1$ and $\mathcal {L}$ is the sublattice of $\widehat{\varLambda }$ made of the vectors that are orthogonal to $\mathbf {e}$, we have that $\mathcal {L}$ is of dimension m. We thus exhibit m independent short vectors of $\mathcal {L}$ to obtain an upper bound on $\lambda _m\left( \mathcal {L}\right)$. We first define the matrix

$$ \overline{\mathbf {B}} = \left( \begin{array}{rrrr} 2 &{} &{} &{} \\ -1 &{} \ddots &{} &{} \\ &{}\ \ \ddots &{} \ddots &{} \\ &{} &{} -1\ &{} 2 \end{array}\right) \in \mathbb {Z}^{\left( \log q\right) \times \left( \log q\right) } $$

and remark that it is a basis for the lattice $\varLambda ^{\perp }_q\left( \mathbf {g}^\intercal \right)$. The lattice $\widehat{\varLambda }$ is then generated by the columns of the matrix:

$$ \mathbf {B}=(\mathbf {b}_1 \mid \ldots \mid \mathbf {b}_{m+1})= \left( \begin{array}{c|c} \mathbf {I}_n \otimes \overline{\mathbf {B}}\ &{}\ \mathbf {0}\\ \hline \mathbf {0}^\intercal &{}\ 1 \end{array}\right) \in \mathbb {Z}^{\left( m+1\right) \times \left( m+1\right) } $$

For $k\le m$ let $\mathbf {u}_k=\mathbf {b}_k-\mathbf {b}_{m+1}\cdot \widehat{\mathbf {e}}^\intercal \mathbf {b}_k$, since $\widehat{\mathbf {e}}^\intercal \mathbf {b}_{m+1}=1$ we directly have $\widehat{\mathbf {e}}^\intercal \mathbf {u}_k=0$ and thus $\mathbf {u}_k\in \mathcal {L}$. The vectors $\mathbf {u}_1,\ldots ,\mathbf {u}_m$ are linearly independent since ${{\mathrm{span}}}\left( \mathbf {u}_1,\ldots ,\mathbf {u}_m, \mathbf {b}_{m+1}\right) ={{\mathrm{span}}}\left( \mathbf {b}_1,\ldots ,\mathbf {b}_m,\mathbf {b}_{m+1}\right) =\mathbb {R}^{m+1}$ (which comes from the fact that $\mathbf {B}$ is a basis of an $(m+1)$-dimensional lattice). We now bound the norm of $\mathbf {u}_k$:

$$\begin{aligned} \Vert \mathbf {u}_k \Vert&\le \Vert \mathbf {b}_{k} \Vert +\Vert \mathbf {b}_{m+1} \Vert \Vert \mathbf {e} \Vert \Vert \mathbf {b}_k \Vert \\&=\sqrt{5}(1+\Vert \mathbf {e} \Vert ) \end{aligned}$$

Note that $\left| \widehat{\mathbf {e}}^\intercal \mathbf {b}_k\right| \le \Vert \mathbf {e} \Vert \Vert \mathbf {b}_k \Vert$ since the last coefficient of $\mathbf {b}_k$ is 0. Finally we obtain $\lambda _m(\mathcal {L})\le \max _{k \le m}\Vert \mathbf {u}_k \Vert \le \sqrt{5} (1+\Vert \mathbf {e} \Vert )$ and the result.    $\square$

The final proof of Lemma 3.1 will necessitate a call to the leftover hash lemma, so before continuing we analyze the min-entropy of $\mathbf {x}\leftarrow \mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) +\mathbf {c}, r}$.

Lemma 3.8

Let $\varepsilon > 0$, $r\ge \eta _{\varepsilon }\left( \varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) \right)$. For any $\mathbf {c}\in \mathbb {R}^m$, we have

$$H_{\infty }\left( \mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) +\mathbf {c},r}\right) \ge \log \left( 1-\varepsilon \right) + m\log \left( r\right) -m.$$

Proof

For any $\mathbf {v}\in \varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) +\mathbf {c}$

The lattice $\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right)$ is generated by the basis $\mathbf {I}_n \otimes \overline{\mathbf {B}}$, with $\overline{\mathbf {B}}$ defined as above, which has determinant $\left( 2^{\log q}\right) ^n = 2^m$. The result follows:

$$H_{\infty }\left( \mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) +\mathbf {c},r}\right) \ge \log \left( 1-\varepsilon \right) + m\log \left( r\right) -m$$

   $\square$

We are now ready to prove Lemma 3.1.

Proof

The proof is done in two steps. First, by Lemma 3.8, we know that $\mathbf {x}$ has min entropy at least $\log (1-\varepsilon )+m\log (r)-m \ge (n+1)\log (q)-2\log (\varepsilon ')-2$. Moreover, $\mathbf {e}^\intercal \mathbf {x}+y$ is in $\mathbb {Z}_q$. Applying the leftover hash lemma 3.5, we obtain

$$ \varDelta \left( \left( \mathbf {A}, \mathbf {A}\mathbf {x}, \mathbf {e}^\intercal \mathbf {x}+ y \right) ,\left( \mathbf {A},\mathbf {u},\mathbf {e}^\intercal \mathbf {x}+ y\right) \right) < \varepsilon ' $$

where $\mathbf {u}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{n-1}$. Now, using Lemma 3.6, we know that

$$ \varDelta \left( \mathbf {e}^\intercal \mathbf {x}+y,e'\right) < 2\varepsilon $$

Summing the two statistical distances concludes the proof.    $\square$

3.3 Rerandomizing LWE samples

We finally describe a simple application of Lemma 3.1. Generating fresh LWE samples for a fixed secret $\mathbf {s}$ from a bounded number of samples is very useful, for example to build a public key encryption scheme from a symmetric one. It has already been shown in the succession of papers [Reg05, GPV08, ACPS09] that multiplying a matrix of m LWE samples $(\mathbf {A},\mathbf {s}^\intercal \mathbf {A}+\mathbf {e}^\intercal )$ by a discrete Gaussian $\mathbf {x}\leftarrow \mathcal {D}_{\mathbb {Z}^m,r}$ and adding another Gaussian term $y \leftarrow \mathcal {D}_{\mathbb {Z}, r}$ to the error part yields a fresh LWE sample $(\mathbf {a}',\mathbf {s}^\intercal \mathbf {a}'+e')$ with a somewhat larger Gaussian noise $e'$. Here we have shown that picking $\mathbf {x}$ according to a discrete Gaussian distribution over a coset $\mathbf {c}$ of $\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right)$ is enough for this rerandomization process. Moreover, we show that the distribution of the final error is independent of the coset $\mathbf {c}$, which will come in handy for hiding homomorphic evaluations. We note that this could be extended to any other lattice with a small public basis (see the last paragraph of Sect. 5), but we mainly focus on $\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right)$ because this is sufficient for our use.

4 Basic GSW Cryptosystem

In this section, we present the Homomorphic Encryption scheme introduced by [GSW13], with notation inspired by [AP14]. We defer setting the parameters to Sect. 5.3. The scheme is composed of the following algorithms:

• $\mathsf {Setup}\left( 1^\lambda \right)$: samples $\bar{\mathbf {s}}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{n-1}$ and returns the secret key $\mathbf {s}=\begin{pmatrix} -\bar{\mathbf {s}}, 1\end{pmatrix} \in \mathbb {Z}_q^n$.

• $\mathsf {Encrypt}(\mathbf {s},\mu )$: given the secret key $\mathbf {s}= \begin{pmatrix} -\bar{\mathbf {s}}, 1\end{pmatrix}$ and a message $\mu \in \left\{ 0,1\right\}$, samples a matrix $\mathbf {A}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{\left( n-1\right) \times m}$ and $\mathbf {e}\leftarrow \mathcal {D}_{\mathbb {Z}^m,\alpha }$. The algorithm then returns $\mathbf {C}= \begin{pmatrix} \mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+ \mathbf {e}^\intercal \end{pmatrix} + \mu \, \mathbf {G}\in \mathbb {Z}_q^{n \times m}$ as the ciphertext. Notice that $\mathbf {s}^ \intercal \mathbf {C}= \mathbf {e}^\intercal + \mu \mathbf {s}^\intercal \mathbf {G}$, the last column of which is close to $\mu \, \frac{q}{2}$.

• $\mathsf {Decrypt}(\mathbf {s}, \mathbf {C})$: given a ciphertext $\mathbf {C}$ and the secret key $\mathbf {s}$, computes the inner product of $\mathbf {s}^\intercal$ and the last column of $\mathbf {C}$, and finally returns 0 if the norm of the result is smaller than $\frac{q}{4}$, otherwise it returns 1.

We omit the original $\mathsf {Eval}$ algorithm since our modified version, which guarantees circuit privacy, is presented in Sect. 5.1.

The IND-CPA security of this scheme comes directly from [GSW13] and the LWE assumption.

In order to shorten several formulas in the rest of the paper, we slightly abuse the notation and define a modified version of the encryption algorithm $\mathsf {Encrypt}_{\gamma }(\mathbf {s},\mu )$, which is exactly the same as the previously defined $\mathsf {Encrypt}(\mathbf {s},\mu )$, except that $\mathbf {e}\leftarrow \mathcal {D}_{\mathbb {Z}^m, \gamma }$. We implicitly use $\mathsf {Encrypt}(\mathbf {s},\mu )$ to denote $\mathsf {Encrypt}_{\alpha }(\mathbf {s},\mu )$.

Extension to Public Key Setting. This scheme can be easily adapted to the public key setting. We now describe $\mathsf {Setup_{pub}}$ and $\mathsf {Encrypt_{pub}}$, as the other algorithms are identical to the private key setting.

• $\mathsf {Setup_{pub}}\left( 1^\lambda \right)$: given the security parameter $\lambda$, samples $\bar{\mathbf {s}}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{n-1}$, $\mathbf {A}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{\left( n-1\right) \times m}$, $\mathbf {e}\leftarrow \mathcal {D}_{\mathbb {Z}^m,\alpha }$. The algorithm returns the secret key $\mathbf {s}=\begin{pmatrix} -\bar{\mathbf {s}}, 1\end{pmatrix} \in \mathbb {Z}_q^n$ and the public key $\widehat{\mathbf {A}}=\begin{pmatrix} \mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+ \mathbf {e}^\intercal \end{pmatrix}$.

• $\mathsf {Encrypt_{pub}}\left( \widehat{\mathbf {A}},\mu \right)$: given the public key $\widehat{\mathbf {A}}$ and a message $\mu \in \left\{ 0,1\right\}$, samples a matrix $\mathbf {R}\mathop {\leftarrow }\limits ^{\$}\left\{ -1,0,1\right\} ^{m \times m}$. The algorithm then sets $\mathbf {C}= \widehat{\mathbf {A}}\mathbf {R}+ \mu \, \mathbf {G}$ and returns $\mathbf {C}\in \mathbb {Z}_q^{n \times m}$ as the ciphertext. Notice that $\mathbf {s}^ \intercal \mathbf {C}= \mathbf {e}^\intercal \mathbf {R}+ \mu \mathbf {s}^\intercal \mathbf {G}$ the last column of which is close to $\mu \, \frac{q}{2}$.

Basic Homomorphic Operations. The homomorphic operations are done as follows:

• $\mathsf {Homomorphic \; addition}$: $\mathbf {C}_1 \boxplus \mathbf {C}_2=\mathbf {C}_1+\mathbf {C}_2$

• $\mathsf {Homomorphic \; multiplication}$: $\mathbf {C}_1 \boxdot \mathbf {C}_2 \leftarrow \mathbf {C}_1\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}_2\right)$

where the $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ algorithm is the randomized bit decomposition described in Definition 2.1.

From now on and for readability, we will assume a correct choice of parameters has been made. This setting is discussed in Sect. 5.3.

4.1 Rerandomizing and Scaling GSW Ciphertexts

Here we describe our new technique to rerandomize GSW ciphertexts. This method allows the scaling of GSW ciphertexts, which will be used in our circuit evaluation procedure.

We recall the form of a GSW ciphertext

$$ \mathbf {C}= \begin{pmatrix}\mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+\mathbf {e}^\intercal \end{pmatrix}+\mu \mathbf {G}$$

Using the rerandomization of LWE samples presented in Sect. 3, it is possible to generate a fresh encryption of 0 by computing $\mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}\right)$, where $\mathbf {C}$ is an encryption of 0 and $\mathbf {V}$ is any matrix in $\mathbb {Z}_q^{n \times m}$.

Lemma 4.1

Let $r> 0$. For any $\mathbf {V}\in \mathbb {Z}_q^{n\times m}$, if $r= \varOmega \left( \alpha \sqrt{\lambda \, m \log m}\right)$, with $\alpha$ being the Gaussian parameter of fresh encryptions, then

$$ \left( \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}\right) +\begin{pmatrix}\mathbf {0} \\ \mathbf {y}^\intercal \end{pmatrix}, \mathbf {C}\right) \approx _{s}\left( \mathbf {C}',\mathbf {C}\right) $$

where $\mathbf {C}=\begin{pmatrix}\mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+\mathbf {e}^\intercal \end{pmatrix} \leftarrow \mathsf {Encrypt}\left( \mathbf {s}, 0\right)$, $\mathbf {C}'\leftarrow \mathsf {Encrypt}_{\gamma }\left( \mathbf {s}, 0\right)$, with $\gamma =r\sqrt{ 1+\Vert \mathbf {e} \Vert ^2}$.

Proof

Fix $\mathbf {v}\in \mathbb {Z}_q^m$ and $\mathbf {e}$ such that $\Vert \mathbf {e} \Vert \le C\alpha \sqrt{m}$, where C is as in Lemma 2.4. Then by applying Lemma 3.1 with $r= \varOmega \left( \alpha \sqrt{\lambda \, m \log m}\right)$ and $\varepsilon '=\varepsilon = 2^{-\lambda }$ we have

$$ \varDelta \left( \left( \mathbf {A}, \mathbf {A}\mathbf {x}, \mathbf {e}^\intercal \mathbf {x}+ y \right) ,\left( \mathbf {A},\mathbf {u},e'\right) \right) < 3\cdot 2^{-\lambda } $$

where $\mathbf {A}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{(n-1)\times m}$, $\mathbf {x}\leftarrow \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right)$ and $y \leftarrow \mathcal {D}_{\mathbb {Z},r}$. From this we obtain that for $\mathbf {e}\leftarrow \mathcal {D}_{\mathbb {Z}^m,\alpha }$:

$$\begin{aligned}&\varDelta \left( \left( \mathbf {A},\mathbf {e}, \mathbf {A}\mathbf {x}, \mathbf {e}^\intercal \mathbf {x}+ y \right) ,\left( \mathbf {A},\mathbf {e},\mathbf {u},e'\right) \right) \\&= \sum _{\mathbf {w}\in \mathbb {Z}^m}\varDelta \left( \left( \mathbf {A}, \mathbf {A}\mathbf {x}, \mathbf {w}^\intercal \mathbf {x}+ y \right) ,\left( \mathbf {A},\mathbf {u},w'\right) \right) \cdot \Pr \left[ \mathbf {e}=\mathbf {w}\right] \\&\le \sum _{\Vert \mathbf {w} \Vert <C\alpha \sqrt{m}} 3\cdot 2^{-\lambda }\Pr \left[ \mathbf {e}=\mathbf {w}\right] + \sum _{\Vert \mathbf {w} \Vert \ge C\alpha \sqrt{m}}\Pr \left[ \mathbf {e}=\mathbf {w}\right] \\&\le 3\cdot 2^{-\lambda } + \Pr \left[ \Vert \mathbf {e} \Vert \ge C\alpha \sqrt{m}\right] \\&\le 3\cdot 2^{-\lambda } + 2^{-\varOmega {(\lambda )}} \end{aligned}$$

In the left operand of the third equation we bound the statistical distance by $3\cdot 2^{-\lambda }$ and in the right operand we bound it by 1. To obtain the last inequality we use Lemma 2.4 and have $\Pr {\left[ \Vert \mathbf {e} \Vert >C\alpha \sqrt{m}\right] } \le 2^{-\varOmega (m)} \le 2^{-\varOmega (\lambda )}$ since $m\ge \lambda$. By rewriting this distance we have for any $\mathbf {v}\in \mathbb {Z}_q^m$

$$ \left( \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}\right) +\begin{pmatrix}\mathbf {0} \\ y \end{pmatrix},\mathbf {C}\right) \approx _{s}\left( \begin{pmatrix}\mathbf {u}\\ \bar{\mathbf {s}}^\intercal \mathbf {u}+e'\end{pmatrix},\mathbf {C}\right) $$

By writing $\mathbf {V}= (\mathbf {v}_1 \mid \ldots \mid \mathbf {v}_{m})$ and $\mathbf {y}= \left( y_1,\ldots , y_{m}\right)$, we have

$$ \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}\right) +\begin{pmatrix}\mathbf {0} \\ \mathbf {y}^\intercal \end{pmatrix}= \left( \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}_1\right) +\begin{pmatrix}\mathbf {0} \\ y_1 \end{pmatrix} \mid \ldots \mid \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}_m\right) +\begin{pmatrix}\mathbf {0} \\ y_m \end{pmatrix}\right) $$

We define the distributions $\left( D_i\right) _{0\le i \le m}$ in which the first i columns of $\mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}\right) +\begin{pmatrix}\mathbf {0} \\ \mathbf {y}^\intercal \end{pmatrix}$ are replaced with “fresh” $\begin{pmatrix}\mathbf {u}\\ \bar{\mathbf {s}}^\intercal \mathbf {u}+e'\end{pmatrix}$ and we obtain through a hybrid argument that

$$ \varDelta \left( \left( \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}\right) +\begin{pmatrix}\mathbf {0} \\ \mathbf {y}^\intercal \end{pmatrix},\mathbf {C}\right) , \left( \begin{pmatrix}\mathbf {A}' \\ \bar{\mathbf {s}}^\intercal \mathbf {A}'+\mathbf {e}'^\intercal \end{pmatrix},\mathbf {C}\right) \right) \le m (3\cdot 2^{-\lambda }+2^{-\varOmega (\lambda )}) $$

   $\square$

As a direct corollary we remark that the scaling of a GSW encryption $\mathbf {C}$ of $\mu$ by a bit a, defined as $\mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( a\cdot \mathbf {G}\right) +\begin{pmatrix}\mathbf {0} \\ \mathbf {y}^\intercal \end{pmatrix}$, where $\mathbf {y}\leftarrow \mathcal {D}_{\mathbb {Z}^m,r}$, does not depend on a, but only on $a\mu$.

5 Our Scheme: Circuit-Private Homomorphic Evaluation for GSW

In this section, we prove that a slight modification of the GSW encryption scheme is enough to guarantee circuit privacy, i.e. that an evaluation of any branching program does not reveal anything more than the result of the computation and the length of the branching program, as long as the secret key holder is honest.

First, we state our definition of circuit privacy, similar to [IP07, Definition 7], which is stronger than the one given in [Gen09, Definition 2.1.6] in the sense that it is simulation based, but weaker in the sense that we leak information about the length of the branching program.

Definition 5.1

(Simulation-based circuit privacy). We say that a homomorphic encryption scheme $\mathcal {E}$ is circuit private if there exists a PPT algorithm $\mathsf {Sim}$ such that for any branching program $\varPi$ of length $L={{\mathrm{poly}}}\left( \lambda \right)$ on $\ell$ variables, any $x_1, \ldots , x_\ell \in \left\{ 0,1\right\}$, the following holds:

$$\begin{aligned}&\left( \mathcal {E}.\mathsf {Eval}\left( evk, \varPi , \left( \mathbf {C}_1, \ldots , \mathbf {C}_\ell \right) \right) , \mathbf {C}_1,\ldots ,\mathbf {C}_\ell ,1^\lambda ,\mathbf {s}\right) \\ \approx _{s}\;&\left( \mathsf {Sim}\left( 1^\lambda , \varPi \left( x_1, \ldots , x_\ell \right) , 1^L, \left( \mathbf {C}_1, \ldots , \mathbf {C}_\ell \right) \right) ,\mathbf {C}_1,\ldots ,\mathbf {C}_\ell ,1^\lambda ,\mathbf {s}\right) \end{aligned}$$

where $\mathbf {s}\leftarrow \mathcal {E}.\mathsf {Setup}\left( 1^\lambda \right)$, $\mathbf {C}_i\leftarrow \mathcal {E}.\mathsf {Encrypt}(\mathbf {s},x_i)$ for $i \in [\ell ]$.

We can now state our main theorem:

Theorem 5.2

(Main theorem). There exists a fully homomorphic encryption scheme for branching programs that is circuit private and whose security is based on the LWE assumption with polynomial noise-to-modulus ratio.

Remark 2

The aforementioned scheme is also multi-hop (see definition in [GHV10]) for branching programs, as long as the noise does not grow beyond q / 4. This means that the output of an evaluation can be used as input for further computation, while the property of circuit privacy is maintained for every hop. More in detail, the evaluation can be carried out by multiple parties and any subset of these parties is not able to gain information about the branching program applied by an evaluator which is not in the subset, beside its length, input and output, even given access to the secret key.

5.1 Homomorphic Evaluation for Branching Programs

We first recall the branching program evaluation algorithm given in [BV14] and describe our modified version.

Permutation Branching Programs. A permutation branching program $\varPi$ of length L and width W with input space $\left\{ 0,1\right\} ^\ell$ is a sequence of L tuples of the form $\bigl (\text {var}\left( t\right) , \pi _{t, 0}, \pi _{t, 1}\bigr )$ where

• $\text {var}\ :\ \left[ L\right] \rightarrow \left[ \ell \right]$ is a function that associates the t-th tuple with an input bit $x_{\text {var}\left( t\right) }$

• $\pi _{t, 0},\pi _{t, 1}: \left[ W\right] \rightarrow \left[ W\right]$ are permutations that dictate the t-th step of the computation.

On input $\left( x_1, \ldots , x_\ell \right)$, $\varPi$ outputs 1 iff

$$ \pi _{L, {x_{\text {var}\left( L\right) }}}(\cdots (\pi _{1, {x_{\text {var}\left( 1\right) }}}(1)) \cdots )= 1. $$

Following [BV14, IP07], we will evaluate $\varPi$ recursively as follows. We associate each $t \in [L]$ with the characteristic vector $\mathbf {v}_t \in \left\{ 0,1\right\} ^W$ of the current “state”, starting with $\mathbf {v}_0 = (1,0,\ldots ,0)$. We can then compute the w-th entry of $\mathbf {v}_t$ (denoted by $\mathbf {v}_t\left[ w\right]$) as follows: for all $t \in [L], w \in [W]$,

$$\begin{aligned} \mathbf {v}_t\left[ w\right]&= \mathbf {v}_{t-1}\left[ \pi _{t, x_{\text {var}\left( t\right) }}^{-1}\left( w\right) \right] \nonumber \\&=x_{\text {var}\left( t\right) }\cdot \mathbf {v}_{t-1}\left[ \pi _{t, 1}^{-1}\left( w\right) \right] + \left( 1-x_{\text {var}\left( t\right) }\right) \cdot \mathbf {v}_{t-1} \left[ \pi _{t, 0}^{-1}\left( w\right) \right] . \end{aligned}$$

(5.1)

Our Branching Program Evaluation. Here we present our $\mathsf {Eval}\left( \varPi , \left( \mathbf {C}_1,\ldots , \mathbf {C}_\ell \right) \right)$ algorithm (note that it does not require any evaluation key), which homomorphically evaluates a branching program $\varPi$ over ciphertexts $\mathbf {C}_1,\ldots ,\mathbf {C}_\ell$. The first state vector is encrypted without noise: the initial encrypted state vector is $\mathbf {V}_0 = \left( \mathbf {G}, \mathbf {0}, \ldots , \mathbf {0}\right)$, i.e. $\mathbf {V}_0[1] = \mathbf {G}$ and $\mathbf {V}_0[w] = \mathbf {0}$, for $2 \le w \le W$. Note that $\mathbf {G}$ and $\mathbf {0}$ are noiseless encryptions of 1 and 0, respectively. The encrypted state vector is then computed at each step by homomorphically applying (5.1) and adding a noise term: for $t \in \left[ L\right]$ and $w \in \left[ W\right]$

(5.2)

where $\mathbf {\mathbf {y}}_{t,w} \leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$. The output of the evaluation algorithm is $\mathbf {V}_L[0] \in \mathbb {Z}_q^{n \times m}$.

Remark 3

(Comparison with [BV14, AP14]. Cf. also Table 1 ). The differences between our homomorphic evaluation procedure and the previous ones are as follows:

• We added an additional Gaussian noise to the computation, as captured in the boxed term;

• [BV14] uses the deterministic $\mathbf {G}^{-1}_{\text {det}}\left( \cdot \right)$ whereas [AP14] introduced the randomized $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ for efficiency. Here, we crucially exploit the randomized $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ for privacy.

Simulator. Towards proving circuit privacy, we need to specify a simulator $\mathsf {Sim}$. We first describe a simulator that is given access to the number of times each variable is used and prove that its output distribution is statistically close to the result of $\mathsf {Eval}$ (Lemma 5.5). We can then pad the branching program so that each variable is used the same number of times. Given the security parameter $\lambda$, the length L of the branching program $\varPi$, the number of times $\tau _i$ that $\varPi$ uses the i-th variable, the final value $x_f$ of the evaluation of $\varPi$ on input $(x_1,\ldots ,x_\ell )$, the ciphertexts $\mathbf {C}_i$ encrypting $x_i$ for $i \in [\ell ]$, $\mathsf {Sim}$ mimics the way error grows in the states of $\mathsf {Eval}$ by doing $\tau _i$ dummy steps of computation with the i-th variable. This gives a new encryption $\widehat{\mathbf {A}}_f$ of 0 with the same noise distribution as the ciphertext output by the $\mathsf {Eval}$ procedure. $\mathsf {Sim}$ then adds the message part $x_f$ to this ciphertext and outputs $\mathbf {C}_f=\widehat{\mathbf {A}}_f+x_f\mathbf {G}$.

In other words,

$$\begin{aligned}&\mathsf {Sim}\left( 1^\lambda ,x_f,\left( 1^{\tau _1},\ldots ,1^{\tau _\ell }\right) , \left( \mathbf {C}_1,\ldots ,\mathbf {C}_\ell \right) \right) \\&\leftarrow \sum _{i=1}^\ell \sum _{t=1}^{\tau _i} \Bigg (\mathbf {C}_{i} \cdot \left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right) \right) + \begin{pmatrix} \mathbf {0} \\ \mathbf {\mathbf {y}}^\intercal _t\end{pmatrix}\Bigg ) + x_f \mathbf {G}\end{aligned}$$

where $\mathbf {\mathbf {y}}_t\leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$ for $t \in [L]$.

We note that the sum of $2\tau _i$ samples $\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right)$ can be sampled at once using the $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ algorithm with a larger parameter $r\sqrt{2\tau _i}$, and the sum of $\tau _i$ samples from $\mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$ is close to a sample from $\mathcal {D}_{\mathbb {Z}^m,r\sqrt{2\tau _i}}$.

5.2 Proof of Circuit Privacy

We proceed to establish circuit privacy in two steps. We first analyze how the ciphertext distribution changes in a single transition, and then proceed by induction to reason about homomorphic evaluation of the entire branching program.

Step 1. We begin with the following lemma, which is useful for analyzing the output of (5.2). Roughly speaking, this lemma says that if at step t, the state vector consists of fresh GSW encryptions with some noise parameter $\zeta$, then at step $t+1$, the state vector is statistically close to fresh GSW encryptions with a somewhat larger noise which depends on the error in the input ciphertext and on $\zeta$.

Lemma 5.3

For any $x, v_0, v_1 \in \left\{ 0,1\right\}$ and $\mathbf {s}=\begin{pmatrix} -\bar{\mathbf {s}}, 1\end{pmatrix} \leftarrow \mathsf {Setup}\left( 1^\lambda \right)$, the following holds:

$$ \left( \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) + \left( \mathbf {G}- \mathbf {C}\right) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}^\intercal \end{pmatrix}, \mathbf {C}\right) \approx _{s}\left( \mathbf {V}'_x, \mathbf {C}\right) $$

where $\mathbf {V}_b\leftarrow \mathsf {Encrypt}_{\gamma }\left( \mathbf {s}, v_b\right)$ for $b\in \left\{ 0,1\right\}$, $\mathbf {C}= \begin{pmatrix}\mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+ \mathbf {e}^\intercal \end{pmatrix} + x\mathbf {G}\leftarrow \mathsf {Encrypt}\left( \mathbf {s}, x\right)$, $\mathbf {\mathbf {y}}\leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$ and $\mathbf {V}'_x \leftarrow \mathsf {Encrypt}_{\zeta }\left( \mathbf {s}, v_x\right)$, with $\zeta = \sqrt{\gamma ^2+2r^2(1+\Vert \mathbf {e} \Vert ^2)}$.

Proof

We begin with a simple identity which is useful in the remainder of the proof:

$$ \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) + (\mathbf {G}- \mathbf {C}) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) = \widehat{\mathbf {A}}\cdot \left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) -\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) \right) + \mathbf {V}_x $$

where $\widehat{\mathbf {A}}= \begin{pmatrix}\mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+ \mathbf {e}^\intercal \end{pmatrix}$ and $\mathbf {V}_0, \mathbf {V}_1, \mathbf {C}$ are as defined in the statement of the Lemma. Showing this identity is correct just requires performing the calculations:

$$\begin{aligned}&\ \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) + (\mathbf {G}- \mathbf {C}) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) \\ =&\left( \widehat{\mathbf {A}}+ x\mathbf {G}\right) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) + \left( \left( 1-x\right) \mathbf {G}- \widehat{\mathbf {A}}\right) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) \\ =&\ \widehat{\mathbf {A}}\cdot \left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) \right) + x \mathbf {V}_1 + \left( 1-x\right) \mathbf {V}_0 \\ =&\ \widehat{\mathbf {A}}\cdot \left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) \right) + \mathbf {V}_x \end{aligned}$$

Then we observe that by applying Lemma 2.3 we have

$$\begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}^\intercal \end{pmatrix} \approx _{s}\begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}_{1}^\intercal \end{pmatrix}-\begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}_{0}^\intercal \end{pmatrix}$$

where $\mathbf {y}_b \leftarrow \mathcal {D}_{\mathbb {Z}^m,r}, b\in \left\{ 0,1\right\}$. Lemma 4.1 also gives

$$ \left( \widehat{\mathbf {A}}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_b\right) + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}_b^\intercal \end{pmatrix} , \mathbf {C}\right) \approx _{s}\left( \mathbf {C}_b,\mathbf {C}\right) $$

where $\mathbf {C}_b \leftarrow \mathsf {Encrypt}_{\zeta '}(\mathbf {s},0)$, for $b\in \left\{ 0,1\right\}$, with $\zeta ' = r\sqrt{1+\Vert \mathbf {e} \Vert ^2}$. We now have

$$\left( \mathbf {C}\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_1\right) + (\mathbf {G}- \mathbf {C}) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_0\right) + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}^\intercal \end{pmatrix}, \mathbf {C}\right) \approx _{s}\left( \mathbf {C}_1-\mathbf {C}_0+\mathbf {V}_x,\mathbf {C}\right) $$

By additivity of variance on independent variables, we obtain that $\mathbf {C}_1-\mathbf {C}_0+\mathbf {V}_x = \mathbf {V}'_x$ looks like a fresh encryption of $0-0+v_x=v_x$ with parameter $\sqrt{\gamma ^2+2r^2(1+\Vert \mathbf {e} \Vert ^2)}$.    $\square$

Step 2. We now prove that, at each step of the evaluation, each entry of the encrypted state $\mathbf {V}_t$ looks like a fresh GSW encryption of the corresponding entry of the state $\mathbf {v}_t$, even given the GSW encryptions of the input bits, except for a small correlation in the noise.

Lemma 5.4

(Distribution of the result of $\mathsf {Eval}$ ). For any branching program $\varPi$ of length L on $\ell$ variables, we define $\tau _{t,i}$ to be the number of times the i-th variable has been used after t steps of the evaluation, i.e. $\tau _{t,i}=\left| \text {var}^{-1}\left( i\right) \cap \left[ t\right] \right|$, for i in $\left[ \ell \right]$ and $t \in \left[ L\right]$.

For any $x_1,\ldots ,x_\ell \in \left\{ 0,1\right\}$, any $\mathbf {s}=\begin{pmatrix} -\bar{\mathbf {s}}, 1\end{pmatrix} \leftarrow \mathsf {Setup}\left( 1^\lambda \right)$, at each step $t \in [L]$, for all indexes $w \in [W]$, the following holds:

$$ \left( \mathbf {V}_t\left[ w\right] , (\mathbf {C}_i)_{i\in [\ell ]}\right) \approx _{s}\left( \mathbf {C}_{t,w}',(\mathbf {C}_i)_{i\in [\ell ]}\right) $$

where $\mathbf {C}_i= \begin{pmatrix} \mathbf {A}_i \\ \bar{\mathbf {s}}^\intercal \mathbf {A}_i + \mathbf {e}_i^\intercal \end{pmatrix} + x_i\mathbf {G}\leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$ for $i\in [\ell ]$, $\mathbf {C}'_{t,w} \leftarrow \mathsf {Encrypt}_{r_t}\left( \mathbf {s},\mathbf {v}_t\left[ w\right] \right)$ for $(t,w)\in [L]\times [W]$ and $r_{t}=r\sqrt{2\sum _{i=1}^\ell \tau _{t,i}\left( 1+\Vert \mathbf {e}_i \Vert ^2\right) }$.

Proof

We prove this lemma by induction on $t \in [L]$. At step $t>1$, for index $w\in \left[ W\right]$ we use a series of hybrid distributions $\mathcal {H}_{t,w,k}$ for $0 \le k \le 2$ to prove that $\left( \mathbf {V}_t\left[ w\right] , (\mathbf {C}_i)_{i\in [\ell ]}\right) \approx _{s}\left( \mathbf {C}'_{t,w}, (\mathbf {C}_i)_{i\in [\ell ]}\right)$. In particular $\mathcal {H}_{t,w,0} = \left( \mathbf {V}_t \left[ w\right] ,(\mathbf {C}_i)_{i\in [\ell ]}\right)$, and $\mathcal {H}_{t,w,2} = \left( \mathbf {C}'_{t,w},(\mathbf {C}_i)_{i\in [\ell ]}\right)$.

Hybrid $\varvec{\mathcal {H}_{t,w,0}}$ . Let $w_b=\pi _{t, b}^{-1}\left( w\right)$ for $b\in \left\{ 0,1\right\}$. We write $w_\beta$ to denote $w_{x_{\text {var}(t)}}$, i.e. $w_0$ or $w_1$, depending on the value of the variable which is used at time t.

$$\begin{aligned} \mathcal {H}_{t,w,0}&= \left( \mathbf {V}_t\left[ w\right] ,(\mathbf {C}_i)_{i\in [\ell ]}\right) \\&= \Bigg (\mathbf {C}_{\text {var}\left( t\right) }\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{t-1} \left[ w_1\right] \right) + \left( \mathbf {G}- \mathbf {C}_{\text {var}\left( t\right) }\right) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{t-1} \left[ w_0\right] \right) \\&\qquad + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}_{t,w}^\intercal \end{pmatrix},(\mathbf {C}_i)_{i\in [\ell ]}\Bigg ) \end{aligned}$$

where $\mathbf {C}_i\leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$ and $\mathbf {y}_{t,w} \leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$.

Hybrid $\varvec{\mathcal {H}_{t,w,1}}$ . We set

$$\begin{aligned} \mathcal {H}_{t,w,1}&= \Bigg (\mathbf {C}_{\text {var}\left( t\right) }\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}_ {t-1,w_1}'\right) + \left( \mathbf {G}- \mathbf {C}_{\text {var}\left( t\right) }\right) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}_ {t-1,w_0}'\right) \\&\qquad + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}_{t,w}^\intercal \end{pmatrix},(\mathbf {C}_i)_{i\in [\ell ]}\Bigg ) \end{aligned}$$

where $\mathbf {C}_i\leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$, $\mathbf {y}_{t,w} \leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$ and $\mathbf {C}'_{t-1,w_b} \leftarrow \mathsf {Encrypt}_{r_{t-1}}(\mathbf {s},\mathbf {v}_{t-1}[w_b])$ for $b\in \left\{ 0,1\right\}$.

By induction hypothesis we have $\mathcal {H}_{t-1,w_{b},0}\approx _{s}\mathcal {H}_{t-1,w_{b},2}$ for $b\in \left\{ 0,1\right\}$, i.e.

$$\left( \mathbf {V}_{t-1}\left[ w_{b}\right] ,(\mathbf {C}_i)_{i\in [\ell ]}\right) \approx _{s}\left( \mathbf {C}'_{t-1,w_{b}},(\mathbf {C}_i)_{i \in [\ell ]}\right) $$

where $\mathbf {C}_i\leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$ and $\mathbf {C}'_{t-1,w_b} \leftarrow \mathsf {Encrypt}_{r_{t-1}}(\mathbf {s},\mathbf {v}_{t-1}[w_b])$ for $b\in \left\{ 0,1\right\}$.

We use the fact that applying a function to two distributions does not increase their statistical distance to obtain $\mathcal {H}_{t,w,0}\approx _{s}\mathcal {H}_{t,w,1}$.

Hybrid $\varvec{\mathcal {H}_{t,w,2}}$ . Let

$$ \mathcal {H}_{t,w,2}=\left( \mathbf {C}',(\mathbf {C}_i)_{i \in [\ell ]}\right) $$

with $\mathbf {C}_i\leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$, $\mathbf {C}'\leftarrow \mathsf {Encrypt}_{\zeta }(\mathbf {s},\mathbf {v}_{t-1}[w_\beta ])$ and $\zeta = \sqrt{r_{t-1}^2+2r^2\left( 1+\Vert \mathbf {e}_{\text {var}(t)} \Vert ^2\right) }$.

By Lemma 5.3 we have:

$$\begin{aligned}&\Bigg (\mathbf {C}_{\text {var}\left( t\right) }\cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}_{t-1,w_1}'\right) + \left( \mathbf {G}- \mathbf {C}_{\text {var}\left( t\right) }\right) \cdot \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {C}_ {t-1,w_0}'\right) \\&\quad + \begin{pmatrix}\mathbf {0}\\ \mathbf {\mathbf {y}}_{t,w}^\intercal \end{pmatrix},(\mathbf {C}_i)_{i\in [\ell ]}\Bigg ) \approx _{s}\left( \mathbf {C}',(\mathbf {C}_i)_{i\in [\ell ]}\right) \end{aligned}$$

where $\mathbf {C}_i\leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$, $\mathbf {y}_{t,w} \leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{2}}$, $\mathbf {C}'_{t-1,w_b} \leftarrow \mathsf {Encrypt}_{r_{t-1}}(\mathbf {s},\mathbf {v}_{t-1}[w_b])$ for $b\in \left\{ 0,1\right\}$ and $\mathbf {C}'\leftarrow \mathsf {Encrypt}_{\zeta }(\mathbf {s},\mathbf {v}_{t-1} [w_\beta ])$. Note that $\mathbf {v}_{t-1}[w_\beta ]=\mathbf {v}_t[w]$ and $r_t= \sqrt{r_{t-1}^2+2r^2\left( 1+ \Vert \mathbf {e}_{\text {var}(t)} \Vert ^2\right) } = \zeta$ from which we have that $\mathbf {C}'$ and $\mathbf {C}_{t,w}'$ are identically distributed, and directly $\mathcal {H}_{t,w,1}\approx _{s}\mathcal {H}_{t,w,2}$.

We note that this recursive formula does not apply to step $t=0$, we thus use $t=1, w\in \left[ W\right]$ as the base case. We only describe the steps that differ from the case $t>1$.

Hybrid $\varvec{\mathcal {H}_{1,w,1}}$ . We have $\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{0} \left[ w_b\right] \right) =\mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {v}_{0}\left[ w_b\right] \cdot \mathbf {G}\right)$ for $b\in \left\{ 0,1\right\}$. Notice that we now have exactly $\mathcal {H}_{1,w,1} = \mathcal {H}_{1,w,0}$.

Hybrids $\varvec{\mathcal {H}_{1,w,2}}$ . The proof for $\mathcal {H}_{1,w,1}\approx _{s}\mathcal {H}_{1,w,2}$ is identical to the one of Lemma 5.3 except for the fact that the ciphertext $\mathbf {V}_x$ from the proof is now of the form $\mathbf {v}_0[w_\beta ] \mathbf {G}$. The resulting ciphertext $\mathbf {C}'_{1,w}$ is now only the sum of two encryptions of 0 and $\mathbf {v}_0[w_\beta ]$ and has a Gaussian parameter $r\sqrt{2\left( 1+ \Vert \mathbf {e}_{\text {var}(1)} \Vert ^2\right) }=r_1$. This implies $\mathcal {H}_{1,w,1} \approx _{s}\mathcal {H}_{1,w,2}$.    $\square$

We now proceed to prove circuit privacy. We will first prove the following lemma, which states that the $\mathsf {Eval}$ algorithm presented in Sect. 5.1 only leaks the final result of the evaluation and the number of times each variable is used.

Lemma 5.5

Let $\mathcal {E}$ be the scheme defined in Sect. 4 with evaluation defined as in this section, and $\mathsf {Sim}$ be the corresponding simulator. Then for any branching program $\varPi$ of length $L={{\mathrm{poly}}}(\lambda )$ on $\ell$ variables, such that the i-th variable is used $\tau _i$ times, and any $x_1,\ldots ,x_\ell \in \left\{ 0,1\right\}$, the following holds:

$$\begin{aligned}&\left( \mathcal {E}.\mathsf {Eval}\left( \varPi ,(\mathbf {C}_1,\ldots ,\mathbf {C}_\ell )\right) ,\mathbf {C}_1, \ldots ,\mathbf {C}_\ell ,1^\lambda ,\mathbf {s}\right) \\ \approx _{s}\;&\left( \mathsf {Sim}\Big (1^\lambda ,\varPi \left( x_1,\ldots ,x_\ell \right) ,(1^{\tau _1}, \ldots ,1^{\tau _\ell }),(\mathbf {C}_1,\ldots ,\mathbf {C}_\ell )\Big ),\mathbf {C}_1,\ldots , \mathbf {C}_\ell ,1^\lambda ,\mathbf {s}\right) \end{aligned}$$

where $\mathbf {s}\leftarrow \mathcal {E}.\mathsf {Setup}\left( 1^\lambda \right)$, $\mathbf {C}_i\leftarrow \mathcal {E}.\mathsf {Encrypt}\left( \mathbf {s},x_i\right)$ for i in $\left[ \ell \right]$.

Proof

As shown in Lemma 5.4, the final result of the homomorphic evaluation of the branching program $\varPi$ is of the form

$$ \mathbf {V}_L\left[ 0\right] \approx _{s}\begin{pmatrix}\mathbf {A}\\ \bar{\mathbf {s}}^\intercal \mathbf {A}+ \mathbf {f}^\intercal \end{pmatrix}+x_f\mathbf {G}$$

where $\mathbf {A}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{\left( n-1\right) \times m}$, $\mathbf {f}\leftarrow \mathcal {D}_{\mathbb {Z}^m,r_L }$ and $r_L=r\sqrt{2\sum _{i=1}^\ell \left( 1+\Vert \mathbf {e}_i \Vert ^2\right) \tau _i}$.

Now we prove that the output of $\mathsf {Sim}$ is statistically close to the same distribution. This proof follows from the fact that scaling GSW ciphertexts yields a result which is independent of the argument of $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$. Let $\mathbf {A}_{i,t},\mathbf {A}'_{i,t}\mathop {\leftarrow }\limits ^{\$}\mathbb {Z}_q^{\left( n-1\right) \times m}$, $\mathbf {f}_{i,f},\mathbf {f}'_{i,t}\leftarrow \mathcal {D}_{\mathbb {Z}^m,r\sqrt{1+\Vert \mathbf {e}_i \Vert }}$, then the joint distribution of the output of $\mathsf {Sim}$ and ciphertexts $(\mathbf {C}_i)_{i\in [\ell ]}$ is

The result is the same as the joint distribution of the output of $\mathsf {Eval}$ and ciphertexts $(\mathbf {C}_i)_{i\in [\ell ]}$, thus concluding the proof.    $\square$

We are now ready to prove Theorem 5.2.

Proof

(Main theorem). Theorem 5.2 follows from Lemma 5.5 by tweaking the $\mathsf {Eval}$ algorithm of $\mathcal {E}$: it is sufficient that this algorithm pads the branching program $\varPi$ so that each variable is used L times. This padding is done by using the identity permutation for all steps after the L-th. After this proof, we discuss more efficient ways to pad branching program evaluations. It is easy to see that this step is enough to reach the desired circuit privacy property: the only information leaked besides the final result is $\tau _i=L$.    $\square$

Padding Branching Program Evaluations. In order to pad a branching program $\varPi$ that uses the i-th variable $\tau _i$ times to one that uses the i-th variable L times, we add $L-\tau _i$ steps, using the identity permutation at each one of these. Given $\mathbf {V}_L\left[ 0\right]$ the final result of the computation, this padding corresponds to steps $t\in \left[ L+1,2L-\tau _i\right]$ defined as follows:

$$ \mathbf {V}_{t}\left[ 0\right] \leftarrow \mathbf {V}_{t-1}\left[ 0\right] +\mathbf {C}_i\left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{t-1}\left[ 0\right] \right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{t-1}\left[ 0\right] \right) \right) + \begin{pmatrix} \mathbf {0} \\ \mathbf {\mathbf {y}}^\intercal _{t,0}\end{pmatrix} $$

Using the same proof as Lemma 5.5 the final output will be

$$\begin{aligned} \mathbf {V}_{2L-\tau _i}\left[ 0\right]&\leftarrow \mathbf {V}_{L}\left[ 0\right] +\mathbf {C}_i \sum _{t=L}^{2L-\tau _i-1}\left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{t}\left[ 0\right] \right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {V}_{t}\left[ 0\right] \right) \right) + \begin{pmatrix} \mathbf {0} \\ \mathbf {\mathbf {y}}^\intercal _{t,0}\end{pmatrix}\\&\approx _{s}\mathbf {V}_{L}\left[ 0\right] +\mathbf {C}_i \sum _{t=L}^{2L-\tau _i-1}\left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right) \right) + \begin{pmatrix} \mathbf {0} \\ \mathbf {\mathbf {y}}^\intercal _{t,0}\end{pmatrix} \end{aligned}$$

Observe that by using Lemma 2.3 we have that

$$\begin{aligned}&\sum _{t=L}^{2L-\tau _i-1}\left( \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right) - \mathbf {G}^{-1}_{\text {rand}}\left( \mathbf {0}\right) \right) \approx _{s}\mathcal {D}_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) ,r_f}\\&\sum _{t=L}^{2L-\tau _i-1} \begin{pmatrix} \mathbf {0} \\ \mathbf {\mathbf {y}}^\intercal _{t,0}\end{pmatrix} \approx _{s}\mathcal {D}_{\mathbb {Z}^m,r_f} \end{aligned}$$

where $r_f=r\sqrt{2 \left( L-\tau _i\right) }$. We can thus do all the steps at once by outputting $\mathbf {V}_L \left[ 0\right] + \mathbf {C}_i \cdot \mathbf {X}+\begin{pmatrix} \mathbf {0} \\ \mathbf {\mathbf {y}}^\intercal _f \end{pmatrix}$, where $\mathbf {X}\leftarrow \mathcal {D}^m_{\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right) ,r_f}$ and $\mathbf {\mathbf {y}}_f\leftarrow \mathcal {D}_{\mathbb {Z}^m,r_f}$. We note that $\mathbf {X}$ can be sampled using the $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ algorithm with parameter $r_f$ instead of $r$.

5.3 Setting the Parameters

In this section we show that, for appropriate values of the parameters, the output of the homomorphic evaluation $\mathbf {V}_L[0]$ decrypts to $\varPi \left( x_1,\ldots ,x_\ell \right)$ with overwhelming probability and guarantees circuit privacy.

We first recall the bounds on the parameters needed for both correctness and privacy. Let $n=\varTheta \left( \lambda \right)$, $q={{\mathrm{poly}}}(n)$, $m=n\log q$, $\alpha$ be the Gaussian parameter of fresh encryptions, $r$ be the parameter of $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$. Let $B=\varTheta (\alpha \sqrt{m})$ be a bound on the norm of the error in fresh encryptions (using a tail cutting argument we can show that $B=C\alpha \sqrt{m}$ is sufficient to have a bound with overwhelming probability), $L_{\max }={{\mathrm{poly}}}(n)$ be a bound on the size of the branching programs we consider and $\ell _{\max }={{\mathrm{poly}}}(n)$ an upper bound on their number of variables. Let $\varepsilon = O(2^{-\lambda })$ and $\varepsilon '=O (2^{-\lambda })$.

We have the following constraints:

• $\alpha = \varOmega \left( \sqrt{m}\right)$ for the hardness of ${\mathsf {LWE}}_{n-1, q,\mathcal {D}_{\mathbb {Z},\alpha }}$

• $r\ge \sqrt{\frac{5\ln \left( 2m\left( 1+1/\varepsilon \right) \right) }{\pi }}$ for the correctness of $\mathbf {G}^{-1}_{\text {rand}}\left( \cdot \right)$ sampling

• $r\ge 4\left( (1-\varepsilon )\left( 2\varepsilon '\right) ^2\right) ^{- \frac{1}{m}}$ for the leftover hash lemma

• $r\ge \sqrt{5}\left( 1+B\right) \sqrt{\frac{\ln \left( 2m \left( 1+1/\varepsilon \right) \right) }{\pi }}$ for Lemma 3.7

• $q = \varOmega \left( \sqrt{m}r\alpha \left( m\, L_{\max }\, \ell _{\max }\right) ^{1/2}\right)$ for the correctness of decryption

We can thus set the parameters as follows:

• $n=\varTheta (\lambda )$,

• $L_{\max }={{\mathrm{poly}}}(n)$,

• $\ell _{\max }={{\mathrm{poly}}}(n)$,

• $\alpha = \varTheta (\sqrt{n})$,

• $r= \tilde{\varTheta } \left( n\right)$,

• $q = \tilde{\varTheta } \left( n^{5/2}\cdot L_{\max }\cdot \ell _{\max }\right)$, a power of 2.

Note that the ciphertext size grows with $\log L_{\max }$. Correctness follows directly.

Lemma 5.6

(Correctness). For any branching program $\varPi$ of length L on $\ell$ variables, any $x_1,\ldots ,x_\ell \in \left\{ 0,1\right\}$, the result of the homomorphic evaluation $\mathbf {C}_f=\mathsf {Eval}\left( \varPi ,(\mathbf {C}_1,\ldots ,\mathbf {C}_\ell )\right)$ decrypts to $\varPi \left( x_1,\ldots ,x_\ell \right)$ with overwhelming probability, where $\mathbf {C}_i \leftarrow \mathsf {Encrypt}\left( \mathbf {s},x_i\right)$ for $i \in \left[ \ell \right]$ and $\mathbf {s}\leftarrow \mathsf {Setup}\left( 1^\lambda \right)$.

Proof

Lemma 5.4 shows that the noise distribution of the output $\mathbf {C}_f$ of $\mathsf {Eval}$ has parameter $r_f= r\sqrt{2\sum _{i=1}^\ell \tau _i\left( 1+\Vert \mathbf {e}_i \Vert ^2\right) }$, that is $r\sqrt{2L\sum _{i=1}^\ell \left( 1+\Vert \mathbf {e}_i \Vert ^2\right) }$ because of the padding we applied to $\varPi$. We have $r_f\le r\sqrt{2L\ell \left( 1+C^2\alpha ^2m\right) }$ with C the universal constant defined in Lemma 2.4, Using the bounds $L_{\max }$ and $\ell _{\max }$ we have $r_L=\tilde{O}\left( r\alpha (m\,L_{\max }\,\ell _{\max })^{1/2}\right)$. Finally, by a tail cutting argument, is enough for decryption to be correct with overwhelming probability.    $\square$

5.4 Arbitrary Modulus and Random Trapdoor Matrix

In this paragraph we show how to instantiate our proofs in a more generic setting.

Our GSW ciphertext rerandomization can be straightforwardly adapted to any matrix $\mathbf {H}$ and modulus q, as long as the lattice $\varLambda _q^\perp \left( \mathbf {H}^\intercal \right)$ has a small public basis, i.e. a small public trapdoor. Observe that the conditions needed to apply GSW ciphertext rerandomization are given in Lemma 3.7, which bounds the smoothing parameter of the lattice

$$\mathcal {L}=\left\{ \mathbf {v}\in \varLambda _q^\perp (\mathbf {H}^\intercal )\times \mathbb {Z}: \widehat{\mathbf {e}}^\intercal \mathbf {v}=0\right\} $$

and in Lemma 3.8 which gives the min-entropy of a Gaussian over $\varLambda _q^\perp (\mathbf {H}^\intercal )$.

Let $\beta \ge \Vert \mathbf {t}_i \Vert$, where $\mathbf {T}=\left\{ \mathbf {t}_1,...,\mathbf {t}_m\right\}$ is the public trapdoor of $\mathbf {H}$ (i.e. $\mathbf {T}$ is a small basis of $\varLambda _q^\perp \left( \mathbf {H}^\intercal \right)$), we show that the previous two lemmas can be proven for $\mathbf {H}$ and the parameter $r$ only grows by a factor $\beta$.

First, observe that Lemma 3.7 aims to find m small independent vectors in $\mathcal {L}$. By noticing that

$$\begin{aligned} \mathcal {L}=\left\{ \left( \mathbf {v},-\mathbf {v}^\intercal \mathbf {e}\right) : \mathbf {v}\in \varLambda _q^\perp (\mathbf {H}^\intercal )\right\} \end{aligned}$$

we can exhibit m small vectors $\mathbf {u}_i=\left( \mathbf {t}_i,-\mathbf {t}_i^\intercal \mathbf {e}\right) , i\in \left[ m\right]$ which are of norm

$$\begin{aligned} \Vert \mathbf {u}_i \Vert \le \Vert \mathbf {t}_i \Vert (1+\Vert \mathbf {e} \Vert )\le \beta (1+\Vert \mathbf {e} \Vert ) \end{aligned}$$

This bound is the one we obtain in Lemma 3.7 for $\varLambda ^{\perp }_q\left( \mathbf {G}^\intercal \right)$ where $\Vert \mathbf {T} \Vert =\sqrt{5}$.

Second, we show that the bound on the min-entropy of Lemma 3.8 can be expressed as a function of $\beta$, simply by using the fact that $\det (\mathbf {T}) \le \Vert \mathbf {T} \Vert ^m=\beta ^m$. From this we have the following bound on the min-entropy:

$$H_{\infty }\left( \mathcal {D}_{\varLambda _q^\perp \left( \mathbf {H}^\intercal \right) +\mathbf {c},r}\right) \ge \log \left( 1-\varepsilon \right) + m\log \left( r\right) -m\log \left( \beta \right) $$

This bound is slightly worse that the one we obtain in Lemma 3.8 for $\mathbf {G}$ (where we had 2 instead of $\beta$). However this is not a problem as it is a weaker bound than the one obtained in Lemma 3.7.

By using these two lemmas we can rerandomize GSW ciphertexts and ensure circuit privacy for arbitrary modulus q, and any matrix $\mathbf {H}$ with public trapdoor by setting the Gaussian parameter of $\mathbf {H}^{-1}\left( \cdot \right)$ to $r=\tilde{\varTheta }\left( \beta n\right)$.

5.5 Extension to General Circuits

We can realize circuit-private FHE for general circuits via bootstrapping using the technique of [OPP14] by combining a compact FHE for general circuits with decryption in $\mathsf {NC}^1$ with our circuit-private FHE for $\mathsf {NC}^1$circuits as follows: the server receives a ciphertext under the first FHE scheme, evaluates its circuit and bootstraps to the second (circuit hiding) FHE scheme. The ensuing scheme however will not satisfy the multi-hop requirement. Nevertheless, by using the construction given in [GHV10] it is possible to reach i-hop circuit private FHE for any a priori chosen i by giving out i pairs of switching keys to bootstrap from one scheme to the other and vice versa.