Counterexamples to New Circular Security Assumptions Underlying iO | Springer Nature Link

Indistinguishability obfuscation (\(i\mathcal {O}\)) for general programs computable in polynomial time [7] enables turning programs into unintelligible ones while preserving their functionality. \(i\mathcal {O}\) is a fundamental primitive and has found many applications in cryptography and beyond. As such, it is extremely important to base the feasibility of \(i\mathcal {O}\) on simple and well-studied hardness assumptions, and to thoroughly understand the objects and assumptions that imply \(i\mathcal {O}\). Current constructions of \(i\mathcal {O}\) can be broadly categorized into two schools: those using multilinear or bilinear pairing, and those without pairing. Very recently, we have seen exciting advances on both fronts. Using pairing, Jain, Lin, and Sahai [31] constructed \(i\mathcal {O}\) from four well-studied assumptions: Learning With Errors (LWE) [40], Decisional Linear assumption (DLIN) [6] over bilinear maps, Learning Pairity with Noise over general fields [28], and Pseudo-Random Generators in \(\mathsf {NC}_0\) [24]. Without pairing, three works [11, 20, 42], following [10], based \(i\mathcal {O}\) on new types of circular security assumptions on integer lattices.

In this work, we focus on these recent constructions [10, 11, 20, 42] and the new circular security assumptions they are based on. These constructions are very interesting because of their novel approaches and distinctive features. First, they are built solely on integer lattices (instead of drawing hardness from multiple cryptosystems) and therefore are possibly secure against quantum attacks. Second, their security assumptions are similar in flavor to the classical circular security heuristic [9, 15], which by now has been extensively studied and widely applied, most notably to un-leveled Fully Homomorphic Encryption (FHE) using Gentry’s boostrapping mechanism [21].

At the same time, the new assumptions are stronger than classical circular security in non-trivial ways. Consider the Gay-Pass assumption. Classical circular security w.r.t. a public key encryption scheme postulates that it is Chosen-Message-Attack (CPA) secure, even in the presence of an encrypted key-cycle that possibly uses other encryption schemes. The Gay-Pass assumption generalizes this blueprint to consider leakage-resilient CPA security: it says that if an encryption scheme is CPA secure when the adversary has access to certain leakage on the randomness of encryption, then additionally publishing an encrypted key-cycle should not harm this leakage-resilient CPA security. Concretely, their \(i\mathcal {O}\) scheme assumes Shielded Randomness Leakage (SRL) resilience in the presence of 2-circular encryption, w.r.t. the Gentry-Sahai-Waters FHE scheme [23] and a Packed version of Regev’s encryption [39, 40]^{Footnote 1}. The work [11] proposes a variant of the Gay-Pass assumption with a key-randomness cycle. Wee and Wichs [42] take a different approach and construct \(i\mathcal {O}\) based on LWE and a new conjecture, Homomorphic Pseudorandom LWE Samples (HPLS). Though this conjecture does not directly follow the circular security blueprint, close examination reveals a circular security flavor, involving the dual-GSW homomorphic commitment [23, 25] and a Pseudo-Random Function (PRF).

Although stronger and more complex than the classical circular security, these new assumptions were formulated in a principled way – indeed, on the surface, they seem to place \(i\mathcal {O}\) on qualitatively similar footing as un-leveled FHE! While exciting and encouraging, when it comes to new assumptions, it is important to be cautious and imperative to conduct cryptanalysis to develop deeper understandings. That is the purpose of our work.

Our Results. We present counterexamples to the Gay-Pass and Wee-Wichs assumptions. In both cases, we consider the GSW FHE scheme and the dual-GSW homomorphic commitment scheme for evaluating arithmetic circuits consisting of arithmetic addition, multiplication, and multiplication by constant gates. We stress that both schemes natively support these arithmetic operations [23]. In particular, in our counterexample to the Wee-Wichs conjecture we will leverage multiplication by a large constant, \(2^{-1} \bmod p\) (which is not needed for the counterexample to Gay-Pass assumption).

• First, we show that the Gay-Pass assumption is false when instantiated with the GSW FHE scheme by presenting a concrete attack.

• Second, Wee and Wichs’s HPLS conjecture is parameterized with a sampling algorithm \(\mathsf {D}\) that takes random coins \(\tau \) and produces a random LWE secret \(\boldsymbol{s}\leftarrow \mathbb {Z}_p^n\) and an error vector \(\boldsymbol{e}\) according to some error distribution. We show the conjecture is sensitive to the circuit implementation of \(\mathsf {D}\), namely, for every \(\mathsf D\), there is an arithmetic circuit \(C_{\mathsf {D}}\) implementing it such that the HPLS conjecture instantiated with \(C_{\mathsf {D}}\) is false. Again, we present a concrete attack.

Notably, classical circular security plausibly holds w.r.t. both the modified GSW and dual GSW schemes. Hence, our work gives the first examples that separate classical circular security and the strengthened versions of circular security underlying recent \(i\mathcal {O}\) schemes, showing evidence that they are not (yet) on the same footing.

Our counterexamples exploit some flexibility in the implementation details of the Gay-Pass and Wee-Wichs assumptions. The choice of such implementation is explicitly given to the adversary in the Gay-Pass assumption and is left unspecified in the Wee-Wichs conjecture. It remains possible that other choices of implementation of circuits do result in an unbroken assumption. Nevertheless, our work shows that this will, at least, require refinement of the assumptions, and in particular that generic circular security assumptions/definitions are delicate, and their security is actually sensitive to the specific structure of the leakages involved.

Next, we describe the Gay-Pass and Wee-Wichs assumptions and our counterexamples in more detail.

Counterexample to the Gay-Pass assumption. As stated in Gay and Pass [20], the 2-circular assumption w.r.t. two public key encryption schemes \(\mathsf {Enc}^1\) and \(\mathsf {Enc}^2\) that are Chosen-Plaintext-Attack (CPA) secure postulates that

• \(\underline{ Classical\,2{\text {-}}circular\,security\,assumption\,w.r.t.\ \mathsf {Enc}^1, \mathsf {Enc}^2:}\) \(\mathsf {Enc}^1\) is (still) CPA secure – that is, honestly generated ciphertexts \(\mathsf {Enc}^1_{\mathsf {pk}^1}(m^0)\) and \(\mathsf {Enc}_{\mathsf {pk}^1}^1(m^1)\) for any two chosen messages \(m^0, m^1\) are indistinguishable – when a length-two encrypted key cycle \(\mathsf {Enc}_{\mathsf {pk}^1}^1(\mathsf {sk}^2)\), \(\mathsf {Enc}_{\mathsf {pk}^2}^2(\mathsf {sk}^1)\) is published.

Classical circular security has been extensively studied as encrypted key cycles of different lengths naturally arise in applications such as encrypted storage system, anonymous credentials [15], and un-leveled FHE [21]. So far, though counterexamples to 2-circular security or 1-circular security for bit encryption^{Footnote 2} (where the key cycle has length 1 \(\{ \mathsf {Enc}_{\mathsf {pk}}(\mathsf {sk}_i)\}_{i \in [|\mathsf {sk}|]}\)) have been constructed (see e.g. [1, 8, 16, 26, 27, 32, 33, 35, 41, 43]), no attacks have been shown against any “natural” encryption schemes. Therefore, classical circular security is still commonly assumed w.r.t. natural encryption schemes such as homomorphic encryption [12, 14, 23], Regev’s encryption [40] etc.

Gay and Pass extend 2-circular security to consider CPA security in the presence of the so-called shielded randomness leakage (SRL). More specifically, shielded randomness leakage is only defined w.r.t. FHE schemes with certain properties including randomness homomorphism. The leakage is captured by an oracle \(\mathcal {O}_{\mathsf {SRL}}\) (described shortly below) and reveals certain information of the randomness of encryption. A public-key FHE scheme \(\mathsf {Enc}^1\) is SRL-secure if CPA security holds even if the adversary has access to \(\mathcal {O}_{\mathsf {SRL}}\). Then the 2-circular SRL security assumption w.r.t. \(\mathsf {Enc}^1, \mathsf {Enc}^2\) where \(\mathsf {Enc}^1\) is SRL secure and \(\mathsf {Enc}^2\) is CPA secure, states that:

• \(\underline{ 2{\text {-}}circular\,SRL\,security\,assumption\,w.r.t.\, \mathsf {Enc}^1, \mathsf {Enc}^2{:}}\) \(\mathsf {Enc}^1\) is (still) SRL secure – that is, honestly generated ciphertexts \(\mathsf {Enc}^1_{\mathsf {pk}^1}(m^0)\) and \(\mathsf {Enc}_{\mathsf {pk}^1}^1(m^1)\) for any two chosen messages \(m^0, m^1\) are indistinguishable, even if the adversary has access to \(\mathcal {O}_{\mathsf {SRL}}\) – when a length two encrypted key cycle \(\mathsf {Enc}_{\mathsf {pk}^1}^1(\mathsf {sk}^2)\), \(\mathsf {Enc}_{\mathsf {pk}^2}^2(\mathsf {sk}^1)\) is published.

The Gay-Pass \(i\mathcal {O}\) scheme relies on the above assumption w.r.t. the GSW FHE scheme as \(\mathsf {Enc}^1\) and the packed Regev encryption as \(\mathsf {Enc}^2\). Notably, they prove that the GSW scheme is SRL-secure based on LWE.

Let’s now understand what shielded randomness leakage is. In the plain SRL security game (without encrypted key cycles), the adversary is given a collection of challenge ciphertexts \(\{ \mathsf {ct}_i = \mathsf {Enc}_{\mathsf {pk}^1}^1(m^b_i; \mathbf {R}_i)\}_i\) encrypting one of the two sets of chosen messages, \(\{ m^0_i\}_i\) or \(\{ m^1_i\}_i\), for a random b, using randomness \(\{ \mathbf {R}_i\}_i\). In addition, the adversary \(\mathcal {A}\) can interact with the SRL oracle \(\mathcal {O}_{\mathsf {SRL}}\) as follows to help it distinguish.

• \(\underline{ The\, \mathcal {O}_{\mathsf {SRL}}\, Oracle\, (Simplified)}\) gives leakage on the message and randomness \(\{ m^b_i; \mathbf {R}_i\}_i\) underlying the challenge ciphertexts as follows:

  1. 1.

     Upon invocation, \(\mathcal {O}_{\mathsf {SRL}}\) samples a fresh encryption \(\mathsf {ct}^\star = \mathsf {Enc}_{\mathsf {pk}^1}^1(0; \mathbf {R}^\star )\) of zero using randomness \(\mathbf {R}^\star \) and sends \(\mathsf {ct}^\star \) to the adversary^{Footnote 3}.

  2. 2.

     \(\mathcal {A}\) chooses a circuit C and an output y.

  3. 3.

     \(\mathcal {O}_{\mathsf {SRL}}\) homomorphically evaluates C on \(\mathsf {ct}^\star \) and the challenge ciphertexts \(\{ \mathsf {ct}_i\}_{i}\) to obtain an output ciphertext \(\mathsf {ct}_C = \mathsf {HEval}(C, \mathsf {ct}^\star , \{ \mathsf {ct}_i\})\) that encrypts \(y'\) with randomness \(\mathbf {R}_C\) (computed by the randomness homomorphism property of HE from \(\{ m^b_i; \mathbf {R}_i\}_i\)). It returns \(\mathbf {R}^\star - \mathbf {R}_C\) if \(y = y'\), or nothing if \(y\ne y'\).

In the 2-circular SRL-security game, the adversary is additionally given an encrypted key cycle \(\mathsf {Enc}_{\mathsf {pk}^1}^1(\mathsf {sk}^2)\), \(\mathsf {Enc}_{\mathsf {pk}^2}^2(\mathsf {sk}^1)\) along with the challenge ciphertexts \(\{ \mathsf {ct}_i\}\) at the beginning. We remark that for security of the ensuing Gay-Pass \(i\mathcal {O}\) construction it is crucial that the adversary is allowed to choose C adaptively. This means in the plain SRL security game, C may depend on \(\mathsf {ct}^\star , \{ \mathsf {ct}_i\}\), and, in the 2-circular SRL security game, additionally on the encrypted cycle \(\mathsf {Enc}_{\mathsf {pk}^1}^1(\mathsf {sk}^2)\), \(\mathsf {Enc}_{\mathsf {pk}^2}^2(\mathsf {sk}^1)\). Indeed, the security reduction from \(i\mathcal {O}\) to the 2-circular SRL security chooses such a “dependent” C. Looking ahead, our counterexample also crucially exploits this adaptivity.

Our counterexample: We show that the 2-circular SRL security assumption is false w.r.t. the GSW FHE scheme in [23]. Let us now give more details.

Our Ideas In a Nut shell: Given that (modified) GSW is both SRL-secure and plausibly circular secure, the attack must simultaneously leverage the shield-randomness leakage \(\mathbf {R}^\star - \mathbf {R}_C\) and the encrypted key cycle \(\mathsf {Enc}_{\mathsf {pk}^1}^1(\mathsf {sk}^2)\), \(\mathsf {Enc}_{\mathsf {pk}^2}^2(\mathsf {sk}^1)\). Recall that the attack can adaptively choose the circuit C depending on the key cycle, \(\mathsf {ct}^\star \), and \(\{ \mathsf {ct}_i\}\), meaning they can be hardcoded in C. Observe also that the input to C is \((\{ m^b_i\},\mathsf {sk}^2)\), and hence C can compute as an intermediate value \(\mathsf {sk}^1\) and can also “access” \(\mathbf {R}^\star \) (by decrypting \(\mathsf {Enc}_{\mathsf {pk}^2}^2(\mathsf {sk}^1)\) and \(\mathsf {ct}^\star \)). Since C can “access” both \(\mathbf {R}^\star \) and \(\{ m^b_i\}\), our attack carefully engineers C so that homomorphic evaluation of C produces an output ciphertext \(\mathsf {ct}_C\) with randomness \(\mathbf {R}_C\) correlated with \((\mathbf {R}^\star ,\{ m^b_i\})\), and then the shield randomness leakage \(\mathbf {R}^\star - \mathbf {R}_C\) reveals information of b. More specifically, the attack creates correlation between the parity bit of noises and values by carefully engineering C using the following correlation-inducing gadget circuits.

• Correlation Gadget: The gadget circuit G(x, 0) multiplies x with 0 and produces a fixed output of 0. Homomorphically evaluating G on GSW ciphertexts \(\mathsf {ct}\) of x and \(\mathsf {ct}_0\) of 0 produces a new ciphertext \(\mathsf {ct}' = \mathbf {A} \mathbf {R}'\) of zero of the following form:

  $$\begin{aligned} \mathsf {ct}= \mathbf {A} \mathbf {R} + x\mathbf {G}, \ \mathsf {ct}_0 = \mathbf {A} \mathbf {R}_0 \quad&\overset{\mathsf {HEval}\ \times }{\longrightarrow } \quad \mathsf {ct}' = \mathbf {A} \mathbf {R}',\ \mathbf {R}' = \mathbf {R}\cdot G^{-1}(\mathsf {ct}_0) + x\mathbf {R}_0 \end{aligned}$$

Consider an attack that chooses a circuit C which first computes \(x = f(m^b_i, \mathsf {sk}^2)\) and then the above G(x, 0) (f is specified shortly below). The attack receives from the SRL oracle leakage

To learn the bit b, we want to 1) correlate x with \(\mathbf {R}^*\) and b, and 2) eliminate the middle term \(\mathbf {R}\cdot G^{-1}(\mathsf {ct}_0)\).

• We achieve the second by finding a vector \(\boldsymbol{v} \in \{0,1\}^{m}\) such that \(G^{-1}(\mathsf {ct}_0)\cdot \boldsymbol{v} = 0 \bmod 2\). This is possible with probability close to 1/2 as \(G^{-1}(\mathsf {ct}_0)\) is a pseudorandom binary matrix and hence is non-singular mod 2 with probability close to 1/2.

• We achieve the first by letting the function f compute \(b\,\cdot \,\boldsymbol{e} \mathbf {R}^* \boldsymbol{v} \bmod 2\). Observe that this is computable since homomorphically decrypting \(\mathsf {ct}^*\) gives exactly \(\boldsymbol{e} \mathbf {R}^*\). One can then further multiply b and \(\boldsymbol{v}\), followed by modulo 2.

This means the attack can learn

Let us observe the difference between the cases when \(b = 0\) or 1. If \(b= 0\), \(\boldsymbol{z} = \mathbf {R}^* \boldsymbol{v} \bmod 2\) which is random since \(\mathbf {R}^*\) is random and independent of v. On the other hand, if \(b=0\), \(\boldsymbol{z} = \mathbf {R}^* \boldsymbol{v} + (\boldsymbol{e} \mathbf {R}^* \boldsymbol{v}) \mathbf {R}_0\boldsymbol{v} \bmod 2\), which satisfies \(\boldsymbol{e} \cdot \boldsymbol{z} = 0 \bmod 2\) if \(\boldsymbol{e} \mathbf {R}_0\boldsymbol{v} = 1\). The latter condition holds with probability 1/2 over the random choice of \(\mathbf {R}_0\). This difference is sufficient for creating a distinguishing attack: Repeat the above many times to collect different \(\boldsymbol{z}_i\) w.r.t. to different \(\mathsf {ct}^*_i = \mathbf {B} \mathbf {R}^*_i\), and the same \(\mathsf {ct}_0 = \mathbf {B}\mathbf {R}_0\). If \(b = 0\), all \(\boldsymbol{z}_i\)’s are random, whereas if \(b = 1\), all \(\boldsymbol{z}_i\)’s satisfy \(\boldsymbol{e} \cdot \boldsymbol{z}_i = 0 \bmod 2\) conditioned on the event \(\boldsymbol{e} \mathbf {R}_0\boldsymbol{v} = 1\) of probability 1/2.

Please see Sect. 5.1 for how we construct the challenge circuit C and other details in the attack. We note that though our attack is described w.r.t. GSW FHE for arithmetic circuits, it can be easily translated into an attack w.r.t. GSW FHE for Boolean circuits. In particular, the correlation gadget circuit will compute homomorphic AND which translates to computing homomorphic multiplication in GSW and the rest of the attack is the same.

Counterexample to the Wee-Wichs assumption. Wee and Wichs [42] take a different approach, constructing \(i\mathcal {O}\) assuming LWE and the ability to obliviously generate LWE samples without knowing the corresponding secrets. They then proposed a heuristic mechanism for oblivious LWE sampling, using the dual-GSW homomorphic commitment and any Pseudo-Random Function (PRF). They formulated a concrete conjecture, called the Homomorphic Pseudorandom LWE Samples conjecture, to capture the security of their mechanism. Let us now recall their conjecture.

The Dual GSW Homomorphic Commitment Scheme The scheme is a variant of the homomorphic encryption/commitment schemes of [23, 25] with the feature that one can homomorphically evaluate a function with a vector output \(f: \{0, 1\}^\ell \rightarrow \mathbb {Z}^m_p\), and the decommitment to the output commitment to f(x) is shorter than m. Given a public random matrix \(\mathbf {A} \in \mathbb {Z}_p^{m \times n}\) where \(m\gg n\), a commitment \(\mathbf {C}\) to an input \(\boldsymbol{x} \in \{0, 1\}^\ell \) is

where \(\mathbf {R}_i\leftarrow \mathbb {Z}_p^{n \times m \log q}\), \(\mathbf {E}_i \leftarrow \chi ^{m \times m \log q}\), and \(\mathbf {G}\) is the gadget matrix.

The key difference from [23, 25] are: 1) the matrix \(\mathbf {A}\) is a thin/tall matrix, whereas in GSW \(\mathbf {A}\) is fat/short, 2) \(\mathbf {R}_i\) is fat/short and uniformly sampled, whereas in GSW, they are square matrices consisting of small entries, and 3) because of the shapes of matrices \(\mathbf {A}\mathbf {R}_i\) is far from (pseudo)random and hence additional noises \(\mathbf {E}_i\) are added. On the other hand, the hiding property of the commitments still follows directly from LWE, and the same homomorphic evaluation procedure applies. For any Boolean function \(f: \{0, 1\}^\ell \rightarrow \{0, 1\}\), one can homomorphically derive a commitment \(\mathbf {C}_f = \mathbf {A} \mathbf {R}_f + f(x)\mathbf {G} + \mathbf {E}_f\). Additionally, using the same “packing” procedure, one can homomorphically evaluate \(g: \{0, 1\}^\ell \rightarrow \mathbb {Z}_p^m\) with a vector output to derive a commitment \(\mathbf {C}_g = \mathbf {A} \boldsymbol{r}_g + g(x) + \boldsymbol{e}_g\). Observe that the opening to this output commitment is \(\boldsymbol{r}_g\) of length \(n \log p \ll m\).

The Homomorphic Pseudorandom LWE Samples (HPLS) conjecture considers the following two distributions parameterized by a PRF \(\mathsf {PRF}\).

where the random variables are sampled as follows: 1) \(\{ \boldsymbol{d}_i\}\) are fresh LWE samples with secret \(\widehat{\boldsymbol{s}}_i \leftarrow \mathbb {Z}_p^n\) and noise \(\widehat{\boldsymbol{e}}_i \leftarrow \chi ^m\), 2) \(\mathbf {C}\) is a dual-GSW commitment to a randomly sampled PRF key k and the bit \(\beta \), and 3) each \(\boldsymbol{s}_i\) is derived from homomorphically evaluating the following computation \(g_i(k,\beta )\): the function \(g_i\) first evaluates \(\mathsf {PRF}\) to obtain random bits \(\tau _i\), then uses them to sample random LWE secret \(\boldsymbol{s}_i^\mathsf {PRF}\) and noise \(\boldsymbol{e}_i^\mathsf {PRF}\leftarrow \chi _\mathsf {PRF}^m\) according to a sampling algorithm \(\mathsf {D}\), and finally outputs a vector \(\mathbf {A} \boldsymbol{s}_i^\mathsf {PRF}+ \boldsymbol{e}_i^\mathsf {PRF}+ \beta \boldsymbol{d}_i\).

The HPLS conjecture states that for appropriate settings of parameters, in particular when the magnitude of the noises satisfy \(\boldsymbol{e}^\mathsf {PRF}_i \gg \widehat{\boldsymbol{e}}_i \gg \boldsymbol{e}^\mathsf {Eval}_i\), there is a choice of \(\mathsf {PRF}\) such that \(\mathsf {DIST}(0)\) and \(\mathsf {DIST}(1)\) are indistinguishable.

Observe that given a sample from the distribution, one can easily compute the noise \(\boldsymbol{e}_i\) in \(\mathbf {C}_{g_i}\) by using the opened secret vectors \(\boldsymbol{s}_i\). Then, the circular security nature of the HPLS conjecture lies in that on one hand we rely on the PRF security to argue that \(\boldsymbol{e}_i^\mathsf {PRF}\) smudges \(\beta \widehat{\boldsymbol{e}}_i + \boldsymbol{e}_i^\mathsf {Eval}\), otherwise dual-GSW security is broken, on the other hand, we rely on the dual-GSW security to argue that the \(\mathsf {PRF}\) key k remains hidden.

Our Counterexample. Our counterexample states that when using dual-GSW for arithmetic computation, for every sampling algorithm \(\mathsf {D}\) used in the second step of \(g_i\)’s (that converts random bits \(\tau \) to a random LWE secret vector \(\boldsymbol{s}\) and an error vector \(\boldsymbol{e}\) of some distribution \(\chi _\mathsf {PRF}\)) there is an arithmetic circuit \(C_{\mathsf {D}}\) that implements \(\mathsf {D}\), such that, for every PRF \(\mathsf {PRF}\) (and every circuit implementation of \(\mathsf {PRF}\)), the distributions \(\mathsf {DIST}(0)\) and \(\mathsf {DIST}(1)\) are distinguishable. In short, the HPLS conjecture is false for every \(\mathsf {PRF}\) and every sampling algorithm \(\mathsf {D}\), if the circuit implementation of \(\mathsf {D}\) is allowed to be arbitrarily chosen.

Our Ideas In a Nutshell: Our counterexample attacks the noise \(\{ \boldsymbol{e}_i = (\boldsymbol{e}_i^\mathsf {PRF}+ \beta \widehat{\boldsymbol{e}}_i + \boldsymbol{e}_i^\mathsf {Eval})\}\) that can be derived from a sample of the distribution. To distinguish between \(\beta = 0\) or 1, our idea is to create correlation between the parity of \(\boldsymbol{e}_i^\mathsf {PRF}[1]\) and \(\boldsymbol{e}_i^\mathsf {Eval}[1]\), so that \(\boldsymbol{e}_i[1] \bmod 2\) reveals information about \(\beta \). We do so by carefully crafting the circuit \(C_{\mathsf {D}}\) using two gadget circuits described below.

• Even Gadget: \(G_1(x)\) implements the identity function on a single element x. It first multiplies x by 1/2, and then adds x/2 with itself to get back x (computation over \(\mathbb {Z}_p\)). Homomorphically evaluating \(G_1\) on a dual-GSW commitment \(\mathsf {ct}= \mathbf {A} \mathbf {R} + x\mathbf {G} + \mathbf {E}\) to x produces a commitment \(\mathbf {C}' = \mathbf {A} \mathbf {R}' + x\mathbf {G} + \mathbf {E}'\) with even errors \(\mathbf {E}'\).

  $$\begin{aligned} \mathbf {C} = \mathbf {A} \mathbf {R} + x\mathbf {G} + \mathbf {E} \quad&\overset{\mathsf {HEval}\ \times \frac{1}{2}}{\longrightarrow } \quad \mathbf {C}'' = \mathbf {A} \mathbf {R}'' + \frac{x}{2}\mathbf {G} + \mathbf {E}''\\ \quad&\overset{\mathsf {HEval}\ +}{\longrightarrow } \quad \mathbf {C}' = \mathbf {A} \mathbf {R}' + x\mathbf {G} + \mathbf {E}', \ \text { where } \mathbf {E}' = 2\mathbf {E}'' \end{aligned}$$

• Correlation Gadget: The second gadget circuit \(G_2(x,1)\) first computes \(G_1(x)\) to get x, and then multiplies it with 1. Homomorphically evaluating \(G_2\) on dual-GSW commitment \(\mathbf {C}\) to x and \(\mathbf {C}_1\) to 1 produces a new commitment \(\mathbf {C}' = \mathbf {A} \mathbf {R}' + x\mathbf {G} + \mathbf {E}'\) of x where the parity of \(\mathbf {E}'[1,1]\) is correlated with x if \(\mathbf {E}_1[1,1]\) is odd, where \(\mathbf {E}_1\) is the noise in \(\mathbf {C}_1\).

  $$\begin{aligned}&\mathsf {ct}= \mathbf {A} \mathbf {R} + x\mathbf {G} + \mathbf {E} \quad \overset{\mathsf {HEval}\ G_1}{\longrightarrow } \quad \mathsf {ct}'' = \mathbf {A} \mathbf {R}' + x\mathbf {G} + (2\mathbf {E}'')\\&\qquad \overset{\mathsf {HEval}\ \times (\mathsf {ct}_1 = \mathbf {A} \mathbf {R}_1 + \mathbf {G} + \mathbf {E}_1)}{\longrightarrow } \quad \mathsf {ct}' = \mathbf {A} \mathbf {R}'+ x\mathbf {G} + \mathbf {E}',\ \mathbf {E}' = 2\mathbf {E}''G^{-1}(\mathsf {ct}_1) + x\mathbf {E}_1 \end{aligned}$$

Using them, we create correlation between \(\boldsymbol{e}_i^\mathsf {PRF}[1] \bmod 2\) and \(\boldsymbol{e}_i^\mathsf {Eval}[1] \bmod 2\).

Before we can declare success, we must resolve two other issues. First, the correlation created by the second gadget is probabilistic, depending on the parity of noise \(\mathbf {E}_1[1,1]\) embedded in commitment \(\mathbf {C}_1\). This is not too much of a problem since \(\mathbf {C}_1\) is reused for all index i and hence with probability 1/2, we see an observable pattern in all \(\boldsymbol{e}_i\). Second, the homomorphic evaluation of \(\beta \boldsymbol{d}_i\) is outside the control of \(C_{\mathsf {D}}\) and its noise will be added to the final output of \(g_i\). We overcome the issue by observing that noises resulting from this homomorphic evaluation induces an over-determined linear system over the noises \(\mathbf {E}_\beta \) in the commitment to \(\beta \). Thus, we can use linearity testing to help the attack distinguish.

Possible Extension. One natural follow-up question is whether our techniques can be extended to directly attack these recent \(i\mathcal {O}\) constructions [10, 11, 20, 42], beyond the circular security assumptions they rely on. On this front, we think that our attack ideas can be extended to break the security of the \(i\mathcal {O}\) scheme of [10] (and possibly its followups [11, 20]), if one is allowed to manipulate the implementation of the underlying FHE scheme (e.g., using odd noises to generate the public key of the GSW FHE scheme) and the implementation of circuits computed (e.g., the circuit for computing mod). However, in this work, we focus only on the assumptions, and leave direct attacks to the schemes as future work.

A Perspective. First, our attacks highlight the importance of building schemes from well-founded assumptions. However, in cases where existing techniques are far from reaching this goal, one way of making progress is through cycles of proposals and attacks, and a measure of progress is the simplicity of the proposed assumptions, and whether they are natural and connected to well-studied areas in computer science. For instance, the recent line of \(i\mathcal {O}\) constructions [4, 5, 19, 29, 30, 34] started with assuming new assumptions, and eventually led to the first \(i\mathcal {O}\) construction [31] based on four well-founded assumptions – LWE, the decision linear assumption over symmetric key pairing, LPN over large fields, and PRG in \(\mathsf {NC}^0\).

At this moment, we still lack good understanding on the front of constructing \(i\mathcal {O}\) solely from lattices (or constructing post-quantum secure \(i\mathcal {O}\)). The works of [10, 11, 20, 42] proposed refreshing approaches and ideas. The purpose of our work, through counterexamples, is finding weak points in these new approaches, so that, they can be addressed and the assumptions can be refined in future works. In particular, a main lesson from our counterexamples is that when working with leakage of noises in LWE, it is important to examine the specific leakage carefully.

Other \(i\mathcal {O}\)Constructions. Our work focuses on the new types of circular security assumptions/hard problems underlying recent \(i\mathcal {O}\) constructions of [10, 11, 20, 42]. Prior to their work, Agrawal [2] gave an \(i\mathcal {O}\) construction based on noisy linear functional encryption and proposed a candidate noisy linear functional encryption based on new types of NTRU assumptions. The work of [3] cryptanalyzed of the new NTRU assumptions and further refined them. There are many \(i\mathcal {O}\) constructions based on multilinear maps, which can be instantiated from lattices (see references in [31]). Though all known multilinear map instantiation have been attacked, there are still \(i\mathcal {O}\) candidates based on them that are unbroken, for instance [18]. Furthermore, Gentry, Jutla and Kane [22] proposed an \(i\mathcal {O}\) candidate using tensor products. Finally, using bilinear pairing, a line of constructions [4, 5, 19, 29, 30, 34] recently led to the first \(i\mathcal {O}\) construction by [31] based on four well-founded assumptions – LWE, the decision linear assumption over symmetric key pairing, LPN over large fields, and PRG in \(\mathsf {NC}^0\).