Verifiable Homomorphic Encryption

The multigroup setting — One scheme to rule them all

The author thanks Chris Curry and Unsplash for the image

Introduction

Homomorphic Encryption (HE) allows computations on encrypted messages without decryption. While a fully HE scheme supporting arbitrary computations was an open problem, Gentry’s breakthrough led to significant progress, including the development of BFV and CKKS. HE is suitable for cloud-based environments, as it supports secure computation without the data owner’s presence.

However, standard HE has limitations in situations involving more than one user, such as the multiparty setting. In the case of multiple data sources, using a single-key HE leads to an authority concentration issue, as one party gains access to all data. Multiparty HE (MPHE) and multikey HE (MKHE) are examples of schemes that overcome this limitation by distributing the decryption authority among multiple parties, thus protecting the privacy of data owners.

One major drawback of implementing HE schemes in cloud-based environments is the absence of any guarantees for clients regarding the accuracy of computations carried out by the cloud. Although there are typically service-level agreements between clients and clouds, some clients may require more reliable assurances and error-detection capabilities to guard against untrustworthy cloud providers who could quickly introduce errors in their sensitive data and applications. For instance, in machine learning setups assisted by cloud computing, a malicious cloud provider may quickly introduce a backdoor while training a model for a security-sensitive application, such as malware detection, or return an incorrect prediction that could lead to a misdiagnosis in a medical application.

We focus on a recent primitive called multigroup HE (MGHE) introduced which offers interaction and flexibility advantages. MGHE is a generalized variant of HE for multiple parties that combines the best of MPHE and MKHE. An MGHE scheme enables a group of parties to collaboratively generate a public key that can be commonly used among the parties for encryption, thus behaving like an MPHE scheme within a single group. Additionally, MGHE supports arbitrary computations over encrypted data, regardless of whether the input ciphertexts are encrypted under the same group key or not, making it similar to MKHE.

Although verifiable computation techniques, including those proposed by Bünz, and others, can be used to verify the integrity of outsourced computations, integrating them with the complex structure of HE schemes remains a challenge. This is particularly true for popular HE schemes such as BFV, which operate over a large polynomial structure that is often incompatible with verifiable computation techniques.

Only a limited number of studies have explored the verification of computations performed on homomorphically encrypted data. Fiore et al. developed a solution utilizing homomorphic message authentication codes to verify computations on ciphertexts, focusing on quadratic functions over a particular variant of the BV scheme. Other subsequent works involve compressing the ciphertexts and generating proofs of correct computation using succinct non-interactive arguments of knowledge (SNARKs). Recently, Ganesh et al. proposed a new ring-based SNARK that is more compatible with lattice-based HE schemes.

The previous studies were limited to specific HE schemes and lacked essential functionalities such as relinearization, rotations, and bootstrapping, rendering them theoretical and impractical for many applications. To address these limitations, we propose a solution for verifying outsourced computations based on the works of Chatel and Gennaro. Unlike the SNARK-based approaches that prioritize efficient verification and succinctness, our primary goal is to provide versatility for homomorphic computations with reasonable costs for both clients and the cloud.

Those interested in the technical details, and a friendlier notation, are kindly invited to read the paper containing our proposal: Verifiable encodings in multigroup fully homomorphic encryption, available in the Cryptology ePrint Archive (paper 2023/365).

Basic concepts

Taxonomy of homomorphic schemes in terms of users

It is well-known that homomorphic encryption schemes can be classified in terms of the operations admitted. With this point of view, one talks about somewhat, levelled or fully homomorphic schemes. Within each of these categories one can also classify schemes in terms of users, involved keys and how the former and the latter relate. In this direction, one can talk about:

Single-user schemes: these are the most familiar schemes, where each user holds its public, secret and evaluation keys and uses them to communicate with a server in charge of performing computations.

Multiparty schemes: in a multiparty scheme one finds a group of individuals collaborating to the generation of a common public key from their individual keys. In this case, each user holds their own secret key.

Multikey schemes: in a multikey scheme one finds a group of users which send encrypted messages, to be computed by a server, using their own public key. As in the previous kinds of schemes, each user also holds their own private key.

Multigroup schemes: this is the most general scenario, where we find different groups of users encrypting messages using a group public key generated in each group using each public key.

Labelled programs

A labelled program is a tuple which consists of a circuit f along with a distinct input label τi for each input wire.

Given some labelled programs P1, …, Pt and a circuit g, one can define the composed program, denoted by P* = g(P1, …, Pt), which corresponds to evaluating g on the outputs of P1, …, Pt. The labelled inputs of the composed program P* are just all the distinct labelled inputs of P1, …, Pt, meaning that one collects all the input wires with the same label and converts them into a single input wire.

One defines the identity program with label τ as Id(τ):= (gid; τ) where gid is the canonical identity circuit and τ is some label. Notice that any labelled program can be written as a composition of identity programs.

Gadget decompositions

Gadget decompositions are conventionally used in homomorphic encryption to manage the noise growth from homomorphic operations such as the product. The purpose of this technique is to represent an arbitrary element as a linear combination of the entries of a fixed vector (the gadget vector) with small coefficients.

The gadget decomposition technique is widely used in the construction of HE schemes. For example, the homomorphic evaluation of a nonlinear circuit is based on the key-switching technique. Most homomorphic schemes exploit various gadget decomposition methods to control noise growth.

Formally, let g ∈ ℤᵈ be a vector, Q an integer and let R = ℤ[X]/(X^N + 1) for a degree N >0. A gadget decomposition, with gadget vector g, is a function g’ from R_Q to Rᵈ which transforms an element a ∈ R_Q into a d-dimensional vector u ∈ Rᵈ of small polynomials such that a = ⟨g’, u⟩ mod q for ⟨ , ⟩ the usual inner product. Observe that we are only writing as a linear combination of g.

A classical example of gadget decomposition is binary decomposition, where the gadget vector is given by g = (1, 2, 2², 2³, …, 2ᵈ) for some d > 0.

Verifiable encodings

Our approach is inspired by the proposal Veritas and the use of homomorphic authenticators started by Gennaro and Wichs. Here one will use an authenticator called replication encoding which can be described, informally, as follows: for each input message, one generates an extended vector a random half of which is filled with challenge values whereas the other half is filled with copies of the original message. This extended vector is then encrypted and offloaded to the server. The server will not be able to decide which parts are copies and which parts are challenges, therefore it will impossible for it to tamper with computations without being detected.

Description of protocol

Let F be a variable length pseudorandom function (PRF) and let H be a collision-resistant hash function (CRHF). The following 5 algorithms define the replication encoding authenticator:

KeyGen: given a power-of-2 security parameter 𝛌, this algorithm sets up a PRF F and a CRHF H achieving at least 𝛌-security. It also generates the evaluation and encryption keys.

SetGen: this algorithm generates a challenge set S ⊂ {1, …, 𝛌} such that |S| = 𝛌 / 2. Since we deal with scenarios involving several users, SetGen will be a kind of multiparty scheme involving each participant in the computations.

Auth: for an input vector m with identifier 𝛕, it proceeds sequentially for each component. It initialises an empty vector M. For the ith component of m, it creates an extended vector Mi where each of its components is either the ith component of m or a challenge value created using the label 𝛕 and an element j belonging to S. It also sets a value 𝛖 = F(𝛕). The extended vector is appended to M. Finally, the algorithm returns the pair (Enc(M), 𝛖).

Eval: consider n inputs, represented by the vector of authentications 𝛔* such that 𝛔*[k] = (ctk, 𝛖k), for all of its components. For a function f, it computes ct’ by evaluating homomorphically the corresponding circuit on inputs (ct1, …, ctn). A hash tree fH is used to ensure that the server has used the appropriate identifiers for all the inputs of the program. A value 𝛖’ = fH(𝛖1, …, 𝛖n) is set with fH the circuit replacing all gates in f by the CRHF H.

Ver: this algorithm takes a labelled program P = (f, 𝛕1, …, 𝛕n). It proceeds sequentially:

1. Offline precomputes the challenge values using both the identifier and the PRF and evaluates the function f on them.
2. It computes the value 𝛖k = F(𝛕k) for 1 ≤ k ≤ n. Then it computes the value 𝛖* = fH(𝛖1, …, 𝛖n). If 𝛖* ≄ 𝛖’, it outputs 0.
3. It decrypts the ciphertext c’ to the plaintext vector M*. It checks for all slots in the challenge set S that the output matches the pre-computed challenge. If not, it outputs 0.
4. Finally, it ensures that all other slots evaluate to the same value m’. If not, it outputs 0.
5. If all the above passes, it outputs 1.

Verifiable multigroup schemes

Multigroup homomorphic encryption (MGHE) is a cryptographic scheme that was introduced by Kwak et al. It extends the concepts of multiparty and multikey homomorphic encryption and is designed to support several parties. The scheme enables a group of parties to collaboratively generate a public key, which can be used for encryption, thus resembling a multiparty scheme. Furthermore, it allows computations to be performed on encrypted data, even when the input ciphertexts were encrypted under different keys, similar to a multikey scheme. Consequently, multigroup homomorphic encryption offers the benefits of both primitives. In this section, we will introduce a variation allowing subsequent verification.

Setting

Let N be the RLWE dimension, that is the degree of the modular polynomial in the polynomial ring R = ℤ[x] / (x^N + 1). Let P be the plaintext space modulus and Q the ciphertext space modulus. Let Q’ be an integer coprime with Q and such that Q · Q’ = Q*. Let 𝝌 be the key distribution over R and 𝝈 > 0 an error parameter. We sample a random vector a ← U(RdQ) and take two homomorphic gadget decompositions, namely h: RQ → Rk and h*: RQ* → Rk* with respective gadget vectors g ∈ Rk and g* ∈ Rk*.

Key generation

Encryption key

It receives as parameters the vector pp. Each party Pi sets the secret and the encryption keys as follows:

1. For the secret key, Pi samples si, ← 𝛘 and sets the secret key as ski = si.
2. For the individual encryption key, Pi takes e_{0,i} ← D(𝛔) and computes bi = — s_i · a + e_{0,i} (mod Q) and sets the individual encryption key as the pair ek_i = (bi[0], a[0]).

Public key

It receives as parameters a secret key s_i, and a vector a. Each party P_i sets the public key pki = (bi, v_{0,i}, v_{1,i}, v_{2,i}) by running the following algorithm:

1. Sample ri ← 𝛘, e_{1,i} ← D(𝛔) and let v_{2,i} = — ri · a + si · ⌊(P/Q’) · g*⌉ + e_{1,i} (mod Q).
2. Sample v_{1,i} ← U(RQ^k), e_{2,i} ← D(𝛔) and let v{0,i} = — si · v_{1,i} — ri · g + e_{2,i} (mod Q).

Joint key

For the joint key generation, given a group of parties I, the joint public key jpk for I is given by the tuple jpk = (b, v0, v1, v2) where: b = 𝚺i∈I bi , v0 = 𝚺i∈I v0,i, v1 = 𝚺i∈I v1,i, v2 = 𝚺i∈I v2,i. Concerning the joint encryption key of group I, it is given by jek = (b[0], a[0]).

Challenge set generation

In our proposal for verification in more general settings, it will not be possible for the participants to set their own challenge set since in the verification stage different challenge sets may lead to different verification results. Therefore participants will be required to set a common challenge set to be able to verify the results obtained from the server.

There exist several ways to define the mechanism, for example using a scheme similar to secret sharing could be a good option. Nevertheless, one will use the fact that public keys for the homomorphic encryption scheme are created right before the generation of the challenge set to use these keys to send encrypted shares of the final challenge set from each user to the rest of the users.

Informally speaking, each participant will create a share of the set, and send it encrypted; then each participant will decrypt their associated shares and join them to generate the set. A first attempt of the mechanism, MPBFV.Challenge(Si, {pkj}j≠i ), follows:

1. Each participant Pi defines a share Si ∈ {0, 1}* such that |Si| = λ/2. This is done by coin-flipping. Here λ is a security parameter.
2. Each participant Pi encrypts Si with all other participant’s public keys and broadcasts the vector {(Enc(Si, ekj), ekj)}j≠i. Observe that the vector is composed of pair components in order to make identification easier.
3. Each participant decrypts their corresponding share of the challenge set S from the list of broadcasted vectors.
4. Each participant defines the challenge set as S = [Σi Si]2.

Authentication

One follows the replication algorithm described in the veritas proposal with a minor change with respect to the original proposal: each participant computes the challenge values using the whole label τ instead of its components τ[i]. To be precise, this means

1. When veritas’ authors compute mij = F(τi, j), one will take τi as the vector identifying the ith input message mi, instead of as the component of a vector τ.
2. When veritas’ authors compute 𝛖i = F(τi), one will also take τi as the vector identifying the ith input message mi, instead of as the component of a vector τ.

Evaluation

This mechanism does not change with respect to the veritas proposal except for the obvious requirement of using MGHE.Add or MGHE.Mult as needed.

In this stage, we use the procedure by Kim et al. for an RNS-friendly multikey product combined with relinearization, having in mind that the indices do not describe keys from individual users, but joint public keys generated by groups of users.

Mind the change of notation between the above scheme and our notation: (b, v0, v1, v2) ⟺ (𝛽j, 𝜐_{0,j}, 𝜐_{1,j}, 𝜐_{2,j}).

Verification

The verification process is composed of two steps: an offline phase where each participant precomputes the challenge values according to function f, and an online stage where a distributed decryption mechanism is used. For the latter one has ct = (c0, …, cn) a multigroup ciphertext corresponding to an ordered set of groups (I1, …, In) and an error parameter 𝛔’ > 0, now:

1. Each participant i ∈ Ij sample ei’ ← D(𝛔’) and broadcast 𝛍j,i = cj · si + e’i (mod Q).
2. Each participant can compute 𝛍j = 𝚺i 𝛍_{j,i} (mod Q).
3. The merging operation is 𝛍 = c0 + 𝚺j 𝛍j (mod Q).
4. Finally, one can decrypt m = ⌊(P/Q) · 𝛍⌉ (mod P).

Once the message has been decrypted, participants run the verification algorithm from Veritas keeping in mind the changes with respect to the original Veritas, introduced above: participants will precompute the challenge sets as rkj = F(τk, j) for τk a vector and not a component.

Conclusion

At IOV Labs we have adopted the recent construction MGHE from Lim et al. to generate a verifiable variation built upon the ideas from Chatel. We also adapted the work from Kwak et al. to improve the efficiency of the most expensive operations, namely the product and the relinearization algorithms. Furthermore, we have constructed a version that avoids requiring the common reference setting, bypassing a possible decrease in terms of security.

We want to finish this article by pointing out that MGHE is such a plastic construction that one can derive from its equivalent constructions for verifiable MKHE and MPHE by considering the number of parties and groups involved in the computations. Indeed, if we consider that there is only one group of users, the construction introduced in this research becomes a verifiable MPHE; on the other hand, if consider the existence of several groups of users composed of one participant in each case, then what one gets is a verifiable MKHE scheme.

It remains as a future research line the implementation of the algorithms and the ideas developed at IOV Labs, which will bring to the table a benchmarking supporting the affirmation that these algorithms attain a high level of efficiency and execution time.

References

Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G. (2018). Bulletproofs: Short Proofs for Confidential Transactions and More, 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 2018, pp. 315–334.

Ganesh, C., Nitulescu, A., Soria-Vazquez, E. (2021). Rinocchio: SNARKs for Ring Arithmetic. Cryptology ePrint Archive, Paper 2021/322.

Chatel, S., Knabenhans, C., Pyrgelis, A., Hubaux, J-P. Verifiable Encodings for Secure Homomorphic Analytics. arXiv:2207.14071v1 [cs.CR].

Gennaro, R., Wichs, D.. Fully Homomorphic Message Authenticators, Cryptology ePrint Archive, Paper 2012/290

Kwak, H., Lee, D., Song, Y., Wagh, S. A Unified Framework of Homomorphic Encryption for Multiple Parties with Non-Interactive Setup, Cryptology ePrint Archive, Paper 2021/1412

Kim, T., Kwak, H., Lee, D., Seo, J., Song, Y. Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition, Cryptology ePrint Archive, Paper 2022/347.