This paper initiates a study ofFine Grained Secure Computation: i.e. the construction ofsecure computation primitives against “moderately complex” adversaries. We present definitions and constructions forcompact Fully Homomorphic Encryption and Verifiable Computation secure against (non-uniform)\(\mathsf {NC}^1\) adversaries. Our results do not require the existence of one-way functions and hold under a widely believed separation assumption, namely\(\mathsf {NC}^{1}\subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}\). We also present two application scenarios for our model:(i) hardware chips that prove their own correctness, and(ii) protocols against rational adversaries potentially relevant to theVerifier’s Dilemma in smart-contracts transactions such as Ethereum.

1. 1.

   We intentionally refer to it as “cost” to keep the notion generic. For concreteness one can think ofC as the running time required to run the protocol.

2. 2.

   A separation implied by\(\mathsf {L}\ne \mathsf {NC}^1\). See Sect. 1.1 for more details.

3. 3.

   This is a reference to Impagliazzo’s “five possible worlds” [Imp95].

4. 4.

   Naturally the security guarantees of these schemes are more limited compared to their standard definitions.

5. 5.

   The techniques in [GKR08,GR18] are based on properties of finite fields. Arithmetic in such fields can be carried out by circuits of constant depth with threshold gates (\(\mathsf {TC}^0\)), but not in\(\mathsf {AC}^0[2]\).

6. 6.

   Where the ciphertexts do not grow in size with each homomorphic operation.

7. 7.

   Where not only the circuit depth is constant but also the size of the circuit is quasilinear – the size of the verification circuit should be\(O({\mathsf {poly}}(\lambda )(n+m))\) wheren andm are the size of the input and output respectively.

8. 8.

   More precisely, that a permutation statistically indistinguishable from a random one can be sampled in\(\mathsf {AC}^0\).

9. 9.

   See also RemarkC.1.

10. 10.

    TrueBit:https://truebit.io/.

11. 11.

    Stated as Lemma 4.3 in [DVV16].

12. 12.

    We are only requiring to decrypt ciphertexts that are output by\(\mathsf {HE.Eval}(\cdots )\).

13. 13.

    In terms of circuit depth, the main overhead when evaluatingf homomorphically is given by the multiplication gates (addition, on the other hand, is “for free” — see definition of\(\mathsf {HE.Eval}\) above). A single homomorphic multiplication can be performed by a depth two\(\mathsf {AC}^0[2]\) circuit, but this requires depth\(\varOmega (\log (n))\) with a circuit of fan-in two. Therefore, a circuit forf with\(\omega (1)\) multiplicative depth would require an evaluation of\(\omega (\log (n))\) depth, which would be out of\(\mathsf {NC}^1\). On the other hand, observe that for any functionf in\(\mathsf {AC}^0[2]\) with constant multiplicative depth, the evaluation stays in\(\mathsf {AC}^0[2]\). This because there is a constant number (depth) of homomorphic multiplications each requiring an\(\mathsf {AC}^0[2]\) computation.

14. 14.

    In the evaluation algorithm we ignore the distinction between deterministic and random input.

15. 15.

    The reader can find additional details in AppendixB.

16. 16.

    Recall that the output of the expanded approximating function\(f'\) is a bit string and thus each\(\varvec{c}^{\text {out}}_i\) encrypts a bit string.

17. 17.

    Further details on the complexity of\(\mathcal{VC}\) follow. All the algorithms are in\(\mathsf {AC}^0_{\text {CM}}[2]\), except for the online stage. In fact,\(\mathsf {VC.Verify}\) and\(\mathsf {VC.ProbGen}\) are in\(\mathsf {AC}^0[2]\). Moreover, they are not in\(\mathsf {AC}^0_{\text {Q}}[2]\) as they perform in parallel a non-constant (polylogarithmic) number of decryptions and permutations respectively, and these involve non-constant fan-in gates. Notice that even though the online stage is not in\(\mathsf {AC}^0_{\text {Q}}[2]\) we still have a gain at verification time (although not in an asymptotic sense). This because of the specific structure of these circuits. Consider for example what happens when implementing\(\mathsf {VC.Verify}\) or\(\mathsf {VC.ProbGen}\) with a fan-in two circuit. Their depth will be\(c (\log (n)+\log (\lambda ))\) for a constantc. Contrast this with a circuitf in\(\mathsf {AC}^0_{\text {Q}}[2]\) of constant depthD that we may want to verify. With fan-in two, the depth off will become\(c'D\log (n)\) (for a constant\(c'\)), which may be significantly larger.

18. 18.

    We refer the reader to [Gol01].

19. 19.

    Notice that the syntax of\(\mathsf {Eval}\) can also be extended to return a sequence of encryptions for the case of multi-output functions. We will use this fact in Sect. 3.3. See also RemarkA.1.

20. 20.

    This allows our\(\mathsf {NC}^0\) circuit to “know” which gates to copy and which ones to transform based on their position only.

21. 21.

    I.e. the size of the verification circuit should be\(O({\mathsf {poly}}(\lambda )(n+m))\) wheren andm are the size of the input and output respectively.

22. 22.

    These observations would not hold for the computational setting, which is out of the scope of this paper.

Authors and Affiliations

1. The City College of New York, New York, USA

   Matteo Campanelli & Rosario Gennaro

Corresponding author

Correspondence toMatteo Campanelli.

Editors and Affiliations

1. Ben Gurion University, Beer Sheva, Israel

   Amos Beimel

2. University of Warsaw, Warsaw, Poland

   Stefan Dziembowski

A Additional Preliminaries

1.1A.1 Infinitely-Often Computational Indistinguishability

Definition A.1

(Infinitely-Often Computational Indistinguishability). Let\(\mathcal {X} = \{X_{\lambda }\}_{\lambda \in \mathbb {N}}\) Let\(\mathcal {Y} = \{Y_{\lambda }\}_{\lambda \in \mathbb {N}}\) be ensembles over the same domain family,\(\mathcal {A}\) a class of adversaries, and\(\varLambda \) an infinite subset of\(\mathbb {N}\). We say that\(\mathcal {X}\) and\(\mathcal {Y}\) are infinitely often computational indistinguishable with respect to set\(\varLambda \) and the class\(\mathcal {A}\), denoted by\(\mathcal {X} \sim _{\varLambda ,\mathcal {A}} \mathcal {Y}\) if there exists a negligible function\(\nu \) such that for any\(\lambda \in \varLambda \) and for any adversary\(A=\{A_\lambda \}_\lambda \in \mathcal {A}\)

When\(\mathcal {A} = \mathsf {NC}^1\) we will keep it implicit and use the notation\(\mathcal {X} \sim _{\varLambda } \mathcal {Y}\) and say that\(\mathcal {X} \text { and } \mathcal {Y}\) are\(\varLambda \)-computationally indistinguishable.

In our proofs we will use the following facts on infinitely-often computationally indistinguishable ensembles. We skip their proof as, except for a few technicalities, it is analogous to the corresponding properties for standard computational indistinguishability^Footnote18.

Lemma A.1

(Facts on\(\varLambda \)-Computational Indistinguishability).

• Transitivity: Let\(m = {\mathsf {poly}}(\lambda )\) and\(\mathcal {X}^{(j)}\) with\(j \in \{0,\dots ,m \} \) be ensembles. If for all\(j \in [m]\)\(\mathcal {X}^{(j-1)} \sim _{\varLambda }\mathcal {X}^{(j)}\), then\(\mathcal {X}^{(0)} \sim _{\varLambda }\mathcal {X}^{(m)}\).

• Weaker than statistical indistinguishability: Let\(\mathcal {X}, \mathcal {Y}\) be statistically indistinguishable ensembles. Then\(\mathcal {X} \sim _{\varLambda }\mathcal {Y}\) for any infinite\(\varLambda \subseteq \mathbb {N}\).

• Closure under\(\mathsf {NC}^1\): Let\(\mathcal {X}, \mathcal {Y}\) be ensembles and\(\{f_{\lambda }\}_{\lambda \in \mathbb {N}} \in \mathsf {NC}^1\). If\(\mathcal {X} \sim _{\varLambda }\mathcal {Y}\) for some\(\varLambda \) then\(f_{\lambda }(\mathcal {X}) \sim _{\varLambda }f_{\lambda }(\mathcal {Y})\).

1.2A.2 Circuit Classes

For a gateg we denote by\({\mathsf {type}}_C(g)\) the type of the gateg in the circuitC and by\({\mathsf {parents}}_C(g)\) the list of gates ofC whose output is an input toC (such list may potentially contain duplicates).

We define the multiplicative depth of a circuit as follows:

Definition A.2

(Multiplicative Depth). LetC be a circuit, we define the multiplicative depth ofC as\({\mathsf {md}}(g_{out})\) where\(g_{out}\) is its output gate and the function\({\mathsf {md}}\), from the set of gates to the set of natural numbers is recursively defined as follows:

where the sum in the last case is over the integers.

The following two circuit classes will appear in several of our results.

Definition A.3

(Circuits with Constant Multiplicative Depth). We denote by\(\mathsf {AC}^0_{\text {CM}}[2]\) the class of circuits in\(\mathsf {AC}^0[2]\) withconstant multiplicative depth.

Definition A.4

(Circuits with Quasi-Constant Multiplicative Depth). For a circuitC we denote by\(S_{\omega (1)}(C)\) the set of\(\mathsf {AND}\) and\(\mathsf {OR}\) gates inC with non-constant fan-in. We say thatC hasquasi-constant multiplicative depth if\(|S_{\omega (1)}(C)| = O(1)\). We shall denote by\(\mathsf {AC}^0_{\text {Q}}[2]\) the class of circuits in\(\mathsf {AC}^0[2]\) with quasi-constant multiplicative depth.

1.3A.3 Public-Key Encryption

A public-key encryption scheme

\(\mathsf {PKE}= (\mathsf {PKE.Keygen}, \mathsf {PKE.Enc}, \mathsf {PKE.Dec})\) is a triple of algorithms which operate as follow:

• Key Generation. The algorithm\((\mathsf {pk},\mathsf {sk})\leftarrow \)\(\mathsf {PKE.Keygen}\)\((1^{\lambda })\) takes a unary representation of the security parameter and outputs a public key encryption key\(\mathsf {pk}\) and a secret decryption key\(\mathsf {sk}\).

• Encryption. The algorithm\(c\leftarrow \)\(\mathsf {PKE.Enc}\)\(_{\mathsf {pk}}(\mu )\) takes the public key\(\mathsf {pk}\) and a single bit message\(\mu \in \{0, 1\}\) and outputs a ciphertextc. The notation\(\mathsf {PKE.Enc}\)\(_{\mathsf {pk}}(\mu ;r)\) will be used to represent the encryption of a bit\(\mu \) using randomnessr.

• Decryption. The algorithm\(\mu ^*\leftarrow \)\(\mathsf {PKE.Dec}\)\(_{\mathsf {sk}}(c)\) takes the secret key\(\mathsf {sk}\) and a ciphertextc and outputs a message\(\mu ^*\in \{0, 1\}\).

Obviously we require that\(\mu =\)\(\mathsf {PKE.Dec}\)\(_{\mathsf {sk}}(\)\(\mathsf {PKE.Enc}\)\(_{\mathsf {pk}}(\mu ))\)

Definition A.5

(CPA Security for PKE). A scheme\(\mathsf {PKE}\) is IND-CPA secure if for an infinite\(\varLambda \subseteq \mathbb {N}\) we have

where\((\mathsf {pk},\mathsf {sk})\leftarrow \)\(\mathsf {PKE.Keygen}\)(\(1^{\lambda }\)).

Remark A.1

(Security for Multiple Messages). Notice that by a standard hybrid argument and LemmaA.1 we can prove that any scheme secure according to DefinitionA.5 is also secure for multiple messages (i.e. the two sequences of encryptions bit by bit of two bit strings are computationally indistinguishable). We will use this fact in the constructions in Sect. 4, but we do not provide the formal definition for this type of security. We refer the reader to 5.4.2 in [Gol09].

Somewhat Homomorphic Encryption. A public-key encryption scheme is said to be homomorphic if there is an additional algorithm\(\mathsf {Eval}\) which takes a input the public key\(\mathsf {pk}\), the representation of a function\(f:\{0, 1\}^l\rightarrow \{0, 1\}\) and a set ofl ciphertexts\(c_1,\ldots ,c_l\), and outputs a ciphertext\(c_f\)^Footnote19.

We proceed to define the homomorphism property. The next notion of\(\mathcal {C}\)-homomorphism is sometimes also referred to as “somewhat homomorphism”.

Definition A.6

(\(\mathcal {C}\)-homomorphism). Let\(\mathcal {C}\) be a class of functions (together with their respective representations). An encryption scheme\(\mathsf {PKE}\) is\(\mathcal {C}\)-homomorphic (or, homomorphic for the class\(\mathcal {C}\)) if for every function\(f_\lambda \) where\(f_\lambda \in \mathcal {F} \{f_{\lambda }\}_{\lambda \in \mathbb {N}} \in \mathcal {C}\) and respective inputs\(\mu _1,\dots ,\mu _n \in \{0, 1\}\) (where\(n = n(\lambda )\)), it holds that if\((\mathsf {pk}, \mathsf {sk}) \leftarrow \mathsf {PKE.Keygen}(1^{\lambda })\) and\(c_i \leftarrow \mathsf {PKE.Enc}_{\mathsf {pk}}(\mu _i)\) then

As usual we require the scheme to be non-trivial by requiring that the output of\(\mathsf {Eval}\) is compact:

Definition A.7

(Compactness). A homomorphic encryption scheme\(\mathsf {PKE}\) is compact if there exists a polynomials in\(\lambda \) such that the output length of\(\mathsf {Eval}\) is at most\(s(\lambda )\) bits long (regardless of the functionf being computed or the number of inputs).

Definition A.8

Let\(\mathcal {C}= \{\mathcal {C}_{\lambda }\}_{\lambda \in \mathbb {N}}\) of arithmetic circuits in\(\text {GF}(2)\). A scheme\(\mathsf {PKE}\) is leveled\(\mathcal {C}\)-homomorphic if it takes\(1^L\) as additional input in key generation, and can only evaluate depth-L arithmetic circuits from\(\mathcal {C}\). The bound\(s(\lambda )\) on the ciphertext must remain independent ofL.

1.4A.4 Verifiable Computation

In aVerifiable Computation scheme a Client uses an untrusted server to compute a functionf over an inputx. The goal is to prevent the Client from accepting an incorrect value\(y'\ne f(x)\). We require that the Client’s cost of running this protocol be smaller than the cost of computing the function on his own. The following definition is from [GGP10] which allows the client to run a possibly expensive pre-processing step.

Definition A.9

(Verifiable Computation Scheme). We define averifiable computation scheme as a quadruple of algorithms\(\mathcal{VC}= (\mathsf {VC.KeyGen},\)\(\mathsf {VC.ProbGen},\mathsf {VC.Compute},\mathsf {VC.Verify})\) where:

1. 1.

   \(\mathsf {VC.KeyGen}(f, 1^\lambda ) \rightarrow (\mathsf {pk}_{\mathsf {W}}, \mathsf {sk}_{\mathsf {D}})\): Based on the security parameter\(\lambda \), the randomizedkey generation algorithm generates a public key that encodes the target functionf, which is used by the Server to computef. It also computes a matching secret key, which is kept private by the Client.

2. 2.

   \(\mathsf {VC.ProbGen}_{\mathsf {sk}_{\mathsf {D}}}(x) \rightarrow (q_x,s_x)\): Theproblem generation algorithm uses the secret key\(\mathsf {sk}_{\mathsf {D}}\) to encode the function inputx as a public query\(q_x\) which is given to the Server to compute with, and a secret value\(s_x\) which is kept private by the Client.

3. 3.

   \(\mathsf {VC.Compute}_{\mathsf {pk}_{\mathsf {W}}}(q_x) \rightarrow a_x\): Using the Client’s public key and the encoded input, the Servercomputes an encoded version of the function’s output\(y = F(x)\).

4. 4.

   \(\mathsf {VC.Verify}_{\mathsf {sk}_{\mathsf {D}}}(s_x,a_x) \rightarrow y \cup \{ \bot \}\): Using the secret key\(\mathsf {sk}_{\mathsf {D}}\) and the secret “decoding”\(s_x\), theverification algorithm converts the worker’s encoded output into the output of the function, e.g.,\(y = f(x)\) or outputs\(\bot \) indicating that\(a_x\) does not represent the valid output off onx.

The scheme should be complete, i.e. an honest Server should (almost) always return the correct value.

Definition A.10

(Completeness). A delegation scheme\(\mathcal{VC}\), with\(\mathcal{VC}= (\mathsf {VC.KeyGen},\mathsf {VC.ProbGen},\mathsf {VC.Compute},\mathsf {VC.Verify})\), hasoverwhelming completeness for a class of functions\(\mathcal {C}\) if there is a function\(\nu (n) = \mathsf {neg}(\lambda )\) such that for infinitely many values of\(\lambda \), if\(f_\lambda \in \mathcal {F} \in \mathcal {C}\), then for all inputsx the following holds with probability at least\(1-\nu (n)\):\((\mathsf {pk}_{\mathsf {W}}, \mathsf {sk}_{\mathsf {D}}) \leftarrow \mathsf {VC.KeyGen}(f_\lambda , \lambda )\),\((q_x,s_x) \leftarrow \mathsf {VC.ProbGen}_{\mathsf {sk}_{\mathsf {D}}}(x)\) and\(a_x\leftarrow \mathsf {VC.Compute}_{\mathsf {pk}_{\mathsf {W}}}(q_x)\) then\(y=f_{\lambda }(x) \leftarrow \mathsf {VC.Verify}_{\mathsf {sk}_{\mathsf {D}}}(s_x,a_x)\).

To define soundness we consider an adversary who plays the role of a malicious Server who tries to convince the Client of an incorrect output\(y \ne f(x)\). The adversary is allowed to run the protocol on inputs of her choice, i.e. see thequeries\(q_{x_i}\) for adversarially chosen\(x_{i}\)’s before picking an inputx and attempt to cheat on that input. Because we are interested in the parallel complexity of the adversary we distinguish between two parametersl andm. The adversary is allowed to dol rounds of adaptive queries, and in each round she queriesm inputs. Jumping ahead, because our adversaries are restricted to\(\mathsf {NC}^1\) circuits, we will have to boundl with a constant, but we will be able to keepm polynomially large.

Remark A.2

In the experiment above the adversary “tries to cheat” on the last input presented in the last round of queries (i.e.\(x_{lm}\)). This is without loss of generality. In fact, assume the adversary aimed at cheating on an input presented before roundl, then with one additional round it could present that same input once more as the last of the batch in that round.

Definition A.11

(Soundness). We say that a verifiable computation scheme is (l, m)-sound against a class\(\mathcal {A}\) of adversaries if there exists a negligible function\(\mathsf {neg}(\lambda )\), such that for all\(A = \{A_\lambda \}_\lambda \in \mathcal {A}\), and for infinitely many\(\lambda \) we have that

Assume the functionf we are trying to compute belongs to a class\(\mathcal {C}\) which is smaller than\(\mathcal {A}\). Then our definition guarantees that the “cost” of cheating is higher than the cost of honestly computingf and engaging in the Verifiable Computation protocol\(\mathcal {VC}\). Jumping ahead, our scheme will allow us to compute the class\(\mathcal {C}=\mathsf {AC}^0[2]\) against the class of adversaries\(\mathcal {A}=\mathsf {NC}^1\).

Efficiency The last thing to consider is the efficiency of a VC protocol. Here we focus on the time complexity of computing the functionf. Letn be the number of input bits, andm be the number of output bits, andS be the size of the circuit computingf.

• A verifiable computation scheme\(\mathcal{VC}\) isclient-efficient if circuit sizes of\(\mathsf {VC.ProbGen}\) and\(\mathsf {VC.Verify}\) areo(S). We say that it islinear-client if those sizes are\(O({\mathsf {poly}}(\lambda )(n + m))\).

• A verifiable computation scheme\(\mathcal{VC}\) isserver-efficient if the circuit size of\(\mathsf {VC.Compute}\) is\(O({\mathsf {poly}}(\lambda )S)\).

We note that the key generation protocol\(\mathsf {VC.KeyGen}\) can be expensive, and indeed in our protocol (as in [GGP10,CKV10,AIK10]) its cost is the same as computingf – this is OK as\(\mathsf {VC.KeyGen}\) is only invoked once per function, and the cost can be amortized over several computations off.

B Proofs for Homomorphic Encryption Constructions

1.1B.1 Constant Multiplicative Depth

Lemma B.1

The construction of\(\mathsf {HE}\) (Sect. 3.1) satisfies Eq. 1 (ibid).

Proof

For homomorphic addition:

where\(\mu _i\) is the plaintext corresponding to\(\mathbf {v}_i\).

For homomorphic multiplication:

where in the third and fourth equality we used respectively Eq. 1 and the definition of\(h_{i,j}\), and\(\mu , \mu '\) are the plaintexts corresponding to\(\mathbf {v}\)\(\mathbf {v}'\) respectively.

   \(\square \)

Theorem B.1

(Security). The scheme\(\mathsf {HE}\) is\(\text {CPA}\) secure against\(\mathsf {NC}^1\) adversaries (Definition A.5) under the assumption\(\mathsf {NC}^1 \subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}\).

Proof

We are going to prove that there exists infinite\(\varLambda \subseteq \mathbb {N}\) such that\((\mathsf {pk},\mathsf {evk}, \mathsf {HE.Enc}_{\mathsf {pk}}(0)) \sim _{\varLambda }(\mathsf {pk},\mathsf {evk}, \mathsf {HE.Enc}_{\mathsf {pk}}(1))\).

When using the notations\(\mathbf {M}^{\mathcal {\text {f}}}\) and\(\mathbf {M}^{\text {kg}}\) we will always denote matrices distributed respectively according to\(\mathcal {D}^{\text {f}}_{\lambda }\) and\(\mathcal {D}^{\text {kg}}\), where\(\mathcal {D}^{\text {f}}_{\lambda }\) and\(\mathcal {D}^{\text {kg}}\) are the distributions defined in Lemma3.1.

We will define the (randomized) encoding procedure\(\mathsf {E}: \{0, 1\}^{\lambda \times \lambda } \rightarrow \{0, 1\}^{\lambda }\) defined as

wherer is uniformly distributed in\(\{0, 1\}^{\lambda }\). The functions we will pass to\(\mathsf {E}\) will be distributed either according to\(\mathbf {M}^{\text {kg}}\) or\(\mathbf {M}^{\mathcal {\text {f}}}\). Notice that:(i)\(\mathsf {E}(\mathbf {M}^{\text {kg}}, b)\) is distributed identically to\(\mathsf {HE.Enc}_{\mathsf {pk}}(b)\);(ii)\(\mathsf {E}(\mathbf {M}^{\mathcal {\text {f}}}, b)\) corresponds to the uniform distribution over\(\{0, 1\}^{\lambda }\) because (by Lemma3.1)\(\mathbf {M}^{\mathcal {\text {f}}}\) has full rank and hence\({\mathbf {r}}^{\intercal }\mathbf {M}^{\mathcal {\text {f}}}\) must be uniformly random.

We will denote with\(\mathbf {M}^{\text {kg}}_1, \dots , \mathbf {M}^{\text {kg}}_{L}\) the matrices\(\mathbf {M}_1, \dots , \mathbf {M}_{L}\) used to construct the evaluation key in\(\mathsf {HE.Keygen}\) (see definition). Recall these matrices are distributed according to\(\mathcal {D}^{\text {kg}}\) as in Lemma3.1.

We will also define the following vectors:

where\(\mathbf {k}_{\ell }\) is defined as in\(\mathsf {HE.Keygen}\) and the matrices in input to\(\mathsf {E}\) will be clear from the context. Notice that all the elements of\(\mathbf {\alpha }^{\text {kg}}_{\ell }\) are encryptions, whereas all the elements of\(\mathbf {\alpha }^{\text {f}}_{\ell }\) are uniformly distributed.

We will use a standard hybrid argument. Each of our hybrids is parametrized by a bitb. This bit informally marks whether the hybrid contains an element indistinguishable from an encryption ofb.

• where\(\mathbf {M}^{\text {kg}}_0\) corresponds to the public key of our scheme. Notice that\(\mathbf {\alpha }^{\text {kg}}_{\ell } \equiv \{ \varvec{a}_{\ell , i, j} \ | \ i,j \in [\lambda ] \}\) where\( \varvec{a}_{\ell , i, j}\) is as defined in\(\mathsf {HE.Keygen}\). This hybrid corresponds to the distribution\((\mathsf {pk},\mathsf {evk}, \mathsf {HE.Enc}_{\mathsf {pk}}(b))\).

• . The only difference from\(\mathcal {E}\) is in the first two components where we replaced the actual public key and ciphertext with a full rank matrix distributed according to\(\mathcal {D}^{\text {f}}_{\lambda }\) and a random vector of bits.

• For\(\ell \in [L]\) we define

  

We will proceed proving that

through a series of smaller claims. In the remainder of the proof\(\varLambda \) refers to the set in Lemma3.1.

• \(\mathcal {E}^{0}\sim _{\varLambda }\mathcal {H}^{0}_0\): if this were not the case we would be able to distinguish\(\mathbf {M}^{\text {kg}}_0\) from\(\mathbf {M}^{\mathcal {\text {f}}}_0\) for some of the values in the set\(\varLambda \) thus contradicting Lemma3.1.

• \(\mathcal {H}^{0}_{\ell -1} \sim _{\varLambda }\mathcal {H}^{0}_{\ell }\) for\(\ell \in [L]\): assume by contradiction this statement is false for some\(\ell \in [L]\). That is

  $$\begin{aligned}&(\mathbf {M}^{\mathcal {\text {f}}}_0, \mathsf {E}(\mathbf {M}^{\mathcal {\text {f}}}_0, b), \mathbf {\alpha }^{\text {f}}_1, \dots , \mathbf {\alpha }^{\text {f}}_{\ell -1}, \mathbf {\alpha }^{\text {kg}}_{\ell }, \dots , \mathbf {\alpha }^{\text {kg}}_L)&\\&\qquad \qquad \qquad \qquad \not \sim _{\varLambda }&\\&(\mathbf {M}^{\mathcal {\text {f}}}_0, \mathsf {E}(\mathbf {M}^{\mathcal {\text {f}}}_0, b), \mathbf {\alpha }^{\text {f}}_1, \dots , \mathbf {\alpha }^{\text {f}}_{\ell }, \mathbf {\alpha }^{\text {kg}}_{\ell +1}, \dots , \mathbf {\alpha }^{\text {kg}}_L)&\, \end{aligned}$$

  Recall that, by definition, the elements of\(\mathbf {\alpha }^{\text {kg}}_{\ell }\) are all encryptions whereas the elements of\(\mathbf {\alpha }^{\text {f}}_{\ell }\) are all randomly distributed values. This contradicts the semantic security of the scheme\(\mathsf {PKE}\) (by a standard hybrid argument on the number of ciphertexts).

• \(\mathcal {H}^{0}_{L} \sim _{\varLambda }\mathcal {H}^1_{L}\): the distributions associated to these two hybrids are identical. In fact, notice the only difference between these two hybrids is in the second component:\(\mathsf {E}(\mathbf {M}^{\mathcal {\text {f}}}, 0)\) in\(\mathcal {H}^{0}_{L}\) and\(\mathsf {E}(\mathbf {M}^{\mathcal {\text {f}}}, 1)\) in\(\mathcal {H}^1_{L}\). As observed above\(\mathsf {E}(\mathbf {M}^{\mathcal {\text {f}}}, b)\) is uniformly distributed, which proves the claim.

All the claims above can be proven analogously for\(\mathcal {E}^1, \mathcal {H}^1_{0}\) and\(\mathcal {H}^1_{\ell }\)-s.

   \(\square \)

1.2B.2 Quasi-constant Multiplicative Depth

Lemma B.2

([Raz87]). LetC be an\(\mathsf {AC}^0_{\text {Q}}[2]\) circuit of depthd. Then there exists a randomized circuit\(C' \in \mathsf {AC}^0_{\text {CM}}[2]\) such that, for all x,

where\(\epsilon = O(1)\). The circuit\(C'\) usesO(n) random bits and its representation can be computed in\(\mathsf {NC}^0\) from a representation ofC.

Proof

Consider a circuit\(C \in \mathsf {AC}^0_{\text {Q}}[2]\) and let\(K = O(1)\) be the total number of\(\mathsf {AND}\) and\(\mathsf {OR}\) gates with non-constant fan-in. We can replace every\(\mathsf {OR}\) gate of fan-in\(m = \omega (1)\) with a randomized “gadget” that takes in inputm additional random bits and computes the function

This function can be implemented in constant multiplicative depth with one\(\mathsf {XOR}\) gate andm\(\mathsf {AND}\) gates of fan-in two. Let\(\mathbf {x} = (x_1,\dots ,x_m)\) and\(\mathbf {r} = (r_1,\dots , r_m)\). The probabilistic gadget\(\hat{g}_{\mathsf {OR}}\) has one-sided error. if\(x_i = 0\) (i.e. if\(\mathsf {OR}(\mathbf {x}) = 0\)) then\(\Pr [\hat{g}_{\mathsf {OR}}(\mathbf {x}; \mathbf {r}) = 0] = 1\); otherwise\(\Pr [\hat{g}_{\mathsf {OR}}(\mathbf {x}; \mathbf {r}) = 1] = \frac{1}{2}\).

In a similar fashion, we can replace every unbounded fan-in\(\mathsf {AND}\) gate with a randomized gadget in computing

This gadget can also be implemented in constant-multiplicative depth and has one-sided error 1 / 2. Finally, by applying the union bound we can observe that\(\Pr [C'(x) \not = C(x)] \le \epsilon \) for a constant\(\epsilon \), because we have only a constant number of gates to be replaced with gadgets for\(\hat{g}_{\mathsf {OR}}\) or\(\hat{g}_{\mathsf {AND}}\).

We only provide the intuition for why the transformations above can be carried out in\(\mathsf {NC}^0\). Assume the encoding of a circuit as a list of gates in the form\((g, t_g, in_1, \dots , in_m)\) whereg andt are respectively the index of the output wire of the gate and its type (possibly of the form “input” or “random input”) and the\(in_i\)-s are the indices of the input wire ofg. The transformation fromC to\(C'\) needs to simply copy all the items in the list except for the gates of unbounded fan-in. We will assume the encoding conventions ofC always puts these gates at the end of the list^Footnote20. For each of such gates the transformation circuit needs to: add appropriate\(r_1,\dots , r_m\) to the list, addm\(\mathsf {AND}\) gates and one\(\mathsf {XOR}\), possibly (if we are transforming an\(\mathsf {AND}\) gate) add negation gates. All this can be carried out based on wire connections and the type of the gate (a constant-size string) and thus in\(\mathsf {NC}^0\).

   \(\square \)

In the construction above, we built\(C'\) by replacing every gate\(g \in {\mathsf {S}}_{\omega (1)}(C)\) (as in DefinitionA.4) with a (randomized) gadget\(G_g\). The output of each of these gadgets will be useful in order to keep the low complexity of the decryption algorithm in our next homomorphic encryption scheme. We shall use an “expanded” version of\(C'\), the multi-output circuit\(C'_{exp}\).

Definition B.1

(Expanded Approximating Function). LetC be a circuit in\(\mathsf {AC}^0_{\text {Q}}[2]\) and let\(C'\) be a circuit as in the proof of LemmaB.2. We denote by\(G_g(\mathbf {x}; \mathbf {r})\) the output of the gadget\(G_g\) when\(C'\) is evaluated on inputs\((\mathbf {x}; \mathbf {r})\). On input\((\mathbf {x}; \mathbf {r})\), the multi-output circuit\(C'_{exp}\) output\(C'(\mathbf {x};\mathbf {r})\) together with the outputs of theO(1) gadgets\(G_g\) for each\(g \in {\mathsf {S}}_{\omega (1)}(C)\). Finally, we denote with\(\mathsf {GenApproxFun}\) the algorithm computing a representation of\(C'_{exp}\) from a representation ofC.

Lemma B.3

There exists a deterministic algorithm\({\mathsf {DecodeApprox}}\) computable in\(\mathsf {AC}^0[2]\) with the following properties. For every circuitC in\(\mathsf {AC}^0_{\text {Q}}[2]\) computing the functionf, there exists\(\mathbf {aux}_f\in \{0, 1\}^{O(1)}\) such that for all\(\mathbf {x} \in \{0, 1\}^n\)

where\(C'\) is an approximating circuit as in LemmaB.2, the probability is taken over the uniformly distributed bit vectors\(\mathbf {r}^{(i)}\)-s for\(i \in [s]\),\(C'_{exp}\) is as in DefinitionB.1. Finally, there exists a function\({\mathsf {GenDecodeAux}}\) that computes\(\mathbf {aux}_f\) from a representation ofC in\(\mathsf {NC}^0\).

Proof

Before we provide a construction for\({\mathsf {DecodeApprox}}\), let us observe how we can amplify the error of\(C'\). Consider for example a gadget\(\hat{g}_{\mathsf {OR}}\) constructed as in the proof of LemmaB.2, approximating an\(\mathsf {OR}\) gate inC. If we repeat the execution of the gadgets times, every time using fresh random bit vectors\(\mathbf {r}'^{(1)},\dots , \mathbf {r}'^{(s)}\), then we can correctly compute\(\mathsf {OR}(\mathbf {x}')\) with overwhelming probability. Define. Clearly\(\Pr [h_{\mathsf {OR}}(\mathbf {x}'; \mathbf {r}'^{(1)},\dots , \mathbf {r}'^{(s)}) = \mathsf {OR}(\mathbf {x}')] \ge 1 - 2^{-s}\). In a similar fashion we can define.

If\(C'\) were composed by a single gadget\(\hat{g}_{\mathsf {OR}}\) (resp.\(\hat{g}_{\mathsf {AND}}\)) we could just let\({\mathsf {DecodeApprox}}\) be the same as\(h_{\mathsf {OR}}\) (resp.\(h_{\mathsf {AND}}\)) and we would be done. To deal with multiple gadgets, however, we need a more general approach. Consider some ordering on the gates in\({\mathsf {S}}_{\omega (1)}\), i.e. let\({\mathsf {S}}_{\omega (1)} = \{g_1, \dots , g_K\}\). For sake of presentation, assume there are only gadgets approximating\(\mathsf {OR}\) gates and let us temporarily ignore\(\mathbf {aux}_f\). We can write each of the\(C'_{exp}(\mathbf {x}; \mathbf {r}^{(j)})\) input to\({\mathsf {DecodeApprox}}\) as\((z^{(j)}, y_1^{(j)}, \dots , y_K^{(j)})\) where\(z^{(j)}\) is the output of\(C'(\mathbf {x}, \mathbf {r}^{(j)})\) and\(y_i^{(j)}\) is the output of the gadget corresponding to\(g_i\) when provided random bits from\(\mathbf {r}^{(j)}\). Define\(y_i^*\) as. We then let the output of\({\mathsf {DecodeApprox}}\) be\(z^{\hat{j}}\) where\(\hat{j}\) is such that for all\(i \in [K]\) it is the case that\(y_i^{(\hat{j})} = y_i^*\). We let\({\mathsf {DecodeApprox}}\) output an arbitrary value if such\(\hat{j}\) does not exist. However we can prove (LemmaB.4) that\(\hat{j}\) exists with overwhelming probability. Denote by\(V_{C,\mathbf {x}}(g_i)\) the value of the output wire of\(g_i\) when evaluatingC on input\(\mathbf {x}\). Clearly, by construction of\(C'_{exp}\),\(\Pr [z^{(\hat{j})} = C(\mathbf {x})] \ge \Pr [ \forall i \ y_i^{(\hat{j})}= V_{C,\mathbf {x}}(g_i)]\) and by the proof of LemmaB.4 we can show that the right hand side probability is overwhelming.

To generalize this same approach to the scenario including both\(\mathsf {OR}\) and\(\mathsf {AND}\) gadgets we let the string\(\mathbf {aux}_f\) include information on the type of gates in\({\mathsf {S}}_{\omega (1)}\). This way\({\mathsf {DecodeApprox}}\) can use\(\hat{g}_{\mathsf {OR}}\) or\(\hat{g}_{\mathsf {AND}}\) accordingly. Clearly the representation of\(\mathbf {aux}_f\) can be computed by a representation ofC in\(\mathsf {NC}^0\).

   \(\square \)

Lemma B.4

\( \Pr [\exists \hat{j}\ \forall i \ y_i^{(\hat{j})}= y_i^*] \ge 1 - \mathsf {neg}(s)\).

Proof

Let\({\mathsf {S}}_{\omega (1)} = \{g_1, \dots , g_K\}\) and\(V_{C,\mathbf {x}}(g_i)\) for\(i \in [K]\) defined as in the proof of LemmaB.3. We have that

We now bound each of the two probabilities in the last product. Denote by\(\mathcal {E}_{i,j}\) the event\(``y_i^{(j)}= V_{C,\mathbf {x}}(g_i)"\) and by\(\overline{\mathcal {E}}_{i,j}\) its negation. Observe that

Remark B.1

(Efficiency of\(\mathsf {HE}'\)in Sect. 3.3). Given in input a functionf not necessarily of constant multiplicative depth,\(\mathsf {GenApproxFun}\) returns a function\(f'\) of constant multiplicative depth that approximates it. As stated in LemmaB.2,\(\mathsf {GenApproxFun}\) is computable in\(\mathsf {NC}^0\) and so is\({\mathsf {GenDecodeAux}}\). The function\(\mathsf {SampleAuxRandomness}\) in\(\mathsf {AC}^0_{\text {CM}}[2]\) and\(\mathsf {EvalApprox}\) makes parallel invocations to\(\mathsf {HE.Eval}\) which is computable in\(\mathsf {AC}^0_{\text {CM}}[2]\) when provided in input a function in\(\mathsf {AC}^0_{\text {CM}}[2]\) (Theorem3.3). This fact will be useful when showing the completeness of the verifiable computation constructions in Sect. 4.

C Proofs for Verifiable Computation Constructions

The following two auxiliary lemmas guarantee that the constructions in Figs. 2 and3 are computable in\(\mathsf {AC}^0[2]\). We refer the reader to [Hag91,MV91] for the proof LemmaC.1.

Lemma C.1

[Hag91,MV91] There are uniform\(\mathsf {AC}^0\) circuits\(C: \{0, 1\}^{{\mathsf {poly}}(l)}\rightarrow [l]^l\) of size\({\mathsf {poly}}(l)\) and depthO(1) whose output distribution have statistical distance\(\le 2^{-l}\) from the uniform distribution over permutations of [l].

Lemma C.2

There are uniform\(\mathsf {AC}^0[2]\) circuits\(C: [l]^l \times \{0, 1\}^l \rightarrow \{0, 1\}^l\) of size\(O(l^2)\) where\(C(\pi , (x_1,\dots , x_l)) = (\pi (1),\dots ,\pi (l))\) and\(\pi \) is a permutation.

Proof

Let\(\mathbf {x} = (x_1,\dots ,x_l)\) the bits to permute and let\(\pi \) be a permutation If\(\pi \) is represented as a permutation matrix with rows\(\mathbf {r}_1,\dots ,\mathbf {r}_l\), we can permute\(\mathbf {x}\) by simply performingl parallel inner products\(\langle \mathbf {x} \, , \mathbf {r}_i \rangle \)-s, which is in\(\mathsf {AC}^0[2]\). We now describe how to generate the permutation matrix from a binary representations\(x_1,\dots ,x_{\mathsf {lg}(l)}\) of the integers in [l]. Let\(f_i : \{0, 1\}^{\mathsf {lg}(l)} \rightarrow \{0, 1\}^l\) be the function that computes thei-th row of the permutation matrix. We can define\(f_i\) as follows:

where\([i-1]_2\) is the binary representation of\(i-1\) and\(\mathsf {eq}\) returns 1 if its two inputs (each of lenght\(\mathsf {lg}(l)\)) are equal. The function\(f_i\) is clearly in\(\mathsf {AC}^0[2]\).

   \(\square \)

1.1C.1 One-time scheme

Remark C.1

(On deterministic homomorphic evaluation). As pointed out in [CKV10], one requirement for the approach in Fig. 2 to work is for the homomorphic evaluation to be deterministic. We point out that once\({\mathbf {\hat{r}}_{\text {aux}}}\) are fixed once and for all the homomorphic evaluation in\(\mathsf {VC.Compute}\) is deterministic.

Lemma C.3

(Completeness of\(\mathcal{VC}\)). The verifiable computation scheme\(\mathcal{VC}\) in Fig. 2 has overwhelming completeness (DefinitionA.10) for the class\(\mathsf {AC}^0_{\text {Q}}[2]\).

Proof

The proof is straightforward and stems directly from the homomorphic properties of\(\mathsf {HE'}\) (Theorem3.4). In fact, by construction and by definition of\(\mathsf {HE'}\) (Sect. 3.3), the distribution of the\(\hat{w}_i\)-s is identical to\(\mathsf {HE'.Eval}_{\mathsf {pk}}(f, \hat{r}_i)\). Analogously, the distribution of\(\hat{y}_i\)-s is identical to\(\mathsf {HE'.Eval}_{\mathsf {pk}}(f, \hat{z}_i)\).

   \(\square \)

Lemma C.4

(One-time Soundness). Under the assumption that\(\mathsf {NC}^1 \subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}\) the scheme in Fig. 2 is (1, 1)-sound (one time secure) against\(\mathsf {NC}^1\) adversaries whenever t is chosen to be\(\omega (\log (\lambda ))\).

Proof

We follow the same proof structure as in the proof of Lemma 12 in [CKV10]. We will keep part of the analysis informal, emphasizing why this proof still works for low-depth circuits. We refer the reader to [CKV10] for further details.

The following observation will be crucial in the rest of the proof. Notice that, by construction and by definition of\(\mathsf {HE'}\) (Sect. 3.3), the distribution of the\(\hat{w}_i\)-s is identical to\(\mathsf {HE'.Eval}_{\mathsf {pk}}(f, \hat{r}_i)\). Analogously, the distribution of\(\hat{y}_i\)-s is identical to\(\mathsf {HE'.Eval}_{\mathsf {pk}}(f, \hat{z}_i)\).

Consider an\(\mathsf {NC}^1\) adversary\(\mathcal {A}^*\) that cheats with non-negligible probability in the one-time security experiment\(\mathbf{Exp}^{\mathsf {Verif}}_{A}[\mathcal{VC}, f, \lambda , 1,1]\) (DefinitionA.11). Let\((\hat{r}_1,\dots ,\hat{r}_{t})\) be the independent copies of\(\mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(\bar{0})\) and\((\hat{r}_{t+1},\dots ,\hat{r}_{2t})\) thet independent copies of\(\mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(x)\) as above. Whenever the verification algorithm accepts, the adversary must have responded correctly on\(\hat{r}_1,...,\hat{r}_t\) and incorrectly (and consistently) on\(\hat{r}_{t+1},\dots ,\hat{r}_{2t}\). Our goal is to bound the probability that the adversary succeeds in doing that.

First, notice that the view of the adversary is\((\mathsf {pk}_{\mathsf {W}}, \hat{r}_1,\dots ,\hat{r}_{2t})\), and identical to\((\mathsf {pk}_{\mathsf {W}}, \mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(\bar{0})^t, \mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(x)^t)\). By semantic security of the homomorphic encryption scheme, there exists an infinitely large set of parameters\(\varLambda \) such that\( (\mathsf {pk}_{\mathsf {W}}, \mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(\bar{0})^t, \mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(x)^t) \sim _{\varLambda }(\mathsf {pk}_{\mathsf {W}}, \mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(\bar{0})^{2t})\). Consider a modified game where the adversary receives\((\mathsf {pk}_{\mathsf {W}}, \mathsf {HE'.Enc}_{\mathsf {pk}_{\mathsf {W}}}(\bar{0})^{2t})\). Denote byp the probability that the adversary succeeds in this game. By computational indistinguishability we have

for all\(\lambda \in \varLambda \). This inequality holds because we can test in\(\mathsf {NC}^1\) whether\(\mathcal {A}^*\) cheats only on\((\hat{r}_{t+1},\dots ,\hat{r}_{2t})\). Therefore, if the adversary’s behavior differed significantly between the two games, one would be able to break the semantic security of the homomorphic scheme. Here we made use of the third fact in Lemma A.1.

We now proceed to upper boundp. Observe that

where the\(\hat{z}_{\pi (i)}\)-s are defined as in Fig. 2. Because of LemmaC.1 that the distribution of\(\pi \) is statistically indistinguishable from that of a uniformly random permutation. Also, observe that the answers\(\hat{y}_i\) of the adversary are independent of\(\pi \). We can then conclude that\(p \le \frac{1}{\left( {\begin{array}{c}2t\\ t\end{array}}\right) } + \mathsf {neg}(t)\), which concludes the security analysis.

   \(\square \)

1.2C.2 Reusable scheme

Transformation from one-time\(\mathcal {VC}\) scheme to areusable\(\mathcal {VC}\) scheme

Full size image

The following is a proof of the completeness of\(\overline{\mathcal{VC}}\).

Proof (Of Theorem 4.1)

The completeness of the reusable scheme follows directly from the completeness of the one-time scheme\(\mathcal{VC}\) and the homomorphic properties of\(\mathsf {HE}\). Notice that we can use\(\mathsf {HE.Eval}\) to homomorphically compute\(\mathsf {VC.Compute}\) as the latter carries out a computation in\(\mathsf {AC}^0_{\text {CM}}[2]\) (although it isapproximating a computation in\(\mathsf {AC}^0_{\text {Q}}[2]\)).

   \(\square \)

The following is a restatement of Theorem4.2.

Theorem C.1

(Many-Times Soundness). Under the assumption that\(\mathsf {NC}^1 \subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}\) the scheme\(\overline{\mathcal{VC}}\) in Fig. 3 is\((O(1),{\mathsf {poly}}(\lambda ))\)-sound (many-times secure) against\(\mathsf {NC}^1\) adversaries whenever t is chosen to be\(\omega (\log (\lambda ))\) in the underlying scheme\(\mathcal{VC}\).

Proof

By LemmaC.4 there exists an infinite set\(\varLambda \subseteq \mathbb {N}\) of security parameters for which\(\mathcal{VC}\) “is secure”. By the proof of LemmaC.4, this set is also the set of parameters where the somewhat homomorphic encryption scheme\(\mathsf {HE}\) “is secure”. We will show that for all values in this same set\(\varLambda \), the probability of success of any\(\mathsf {NC}^1\) adversary in\(\mathbf{Exp}^{\mathsf {Verif}}_{A}[\overline{\mathcal{VC}}, f, \lambda , O(1), {\mathsf {poly}}(\lambda )]\) is negligible.

Assume by contradiction there exists an\(\mathsf {NC}^1\) adversary\(\mathcal {A}^*\) that achieves non-negligible advantage in\(\mathbf{Exp}^{\mathsf {Verif}}_{A}[\overline{\mathcal{VC}}, f, \lambda , O(1), {\mathsf {poly}}(\lambda )]\) for some\(\lambda \in \varLambda \).

Claim: If\(\overline{\mathcal{VC}}\)is not secure for some\(\lambda ^* \in \varLambda \)then we can break the one-time security of\(\mathcal{VC}\). Let\(l = O(1)\) be the number of rounds in the many-time soundness experiment for\(\overline{\mathcal{VC}}\). Consider the following\(\mathsf {NC}^1\) adversary\(\mathcal {A}_1\) for the experiment\(\mathbf{Exp}^{\mathsf {Verif}}_{A}[\mathcal{VC}, f, \lambda , 1,1]\):

• \(\mathcal {A}_1\) obtains a pair a public key\(\mathsf {pk}_{\mathsf {W}}\) and sends it to\(\mathcal {A}^*\);

• For all rounds\(i \in \{1,\dots ,l-1 \}\),\(\mathcal {A}_1\) replies to\(\mathcal {A}^*\) queries by generating a fresh pair of keys\((\mathsf {pk}, \mathsf {sk})\) and sending back encryptions of\(\mathsf {HE.Enc}_{\mathsf {pk}}(\bar{0})\);

• At roundl,\(\mathcal {A}_1\) responds to all input queries but the last one as above. This, by experiment definition, is the input where\(\mathcal {A}^*\) will try to cheat; we denote this input by\(x^*\). Now\(\mathcal {A}_1\) sends\(x^*\) as the only input query in the one-time security experiment and will receive back\(q^*\). It will then obtain a fresh pair of keys\((\mathsf {pk}^*, \mathsf {sk}^*)\) and send\(\mathsf {HE.Enc}_{\mathsf {pk}^*}(q^*)\) to\(\mathcal {A}^*\).

• \(\mathcal {A}^*\) will respond with\(\hat{a}^*\) and\(\mathcal {A}_1\) will send\(\mathsf {HE.Dec}_{\mathsf {sk}^*}(\hat{a})\) to the challenger for one-time security experiment.

The advantage of\(\mathcal {A}_1\) depends on how likely is\(\mathcal {A}^*\) can successfully cheat in that interaction. Letp be the advantage of\(\mathcal {A}_1\) in the one-time security experiment. Clearly, ifp is close to the advantage of\(\mathcal {A}^*\) in the many-times security experiment\(\mathcal {A}_1\) breaks the security of the one-time scheme.

Claim: the advantage of\(\mathcal {A}_1\)is negligibly close to that of\(\mathcal {A}^*\)in the many-time security game for security parameter\(\lambda ^*\). We can prove this by relying on the semantic security of the homomorphic encryption and on a hybrid argument.

Let\(L = lm\), the total number of input queries in the many-times security experiment. We now define the hybrids\(H^{(j)}\) with\(j \in \{0, \dots , L\}\). We define\(H^{(0)}\) to be the exactly the many-time security experiment. For\(j \in [L]\) we define\(H^{(j)}\) to be an experiment where we respond to input queries with\(\mathsf {HE.Enc}_{\mathsf {pk}_f}(\bar{0})\) where\(\mathsf {pk}_f\) is a fresh public key up to input queryj and behaves the many-time security experiment from input query\(j+1\) on. Notice that\(H^{(L)}\) corresponds to the interaction with\(\mathcal {A}_1\) above.

Denote by\(A^{(j)}\) the output distribution of\(\mathcal {A}^*\) when interacting with\(H^{(j)}\). Intuitively, if the advantage of the\(\mathcal {A}_1\) in the one-time experiment is significantly different from the advantage of\(\mathcal {A}^*\) in the many-times security games, then\(A^{(0)}\) and\(A^{(L)}\) are not\(\varLambda \)-computationally indistinguishable. Therefore (by LemmaA.1), there exists\(j \in [L]\) such that\(A^{(j-1)} \not \sim _{\varLambda } A^{(j)}\).

Claim: If there exists\(j \in [L]\)such that\(A^{(j-1)} \not \sim _{\varLambda } A^{(j)}\)then we can break the semantic security of\(\mathsf {HE}\). Consider the following\(\mathsf {NC}^1\) adversary\(\mathcal {A}_{\text {CPA}}\) which receives in input a “challenge” public key\(\mathsf {pk}^*\).\(\mathcal {A}_{\text {CPA}}\) will interact with\(\mathcal {A}^*\) simulating\(H^{(j)}\) until receiving input query\(x_{j}\). At this point it will compute\(q_j\) from\(\mathsf {VC.ProbGen}(x_j)\) and send to the CPA challenger (see RemarkA.1)\(q_j\) and\(\bar{0}\), receiving back an encryption\(c^*\) of either message under the public key\(\mathsf {pk}^*\).\(\mathcal {A}_{\text {CPA}}\) will now send\((\mathsf {pk}^*, c^*)\) to\(\mathcal {A}^*\) and continue simulating\(H^{(j)}\) till the end of the experiment. The adversary\(\mathcal {A}_{\text {CPA}}\) will check whether\(\mathcal {A}^*\) cheated successfully at the end of the experiment and output (in the multiple-message CPA experiment) 1 if that is the case and 0 otherwise. This would allow\(\mathcal {A}_{\text {CPA}}\) to have a noticeable advantage in the experiment thus breaking the semantic security of\(\mathsf {HE}\).

   \(\square \)

D On Approaches Based on Randomized Encodings

A randomized encoding of a functionf is a randomized function\(\hat{f}\) such that for any inputx, the distribution of\(\hat{f}(x)\) revealsf(x), but nothing more aboutx. We observe that approaches based on low-depth information-theoretic affine randomized encodings (as constructed in [IK00a,IK02,AIK04] or as applied in [SYY99,AIK10,GGH+07]) may be used to obtain results similar to ours. Known ways to construct these tools, however, all seem to have significant limitations, which pushed us to look for different solutions.

Example Constructions. An example construction for homomorphic encryption: the encryptor could send to the evaluator a linearly homomorphic encryption of the inputs and the evaluator could reply with an affine (requiring only linear operations) randomized encoding off computed on the ciphertexts. Possible constructions for verifiable computation could be based on [AIK10] or using a constant-round variant of [GKR08] for\(\mathsf {NC}^1\) circuits together with the approach in [GGH+07].

Limitations of constructions from RE. Such approaches can yield homomorphic encryption for\(\mathsf {NC}^1\) circuits and verifiable computation in low-depth. Noticeably, such schemes would be (partly) implementable in\(\mathsf {NC}^0\) and the soundness of the (one-time) verifiable computation could hold unconditionally.

In our work, however, we are interested incompact homomorphic encryption schemes (where the ciphertexts do not grow in size with each homomorphic operation) and in verifiable computation schemes where the total (online) work of the verifier is approximately linear in the I/O size^Footnote21. When using currently known constructions the techniques mentioned above seem to fail in both respects. One reason for this is that having the verifier (resp. evaluator) compute (resp. send) aninformation-theoretic^Footnote22 randomized encoding would require verification time (resp. communication complexity) to be at best\(\varOmega (n^2)\) (resp.\(\varOmega (2^d)\), whered is the depth of the fan-in two evaluation circuit). These lower bounds refer to the complexity of known constructions for information-theoretic randomized encodings [AIK04], which stem from two main approaches: the branching-program based one in [IK00a] and the “Yao-like” in [IK02] (Sect. 3). The former constructs randomized encodings computable in time\(\varOmega (\ell ^2)\) and of the same size, where\(\ell \) is the size of the (polynomial-size) branching program describingf (the related approach in [GGH+07] has output size and computation time of\(\ell ^3\)). The latter describes randomized encodings of size\(2^d\) and computable in\(s^2\) for circuits of sizes and (logarithmic) depthd. The complexity of these encodings can be improved under the existence of PRGs with linear stretch (e.g. [AIK10] uses this fact to build verifiable computation with low online communication). Unfortunately it is not known how to build such primitives under the assumption\(\mathsf {NC}^1 \subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}\) [DVV16].

It would be worth investigating exactly the extent to which we can exploit such techniques in a context where low communication complexity and low sequential verification complexity are not constraints. We leave this as an open problem. We finally point out that some of these depth-reduction techniques can be applied to our results (naturally, with overheads similar to the ones pointed out above).

Reprints and permissions

© 2018 International Association for Cryptologic Research

Policies and ethics