---
title: "HELIOPOLIS: Verifiable Computation over Homomorphically Encrypted Data from Interactive Oracle Proofs is Practical"
authors: "Diego F. Aranha, Anamaria Costache, Antonio Guimarães, Eduardo Soria-Vazquez"
venue: "Advances in Cryptology – ASIACRYPT 2024, Kolkata"
source: "IACR ePrint 2023/1949 (author copy)"
source_version: 2024-08-15
canonical: https://antonioguimaraes.org/publications/heliopolis/
pdf: https://eprint.iacr.org/2023/1949.pdf
generator: scripts/fulltext.py (pdftotext)
---

# HELIOPOLIS: Verifiable Computation over Homomorphically Encrypted Data from Interactive Oracle Proofs is Practical

*Diego F. Aranha, Anamaria Costache, Antonio Guimarães, Eduardo Soria-Vazquez*. Advances in Cryptology – ASIACRYPT 2024, Kolkata.

> Automatic plain-text transcript of the author version, provided for search and AI assistants. Formulas, tables, figures and footnotes are not reproduced faithfully. Read and cite the paper: https://eprint.iacr.org/2023/1949.pdf

<!-- page 1 -->

HELIOPOLIS: Verifiable Computation over Homomorphically Encrypted Data from Interactive Oracle Proofs is Practical

Diego F. Aranha 1 , Anamaria Costache 2 , Antonio Guimarães 3 , and Eduardo Soria-Vazquez 4

Aarhus University, Denmark. NTNU, Norway. IMDEA Software Institute, Spain. Technology Innovation Institute, UAE.

Abstract. Homomorphic encryption (HE) enables computation on encrypted data, which in turn facilitates the outsourcing of computation on private data. However, HE offers no guarantee that the returned result was honestly computed by the cloud. In order to have such guarantee, it is necessary to add verifiable computation (VC) into the system. The most efficient recent works in VC over HE focus on verifying operations on the ciphertext space of the HE scheme, which usually lacks the algebraic structure that would make it compatible with existing VC systems. For example, multiplication of ciphertexts in the current most efficient HE schemes requires non-algebraic operations such as real division and rounding. Therefore, existing works for VC over HE have to either give up on those efficient HE schemes, or incur a large overhead (an amount of constraints proportional to the ciphertext ring’s size) in order to emulate these non-algebraic operations. In this work, we move away from that paradigm by placing the verification checks in the plaintext space of HE, all while the prover remains computing on ciphertexts. We achieve this by introducing a general transformation for Interactive Oracle Proofs (IOPs) to work over HE, whose result we denote as HE-IOPs. We apply this same transformation to the FRI [Ben-Sasson et al., ICALP 2018] IOP of proximity and we show how to compile HE-Reed Solomon-encoded IOPs and HE-δ-correlated-IOPs with HE-FRI into HE-IOPs. Furthermore, our construction is compatible with a prover that provides input in zero-knowledge, and only relies on building blocks that are plausibly quantum-safe. Aligning the security parameters of HE and FRI is a difficult task for which we introduce several optimizations. We demonstrate their efficiency with a proof-of-concept implementation and show that we can run FRI’s commit phase for 4096 encrypted Reed Solomon codewords with degree bound 2 11 in just 5.4 seconds (using 32 threads) on a c6i.metal instance using less than 4GB of memory. Verification takes just 12.3 milliseconds (single-threaded) for the same parameter set and can be reduced to just 5.6ms with parameters optimized for the verifier.

Introduction

There are many usability and economic benefits for citizens and companies to outsource data storage/processing to remote servers, but cloud computing brings significant integrity and privacy risks. Homomorphic Encryption (HE) has been referred to by many as the “holy grail” technology to address the privacy risks of outsourced computing. Since the first scheme introduced by Gentry in 2009 [Gen09b], numerous advances and improvements have followed [BGV12, Bra12, FV12, CGGI20, CKKS17]. In particular, a privacy-preserving variant of the use-case of Machine Learning as a Service (MLaaS) has been shown to be particularly suitable for HE by a recent line of work [BMMP18, BCCW19, BGBE19]. However, HE by itself does not guarantee the integrity of the computing party. Dealing with this issue falls within the scope of Verifiable Computation (VC), which describes a collection of techniques ensuring that the output returned by the cloud servers is indeed the honest result of

<!-- page 2 -->

applying the requested function to the designated data. On the other hand, VC on its own does not protect the privacy of the outsourced yet sensitive data from the clients. The cryptographic community realized that VC and HE are very complementary, since the limitations of the one are perfectly covered by the features of the other. Combining the two techniques is often referred to as “privacy-preserving verifiable computation" or “verifiable computation on encrypted data". The first solution was proposed by Gennaro, Gentry and Parno [GGP10] in 2010, and employs a heavy combination of Yao’s garbled circuit for an one-time verifiable computation together with HE to reuse the garbled circuit across many inputs. The later work of [FGP14] is efficient, but very limited in expressiveness. The use of homomorphic MACs limits the application to depth-1 circuits and requires to keep a secret verification key hidden from the prover, hence eliminating public verifiability. The work of [FNP20] improves the expressiveness of [FGP14], by allowing to efficiently compute circuits of (arbitrary) constant depth. Nevertheless, they only deal with a very narrow subset of inefficient HE schemes: a variant of BV [BV14], where the integer ciphertext modulus q matches the (prime) order of the source groups in the underlying pairing-based SNARK. Both [GNS23] and [BCFK21] overcome the limitation in the selection of HE schemes in [FNP20] by supporting an arbitrary rather than a prime ciphertext modulus q. Still, for both works, dealing with the more complex HE operations such as modulo switching and key switching is very expensive. This makes it unclear whether it would be more practical to support efficient but complex schemes such as BGV and BFV, or BV with a potentially non-prime q. The main problem for all those works is that they verify whether certain operations are done on (simplified versions of) the ciphertext space. Furthermore, they need to emulate the arithmetic of HE ciphertexts in one way or another, incurring large overheads. While the addition of ciphertexts can be easily emulated (as addition of elements in the ciphertext space R q 2 ), the product of ciphertexts is less algebraically structured and hard to emulate, since it mixes a number of computational steps such as bit-wise operations, real division, rounding, the product of elements in R q and changing q during modulo switching operations. As an example of how expensive these techniques were, consider trying to emulate the HE arithmetic within R q (as in [GNS23, FNP20]), which is arguably the closest algebraic structure. Every bitwise operation involved in the product of ciphertexts, such as rounding (present in the HE.ModSwitch operation in BGV and BFV), has the cost of one constraint 5 per bit of the ciphertext ring R q . This cost increases rapidly as the multiplicative depth of the circuit grows, not only because of the number of such operations but also because of how the HE parameters (including ciphertext size) grow accordingly. In the BGV scheme (as well as the BFV and CKKS one), increasing the multiplicative depth of the circuit by one usually requires to add a prime to the prime chain that makes up the ciphertext modulus. In more practical terms, this corresponds to increasing the ciphertext modulus by 30−50 bits every time we increase the multiplicative depth by one. This means that the ciphertext modulus will grow exponentially with the depth d of the circuit that one wants to evaluate (this takes the security level into account; see for example [APS15, CP19]). Alternatively, works like [BCFK21] circumvent the issue of doing bit-wise operations by using the BV scheme. In their work, the size of the ciphertext ring grows exponentially with the number of ciphertext-ciphertext multiplications that one wants to evaluate.

The number of constraints in R1CS or other models of computation are the main metric for the efficiency in SNARKs.

<!-- page 3 -->

In this work, we deviate from this paradigm by enabling the verification of operations on the plaintext space of the HE scheme. At a high level, we show how to adapt holographic IOP-based SNARKs so that, on the one hand, the prover computes obliviously on the encrypted values while, on the other hand, the verifier performs the verification checks on the plaintext space. We choose to focus on holographic IOPs as a departure point for our verifiable computation protocol, since the holography property is particularly well suited for outsourcing scenarios. Nevertheless, our techniques could easily be adapted to non-holographic IOPs. We call our overall framework HElIOPolis, since its central components are homomorphic encryption (HE) and Interactive Oracle Proofs (IOPs).

Technical overview

We manage to move verification from the ciphertext to the plaintext space by replacing the IOP oracles O with encrypted oracles O HE , which are oracles to data that is homomorphically encrypted. While the prover P does not know what the plaintexts they are computing on are, P knows how to arrange them into oracles (i.e. P can place HE.Enc(x) into an oracle O HE , rather than x into O). Whereas the modified IOP (denoted HE-IOP) can now only be verified by whoever has the HE decryption key 6 , this new abstraction is very powerful: not only is the prover much more efficient, it is also very simple to reduce the security of an HE-IOP to that of its corresponding IOP (Theorem 2). Moreover, we also adapt several results in the literature compiling different variants of (zk)IOPs into (zk)SNARKs [COS20, BGK + 23]. Our resulting zkSNARKs are plausibly post-quantum, since so are the BCS transform [BCS16, CMS19] and all the efficient HE schemes we have today. Once oracles are replaced with encrypted oracles, our approach is black box on the different components of these compilers. A central part of these is the use of an IOP of proximity (IOPP) to Reed-Solomon Codes, which is interpreted either as a low degree test or a correlated agreement test [BCI + 20, BGK + 23]. As done in practice for unencrypted IOPs, we choose FRI [BBHR18] to instantiate this IOPP component. FRI is, a priori, particularly HE-friendly, in the sense that it only runs linear operations on the functions being tested, and products in HE are particularly expensive. Nevertheless, there are several challenges when trying to align the security parameters of HE schemes and FRI. This constitutes a significant part of our work, for which we discuss trade-offs and optimizations (Section 6) as well as we provide experimental data (Section 7). Aligning security parameters. The first challenge is enabling FRI to work over a field of size |F p D | ≈ 2 256 for some prime p, This ensures that FRI remains secure when making it non-interactive through Fiat-Shamir for any Reed-Solomon codeword we would encounter in practice when compiling IOPs [BGK + 23]. Using p D as a plaintext modulus in the HE scheme would result in unmanageable parameters. We address this by emulating F p D arithmetic using D ciphertexts, each encrypting elements from F p . Reducing depth and exploiting HE packing. A second challenge to the homomorphic evaluation of FRI is its multiplicative depth. Although it only involves multiplications between plaintexts and ciphertexts, the noise level can increase almost as much as with ciphertext multiplications, since plaintext are random elements of F p . A typical implementation of FRI would have depth 2n for an input of size 2 n , which represents a performance challenge for HE schemes. We solve this problem by introducing low-depth versions of every sub-routine required to evaluate FRI, and

In concurrent work on IOPs over encrypted data [GGW23], the authors discuss the use of fully homomorphic commitments [GVW15] as a way to recover public verifiability, but all known constructions for such primitive are very inefficient.

<!-- page 4 -->

show how to perform Reed-Solomon codeword encoding with small fixed depth, as opposed to the traditional depth-n methods. We also propose a “Shallow Fold" algorithm to replace FRI’s standard Fold operation, which reduces the depth to 1 (from n), at the cost of increasing the complexity to O(2 n log(2 n )) (from O(2 n )), which does not change the overall asymptotics. Additionally, we exploit packing within the HE scheme to further reduce the cost of Reed-Solomon encoding. In more detail, we consider packing methods that trade off memory consumption and execution time to accelerate the prover. Minimizing HE overhead for the verifier. Finally, we take advantage of techniques proposed in [CGGI20, CLOT21] to implement a repacking and recomposing technique, which significantly reduces the overhead of ciphertext decryption for the verifier. During the commit phase of FRI, the prover performs computations using RLWE samples of dimension N encrypting N messages in F p . During the query phase, however, the verifier only needs to learn two evaluation points in F p D per round for each linearity check. If those ciphertexts are fully packed, an overhead of at least N/(2D) is introduced. In order to avoid this, we extract the evaluation points from the RLWE samples of dimension N and repack them in another RLWE sample, but of a much smaller dimension, reducing decryption costs up to 128 times depending on the selected parameters. One key observation is that at this point, we do not need to preserve any homomorphic properties, as the verifier does not perform any further operations on these. Indeed, once the commit phase is finished, we can view the evaluation points as simply strings of bits, and our goal then becomes to encrypt them in the smallest possible ciphertext. This also makes the HE parameters adopted by the verifier completely independent of the ones adopted by the prover or of the input size 2 n . All our optimizations are specifically targeted for FRI. Whether other existing IOPs of proximity (e.g. [ACY23]) or new ones could be better aligned in practice with HE schemes such as BGV and BFV is an interesting open work that our theoretical machinery already supports. Proof-of-Concept Implementation. To demonstrate the practicality of our construction, we implement a proof-of-concept over the FRI implementation of Szepieniec et al. [S + 21]. We extend it to work over non-prime fields and connect it to optimized FHE libraries. We test two parameter sets for encrypted codewords of size up to 2 16 representing polynomials with degree bound up to d = 2 15 . For a batch of 4096 polynomials with degree bound d = 2 11 , our implementation takes just 5.4 seconds to run FRI’s commit phase (including the Reed-Solomon code encoding) on 32 threads in a c6i.metal instance on AWS and requires less than 4GB of memory. Verification is much faster, taking just 12.3ms single-threaded (also for a batch of 4096 polynomials). With a parameter set optimized for the verifier, verification time drops to just 5.6ms single-threaded, at the cost of increasing the prover execution to 1.3 minutes. Our implementation is publicly available at https://github.com/antoniocgj/HELIOPOLIS. Oracle attacks. Moving verification from the ciphertext to the plaintext space inherently opens up for side-channel and composition attacks. If the verifier signals to the prover whether verification passes, this leaks 1 bit of information about the plaintext/secret key. A priori, it could seem that reusing the plaintext output obtained by the verifier as input to another protocol could also leak about the secret key, but such issues can be avoided altogether by having the prover provide Zero Knowledge Proofs of Knowledge for any ciphertext it would use as input. We discuss these risks in more detail in Section 3.1. We believe that, for many applications, the speed-ups we achieve through this paradigm shift far outweigh the one-bit privacy loss. This is reflected by the lack of implementations for works on the previous paradigm (verification over the ciphertext space), for which, except for very low-depth circuits, their lack of efficiency is a non-starter.

<!-- page 5 -->

Comparison with existing works

In concurrent work [GGW23], Garg, Goel and Wang offer a framework to prove statements on values that are hidden from the prover. Their framework is based on making FRI work over such hidden values, and they show how to compile Polynomial IOPs into SNARKs given such a tool. Besides HE, their work considers more general ways to hide these values from the prover, such as homomorphic commitments and group exponentiation, grouped under the abstraction of Linearly-Homomorphic Encapsulations. A formal issue in [GGW23] is that their notion of a decryptable (or that of linearly-homomorphic w.r.t. randomness) Linearly-Homomorphic Encapsulation is not sufficient when such an encapsulation is a building block of more complex components such as FRI or polynomial commitments. Namely, their notion only considers decryption of a freshly encrypted ciphertext on which no operations have been performed. This overlooks the fact that the evaluation correctness of HE schemes, which are based on (Ring) Learning with Errors, is function-specific and needs to support the operations computed within those components. Whereas FRI only requires to perform a series of linear combinations on the ciphertexts, it turns out that the size of the coefficients in the linear combination and the additive depth of FRI constitutes a significant obstacle for noise management in practice (see Section 6). While [GGW23] is more theoretical and lacks implementation, our work focuses on concretely accelerating VC on encrypted data. In addition to various technical optimizations and trade-offs informed by our experimentation, we address two key aspects that [GGW23] does not: scenarios where the prover provides inputs in zero knowledge, and the direct use of FRI (e.g. by compiling δcorrelated IOPs into (zk)SNARKs [BGK + 23]), rather than going through a polynomial commitment abstraction. The former greatly improves the parameters of the HE scheme in several applications, such as Privacy-Preserving Machine Learning (where the prover provides their model as a plaintext in zero-knowledge while the verifier’s input are HE ciphertexts), whereas the latter improves FRI’s parameters by allowing to use a proximity parameter up to the Johnson bound.

Preliminaries

Notation

We use R[X] ≤d to refer to polynomials with coefficients in a finite, commutative ring R and degree at most d. For an element a ∈ R, we write [a] q to denote the reduction of a modulo q (coefficient-wise), with the set of representatives of coefficients lying in {0, . . . , q − 1}. This should not be confused with [n], which we will sometimes use to denote the set of integers {1, . . . , n}. We use bold notation (e.g. b) to refer to vectors. We use y ← C to denote that y is the output of a given computation C. We use a ← A for sampling an element a from a distribution A. When $ A is a set rather than a distribution, we write a ← A for sampling a uniformly at random in A. We f write Jf K to denote an oracle to f , and M to denote that M has oracle access to f . We abbreviate Probabilistic Polynomial Time as PPT. We let λ denote a computational security parameter. We c denote computational indistinguishability by ≈ when no PPT algorithm can distinguish between two distributions except with negligible probability.

<!-- page 6 -->

Basic algebra and Galois theory

Next, we present some Number and Galois Theory facts that were noted in the context of FHE in [SV14], but that are fairly standard. Let p be a prime, F (x) ∈ F p [x] be a polynomial, deg(F ) = N , and assume that it factorises (mod p) into ℓ factors, all of degree D, for D · ℓ = N , i.e.

ℓ Y

F (x) =

F i (x)

i=1

(mod p),

where deg(F i ) = D, ∀i ∈ [ℓ]. Then we can define R p := F p [x]/(F ), and the following holds.

R p ∼ = F p [x]/(F 1 ) × . . . × F p [x]/(F ℓ ) ∼ = F D ⊗ . . . ⊗ F D .

p

p

(1)

Let F = Φ 2N be the 2N th cyclotomic polynomial, for N a power of two, and deg(Φ 2N ) = N . We note in particular that the above implies that, if p is a prime such that F p contains a primitive 2ℓ th root of unity, we have that

Y

Φ 2N (x) =

i∈(Z/2ℓZ) ×

(x D − ζ i )

(mod p).

In the fully-splitting case, we have that D = 1, and can therefore write

R p ∼ = F p ⊗ . . . ⊗ F p . | {z }

N copies

We refer to the cases where D is small with respect to N as almost-fully splitting.

Homomorphic Encryption

Definition 1 A public-key Homomorphic Encryption scheme HE over a set of admissible circuits d consists of the following algorithms. Circ

d : Given a message space M, a set of admissible circuits Circ, d – (pp, C) ← HE.Setup(1 λ , M, Circ) output the public parameters pp and the ciphertext space C such that the scheme is semantically secure. – (sk, pk, evk) ← HE.KeyGen(1 λ , C, pp) : Given the public parameters pp and the ciphertext space C, output the secret key sk, the public key pk and the evaluation key evk. – ct ← HE.Enc(pk, m) : Given a message m ∈ M, output its encryption ct. – m ′ ← HE.Dec(sk, ct) : Given a ciphertext ct and its corresponding secret key sk, output the decryption of ct, m ′ . d output the evaluation of Ĉ on ct. – ct ′ ← HE.Eval(evk, ct, Ĉ) : Given a circuit Ĉ ∈ Circ,

When the context is clear, we will omit specifying the sk, pk, pp, C parameters. The (standard) definition for semantic security of HE schemes is given in Appendix B.

<!-- page 7 -->

Definition 2 Let HE be a homomorphic scheme as in Definition 1. We say that HE is correct if the equation

HE.Dec(sk, HE.Eval(evk, HE.Enc(pk, m), Ĉ)) = C(m)

d holds with overwhelming probability for all admissible circuits Ĉ ∈ Circ.

b refers to the set of circuits that the scheme can support – for example, We note that the set C some HE schemes support non-linear operations such as ReLu, and some do not. In particular, each d has a corresponding circuit C on the plaintext space. To give a concrete example, if circuit Ĉ ∈ Circ we want to evaluate the homomorphic multiplication of two ciphertexts, Ĉ could be a multiplication followed by a bootstrapping, whereas C would simply be a multiplication.

Reed Solomon Codes

Reed-Solomon (RS) codes are arguably the most common linear error correction codes. Let us recall their definition and fix some notation relative to them. In this work, we will parameterize them by a finite field F, a multiplicative subgroup L ⊆ F ∗ and a degree bound d. Hence, RS[F, L, d] is defined as follows: RS[F, L, d] = {(f (x)) x∈L ∈ F |L| : f ∈ F[X] <d }.

The code rate of RS[F, L, d] is ρ = d/|L|. Unless we state it otherwise, in this work we will assume that |L| = 2 k , ρ = 2 −R and d = 2 k−R . For two vectors u, v ∈ F n , we let ∆(u, v) denote the relative Hamming distance between u and v, defined as ∆(u, v) := |{u i ̸ = v i |i ∈ {1, . . . , n}|/n. For a set of vectors S ⊂ F n and any vector u ∈ F n , we define ∆(u, S) = ∆(S, u) := min v∈S {∆(u, v)}. For δ ∈ (0, 1), we say that u is δ-far from S if ∆(u, S) ≥ δ. Otherwise, we say that u is δ-close to S. Equivalently, u is δ-far from S if ∆(u, S) ≥ δ for all v ∈ S, and u is δ-close to S if there exists v ∗ ∈ S such that ∆(u, v ∗ ) < δ. We refer to δ as the proximity parameter. When δ < (1 − ρ)/2, we say that δ is within the unique √ decoding radius; and when δ < 1 − ρ, we say that δ is within the Johnson bound.

Definition 3 (Correlated agreement) Let δ ∈ (0, 1). Let V = RS[F, L, d] and let W = {w 1 , . . . , w k } ⊆ F |L| . We say W has δ-correlated agreement with V on an agreement set S ⊆ L if |S|/|L| ≥ 1 − δ and there exist v 1 , . . . , v k ∈ V such that, ∀x ∈ S, w i (x) = v i (x).

Interactive Oracle Proofs (of Proximity)

There are several variations of the IOP abstraction [BCS16]. Polynomial IOPs (PIOPs) ask for the IOP oracles to be polynomials evaluated over the entire field F, whereas for the weaker notion of Reed Solomon-encoded IOPs (RS-IOPs) those are Reed-Solomon codewords (i.e. the evaluation of a polynomial over some specific domain L ⊂ F). In this work, we focus on RS-encoded IOPs and on δ-correlated IOPs, which were introduced in [BGK + 23]. Our results could nevertheless be easily adapted to other IOP flavors, e.g. to PIOPs as in [GGW23]. The main attractive of δ-correlated IOPs is that they allow for a better proximity parameter δ (up to the Johnson bound, rather than within the unique decoding radius) when they are compiled into SNARKs. When δ = 0, δ-correlated IOPs can be seen as a subclass of RS-encoded IOPs [BCR + 19, COS20].

<!-- page 8 -->

Definition 4 An indexed relation R is a set of triples ( i , x ; w ) ∈ {0, 1} ∗ × {0, 1} ∗ × {0, 1} ∗ . The string x is the called input, statement or instance, the string w is called the witness and the string i is an index. The index can be thought as something that is fixed at setup time, and chooses among a universe of binary relations R i = {( x ; w ) : ( i , x ; w ) ∈ R}.

In the setting of holographic proofs, a good example is an indexed relation for circuit satisfiability, where the index i is a description of the circuit, the statement x contains the “public" values on some of the circuit’s input wires and the witness w consists in the values taken by the remaining “private" wires.

Definition 5 ([BGK + 23]) Let H ⊆ F and d ≥ 0. An indexed (F, H, d)-polynomial oracle relation R is an indexed relation where for each ( i , x , w ) ∈ R, the index i and input x may contain oracles to codewords from RS[F, H, d] and the actual codewords corresponding to these oracles are contained in w .

Definition 6 A µ-round holographic interactive oracle proof (hIOP) for an indexed relation R is a tuple of PPT interactive algorithms Π = (P, V) and a deterministic polynomial-time algorithm Ind (the indexer), with two phases:

– In an offline phase, given an index i , Ind computes an encoding of it, Ind( i ). – In an online phase, P(Ind( i ), x , w ) and V Ind( i ) ( x ) exchange 2µ + 1 messages, where P sends the fist and last message. V gets only oracle access to P’s messages, and after P’s final message, V either accepts or rejects.

Furthermore, an hIOP has to satisfy the two following properties:

Completeness: For all ( x , w ) ∈ R, we have that

Pr[⟨P(Ind( i ), w ), V Ind( i ) ⟩( x ) = 1] ≥ γ,

where the probability is taken over the random coins of V. If, for all x , γ = 1, then the hIOP has perfect completeness. Soundness: For any x ∈ / L R and any unbounded malicious P ∗ ,

Pr[⟨P ∗ (Ind( i ), w ), V Ind( i ) ⟩( x ) = 1] ≤ ϵ,

where the probability is taken over the random coins of V.

In δ-correlated hIOPs, the prover is supposed to send oracles to maps that agree with low degree polynomials on a fraction of 1 − δ points (see Definition 3). On top of checking all the received oracles correspond indeed to δ-correlated maps (which we capture by the relation in Definition 7), it is necessary to verify some algebraic equalities involving some evaluations of those maps. These are made concrete in Definition 8.

Definition 7 ([BGK + 23]) Let 0 ≤ δ < 1. The δ-correlated agreement relation for RS[F, L, d] is the following indexed (F, L, d)-polynomial oracle relation:       r, δ ≥ 0, ρ = d/|L|     (F, L, d, δ, r) i     L  f i ∈ F ∀i ∈ [r]    (Jf K) CoAgg =  x  =  i i∈[r]  :    (f i ) i∈[r] has δ-correlated agreement with      w (f i ) i∈[r] RS[F, L, d]

<!-- page 9 -->

Definition 8 (δ-correlated hIOP, [BGK + 23]) Let L = ⟨ω⟩ be a smooth multiplicative subgroup of F ∗ of order d = 2 v /ρ for some v ≥ 1 and rate 0 < ρ < 1 and define the Reed-Solomon code RS[F, L, d]. Let 0 ≤ δ < 1 and let R be an indexed (F, L, d)-polynomial oracle relation. Let Π be a hIOP for R. Given a (possibly partial) transcript ( x , τ ) generated during Π, let Words( x , τ ) be the words from F L that fully describe the oracles appearing in ( x , τ ). We say that Π is δ-correlated if:

– The verifier V has oracle access to the δ-correlated agreement relation CoAgg(δ). – For all ( i , x , w ) ∈ R: • In the last round of interaction between P(Ind( i ), x , w ) and V Ind( i ),CoAgg(δ) ( x ), the verifier sends a field element z uniformly sampled from a subset of (a field extension of ) F and the honest prover replies with the values:

Evals( x , τ, z) = (w(ω k w,1 z), . . . , w(ω k w,nw z) : w ∈ Words( x , τ ))

where τ is the transcript so far and κ = {k w,i : w ∈ Words( x , τ ), i ∈ [n w ]} is a fixed set of integers which are output by Ind. • To decide whether to accept or reject a proof, V Ind( i ),CoAgg(δ) ( x ) makes the two following checks: Check 1 Assert whether the received values Evals(τ, z) are a root to some multivariate polynomial F i , x ,τ depending on i , x and τ . Check 2 Assert whether the maps

n w(X) − w(ω k w,j z)

quotients( x , τ, z) =

o : w ∈ Words( x , τ ), j ∈ [n w ]

X − ω k w,j z

have δ-correlated agreement in RS[F, L, d − 1] by using the CoAgg(δ) oracle on the oracles to such maps.

Next, we define the notions of round-by-round (RBR) soundness and knowledge soundness [CCH + 19] for holographic IOPs. Since those are a superset of δ-correlated hIOPs, the same definition applies to the latter.

Definition 9 A holographic IOP for an indexed relation R has round-by-round (RBR) soundness with error ϵ if for every index i there exists a “doomed set" D( i ) of partial and complete transcripts such that:

1. If x ∈ / L R i , then ( x , ∅) ∈ D( i ), where ∅ denotes the empty transcript. 2. For every possible input x and complete transcript τ , if ( x , τ ) ∈ D( i ), then V Ind( i ) ( x , τ ) = reject. 3. If i ∈ [µ] and ( x , τ ) is a (i−1)-round partial transcript such that ( x , τ ) ∈ D( i ), then Pr $ [( x , τ, m, c) ∈ /

c ←C i

D( i )] ≤ ϵ( i ) for every possible next prover message m.

Definition 10 A holographic IOP for an indexed relation R has round-by-round (RBR) knowledge soundness with error ϵ k if there exists a polynomial time extractor Ext and for every index i there exists a “doomed set" D( i ) of partial and complete transcripts such that:

/ D( i ). 1. For every possible input x (regardless of whether x ∈ / L R i or not), ( x , ∅) ∈ 2. For every possible input x and complete transcript τ , if ( x , τ ) ∈ D( i ), then V Ind( i ) ( x , τ ) = reject.

<!-- page 10 -->

3. Let i ∈ [µ] and ( x , τ ) be a (i − 1)-round partial transcript such that ( x , τ ) ∈ D( i ). If for every possible next prover message m it holds that

Pr [( x , τ, m, c) ∈ / D( i )] > ϵ k ( i ),

$

c ←C i

then Ext( i , x , τ, m) outputs a valid witness for x .

Finally, let us also discuss zero knowledge, which will be particularly interesting in our work.

Definition 11 An hIOP Π for an indexed relation R has statistical zero knowledge with query bound b if there exists a PPT simulator S such that for every ( i , x , w ) ∈ R and any V ∗ making ∗ less than b queries in total to its oracles, the random variables View(P( i , x , w ), V ∗ ) and S V ( i , x ), defined below, are statistically indistinguishable

– View(P( i , x , w ), V ∗ ) is the view of V ∗ , i.e. the random variable (r, a 1 , . . . , a q ) where r is V ∗ randomness and a 1 , . . . , a q are the responses to V ∗ ’s queries determined by the oracles sent by P. ∗ – S V ( i , x ) is the output of S( i , x ) when given straightline (i,e, without rewinding) access to V ∗ , prepended with V ∗ randomness r.

Π is honest-verifier zero knowledge if the above holds with V ∗ = V Ind( i ) ( x ).

Some examples of δ-correlated hIOPs are Plonky2, RISC Zero, ethSTARK, Aurora and Fractal [COS20]. One particular advantage of hIOPs is how easy it is to compile them into SNARKs through the so-called BCS transformation [BCS16]. In a nutshell, this consists in replacing oracles sent by the prover with Merkle-tree-based commitments and then removing interaction with the verifier by applying the Fiat-Shamir transform. It has been proved that if an hIOP is round-by-round sound, applying the BCS transformation results in a SNARK that is adaptively knowledge sound versus both classic and quantum adversaries in the random oracle model [CMS19, COS20]. A similar concept to the above one is that of an IOP of Proximity (IOPP), which is an IOP to test proximity to a specific code. In this work, we restrict ourselves to IOPPs for Reed Solomon Codes.

Definition 12 Let RS denote the family of Reed Solomon codes RS[F, L, d]. A protocol between a pair of interactive machines ⟨P, V⟩ is an r-round interactive oracle proof of δ-proximity for RS is an IOP with the following modifications

– Input format: The first message from P is f 0 : L → F, allegedly a RS codeword. – Completeness: Pr[⟨P, V⟩ = 1 : ∆(f 0 , RS) = 0] = 1 − θ for a negligible θ. If θ = 0 we refer to this as perfect completeness. – ϵ-soundness: For any unbounded P ∗ , Pr[⟨P ∗ , V⟩ = 1 : ∆(f 0 , RS) ≥ δ] ≤ ϵ.

The next theorem summarizes the compilation results of [BGK + 23]. Informally, given a δcorrelated hIOP, it suffices to analyse its RBR knowledge soundness when δ = 0 and replace oracles with a δ-correlation check 7 to produce an RBR knowledge sound hIOP as a result. This hIOP can then be turned into a SNARK through the usual BCS transformation [BCS16]. Interestingly, having δ ̸ = 0 (and actually up to the Johnson bound!) does not affect knowledge soundness when following the [BGK + 23] recipe, whereas previous compilers [CMS19, COS20] were restricted to the unique decoding regime, i.e. δ < (1 − ρ)/2.

Such as batched FRI

<!-- page 11 -->

Theorem 1 ([BGK + 23]). Let Π δ O be a δ-correlated hIOP, where O is an oracle for δ-correlated √ agreement. Let 0 < η ≤ 1 and ρ > 0 be such that δ = 1 − ρ − η is strictly positive. Assume Π 0 O has RBR knowledge soundness with error ϵ. Then, Π δ O has RBR knowledge soundness with error √ ϵ/(2η ρ). Moreover if Π CA is an IOPP for δ-correlated agreement in RS[F, L, d] with RBR soundness error Π ϵ CA , then the protocol Π δ CA obtained by replacing O with Π CA in Π δ O has RBR knowledge soundness √ error ϵ 1 = max{ϵ/(2η ρ), ϵ CA }.

Π

Furthermore, given a random oracle with λ-bit output and a query bound Q, compiling Π δ CA with √ the BCS transformation [BCS16] yields a SNARK with knowledge error Q · max{ϵ/(2η ρ), ϵ CA } + O(Q 2 /2 λ ).

Verifiable Computation over encrypted data

The notion of verifiable computation (VC) proposed by Gennaro et al. in [GGP10] tries to better capture the way in which proof and argument systems are used in practice. In Definition 1 we tweak their definition and syntax to fit our constructions. In particular, we allow for the verification algorithm to be interactive, since we will often discuss at the IOP rather than SNARK level of abstraction. Furthermore, we would like to support circuits of the form C( x , w P ) where (the homomorphic encryption of) the input x is provided by the verifier, while the prover specifies w P , which includes plaintexts and/or ciphertexts revealed to V during verification. Without threshold decryption to prevent the verifier from unauthorized decryptions, all w P values are exposed to the verifier. Thus, for single-client outsourcing, w P should consist only of plaintexts. If w P must remain hidden, it can be treated as a private witness mixed with the encryption x in zero-knowledge. For example, one could think about a private Machine-Learning-as-a-Service [AHH + 24], where the client sends encrypted queries HE.Enc( x ) to the server, who applies their private model w P . This approach, also pursued in [BCFK21, GNS23], is advantageous because multiplying plaintexts (such as those in w P ) with ciphertexts (the encryptions of x and the outputs that result from operating on them) is much cheaper than multiplying ciphertexts.

Definition 1 (Verifiable Computation). A verifiable computation scheme VC is a tuple of polynomial time algorithms (VC.Setup, VC.ProbGen, VC.Compute, VC.Ver) defined as follows.

– (SK, PK) ← VC.Setup(1 λ , C): A randomized key generation algorithm takes a circuit C as input and outputs a secret key SK and a public key PK. – (σ x , VK x ) ← VC.ProbGen(PK, x): A randomized problem generation algorithm (to be run by V) takes the public key PK, an input x, and outputs a public encoding σ x of x, together with a private verification key VK x . – η y ← VC.Compute(PK, σ x , w P , C): Given a public key PK for a circuit C, the encoded input σ x and input w P , P computes η y , which consists of an encoded version σ y of the circuit’s output y = C(x, w P ) and data to answer challenges about that statement. – acc ← VC.Ver⟨P(PK, η y ), V(SK, VK x , σ y )⟩(C) : The interactive verification algorithm uses the input-specific verification key VK x , the setup secret key SK and a proof η y to return σ y together with a bit acc ∈ {0, 1} such that acc = 1 if VC.Decode(σ y , SK) = C(x, w P ) or acc = 0 otherwise.

<!-- page 12 -->

– y ← VC.Decode(σ y , SK): Using the secret key, the decoding algorithm outputs the value y behind the public encoding σ y .

A verifiable computation scheme can satisfy a range of properties which we next define. We omit the VC. prefix in the different algorithms for ease of readability. In our work, we will always be interested in all of the following ones whenever w P does not need to be kept private.

– Correctness. Correctness guarantees that if P is honest, the verification test will pass. That is, for all C, and for all valid inputs x, w P of C the following probability equals 1 − negl(λ).   (SK, PK) ← Setup(1 λ , C)   acc = 1 (σ x , VK x ) ← ProbGen(PK, x)  Pr    Decode(σ y , SK) = C(x, w P ) : η y ← Compute(PK, σ x , w P , C) acc ← Ver⟨P(PK, η y ), V(SK, VK x , σ y )⟩(C)

– Outsourceability. A VC scheme is outsourceable if for any x and any η y , the time required by V to run ProbGen(x), Ver⟨P(PK, η y ), V(SK, VK x )⟩(C) and Decode(σ y , SK) is o(T ), where T is the time required to compute C(x, w P ). – ϵ-Soundness. A VC scheme is ϵ-sound if a malicious P cannot make the verification algorithm accept an incorrect answer for any valid circuit C. That is, a scheme is sound if the advantage of any PPT adversary A in the game Exp V A er defined as Pr Exp V A er [V C, C, λ] = 1 is ϵ. – Verifier-Privacy. For any valid circuit C, riv Pr Exp V.P [V C, C, λ] = 1 ≤ 1/2 + negl(λ). A

V er 1 Game Exp A (V C, C, λ) (SK, PK) ← Setup(1 λ , C)

x ← A(PK, C) (σ x , VK x ) ← ProbGen(PK, x) η y ← A(PK, σ x , C) acc ← Ver⟨P(PK, η y ), V(SK, VK x , σ y )⟩(C) y ← Decode(σ y , SK) if acc = 1∧ ̸ ∃ w P : C(x, w P ) = y return 1

return 0

On verifier privacy and oracle attacks

V.P riv 1 Game Exp A (V C, C, λ)

$

b ← {0, 1} (SK, PK) ← Setup(1 λ , C) (x 0 , x 1 , state) ← A(PK, C) (σ x b , VK x b ) ← ProbGen(PK, x b ) b̂ ← A(state, σ x b )

?

return b = b̂

Our definition of verifier-privacy assumes that the verifier does not signal to the prover whether verification passes or not (i.e. there are no verification oracles) and that the value y it obtains after running the Decode algorithm is not used as input to future algorithms (which we refer to as a decryption oracle). We briefly discuss the privacy impact of such oracles, which is inherent to moving verification from the ciphertext to the plaintext layer. Verification oracles: When a malicious prover provides tampered ciphertexts (e.g. by manipulating their noise), the result of decryption is a function of such changes. The results of decryption

<!-- page 13 -->

also depend on the secret key and underlying message. Since the actions of the verifier (such as rejecting a proof or not, i.e. the value acc ∈ {0, 1}) depend on the decrypted ciphertexts, this is a source of leakage. All protocols we present are non-interactive, implying that there is at most one such verification oracle per proof sent. Hence, a malicious prover can learn at most a one-bit leakage predicate (which evaluates to acc) about the secret key/message. Regarding leakage about the key, the concrete security loss this incurs can be measured with tools such as the Leaky Estimator [DDGR20]. Additionally, stopping any further executions with a prover for which acc = 0, refreshing the keys and/or increasing their length are easy solutions. Decryption oracles: First, note that the output of the decryption of the prover’s answers to verifier challenges has no use beyond verification. Therefore, the only value we need to be concerned about in a decryption oracle is the output of the computation itself. Consequently, decryption oracles may only occur in the composability case – i.e., when VC.Decode(σ y , SK) is used as input in another protocol. Further, these decryption oracles arise only in the case where verification passes, as the Verifier would otherwise abort (and then, at worst, we would be in the presence of a verification oracle, as explained above). Finally, we note that the output of the computation (C(x, w P )) leaks nothing unexpected, as long as w P does not contain ciphertexts for which P did not provide a zero knowledge proof of knowledge (ZKPoK) for the underlying plaintext. In summary, the only scenario in which a decryption oracle may pose a threat is: the prover provides as input ciphertext without an accompanying ZKPoK, verification passes and the HELIOPOLIS output is passed along to another protocol for further processing.

Prover privacy

In previous works on verifiable computation over encrypted data, the goal of keeping w P private was modeled as a context-hiding property of the VC scheme [BCFK21, GNS23]. This is a reminiscence of a similar notion in the setting where w P did not exist, but the parties running VC.ProbGen and VC.Ver were different [FNP20]. In our following sections we will deviate from that modeling and hence refrain from the context-hiding property. We do this not only because we focus on the more common scenario where the verifier is running both VC.ProbGen and VC.Ver, but also because context-hiding would not be able to model e.g. the interactivity of VC.Ver. We believe that our new security modeling will be useful for future work in this area. We formalize the notion of honest-verifier prover privacy (HVPP) by showing that whatever a semi-honest V can compute by participating in the protocol, V could compute merely from its input and prescribed output. Our definition is in the simulation paradigm and thus we have a stateful simulator S that generates V’s view given its input and output. We remark that, since V is semi-honest, it is guaranteed that it uses its actual input and random tapes. In particular, S can furthermore generate V’s random tape and, at that point, generate the whole protocol transcript on its own without ever needing to interact with V.

Definition 2. We say that a VC protocol is honest-verifier prover-private(HVPP) if there exists a PPT simulator S such that for every circuit C:

c

{S(1 λ , PK, x, C(x, w P ))} x, w P ,λ,PK ≈ {View V (SK, PK, x, w P , λ)} x,y,λ,SK,PK

where (SK, PK) ← VC.Setup(1 λ , C) and View V (SK, PK, x, w P , λ) denotes the view of V during an execution of the protocol on inputs (x, w P ) and security parameter λ, that is (SK, PK, x, r; m 1 , . . . , m e , out)

<!-- page 14 -->

where r is V’s random tape, each m i value is the i-th message V receives and out denotes V’s output, which is computed from all other values in its own view of the execution.

In Figure 1, we provide our general recipe for a correct, sound and verifier-private Verifiable Computation scheme. Verifier-privacy follows from the use of encryption within the ProbGen step, and correctness from the fact that such encryption is homomorphic. Soundness is less immediate, since it requires to have an HE-IOP at hand, which is an object we define and construct in Section 4. Notice that, since we specialize the construction to use holographic IOPs (as a means to achieve outsourceability), the syntax of the verification is slightly modified, replacing the circuit C with the corresponding indexer algorithm.

Verifiable Computation over encrypted data

Let IOP be an holographic Interactive Proof. Let HE be an exact homomorphic encryption scheme with N Oracle ℓ be the CRT isomorphism. Let C : F inp × F wit → F out be an F plaintext space R p . Let ϕ : R p → D p p p i=1 p arithmetic circuit that we want to verify. Let L x = ⌈inp/ℓ⌉, L w = ⌈wit/ℓ⌉.

(sk, (pk, evk)) ← Setup(1 λ , C) : Run HE setup: d which contains a circuit C b that homomorphically computes 1. V determines a set of admissible circuits Circ C. d 2. V runs (pp, R q 2 ) ← HE.Setup(1 λ , R p , Circ). 3. V runs (sk, pk, evk) ← HE.KeyGen(1 λ , C, pp). 4. Given an index i for the circuit C, the indexer Ind computes an encoding of it, Ind( i ). (σ x , vk x ) ← ProbGen( x , pk) : V parses x = (x 0 , . . . , x inp−1 ) ∈ F inp p . For i = 0, . . . , L x − 1, let m x ,i = x −1 ϕ −1 (x iℓ , . . . , x (i+1)ℓ−1 ). Encrypt these inputs as σ x = {HE.Enc(pk, m x ,i )} L i=0 . Set vk x = (sk, x ). b : P parses σ x and evaluates C(σ b x , w P ), by which it obtains the rest of the w ← Compute(evk, σ x , w P , C) witness: the values on intermediate wires w C and the circuit output σ y . Notice that the whole witness becomes w = ( w P , w C , σ y ), which is a mix of plaintext values (such as w P ) and ciphertext values (those depending on any input σ x ). acc ← Ver⟨P(Ind( i ), evk, (σ x , w )), V Ind( i ) (sk, (vk x , σ y ))⟩ : P and V run the HE-IOP corresponding to the IOP for the plaintext circuit C, i.e. ⟨P(Ind( i ), evk, σ x , w ), V Ind( i ) (sk, ( x , HE.Dec(sk, σ y )))⟩. y ← Decode(σ y , sk) : V outputs y = HE.Dec(sk, σ y ).

Fig. 1: Verifiable Computation over Encrypted Data through HE-IOPs.

Compiling Interactive Oracle Proofs to work over HE

Given an IOP which was not conceived to work over encrypted data, we show how to adapt it to work with HE in Definition 13.

Definition 13 (HE-transformation) Let ⟨P( x , w ), V( x )⟩ be an IOP, where the elements of x and w belong to a finite field F. We define its encrypted version HE-IOP, for some HE scheme as follows:

d where R p splits into copies of F and – There is a trusted setup (pp, C) ← HE.Setup(1 λ , R p , Circ), d is a family of admissible circuits that captures all necessary computation within the IOP as Circ well as any preceding/posterior one (such as coming up with parts of the witness, or using an IOPP and the BCS transformation to compile into a SNARK). – There is also a trusted key generation step (sk, pk, evk) ← HE.KeyGen(1 λ , C, pp). P has as an additional input evk and V has as an additional input sk.

<!-- page 15 -->

– P’s input x is replaced by its encryption HE.Enc( x ). Parts of w could be also replaced by their homomorphic encryption. – As a result, some oracles in the HE-IOP might now contain ciphertexts. We refer to them as HE-oracles or encrypted oracles. V has to decrypt the ciphertexts obtained from HE-oracles and perform the same checks as in F.

If we need to refer explicitly to the HE-IOP, we denote it as ⟨P(evk, HE.Enc( x ), w ), V(sk, x )⟩, as a slight abuse of notation of the original P and V. The different properties of IOPs (completeness, soundness, round-by-round soundness, round-by-round knowledge soundness) can be trivially redefined for HE-IOPs.

One of the main interests of our HE-transformation, besides its simplicity, is that it preserves most parameters of the original IOP, with only some negligible degradation due to the use of homomorphic encryption.

Theorem 2. Let IOP be an ϵ k RBR knowledge sound, ϵ rbr RBR sound, ϵ-sound, complete IOP. It’s encrypted version HE-IOP is ϵ k + negl(λ) RBR knowledge sound, ϵ rbr + negl(λ) RBR sound, ϵ + negl(λ)-sound and complete.

Proof. Completeness follows from the evaluation correctness of the HE scheme and the way the circuit d was chosen. There is only a negligible loss in γ due to the way evaluation correctness is family Circ defined (Definition 2). The soundness, RBR soundness and RBR (knowledge) soundness of an HE-IOP can be reduced to that of IOP as follows. Let A be an adversary against HE-IOP with an advantage bigger than adding a factor negl(λ) to the one for the corresponding notion of the IOP (ϵ, ϵ rbr , ϵ k respectively). We will build an adversary A ′ against IOP with the same such greater advantage and hence reach a contradiction. A ′ runs (sk, pk, evk) ← HE.KeyGen(1 λ , C, pp) for the relevant HE scheme, obtaining in particular sk. Given any input, A ′ encrypts it under pk and forwards it to A. For every message received from V, A ′ directly forwards it to A. In order to reply to those, A ′ queries the encrypted oracles Jf K HE received from A at every point, decrypts the answers using sk to recover f , and then sends the oracle Jf K to V. Clearly, if A succeeds, so does A ′ .

The HE-transformation applies to all variants of IOPs presented in this paper, such as holographic IOPs, RS-encoded hIOPs, δ-correlated hIOPs and IOPs of proximity. In order to denote this transformation, we will also add the HE prefix to those (HE-hIOPs, δ-correlated HE-hIOPs, HE-IOPP, etc). The upcoming subsections are organized as follows. In Section 4.1, we discuss how to keep w hidden from the verifier through zero knowledge. Sections 4.2 and 4.3 show how to compile these HE- IOPs into HE-friendly SNARKs using an HE-friendly low degree test (such as the HE transformation of the Batched FRI protocol, which we will show in Section 5.1).

Achieving prover-privacy from ZK-IOPs

We first consider the case of honest-verifier prover-privacy (HVPP, see Definition 2), since it allows for a more practical construction and it also acts as a stepping stone towards understanding the malicious case. There are three main aspects to consider when compiling using IOPs for a proverprivate version of Figure 1, which we describe next. Two of them (Consideration #1 and #3) are specific to the use of homomorphic encryption.

<!-- page 16 -->

Consideration #1: Circuit privacy. A requirement for prover-private constructions is the fact that the HE scheme needs to support circuit-privacy. Namely, all the ciphertexts of the HE-IOP that are exposed to the verifier need to be re-randomized, since their noise carries information about the circuit that was computed on them and hence 8 about w P . We provide our own definition of the circuit-privacy notion that is best aligned with our HVPP goal.

Definition 14 A homomorphic encryption scheme HE (see Definition 1) is circuit-private if there exists a rerandomization algorithm HE.Rerand(evk, pk, Ĉ, ct) and a simulator S HE such that, for any admissible circuit Ĉ with inputs HE.Enc(x 1 ), . . . , HE.Enc(x n ) and outputs ct y 1 , . . . , ct y m , it holds that (some inputs omitted for simplicity):

c

(sk, HE.Rerand(ct y 1 ), . . . , HE.Rerand(ct y m )) ≈ (sk, S HE (pk, C(x 1 , . . . , x n ))).

One of the standard ways that the above definition can be achieved is by employing noise flooding to instantiate HE.Rerand, as done in [Gen09a]. In more detail, we add to the verifierexposed ciphertexts an encryption of 0 with large enough noise to statistically hide the noise of the circuit that led to the production of that specific ciphertext. We will denote by Ω 0,C the set of such encryptions of zero. Notice that since all messages within an encrypted oracle are susceptible of being queried, we need to add such an encryption of zero to each of them before putting them within the oracle.

Consideration #2: Combining zkIOPs with LDTs. Assume either a zero-knowledge RS-hIOP or a δ-correlated hIOP is given. To compile it into a zk-IOP while making black-box use of a pre-existing Low Degree Test (in the form of an IOPP such as FRI), it is necessary for the prover to additionally send a random codeword r ahead of time, which is added to the linear combination of functions that are being tested for low-degreeness. Adding such an r does not affect soundness. However, since input to the LDT is now a random codeword, there is no need to worry about its inner workings beyond knowing what is the amount of queries made to the random codeword (which links with Consideration #3). For a more detailed leakage analysis when using FRI, see [Hab22].

Consideration #3: Combining zkIOPs with LDTs – query blow-up from packing. Compilers, such as the ones discussed in Consideration #2 and the one presented in Section 4.2, incur losses in several parameters of the resulting output IOP according to the number of queries to the LDT. This includes soundness, which in turn also loops into increasing the size of the underlying field in order to compensate. But, most importantly, the increase in the number of queries through the introduction of the LDT also degrades the query bound for zero knowledge (see Definition 11). As an example, see [COS20, Theorem 8.1.] To make things worse, the HE-transformation of these protocols replaces oracles with encrypted oracles, where ciphertexts (rather than plaintexts) are placed within them. This means that, if the chosen HE scheme supports plaintext packing and we are exploiting this property, whenever the verifier V would need to query only one of the plaintexts m i on the ciphertext ct = HE.Enc(m 1 , . . . , m l ) behind the oracle, V learns every other plaintext m j , j ̸ = i within it. Effectively, this blows-up the query loss for zero knowledge by a factor of up to l. 9 Packing becomes then as devastating (or

Notice that one can think about the circuit evaluation C(x, w P ) with a private w P as providing the evaluation of some unspecified circuit from the family {C w P (x)} w P . It could be that V sometimes happens to query values that happen to be packed within the same ciphertext, slightly reducing the blow-up in this case.

<!-- page 17 -->

even more) for zero knowledge as it is an improvement for computational efficiency, which is a very problematic tension in practice. Hence, it is paramount to reduce the packing-induced multiplicative loss while maintaining efficiency. We provide a solution for this in Section 6.5.

Malicious verifier We will only briefly address handling a malicious verifier. Instead of creating an ad-hoc “malicious-verifier prover-private" notion, it is best to model security as a maliciously secure 2-party computation protocol (see [CCL15]). Beyond the precautions for an honest verifier, we must ensure honest behavior in the Setup and ProbGen steps. This can be achieved through a trusted setup and enforced via zero-knowledge proofs, similar to a GMW-style compiler from passive to active security [GMW87]. For the ProbGen step, it is crucial to ensure the verifier provides valid ciphertexts, meaning the noise must be within bounds in lattice-based HE. Using a zero-knowledge proof of knowledge (ZKPoK) ensures the right bounds for the cleartext and encryption randomness (see e.g. [DPSZ12, Figure 9]).

A compiler for RS-encoded IOPs

Our first compiler is for Reed-Solomon encoded IOPs, and is a result of adapting the works of Aurora [BCR + 19] and Fractal [COS20].

Protocol 1 (Aurora/Fractal) Let (P R ( x , w ), V R ( x )) be an RS-encoded hIOP over L ⊆ F, with maximum degree (d c , d e ) for an indexed relation R. Let HE-IOP be its HE-transformation. Let c 1−ρ c (P LDT , V LDT ) be an IOPP for the RS code RS[F, L, d c ] with proximity parameter δ < min( 1−2ρ 2 , 3 , 1− ρ e ) where ρ c = (d c + 1)/|L| and ρ e = (d e + 1)/|L|. Let HE-IOPP be its HE-transformation. Proceed as follows:

1. Masking codeword for low-degree test: P sends V an oracle to a random r ∈ RS[F, L, d c ]. This step can be skipped when not interested in obtaining a zk-HE-hIOP. 2. RS-encoded HE-IOP for R: In parallel to the above, P and V simulate (P R (HE.Enc( x ), w ), V R ( x )). Over the course of this protocol, the prover sends encrypted oracles containing codewords π 1 ∈ RS[F, L, d 1 ], . . . , π k R ∈ RS[F, L, d k R ], and the verifier specifies a set of rational constraints C P R [COS20, Definition 4.1]. Let l := k i=1 l i + |C|. 3. Random linear combination: V samples v ∈ F 2l uniformly at random and sends it to P v ⊤ Π+r 4. Low-degree test through HE-IOPP: P and V simulate (P LDT (v ⊤ Π + r), V LDT ), where Π := Π 0 2l×L + is defined as in [BCR 19, Protocol 8.2]. Π 1 ∈ F 5. V accepts if and only if V LDT accepts

Theorem 3. Protocol 1 is an HE-hIOP for R with the following parameters, where the R (resp. LDT) superscript denotes the parameters of the RS-encoded IOPP (resp. IOPP):

– Round complexity: k R + k LDT . LDT (k R + 1). – Query complexity: q π LDT + q w – Proof length HE.Expand(L R + L LDT ), where HE.Expand is a ciphertext expansion function that depends on the specific HE scheme and how the different intermediate values are computed. LDT – Round-by-round soundness error: ϵ 1 = max(ϵ R rbr , ϵ rbr , |L|/|F|). R LDT – Round-by-round knowledge error: ϵ 2 = max(ϵ knw , ϵ rbr , |L|/|F|).

<!-- page 18 -->

Furthermore, if the RS-encoded IOP is zero-knowledge, then so is Protocol 1, with the same query bound.

Proof. All the claimed parameters can be reduced to the ones claimed in [COS20, Theorem 8.2]. The round and query complexity clearly remain the same as in there, and the proof length is only affected by the ciphertext expansion of the HE scheme. Completeness and RBR (knowledge) soundness follow from Theorem 2 and [COS20, Theorem 8.2].

A correlated-agreement-based compiler

Our second compiler allows to set the proximity parameter up to the Johnson bound, which improves efficiency. It is the result of adapting one of the central theorems in [BGK + 23] through the application of the HE transformation (Definition 13). The overall compiler appears in Figure 2.

Theorem 4. Let Π δ O be a δ-correlated HE-hIOP, where O is an HE-oracle for δ-correlated agree- √ ment in RS[F, L, d]. Let 0 < η ≤ 1 and ρ > 0 be such that δ = 1 − ρ − η is strictly positive. Assume Π 0 O has RBR knowledge soundness with error ϵ. Then, Π δ O has RBR knowledge soundness √ with error ϵ/(2η ρ). Let HE be an homomorphic encryption scheme whose plaintext space R p splits into copies of F. If Π HE-CA is an HE-IOPP for δ-correlated agreement in RS[F, L, d] with RBR soundness error ϵ CA , then Π the protocol Π δ HE-CA obtained by replacing O with Π HE-CA in Π δ O has RBR knowledge soundness √ error ϵ 1 = max{ϵ/(2η ρ), ϵ CA }. Π Furthermore, given a random oracle with λ-bit output and a query bound Q, compiling Π δ HE-CA with the BCS transformation [BCS16] yields a SNARK (over encrypted data) with knowledge error √ Q · max{ϵ/(2η ρ), ϵ CA } + O(Q 2 /2 λ ).

Proof. Consequence of combining Theorems 2 and 1.

[BGK + 23]

RBR knowledge sound 0-correlated IOP

RBR knowledge sound HE-IOP

[BCS16]

HE-SNARK

RBR knowledge sound δ-correlated IOP

HE-transformation Definition 13

RBR knowledge sound δ-correlated HE-IOP

Theorem 4

RBR sound HE-IOPP for δ-correlated agreement

Fig. 2: Summary of compilation flow for δ-correlated IOPs.

<!-- page 19 -->

Low Degree Tests for encrypted polynomials

The compilers from Section 4 need to eventually test whether the oracles sent by the IOP prover correspond to low-degree polynomials or not, with different variations of what such a test should exactly verify (δ-correlated agreement or merely closeness to an RS code). First of all, we need to think about how polynomials mix with HE. For example, the following map

f : R p → R p

d X a 7→ HE.Dec( ct i · a i ),

i=0

ct i = HE.Enc(f i )

P only corresponds to a degree-d polynomial f ∈ R p [X] as long as f (a) = di=0 f i a i ∀a ∈ R p , i.e. as long as it preserves evaluation correctness 10 . In this work, as it is common in the IOP literature, polynomials are given in a point-value representation, which matches the definition of a Reed Solomon codeword. There are a series of operations that the prover (and maybe the verifier) will have to perform on the ciphertexts within those oracles, so we also need to make sure to preserve evaluation correctness when presented with such a representation. To achieve this, we introduce the notion of encrypted polynomials. Q ℓ Definition 15 Let HE be a homomorphic encryption scheme with plaintext space R p ∼ = j=1 F p D and ciphertext space R q 2 . Let HE-IOPP be an HE-IOP of proximity. Let L = {x i,j } i∈[d],j∈[ℓ] , L ⊆ F p D Q and let ct 1 , . . . , ct d ∈ R q 2 be alleged ciphertexts such that HE.Dec(ct i ) = (m i,1 , . . . , m i,ℓ ) ∈ ℓj=1 F p D . Finally, let f ∈ F p D [X] <|L| be the polynomial such that f (x i,j ) = m i,j ∈ F p D for every x i,j ∈ L. We say that ct 1 , . . . , ct d ∈ R q 2 define an encrypted polynomial (of f , at L) if there exist admissible circuits such that, Q – On input ct 1 , . . . , ct d ∈ R q 2 and any (α 1 , . . . , α ℓ ) ∈ ℓj=1 F p D , it returns a ciphertext ct ′ such Q that, with overwhelming probability, HE.Dec(ct ′ ) = (f (α 1 ), . . . , f (α ℓ )) ∈ ℓj=1 F p D . – On input ct 1 , . . . , ct d ∈ R q 2 to the HE-IOPP, all honestly produced messages within it decrypt correctly (with overwhelming probability).

When we want to make the plaintext polynomial and evaluation domain explicit, we write (ct 1 , . . . , ct d ) ∈ EncPoly(f, L).

In other words, (ct 1 , . . . , ct d ) ∈ EncPoly(f, L) if, given those ciphertexts, it is possible both to compute EncPoly(f, F p D ) and to show within the HE-IOPP that there exists such an f .

The HE-Batched-FRI protocol

The specific HE-IOPP we will employ is the HE transformation (see Definition 13) of the (Batched) FRI protocol. The batched FRI protocol allows agreement of P a t prover to prove the δ-correlated 11 f 1 , . . . , f t by running the FRI protocol on f = i=1 β i f i for i.i.d. uniformly random β i . In fact,

P d i It could happen, for a malicious choice of the ct i ∈ R q 2 , that f (a) = i=0 g i a ∀a ∈ R p for some g i ̸ = f i . In practice, this does not give any power to the adversary: it would be equivalent to putting a wrong polynomial of the right degree within the oracle, which should be caught by the IOP. We use i.i.d uniformly random coefficients, rather than powers of a single β, since otherwise we would incur an O(n) soundness loss, see [BCI + 20, BGK + 23].

<!-- page 20 -->

replacing FRI with another IOPP would still result in a δ-correlated agreement test and as we showed before (Theorems 3 and 4), we could use any other IOPP, to which we would previously apply our HE-transformation (Definition 13).

The HE-Batched-FRI protocol

Setup: Agree on the following: Q ℓ – A HE scheme with ciphertext space R q 2 and plaintext space R p ∼ = j=1 F p D , p ̸ = 2, satisfying 2 n |(p D − 1) for some positive integer n. n – A multiplicative group L 0 = {ω, . . . , ω 2 } ⊆ F ∗ p D of order 2 n , i.e. L 0 = ⟨ω⟩. – The rate of the Reed-Solomon code, ρ = 2 −R for a positive integer R. i – A number of rounds r < n − R, each of which will use a domain L i+1 = {x 2 | x ∈ L i }, i.e. L i+1 = ⟨ω 2 ⟩. Input: For i = 1, . . . , t, alleged ciphertexts (c i,1 , . . . , c i,2 n /ℓ ) ∈ R q which allegedly satisfy (c i,1 , . . . , c i,2 n /ℓ ) ∈ EncPoly(f i , L 0 ) for some f i (X) ∈ F p D [X] <2 n−R . In other words, it should be that f i L ∈ RS[F p D , L 0 , 2 n−R ]. V has oracles {JEncPoly(f i , L 0 )K} ti=1 , whereas P has the underlying ciphertexts {EncPoly(f i , L 0 )} ti=1 . Commit phase: P batches the encryptions of functions f 1 , . . . , f t into a single encryption of a function f . Afterwards, it sequentially constructs a series of oracles to “foldings” of encryptions of that function. P $ 1. Obtain challenges β 1 , . . . , β t ← F p D from the verifier. Implicitly define the oracle Jf L K HE = ti=1 β i · Jf i L K HE from the oracles to the encrypted polynomials {EncPoly(f i , L 0 )} ti=1 . 2. For 0 ≤ i < r : $ – Obtain a challenge α i ← F p D from the verifier.

i+1

– P computes and sends the oracle JEncPoly(f (i+1) , L i+1 )K, where L i+1 = ⟨ω 2 F p D is allegedly such that (for j ∈ [2 n−i ]):

i

⟩ and f (i+1) : L i+1 →

i

i

i

f (i) (ω 2 j ) + f (i) (−ω 2 j ) f (i) (ω 2 j ) − f (i) (−ω 2 j ) + α i · . 2 · ω 2 i j

i+1

f (i+1) (ω 2

j

)=

r−1

3. The last oracle (to an encryption of) f (r) : L r → F p D , L r = ⟨ω 2 ⟩ is allegedly an encryption of a polynomial of degree strictly less than ρ · |L r |, so P can just directly send it as EncPoly(f (r) , L r ) to V.

Query phase: V, using the HE secret key sk in order to decrypt the encrypted polynomials within the oracles, checks the consistency of the messages sent by the prover. If any of the following checks fails, reject and abort. Otherwise, accept. 1. For 0 ≤ ℓ < m, V does the following in parallel: $ – Sample a random µ ℓ ← L 0 . – For 0 ≤ i < r, using the oracles {JEncPoly(f (j) , L j )K} rj=0 and challenges {α j } r−1 j=0 from the commit phase, check whether:

i

i

i

i

f (i) (µ 2 ℓ ) + f (i) (−µ 2 ℓ ) f (i) (µ 2 ℓ ) − f (i) (−µ 2 ℓ ) + α i · . i 2 · µ 2 ℓ

i+1

?

f (i+1) (µ ℓ 2

) =

i

i

i+1

Notice that the verifier needs to decrypt the values f (i+1) (µ 2 ℓ ), f (i) (µ 2 ℓ ) and f (i) (−µ 2 ℓ ) inside the oracles in order to do this. ? ∈ RS[F p D , L r , d]. 2. Decrypt EncPoly(f (r) , L r ) and check whether f (r)

L r

Fig. 3: The HE-Batched-FRI protocol.

Whereas there are new, concretely more efficient IOPs for circuit satisfiability every year [BCR + 19, COS20], a series of variants of the FRI protocol have remained as the most practical choice for an IOPP until this day. Since this is the most stable component of our overall compilers, we provide our HE-Batched-FRI protocol in Figure 3. We also adapt the results of [BGK + 23] concerning

<!-- page 21 -->

round-by-round soundness of FRI to HE-Batched-FRI. Notice that we only need to consider RBR soundness, rather than RBR knowledge soundness, since the former is enough for their δ-correlated hIOP-to-SNARK compiler.

Theorem 5. Let F be a finite field, L 0 ⊆ F ∗ a smooth multiplicative subgroup of size 2 n , d 0 = √ 2 k , ρ = d 0 /|L 0 | = 2 k−n and ℓ a positive integer. For any integer m ≥ 3, η ∈ (0, ρ/(2m)), relative √ (0) (0) distance δ ∈ (0, 1 − ρ − η) and functions f 1 , . . . , f t : L 0 → F for t ≥ 2 such that at least one of them is δ-far from RS (0) , the HE-Batched-FRI protocol (Figure 3) is complete and has round-byround soundness error n (m + 1/2) 7 · |L | 2 o ℓ ϵ = max , (1 − δ) . 3ρ 3/2 |F|

Furthermore, under Conjecture 1 (see Appendix A), the error can be further reduced to

n |L | c 2 o ℓ , (1 − δ) . (ρη) c 1 |F|

ϵ = max

Proof. Completeness follows from Theorem 2 and Definition 15. RBR soundness follows from Theorem 2 and [BGK + 23, Theorem 4.2].

Optimisations

To make our construction practical, we introduce several optimizations that may have independent value and applications beyond this work.

On the choice of HE Scheme

Our construction requires an HE scheme that supports finite fields as the plaintext space, making it compatible with nearly all modern HE schemes, such as TFHE [CGGI20], BGV [BGV12], and BFV [Bra12, FV12]. The notable exception is CKKS [CKKS17], which is inherently approximate (even for a fresh encryption, HE.Dec(HE.Enc(pk, m), sk) ≈ m rather than HE.Dec(HE.Enc(pk, m), sk) = m). This is incompatible with our verification approach, which requires exact arithmetic. Thus, our choices are BGV/BFV and TFHE, guided by practical performance and implementation availability, detailed in Section 7.

Tensoring

Recall the HE plaintext space structure from Section 2. Ideally, the plaintext ring R p should split into ℓ copies of F p D , where D meets FRI security requirements, i.e., |F p D | ≈ 2 256 . This requires F p to contain roots of unity of order at most 2N/D, where N is the cyclotomic ring degree. Given the HE scheme’s requirement that log(N ) ∈ 11, . . . , 17, p would have to be smaller than 2N/D. Additionally, FRI requires F p D to have a 2 n -th root of unity, thus pD > 2 n . In practice, using roots of unity in F p (requiring p > 2 n ) allows the NTT (Section 6.3) to run D times faster. Combining all requirements (FRI, HE, implementation), 2 n = dρ −1 < p < 2N/D, restricting input polynomial size to d < 2N ρ/D. This is feasible with parameter sets like (log(N ), ρ, D) = (17, 1/2, 6), allowing d up to 2 14 . However, better-performing parameters, such as (log(N ), ρ, D) = (14, 1/16, 12), restrict d to around 2 6 , almost entirely restricting the use of FRI use.

<!-- page 22 -->

To address this, we use a field extension F p D of F p in our HE-FRI protocol. When evaluating an encrypted polynomial on an element of F p D , we emulate the arithmetic of F p D through a circuit. This results in D HE ciphertexts, which together encrypt a single value in F p D . Alternatively, an intermediate approach uses a value d ′ , with the plaintext space as F p d ′ , and emulates F p D arithmetic with D/d ′ ciphertexts. The ideal value of d ′ depends on the application, since increasing the plaintext modulus increases all HE parameters.

Shallow Reed-Solomon encoding

Reed-Solomon encoding consists of interpreting data as a polynomial of degree (d − 1) and evaluating it at 2 n = dρ −1 independent points. Polynomial evaluation is linear and simply evaluating it 2 n times would result in quadratic performance. The Fast Fourier Transform is a staple solution for this problem, enabling the evaluation in O(2 n log 2 n ) operations. Commonly, however, it is implemented as a circuit with depth log 2 n , which poses some challenges for its homomorphic evaluation. Fortunately, FFTs, and, more specifically, Number-Theoretic Transforms (NTTs), their generalization to finite fields, are ubiquitous in the FHE literature, and solutions for evaluating them with small depth are very well established [CG99, GPvL23]. In this work, we adopt a radix-k NTT of √ parametrizable depth for some k ∈ [[2, 2 n ]] optimized based on practical performance. The NTT can be especially costly when running batched FRI, as the RS codeword needs to be calculated for each polynomial individually. This cost can be minimized by exploiting the HE scheme packing to perform the NTT over several polynomials at once. We consider the following strategies for packing.

P k X i ∈ F p [X]. We encrypt k – Single polynomial packing: Let k be a single polynomial k = d−1 P d−1 i=0 j i in an array of d/N ciphertexts ct, such that ct i encrypts j=0 k i·N +j X . The main advantage of this approach is the significantly reduced memory usage, as we process one polynomial at a time. Conversely, evaluating the NTT algorithm with this packing requires performing permutations within each ciphertext [CG99], which is an expensive process compared to the other operations needed for evaluating the NTT. – Batched polynomial packing: Let k be an N -sized list of polynomials with maximum degree (d−1), and k i,j be the coefficient of degree j of the i-th polynomial. We encrypt k in an array of d ciphertexts ct i , such that the j-th slot of ct i encrypts k j,i . The main advantage of this approach is avoiding the aforementioned permutations, as each coefficient of a polynomial would be in different ciphertexts. For large polynomials, the memory requirements to run the NTT with this packing might be impractical, however.

In both cases, even though FRI is defined over F p D , we perform the entire NTT in F p by selecting roots of unity in F p , as roots of unity in F p D would bring negligible advantage compared to the size of p (as discussed in Section 6.2). Further, the goal of the NTT is to create a redundant representation of the polynomial (i.e., the RS codeword), which consumes more memory to be stored. In this way, storing the codewords could represent a problem, even if storing the original polynomials was not. This is the main aspect we consider when choosing which type of packing we adopt. Mixed packing approaches could likely be a better solution for this problem, but developing them is not within our scope.

<!-- page 23 -->

Shallow folding

In the commit phase of HE-FRI (Figure 3), P needs to compute a series of oracles JEncPoly(f (i) , L i )K. Let us denote f (i+1) = Fold(f (i) , α i ). The complexity of producing all such foldings as described there is O(2 n ), while the depth 12 is n. To reduce depth, we replace the FFT-like algorithm with a DFT-like algorithm. We compute the first layer of the Fold operation as usual, then pre-compute constants for the following layers, expressing each as a composition Fold ◦ . . . ◦ Fold. Each layer can now be expressed as inner products of the original polynomial, reducing the depth to 1, while increasing the complexity to O(2 n log(2 n )). This does not affect the overall FRI complexity (dominated by the NTT). The Verifier’s side remains unchanged. The full algorithm is presented in Appendix D.

Fast decryption

In RLWE-based cryptography, decrypting small amounts of data may incur a significant overhead depending on the adopted parameters. An RLWE sample of dimension N encrypts up to N messages in F p , which can all be decrypted at once with cost O(N log N ). However, if one wants to decrypt just a single message in F p , the cost would be at least O(N ), which represents a performance overhead of N/ log(N ) times compared to the amortized cost of decrypting all messages at once. During the commit phase of HE-FRI, the prover performs computation using RLWE samples of dimension N encrypting N messages in F p . During the query phase, however, the verifier only needs to learn two evaluation points in F p D per round for each linearity check. In this way, if the prover provides these points packed in a ciphertext of dimension N , it would impose a performance overhead of at least N/(2D) times for the verifier compared to an optimal RLWE decryption (i.e., it would be decrypting at least N/(2D) more messages than necessary). To improve on this, we propose three possible approaches. We summarise them here and present the full details in Appendix D.

Repacking The simplest way of minimizing decryption costs is to reduce the ciphertext dimension. This can be achieved in several ways. In this work, since the prover also needs to arithmetically manipulate points individually, we choose to extract the points to LWE samples and repack them using a key-switching algorithm. We pack the two points needed per linearity check in the same RLWE samples, further minimizing decryption costs.

Decomposition and recomposing While the repacking already enables us to significantly reduce the ciphertext dimension, we are still limited by the value of p. Specifically, the ciphertext dimension depends on the ciphertext modulus for security, which, in turn, depends on the plaintext modulus p. To enable further reductions in the size of N , we introduce a decomposition and recomposing procedure based on techniques introduced in [CLOT21] and described in [CGGI20]. Our proposal starts from the observation that since the verifier does not compute any homomorphic operations on these samples (it only decrypts them), we do not need to preserve any homomorphic properties. In fact, once the commit phase is finished, the evaluation points can be treated simply as strings of bits, and the goal becomes to encrypt them in the smallest possible RLWE ciphertext. Considering this, we homomorphically decompose elements in F p in digits of size log p̄ for some p̄ < p. This process enables us to repack the evaluation points in RLWE ciphertexts with smaller moduli and, hence, smaller dimensions. We present our full recomposition process in Algorithm 3.

n is the logarithm of the codeword size. Folding is a linear algorithm.

<!-- page 24 -->

Adding samples Adding samples appears as an alternative to the decomposition. The repacking procedure mentioned above allows us to reduce the dimension of the RLWE samples that are sent to the verifier, but we are still not using all the coefficients in the sample. Concretely, our implementation uses ciphertexts with N = 512 to only encrypt 2D = 32 messages. Considering this, the verifier can further minimize decryption costs by adding rotations of ciphertexts together and decrypting messages from multiple ciphertexts at once. We note that rotation can be done considering coefficient representation, which is inexpensive. While this efficiently minimises the number of decryptions, it does not, contrary to the decomposition, reduce the cost of hashing operations or proof size.

Experimental Results

Operating over the plaintext space allows compatibility with nearly all HE schemes (except CKKS), enabling various implementation methods. For this proof of concept, we focus on a simple and efficient implementation that demonstrates practical execution times for both the prover and verifier. While we make specific choices of schemes and techniques, our construction remains compatible with most existing schemes. Appendix E provides a performance characterization based on the number of basic operations executed by each party, with and without the optimizations in Section 6. This broader view of HE-FRI performance helps extrapolate the results to other parameters or schemes.

Practical Parameters

For the security of FRI, we consider parameters established by previous literature [BGK + 23], reproduced in Table 1. There are also practical parameters that are required for functionality, as we discussed in Section 6.2. Considering this, Table 2 presents the main choices of parameters according to the maximum size of the input polynomial that they support. We note that, for every parameter, the maximum size of the input polynomial can be increased by up to D times at the cost of D times more expensive NTT (as also discussed in Section 6.2).

Table 1: Security parameters we adopt for FRI, based on estimates of [BGK + 23] using Conjecture 1. We approximate the size of the field for practical reasons.

log 2 (|F p D |)

Parameter

FRI 0 FRI 1 FRI 2 FRI 3

251-269

Proof-of-concept implementation

m

δ

ρ

1/2 1/4 1/8 1/16

We build our proof of concept over the implementation of [S + 21], a Python-implemented version of FRI for prime fields. We extend it to work over the extension field F p D and connect it to optimized FHE libraries to implement the encrypted arithmetic. We consider polynomials of degree up to 2 15

<!-- page 25 -->

Table 2: Practical parameters for FRI based on the maximum size of the input polynomial d.

Maximum input size log 2 (d)

D

log 2 (|F p D |)

log 2 (p)

p

and present results for parameter sets FRI 0 and FRI 3 , which are optimized for the verifier and the prover, respectively. We run all the experiments in a c6i.metal instance (Intel Xeon 8375C at 3.5 GHz with 256 GiB of RAM) on AWS. The prover is parallelized to use up to 32 threads and the verifier is single-threaded.

FRI 3 FRI 0

Time (s)

Polynomial Size (log 2 )

(a) Prover (32 threads)

Time (ms)

Polynomial Size (log 2 )

(b) Verifier (single-thread)

Fig. 4: Performance of HE-FRI using parameter sets FRI 3 and FRI 0 for D = 16 for 4096 polynomials (batched). Detailed results are provided in Appendix F.

Prover performance Figure 4a shows the results for the prover. It includes the execution time of the RS encoding, batching, and folding procedures. For the RS encoding, we implemented a generic RNS-based homomorphic NTT implementation built over Intel HEXL [BKS + 21]. Its performance should be similar to most commonly used HE libraries, as HEXL is used for RNS implementations on libraries such as HELib [HS20] and OpenFHE [ABBB + 22]. We use depth-2 NTTs with paral-

<!-- page 26 -->

lelized recursive calls (up to a maximum of 32 threads) and perform batched polynomial packing (Section 6.3) to compute it on N = 4096 polynomials at once. Our construction is flexible to the HE encoding, as we may later move to the required encodings during batching, as Appendix C details. Our folding procedure, on the other hand, has fixed depth (Section 6.4) and is the last procedure to run before decryption. As such, it requires a much smaller ciphertext modulus and can be evaluated using single-precision (non-RNS) implementations. In this way, whenever possible, we evaluate it using implementation techniques from TFHE [CGGI20] using the MOSFHET library [GBA24]. Despite being asymptotically quasi-linear, we note that the execution time increases almost linearly with the polynomial size, which is a result of better parallel efficiency and the overhead introduced by repacking (which is linear). With FRI 0 , it takes less than 0.5 seconds to run for polynomials of degree bound up to 2 8 , going up to 207 seconds for polynomials of degree bound 2 15 .

Verifier performance Figure 4b shows the verifier results. Verification in FRI is sublinear and typically runs in milliseconds. Hence, Python is not a good fit to showcase practical timings, and we implemented an optimized version of it in C. We only present a single-threaded version, but we note that it is trivially parallelizable and could be significantly accelerated for larger parameters. We show results for FRI 0 and FRI 3 , noting that other parameters can also affect verifier performance, particularly decryption costs. To minimize these, we only considered repacking without decompositions, but Appendix D discusses further improvements. Our current setup allows for batched verification of 4096 codewords in as low as 6ms, with performance scaling linearly with the batch size. Future work includes optimizing for smaller batches and other parameters.

## Acknowledgements

We would like to thank Zvika Brakerski for comments about our repacking optimization for the HE-Batched-FRI protocol. We also want to thank Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari and Michał Zajac for a useful conversation about their work [BGK + 23] and confirming that their analysis does not require finite fields to be prime. This work was partly done while A. Guimarães was a Ph.D. student at University of Campinas, Brazil. He was supported by the São Paulo Research Foundation under grants 2013/08293- 7, 2019/12783-6, and 2021/09849-5. This work is partially funded by the European Union (GA 101096435). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Commission. Neither the European Union nor the European Commission can be held responsible for them.

## References

ABBB + 22. Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. OpenFHE: Open-Source Fully Homomorphic Encryption Library. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC’22, page 53–63, New York, NY, USA, 2022. Association for Computing Machinery. ACY23. Gal Arnon, Alessandro Chiesa, and Eylon Yogev. IOPs with inverse polynomial soundness error. Cryptology ePrint Archive, 2023.

<!-- page 27 -->

AHH + 24.

Nuttapong Attrapadung, Goichiro Hanaoaka, Ryo Hiromasa, Yoshihiro Koseki, Takahiro Matsuda, Yutaro Nishida, Yusuke Sakai, Jacob C. N. Schuldt, and Satoshi Yasuda. Privacy-preserving verifiable CNNs. In Christina Pöpper and Lejla Batina, editors, Applied Cryptography and Network Security, pages 373–402, Cham, 2024. Springer Nature Switzerland. APS15. Martin R Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. BBHR18. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast reed-solomon interactive oracle proofs of proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 14:1–14:17. Schloss Dagstuhl, July 2018. BCCW19. Fabian Boemer, Anamaria Costache, Rosario Cammarota, and Casimir Wierzynski. nGraph-HE2: A high-throughput framework for neural network inference on encrypted data. In Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 45–56, 2019. BCFK21. Alexandre Bois, Ignacio Cascudo, Dario Fiore, and Dongwoo Kim. Flexible and efficient verifiable computation on encrypted data. In Juan Garay, editor, PKC 2021, Part II, volume 12711 of LNCS, pages 528–558. Springer, Heidelberg, May 2021. BCI + 20. Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for reed-solomon codes. In 61st FOCS, pages 900–909. IEEE Computer Society Press, November 2020. BCR + 19. Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 103–128. Springer, Heidelberg, May 2019. BCS16. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B, Part II, volume 9986 of LNCS, pages 31–60. Springer, Heidelberg, October / November 2016. BGBE19. Alon Brutzkus, Ran Gilad-Bachrach, and Oren Elisha. Low latency privacy preserving inference. In International Conference on Machine Learning, pages 812–821. PMLR, 2019. BGK + 23. Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, and Michał Zając. Fiat-Shamir Security of FRI and Related SNARKs. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, pages 3–40, Singapore, 2023. Springer Nature Singapore. BGKS20. Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling outside the box improves soundness. In Thomas Vidick, editor, ITCS 2020, volume 151, pages 5:1–5:32. LIPIcs, January 2020. BGV12. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, pages 309–325. ACM, January 2012. BKS18. Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-case to average case reductions for the distance to a code. In 33rd Computational Complexity Conference (CCC 2018). Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, 2018. BKS + 21. Fabian Boemer, Sejun Kim, Gelila Seifu, Fillipe D.M. de Souza, and Vinodh Gopal. Intel HEXL: Accelerating Homomorphic Encryption with Intel AVX512-IFMA52. In Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC ’21, page 57–62, New York, NY, USA, 2021. Association for Computing Machinery. BMMP18. Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. Fast homomorphic evaluation of deep discretized neural networks. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 483–512. Springer, Heidelberg, August 2018. Bra12. Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 868–886. Springer, Heidelberg, August 2012. BV14. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on computing, 43(2):831–871, 2014. CCH + 19. Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs. Fiat-Shamir: from practice to theory. In Moses Charikar and Edith Cohen, editors, 51st ACM STOC, pages 1082–1090. ACM Press, June 2019. CCL15. Ran Canetti, Asaf Cohen, and Yehuda Lindell. A simpler variant of universally composable security for standard multiparty computation. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 3–22. Springer, Heidelberg, August 2015. CG99. Eleanor Chu and Alan George. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. CRC Press, November 1999. Google-Books-ID: 30S3kRiX4xgC.

<!-- page 28 -->

CGGI20.

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91, January 2020. Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 409–437. Springer, Heidelberg, December 2017. Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, pages 670–699. Springer, Heidelberg, December 2021. Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. Succinct arguments in the quantum random oracle model. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part II, volume 11892 of LNCS, pages 1–29. Springer, Heidelberg, December 2019. Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 769–793. Springer, Heidelberg, May 2020. Benjamin R Curtis and Rachel Player. On the feasibility and impact of standardising sparse-secret LWE parameter sets for homomorphic encryption. In Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 1–10, 2019. Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. LWE with side information: Attacks and concrete security estimation. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 329–358. Springer, Heidelberg, August 2020. Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 643–662. Springer, Heidelberg, August 2012. Léo Ducas and Damien Stehlé. Sanitization of FHE ciphertexts. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages 294–310. Springer, Heidelberg, May 2016. Dario Fiore, Rosario Gennaro, and Valerio Pastro. Efficiently verifiable computation on encrypted data. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014, pages 844–855. ACM Press, November 2014. Dario Fiore, Anca Nitulescu, and David Pointcheval. Boosting verifiable computation on encrypted data. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part II, volume 12111 of LNCS, pages 124–154. Springer, Heidelberg, May 2020. Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144, 2012. https://eprint.iacr.org/2012/144. Antonio Guimarães, Edson Borin, and Diego F. Aranha. MOSFHET: Optimized Software for FHE over the Torus. Journal of Cryptographic Engineering, July 2024. Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. crypto. stanford.edu/craig. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 169–178. ACM Press, May / June 2009. Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 465–482. Springer, Heidelberg, August 2010. Sanjam Garg, Aarushi Goel, and Mingyuan Wang. How to prove statements obliviously? Cryptology ePrint Archive, Paper 2023/1609, 2023. https://eprint.iacr.org/2023/1609. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218–229. ACM Press, May 1987. Chaya Ganesh, Anca Nitulescu, and Eduardo Soria-Vazquez. Rinocchio: SNARKs for ring arithmetic. Journal of Cryptology, 36(4):41, October 2023. Antonio Guimarães, Hilder V. L. Pereira, and Barry van Leeuwen. Amortized bootstrapping revisited: Simpler, asymptotically-faster, implemented. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, pages 3–35, Singapore, 2023. Springer Nature Singapore. Sergey Gorbunov, Vinod Vaikuntanathan, and Daniel Wichs. Leveled fully homomorphic signatures from standard lattices. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 469–477. ACM Press, June 2015.

CKKS17.

CLOT21.

CMS19.

COS20.

CP19.

DDGR20.

DPSZ12.

DS16.

FGP14.

FNP20.

FV12.

GBA24.

Gen09a.

Gen09b.

GGP10.

GGW23.

GMW87.

GNS23.

GPvL23.

GVW15.

<!-- page 29 -->

Hab22.

Ulrich Haböck. A summary on the fri low degree test. Cryptology ePrint Archive, Paper 2022/1216, 2022. https://eprint.iacr.org/2022/1216. Shai Halevi and Victor Shoup. Bootstrapping for HElib. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 641–670. Springer, Heidelberg, April 2015. Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Report 2020/1481, 2020. https://eprint.iacr.org/2020/1481. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1–23. Springer, Heidelberg, May / June 2010. Szepieniec et al. Anatomy of a stark - tutorial for starks with supporting code in python, November 2021. https://github.com/aszepieniec/stark-anatomy. Nigel P. Smart and Frederik Vercauteren. Fully homomorphic SIMD operations. DCC, 71(1):57–81, 2014.

HS15.

HS20.

LPR10.

S + 21.

SV14.

A

A conjecture on FRI

Our implementation makes use of the following Conjecture (Conjecture 5.12 from [BGK + 23]). Before presenting it, we introduce the following notation. For an index i ∈ {0, . . . , k}, we let RS (i) := RS[F, L i , d i ], where L 0 ⊂ F ∗ is a smooth multiplicative subgroup of size 2 n , d 0 = 2 n−R , L i := {z 2 : z ∈ L i−1 }, and d i = d i−1 /2. Note that this implies that for every i ∈ {0, . . . , n − R}, L i is a smooth multiplicative subgroup of size 2 n−i . For a function f : L i → F and x ∈ F, we define an “algebraic hash function" [BKS18] as follows:

H x [f ] : L i+1 → F

x − s ′ x − s ′′ ′′ · f (s ) + · f (s ′ ) s ′′ − s ′ s ′ − s ′′ s, s ′ ∈ L i , s ′ ̸ = s ′′ , (s ′ ) 2 = (s ′′ ) 2 = s ∈ L i+1 .

H x [s] :=

This hash function H x has the property that if f ∈ RS (i) , then H x [f ] ∈ RS (i+1) for any x. Additionally, for arbitrary G i : L i → F and G i+1 = H x [G i ], then G i and G i+1 will pass all verifier checks during the Query Phase of the FRI protocol, so long as d i+1 > 1.

Conjecture 1. Let F be a finite field, L 0 ⊂ F ∗ a smooth multiplicative subgroup of size 2 n , d 0 = 2 n−R and ρ = 2 −R . There exist constants c 1 and c 2 such that for all ν > 0 and any δ ≤ 1 − ρν, for any function G i : L i → F that is δ-far from RS (i) we have that

h i |L 0 | c 2 Pr ∆(H x [G i ], RS (i) ) ≤ δ ≤ . $ (νρ) c 1 · |F| x ← − F Moreover, for any f 1 , . . . , f t : L 0 → F such that at least one f i is δ-far from RS (0) , we have " X |L 0 | c 2 (0) , Pr ∆(G 0 , RS ) ≤ δ|G 0 = α i f i ≤ $ (νρ) c 1 · |F| α 1 ,...,α t ← − F i " X t · |L 0 | c 2 (0) i−1 Pr ∆(G 0 , RS ) ≤ δ|G 0 = α f i ≤ . $ (νρ) c 1 · |F| α ← − F

i

In their work, Ben-Sasson et al. [BCI + 20] state the following: “To the best of our knowledge,

nothing contradicts setting c 1 = c 2 = 2", and when the characteristic of F is greayer than d 0 state that they “are not aware of anything contradicting c 1 = c 2 = 1". Finally, they do note that if F has characteristic 2, then c 1 = c 2 = 1 is impossible, due to an attack of [BGKS20].

<!-- page 30 -->

B

HE definitions

B.1

Semantic Security

Definition 16 (Semantic Security) Let HE = (HE.KeyGen, HE.Enc, HE.Dec, HE.Eval) be a (publicd and let key) homomorphic encryption scheme as defined above, let (pp, C) ← HE.Setup(1 λ , M, Circ), A be an adversary. The advantage of A with respect to HE is defined as follows, with (sk, pk, evk) ← HE.KeyGen(1 λ , C, pp).

Adv HE A (λ) := Pr[A(pk, ct) = 1 : ct ← HE.Enc(pk, 1)]

− Pr[A(pk, ct) = 1 : ct ← HE.Enc(pk, 0)] .

HE is semantically secure if Adv HE A = negl(λ) for every PPT adversary A.

B.2

The BGV Scheme

Following [HS20], we define the BGV scheme [BGV12] as a levelled FHE scheme based on the RLWE problem [LPR10]. The ciphertext space is R q = Z q [x]/(x n + 1), where q is the ciphertext modulus. The plaintext space is R p = Z p [x]/(x n + 1), where p is the plaintext modulus. Messages and ciphertexts will be considered as polynomials in R p and R q , respectively. The BGV scheme is parametrised by the following:

– The length L of the moduli chain Q L ≫ . . . ≫ Q 0 , where Q i |Q i+1 for i ∈ {0, . . . , L − 1} – The decomposition base ω, where h = ⌊log(q)⌋ + 1 is the number of elements in a decomposition of an element modulo q in base ω. – The secret key distribution S, typically ternary with a specified Hamming weight – The error distribution χ, typically a discrete Gaussian of small standard deviation

BGV consists of the algorithms HE.KeyGen, HE.Enc, HE.Dec, HE.Add, HE.PreMult, HE.Relinearize, HE.KeySwitch and HE.ModSwitch, defined as follows. Below, we assume that a fresh encryption will be “at the top" modulus L, but note that HE.Enc can be defined at any level i.

HE.KeyGen(1 λ ): Draw s ← S and set (1, s) := sk as the secret key. Sample a ← R Q L and e ← χ. Set pk = (pk[0], pk[1]) := ([−as − pe] Q L , a) as the public key. The evaluation key is defined as follows. For i ∈ {0, . . . , h}, sample a i ← R q uniformly at random, and e i ← χ. Output evk = {(−(a i s + pe i ) + w i s 2 , a i )} i∈{0,...,h} in R q . Return (sk, pk, evk).

HE.Enc(pk, m): Let m ∈ R p be a message. Let Q i , i ∈ {0, . . . , L} be the modulus in the moduli chain of the current level. Sample u ← S and e 1 , e 2 ← χ. Return ct = (ct[0], ct[1]) := ([m + pk[0]u + pe 1 ] Q i , [pk[1]u + pe 2 ] Q i ).

HE.Dec(sk, ct): Let ct = (c 0 , c 1 ) and sk = (1, s). Return m ′ = [[c 0 − sc 1 ] Q i ] p .

HE.Add(ct 0 , ct 1 ): Bring ct 0 , ct 1 to the same level by modulus switching the ciphertext at the higher level to the lower level. Return ct := ([ct 0 [0] + ct 1 [0]] Q i , [ct 0 [1] + ct 1 [1]] Q i ).

<!-- page 31 -->

HE.Mult(ct 0 , ct 1 , evk): Bring ct 0 , ct 1 to the same level by modulus switching the ciphertext at the higher level to the lower level. Calculate ct mult = (c 0 , c 1 , c 2 ) := ([ct 0 [0]ct 1 [0]] Q i , [ct 0 [0]ct 1 [1] + ct 0 [1]ct 1 [0]] Q i , [ct 0 [1]ct 1 [1]] Q i ). j m j m Q j Q j ms HE.ModSwitch((ct,Q i ),Q j ): Let ct = (ct[0], ct[1]) be at level i. Return ct := , Q i ct[1] . Q i ct[0]

p

p

HE.KeySwitch(ct, sk ′ , evk): Let ct[0] = c 0 , ct[1] = c 1 and ct[2] = c 2 . Let evk[i][0] = −(a i s + pe i ) + w i s 2 and evk[i][1] = a i , and express c 2 in base ω as

c 2 =

i=0

h X (i) c 2 ω i .

P h (i) (i) ′ ′ ′ ′ i=0 c 2 evk[i][1]. Output ct = (c 0 , c 1 ). i=0 c 2 evk[i][0] and c 1 = c 1 +

P h

Set c ′ 0 = c 0 +

Batching from slot encoding

C

Applications using FHE schemes such as BGV and BFV often employ the CRT encoding [SV14] to work with “plaintext slots”, which can be multiplied element-wise. HE-FRI doesn’t require such slots as it doesn’t perform multiplications between ciphertexts. One could choose to employ them nonetheless, but the LWE extraction procedure needed for the repacking becomes significantly more expensive when using slot encoding. The simplest way of approaching this issue would be converting from slots to the standard coefficient encoding before evaluating FRI. Efficient methods for it are well defined in the bootstrapping literature [HS15] and are composed of linear combinations that are reasonably inexpensive to evaluate. Notwithstanding, we introduce a method for evaluating (batched) HE-FRI directly over the slot representation that produces evaluation points in coefficient representation at no additional cost. This method comes from the observation that the first step of the folding is to perform a linear combination of several codewords, which are packed according to the batched polynomial packing described in Section 6.3. This process consists essentially of a linear combination of values in the same ciphertext, which can be obtained directly from the slot representation. More specifically, let m ∈ R p be the polynomial encoding the plaintext t = [t 0 , t 1 , . . . , t N −1 ] ∈ F p × . . . × F p in slot representation, which contains the k-th evaluation points of every input polynomial. The process for converting from slot to coefficients can be implemented as follows, where z i are vectors of constants and m̂ is the vector of coefficients of m. We can recover t as a coefficient-wise encoded polynomial as follows.

t = [⟨ m̂, z 0 ⟩, ⟨ m̂, z 1 ⟩, . . . , ⟨ m̂, z N −1 ⟩].

(2)

In practice, each z i would be a different permutation of a vector of powers of some root of unity in R p and the vector t would be encoded as a polynomial (coefficient encoding). For our purposes, however, the specific details of this process are unimportant. At the beginning of the folding, we would batch the codewords as follows, to obtain the k-th point of the initial codeword f (0) .

<!-- page 32 -->

N X (k) = ⟨ m̂, z i ⟩ · β i .

(0)

f

i=0

(3)

Writing the inner product explicitly and reordering the summations, we have that:   ! N N N N X X X X (0)  f (k) = m̂ j · z i,j  · β i = m̂ j · z i,j · β i

i=0

j=0

(4)

i=0

j=0

In this way, we can pre-compute the inner summation of constants, and obtain f (0) (k) from a single inner product with m̂, without having to calculate t. As this is a single inner product, we P N ′ can evaluate it with just a polynomial multiplication. Let z j = i=0 z i,j · β i , we have that:   N −1 X f (0) (k) = ExtractLWE(m ·  z 0 ′ − z j ′ x N −j  , 0). (5)

D

Further improvements for decryptions

D.1

Shallow Fold

Algorithm 1: Shallow Fold

Input : n ′ = 2 n , r, f (0) , ω. Output: codewords f (i) , for i ∈ [[0, r − 1]]. 1 c ← [0, . . . , 0] 2 for k ← 0 to r − 1 do for i ← 0 to n ′ /2 − 1 do for j ← 0 to 2 k+1 − 1 do

(−1) j α j ω i

c i+jn ′ /2 ← c i+jn ′ /2 · 12 · 1 +

j=1

// First pre-compute the constants

for i ← 0 to n ′ /2 − 1 do (k) f i ← 0 for j ← 0 to 2 k+1 − 1 do ′ f (k) (ω i ) ← f (k) (ω i ) + c i+j·(n ′ /2) · f (ω i+j·(n /2) ) (0)

n ′ ← n ′ /2 ω ← ω 2

return f

D.2

Decomposed Repacking

// Now compute the Fold

The verifier does not compute any homomorphic operations over ciphertexts in our construction, hence we do not need to preserve any homomorphisms for them. In fact, once the commit phase is finished, the evaluation points can be treated as just strings of bits, and our goal becomes to

<!-- page 33 -->

encrypt them in the smallest possible ciphertext. As described in Section 6.5, we define repacking and recompositions algorithms to improve performance by exploiting this fact. Algorithm 2 shows the repacking procedure, which requires the subprocedures listed in the following paragraph. We use techniques introduced in [CLOT21] for the decomposition and described in [CGGI20] for the other procedures. We note that, although most of these subprocedures are often used with the TFHE scheme [CGGI20] in previous literature, they are generic for RLWE-based FHE, and we do not rely on any specific property of TFHE.

Algorithm 2: Repacking

Input : Two vectors of RLWE samples x = [x 0 , x 1 , . . . , x d−1 ] and y = [y 0 , y 1 , . . . , y d−1 ], encrypting N evaluation points in F p D each; Input : indices i x , i y ∈ {0, . . . , N − 1} indicating the position of two evaluation points within each element of x and y, respectively; Input : input and output parameter sets (p, q, N ) and (p, q, N ); Input : decomposition base b = log(p); Input : a packing key switching key ksk Output: Repacked ciphertext // Extract the evaluation points to LWE samples 1 for j ← 0 to d do x̂ j ← ExtractLWE(x j , i x ) ŷ j ← ExtractLWE(y j , i y )

// Decompose each LWE sample in k new samples, each encrypting log(p) bits of the evaluation points b 4 k ← log (p) /2 5 for j ← 0 to D − 1 do for i ← 0 to k − 1 do c̃ kj+i ← Decompose p,q (x̂ j , i) c̃ k(j+D)+i ← Decompose p,q (ŷ j , i)

// Pack all LWE samples in a single RLWE return PackingKeySwitching([c̃ 0 , c̃ 1 , . . . , c̃ 2Dk ], ksk)

P −1 i – ExtractLWE: Given an RLWE sample c encrypting a polynomial m = N i=0 m i X under ′ key s, ExtractLWE(c, i) produces an LWE sample encrypting m i under key s , where s ′ is the vector interpretation (i.e. the array of coefficients) of s. – Decompose: Given an LWE sample c encrypting a message m ∈ Z p with ciphertext modulus q, the procedure Decompose p,q (c, i) decomposes the message in base p and produces an LWE sample encrypting its i-th most significant digit with ciphertext modulus q < q. This procedure is implemented as modular reduction followed by a real division (ModDown), as shown in Equation 6: q Decompose p,q (c, i) 7→ [c] (q/p i ) · . (6) (q/p i ) q

– PackingKeySwitching: Given a list of LWE samples c i encrypting messages m i , respectively, for i ∈ [[0, N −1]] and a key switching key ksk, the PackingKeySwitching produces an RLWE P −1 i sample C encrypting the polynomial m = N i=0 m i X . In this process, the dimension of C is defined by ksk.

<!-- page 34 -->

We select p and its associated dimension N as the smallest possible values that allow the encryption of a string of 2 log(|F p D |) bits while providing a 128-bit security level. Additionally, the decomposition algorithm requires the ciphertext modulus q to be divisible by p, which, for simplicity, we achieve by mod-switching the ciphertext to a power-of-two modulus before the repacking. Table 3 presents the main practical choices for these parameters. We note that, depending on the size of p, some of them may not require decomposition but would still benefit from the repacking.

Table 3: Practical choices for FHE parameters for the repacking procedure. In this table, k is the module-LWE dimension and q is the ciphertext modulus. All parameters are estimated for the 128-bit security level, and the decryption cost is measured in the number of multiplications.

k

log 2 (q)

N

Parameter Set

P 0 P 1 P 2 P 3 P 4 P 5

Decryption Cost

Size (bytes)

To minimize the noise generated by the repacking, we always run the PackingKeySwitching with a larger parameter set and perform another key switching to reduce the dimension at the end. For example, we could first perform the folding using P 5 ; then, the repacking would extract and decompose the samples still using P 5 . PackingKeySwitching would repack them using P 1 . Finally, before committing to the codeword, the prover would run another key switching to reduce from P 1 to P 0 . This final reduction may not improve performance considerably (as decryption in P 1 is only 10% slower than in P 0 ), but it would reduce the size of the ciphertext by 33%, accelerating hash operations and reducing proof size.

D.3

Recomposition

The repacking process is fundamental for minimizing the impact of the HE overhead on FRI, but, if used with the decomposition, it also introduces some challenges for the verifier to recover the evaluation points in F p D . Algorithm 3 shows the full recomposition process, and the next paragraphs describe the main challenges it addresses. We first recall the definition of the phase function.

Definition 17 ([CGGI20]) Let HE be a Homomorphic Encryption scheme as defined above. For a concrete instantiation, that is to say, for a fixed key pair (sk, pk, evk), and for a ciphertext ct = (ct 0 , ct 1 ) that is the output of the HE.Enc algorithm (and has possibly been computed on) defined modulo some q. We define the phase function as

ψ(ct) sk = ct 1 − sk · ct 0

(mod q).

<!-- page 35 -->

Algorithm 3: Recomposition

Input : Repacked RLWE ciphertext ct = (ct 0 , ct 1 ) Input : Secret key sk Input : Decomposition base b = log(p), and message scaling factor ∆ Output: An array of points v̂ ∈ F 2D p ct 1 −ct 0 ·sk 1 v ← // Calculate the phase 2 b+2 b 2 k ← log (p) /2 // Recompose each point in F p 3 for j ← 0 to 2D − 1 do v v̂ j ← kj+k−1 4 k j v̂ j x ← 2 b−2

for i ← k − 2 to 0 step − 1 do // Calculate the noise propagated by the previous digit c ← SignExtend (x − [v kj+i ] 4 ) // Remove the noise and scale j k v +c v̂ j ← v̂ j + kj+i · 2 b(k−1−i)

// Extract the two most significant bits to x j k (v kj+i +c) x ← 2 b j m v̂ v̂ j ← ∆ j

return v̂ Procedure SignExtend(x) if x = 3 then return −1

else if x = 1 then return 1 return 0

Message recomposition. During the repacking process, we extract digits relying on the fact that p divides q. Our plaintext space, on the other hand, is defined by a prime modulus p following FRI requirements, which is not divisible by p. Therefore, we will interpret the extracted digits not as digits of the message, but as digits of the phase function (Definition 17). Recall that the phase function is computed modulo q, and we have that p | q. At the time of decryption, the verifier needs therefore to first remove the noise and recompose the phase before dividing by the scaling factor ∆.

Digit decomposition noise. Considering the decomposition process presented in Equation 6, at the extraction of the i-th digit, the (i + 1)-th digit remains in the sample and is treated as noise. This noise increases the probability of a decryption error significantly once added to the key-switching noise. To avoid this problem, we select parameters that allow us to encrypt at least two extra bits. To give a concrete example, if p = 2 8 , we select the HE parameters to encrypt a 10-bit message, so that we also preserve the bits following the least significant bit (LSB) of our message, as illustrated in Figure 5). At high level, one can view these two extra bits as “redundant", that allow for a higher noise growth, without causing a decryption error. Notice that, for the (k − 1)-th digit, these redundant bits will be zero, as there is no k-th digit, counting from zero. For all other digits, the redundant bits of the i-th digit should be the two most significant bits (MSBs) of the (i + 1)-th digit. Considering this, the verifier decrypts the digits sequentially from the least to the most significant and uses the MSBs of the previous digit and the redundant bits to correct for possibly propagated errors. Notice that these bits are supposed to be the same, and hence this process will not change

<!-- page 36 -->

the redundant bits if there is no propagated noise. Otherwise, if the noise propagates up to the redundant bits (also shown in Figure 5), it will correct the message to its original value.

Message

Decompose

i-th Digit

i=0

i=1

Correct

i=2

i=3

Redundancy Bits

Noise

i-th Digit

i=0

i=1

i=2

i=3

Redundancy Bits

Fig. 5: Example of decomposition and error correction. Notice that the process for correcting using the redundant bit only occurs after the decryption.

D.4

Using bootstrapping

Besides reducing costs for the verifier, the repacking technique also allows us to produce ciphertexts with a small plaintext modulus, regardless of the size of the base field we adopt for FRI. This in turn makes it possible to bootstrap these ciphertexts, which would otherwise be prohibitively expensive for some of the sizes of base fields we consider for FRI (we consider |F p | ranging from 2 16 up to 2 50 ). Bootstrappings are particularly useful for our construction in two ways. First, they enable the prover to remove the digit decomposition noise, which leads to better parameters and hence better performance for the verifier. Bootstrapping also makes the error correction part of Algorithm 3 unnecessary. Second, it can also enable us to achieve the notion of Circuit Privacy defined in Definition 14. In particular, we know that we can use bootstrapping as a rerandomization algorithm [DS16].

E

HE-FRI performance in the number of operations

Table 4 shows the impact of our optimizations for FRI with a constant depth equal to 4. While the number of operations grows for the prover, the growth for the verifier (Query and RS decode

<!-- page 37 -->

procedures) only depends on the RLWE decryption overhead, which is independent of the size of n. Furthermore, all our optimizations allow for tradeoffs between the number of operations and the depth of the circuit for the prover.

Table 4: Cost and depth comparison between FRI [BBHR18] and HE-FRI. We only consider the number of cost-dominant operations, which is the multiplication in F p D for all procedures except for the Merkle Tree and query phases, where the cost of committing and verifying the Merkle tree dominates. For HE-FRI, we also include the overhead of RLWE encryption and decryption operations, given by the factors P 0 and P 1 which refer to the decryption costs presented in Table 3. In turn, P ′ i = P i log 2 (p D )/b is the amortized cost of decrypting each element in F p D using the repacking method (Section 6.5), where b is the number of bits this parameter set can encrypt. Finally, to simplify notation, let m ′ = ⌈log 2 (m)⌉, where m is the number of linearity checks defined by the security parameters of FRI.

Cost

Procedure

FRI

RS encode 2 n (n) ′ n+1 Folding 2 − 2 m +1

′

Depth FRI HE-FRI

HE-FRI √ 2 n+1 2 n 2 n (n − m ′ )

n (n − m ′ )

′

Merkle Tree 2 n+1 − 2 m +1 2 n+1 − 2 m +1 P 1

′

′

Query 2m (n − m ) ′ RS decode 2 m m ′

E.1

Operation counting

m (n − m ) P 0 /D ′ 2 m (m ′ + P ′ 1 )

As we built HE-FRI over the FRI implementation of Szepieniec et al. [S + 21], we extended it with our proposals and instrumented it to measure the number of operations. We only consider the number of cost-dominant operations in F p D , and we measure them for each level of depth of the algorithm individually. We evaluate each phase of the protocol separately, leaving the tradeoffs between them to be addressed when considering practical instantiations.

Verifier Performance Figure 6-a shows the number of F p D elements received by the verifier during FRI, a key performance metric since each element requires a Merkle Tree check, the most expensive verifier operation. In HE-FRI, each element also needs decryption, adding significant overhead, as shown in Figure 6-b. We define our comparison baseline based on two scenarios:

– Outsourcing: A client (the verifier) wants to outsource a polynomial evaluation to a (usually more powerful) server. In this case, the baseline for comparison is a local evaluation, i.e., one in which the verifier receives the entire polynomial encrypted from the server, decrypts it and evaluates it themselves. For this scenario, HE-FRI provides gains for polynomials larger than 2 17 , as Figure 6-b shows. – Zero-Knowledge: A client (verifier) wants to know the evaluation of a polynomial P at some points x, but the server does not want to reveal any information about P besides its evaluation at x. In this scenario, local evaluation is not an option, and HE-FRI, or some other verifiable polynomial evaluation method over encrypted data, must be used.

<!-- page 38 -->

FRI 0 m = 102, ρ = 1/2

FRI 1 m = 51, ρ = 1/4

FRI 2 m = 34, ρ = 1/8

FRI 3 m = 26, ρ = 1/16 Local Evaluation

Elements in F p D

Polynomial size (log 2 )

(a)

FRI 0 m = 102, ρ = 1/2

FRI 1 m = 51, ρ = 1/4

FRI 2 m = 34, ρ = 1/8

FRI 3 m = 26, ρ = 1/16 Local Evaluation

Decryption cost

Polynomial size (log 2 )

(b)

Fig. 6: Estimated cost for the Verifier in HE-FRI (a) in the number of elements in F p D received and (b) in the number of multiplications required to decrypt them.

Prover Performance Once we establish the minimum size for which gains with HE-FRI are possible, our goal becomes minimizing the cost for the prover. Taking, for example, a polynomial of size 2 17 and ρ = 1/2, the RS encoding and the folding algorithm would have depths 18 and 17, respectively in the the original implementation of FRI. Even for a small value of p, let us suppose p = 2 20 , depth (18 + 17) = 35 would require a ciphertext modulus with at the least 20 · 35 = 700 bits. In turn, this modulus would require dimension N = 2 15 , and each ciphertext would weigh at least 7 megabytes (MB). If we consider batched FRI, memory could already be a problem for this size of ciphertext depending on the number of input polynomials. Nonetheless, even in a nonbatched scenario (or one with a small number of polynomials), increasing the ciphertext modulus has typically a quadratic impact on the HE evaluation performance.

In Section 6, we showed how to solve this problem with a series of optimizations that enable to run FRI with significantly smaller, fixed depth. In principle, we could evaluate FRI at depth only 1, but decreasing depth comes at the expense of increasing the total number of operations. Considering this, we address several trade-offs between depth, performance, and memory use enabled by our techniques. We present several options of depth that should suit most applications, but choosing among them is ultimately an application-dependent choice.

For the Folding, as we discussed in Section 6, minimizing depth to 1 only increases complexity from O(2 n ) to O(2 n log 2 n ), preserving the overall complexity of FRI. In practice, this increment is also negligible for the prover as the cost of the folding is dominated by the number of executions of the repacking, which remains linear in the input size. Therefore, for practical purposes, we always implement folding with depth 1 and focus our efforts on the trade-offs enabled by the shallow NTT during the RS encoding phase.

<!-- page 39 -->

Reed-Solomon code encoding Increasing arity is a standard way of enabling shallower NTT circuits. Finding the optimal arity, however, depends both on the general goal as well as on the adopted cost model. For HE-FRI, while we want to minimize depth, we only use multiplications by constants, a procedure in which performance is linear in the depth. Therefore, we model the cost of our NTT as the number of multiplications weighted according to the depth in which they occur in the algorithm. Specifically, a multiplication at depth k ′ has cost (k − k ′ ), where k is the total depth of HE-FRI. Notice that operations happening at a higher depth are considered linearly less expensive, as the ciphertext levels were already consumed by operations from shallower levels.

Number of Operations Expected cost

Depth

(a) NTT for an input of size 2 18

Depth 2 Depth 3 Depth 4 Depth 6 Depth n

Expected cost

Polynomial size (log 2 )

(b) Optimal expected cost

Fig. 7: Expected cost of our NTT implementation.

Figure 7-a shows the results for an NTT with an input of size 2 18 . For each value of maximum depth, we choose arity to minimize the expected cost (even if it would increase the number of operations). While the cost decreases quickly with the depth at first, it stabilizes with depth as low as just 6. Based on this, we selected a few different values for the maximum depth and extended this analysis to different sizes of polynomials. Figure 7-b shows the results as well as the estimated cost for a standard depth-n (radix-2) NTT, using the same cost model. This second result explains depth 6 as a stability point for the cost since it reaches essentially the same performance level provided by the depth-n NTT.

Complete results

F

This section presents the complete practical results. Execution times for the verifier are an average of 100 executions.

<!-- page 40 -->

Table 5: Results for batches of 4096 polynomials, for up to 32 threads.

FRI 3

Polynomial Size (log 2 )

Prover (s)

Verifier (ms)

λ

FRI 0

Memory (GB)

Memory (GB)

Prover (s)

Verifier (ms)

λ

Table 6: Results for batches of 8192 polynomials, for up to 32 threads.

FRI 3

Polynomial Size (log 2 )

Prover (s)

Verifier (ms)

λ

FRI 0

Memory (GB)

Memory (GB)

Prover (s)

Verifier (ms)

λ