# README
MHE
The MHE package implements several Multiparty Homomorphic Encryption (MHE) primitives based on Ring-Learning-with-Errors (RLWE).
It provides generic interfaces for the local steps of the MHE-based Secure Multiparty Computation (MHE-MPC) protocol that are common across all the RLWE distributed schemes implemented in lattigo (e.g., collective key generation).
The mhe/heinteger
and mhe/hefloat
packages import mhe
and provide scheme-specific functionalities (e.g., interactive bootstrapping).
This package implements local operations only, hence does not assume or provide any network-layer protocol implementation.
However, it provides serialization methods for all relevant structures that implement the standard encoding.BinaryMarshaller
and encoding.BinaryUnmarshaller
interfaces (see https://pkg.go.dev/encoding) as well as the io.WriterTo
and io.ReaderFrom
interfaces (see https://pkg.go.dev/encoding).
The MHE-MPC protocol implemented in the library is based on the constructions described in "Multiparty Homomorphic Encryption from Ring-Learning-with-Errors" by Mouchet et al. (2021), which is an RLWE instantiation of the MPC protocol described in "Multiparty computation with low communication, computation and interaction via threshold FHE" by Asharov et al. (2012).
MHE-MPC Protocol Overview
The protocol enables a group of N input parties to compute a joint function over their private inputs under encryption and to provide a receiver party with the result. The protocol is generic and covers several system- and adversary-models:
Peer-to-peer vs Cloud-assisted models. The parties can execute the protocol in a peer-to-peer way or receive assistance from a third-party server (which is also considered an adversary).
Internal vs External receivers. Receiver parties are the intended recipients of the computation result and can be either internal or external depending or whether they are or not input parties themselves, respectively. This distinction is important in practice, because external receivers do not need to be online (and even to be known) during the setup phase.
Anytrust vs Full-threshold Access-structure. As for many MPC protocols, the assumption on the worst-case number of corrupted parties can be mapped in the cryptographic access-control mechanism (the access structure). The implemented MHE-MPC protocol is "anytrust" (N-out-of-N-threshold) by default, but can be relaxed to any positive threshold t-out-of-N (see Threshold Secret-Key Generation).
Passive vs Active Adversaries. The implemented MHE-MPC protocol is secure against passive adversaries, and can in theory be extended to active security by requiring the parties to produce proofs that their shares are correctly computed for every round. Note that those proofs are not implemented in this library.
An execution of the MHE-based MPC protocol has two phases: the Setup phase and the Evaluation phase, each of which comprises a number of sub-protocols as depicted below (the details of each protocols are provided later).
- Setup Phase
- Secret Keys Generation
- [if t < N] Threshold Secret-Key Generation
- Collective Public Encryption-Key Generation
- Collective Public Evaluation-Key Generation
- Relinearization-Key
- Galois-Keys
- Generic Evaluation-Keys
- Evaluation Phase
- Input (Encryption)
- Circuit Evaluation
- Output phase (Decryption)
- Collective Key-Switching
- Local Decryption
MHE-MPC Protocol Steps Description
This section provides a description for each sub-protocol of the MHE-MPC protocol and provides pointers to the relevant types and methods.
This description is a first draft and will evolve in the future.
For concrete code examples, see the example/mhe
folders.
For a more formal exposition, see "Multiparty Homomorphic Encryption from Ring-Learning-with-Errors" and An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption.
The system model is abstracted by considering that the parties have access to a common public authenticated channel. In the cloud-assisted setting, this public channel can be the helper cloud-server. In the peer-to-peer setting, it could be a public broadcast channel. We also assume that parties can communicate over private authenticated channels.
Several protocols require the parties to have access to common uniformly random polynomials (CRP), which are sampled from a common random string (CRS).
This CRS is implemented as an interface type mhe.CRS
that can be read by the parties as a part of the protocols (see below).
The mhe.CRS
can be implemented by a utils.KeyedPRNG
type for which all parties use the same key.
1. Setup
In this phase, the parties generate the various keys that are required by the Evaluation phase. Similarly to LSSS-based MPC protocols such as SPDZ, the setup phase does not depend on the input and can be pre-computed. However, unlike LSSS-based MPC, the setup produces public-keys that can be re-used for an arbitrary number of evaluation phases.
1.i Secret Keys Generation
The parties generate their individual secret-keys locally by using a rlwe.KeyGenerator
; this provides them with a rlwe.SecretKey
type.
See rlwe/keygenerator.go for further information on key-generation.
The ideal secret-key is implicitly defined as the sum of all secret-keys. Hence, this secret-key enforces an N-out-N access structure which requires all the parties to collaborate in a ciphertext decryption and thus tolerates N-1 dishonest parties.
1.ii [if t < N] Threshold Secret-Key Generation
For settings where an N-out-N access structure is too restrictive (e.g., from an availability point of view), an optional Threshold Secret-Key Generation Protocol can be run to enable t-out-of-N access-structures (hence tolerating t-1 dishonest parties). The idea of this protocol is to apply Shamir Secret Sharing to the ideal secret-key in such a way that any group of t parties can reconstruct it. This is achieved by a single-round protocol where each party applies Shamir Secret-Sharing to its own share of the ideal secret-key.
We assume that each party is associated with a distinct mhe.ShamirPublicPoint
that is known to the other parties.
This protocol is implemented by the mhe.Thresholdizer
type and its steps are the following:
- Each party generates a
mhe.ShamirPolynomial
by using theThresholdizer.GenShamirPolynomial
method, then generates a share of typemhe.ShamirSecretShare
for each of the other parties'ShamirPublicPoint
by using theThresholdizer.GenShamirSecretShare
. - Each party privately sends the respective
ShamirSecretShare
to each of the other parties. - Each party aggregates all the
ShamirSecretShare
s it received using theThresholdizer.AggregateShares
method.
Each party stores its aggregated ShamirSecretShare
for later use.
1.iii Public Key Generation
The parties execute the collective public encryption-key generation protocol to obtain an encryption-key for the ideal secret-key.
The protocol is implemented by the mhe.PublicKeyGenProtocol
type and its steps are as follows:
- Each party samples a common random polynomial (
mhe.PublicKeyGenCRP
) from the CRS by using thePublicKeyGenProtocol.SampleCRP
method. - [if t < N] Each party uses the
mhe.Combiner.GenAdditiveShare
to obtain a t-out-of-t sharing and uses the result as its secret-key in the next step. - Each party generates a share (
mhe.PublicKeyGenShare
) from the CRP and their secret-key, by using thePublicKeyGenProtocol.GenShare
method. - Each party discloses its share over the public channel. The shares are aggregated with the
PublicKeyGenProtocol.AggregateShares
method. - Each party can derive the public encryption-key (
rlwe.PublicKey
) by using thePublicKeyGenProtocol.GenPublicKey
method.
After the execution of this protocol, the parties have access to the collective public encryption-key, hence can provide their inputs to computations.
1.iv Evaluation-Key Generation
In order to evaluate circuits on the collectively-encrypted inputs, the parties must generate the evaluation-keys that correspond to the operations they wish to support.
The generation of a relinearization-key, which enables compact homomorphic multiplication, is described below (see mhe.RelinearizationKeyGenProtocol
).
Additionally, and given that the circuit requires it, the parties can generate evaluation-keys to support rotations and other kinds of Galois automorphisms (see mhe.GaloisKeyGenProtocol
below).
Finally, it is possible to generate generic evaluation-keys to homomorphically re-encrypt a ciphertext from a secret-key to another (see mhe.EvaluationKeyGenProtocol
).
1.iv.a Relinearization Key
This protocol provides the parties with a public relinearization-key (rlwe.RelinearizationKey
) for the ideal secret-key. This public-key enables compact multiplications in RLWE schemes. Out of the described protocols in this package, this is the only two-round protocol.
The protocol is implemented by the mhe.RelinearizationKeyGenProtocol
type and its steps are as follows:
- Each party samples a common random polynomial matrix (
mhe.RelinearizationKeyGenCRP
) from the CRS by using theRelinearizationKeyGenProtocol.SampleCRP
method. - [if t < N] Each party uses the
mhe.Combiner.GenAdditiveShare
to obtain a t-out-of-t sharing and use the result as their secret-key in the next steps. - Each party generates a share (
mhe.RelinearizationKeyGenShare
) for the first protocol round by using theRelinearizationKeyGenProtocol.GenShareRoundOne
method. This method also provides the party with an ephemeral secret-key (rlwe.SecretKey
), which is required for the second round. - Each party discloses its share for the first round over the public channel. The shares are aggregated with the
RelinearizationKeyGenProtocol.AggregateShares
method. - Each party generates a share (also a
mhe.RelinearizationKeyGenShare
) for the second protocol round by using theRelinearizationKeyGenProtocol.GenShareRoundTwo
method. - Each party discloses its share for the second round over the public channel. The shares are aggregated with the
RelinearizationKeyGenProtocol.AggregateShares
method. - Each party can derive the public relinearization-key (
rlwe.RelinearizationKey
) by using theRelinearizationKeyGenProtocol.GenRelinearizationKey
method.
1.iv.b Galois Keys
This protocol provides the parties with a public Galois-key (stored as rlwe.GaloisKey
types) for the ideal secret-key. One Galois-key enables one specific Galois automorphism on the ciphertexts' slots. The protocol can be repeated to generate the keys for multiple automorphisms.
The protocol is implemented by the mhe.GaloisKeyGenProtocol
type and its steps are as follows:
- Each party samples a common random polynomial matrix (
mhe.GaloisKeyGenCRP
) from the CRS by using theGaloisKeyGenProtocol.SampleCRP
method. - [if t < N] Each party uses the
mhe.Combiner.GenAdditiveShare
to obtain a t-out-of-t sharing and uses the result as its secret-key in the next step. - Each party generates a share (
mhe.GaloisKeyGenShare
) by usingGaloisKeyGenProtocol.GenShare
. - Each party discloses its
mhe.GaloisKeyGenShare
over the public channel. The shares are aggregated with theGaloisKeyGenProtocol.AggregateShares
method. - Each party can derive the public Galois-key (
rlwe.GaloisKey
) from the finalGaloisKeyGenShare
by using theGaloisKeyGenProtocol.AggregateShares
method.
1.iv.c Other Evaluation Keys
This protocol provides the parties with a generic public Evaluation-key (stored as rlwe.EvaluationKey
types) for the ideal secret-key. One Evaluation-key enables one specific public re-encryption from one key to another.
The protocol is implemented by the mhe.EvaluationKeyGenProtocol
type and its steps are as follows:
- Each party samples a common random polynomial matrix (
mhe.EvaluationKeyGenCRP
) from the CRS by using theEvaluationKeyGenProtocol.SampleCRP
method. - [if t < N] Each party uses the
mhe.Combiner.GenAdditiveShare
to obtain a t-out-of-t sharing and uses the result as its secret-key in the next step. - Each party generates a share (
mhe.EvaluationKeyGenShare
) by usingEvaluationKeyGenProtocol.GenShare
. - Each party discloses its
mhe.EvaluationKeyGenShare
over the public channel. The shares are aggregated with theEvaluationKeyGenProtocol.AggregateShares
method. - Each party can derive the public Evaluation-key (
rlwe.EvaluationKey
) from the finalEvaluationKeyGenShare
by using theEvaluationKeyGenProtocol.AggregateShares
method.
2 Evaluation Phase
2.i Input step (Encryption Phase)
The parties provide their inputs for the computation during the Input Phase.
They use the collective encryption-key generated during the Setup Phase to encrypt their inputs, and send them through the public channel.
Since the collective encryption-key is a valid RLWE public encryption-key, it can be used directly with the single-party scheme.
Hence, the parties can use the Encoder
and Encryptor
interfaces of the desired encryption scheme (see heint.Encoder, hefloat.Encoder and rlwe.Encryptor).
2.ii Circuit Evaluation step
The computation of the desired function is performed homomorphically during the Evaluation Phase. The step can be performed by the parties themselves or can be outsourced to a cloud-server. Since the ciphertexts in the multiparty schemes are valid ciphertexts for the single-party ones, the homomorphic operation of the latter can be used directly (see heint.Evaluator and hefloat.Evaluator).
2.iii Output step
The receiver(s) obtain their outputs through the final Output Phase, whose aim is to decrypt the ciphertexts resulting from the Evaluation Phase. It is a two-step process with an optional pre-processing step when using the t-out-of-N access structure. In the first step, Collective Key-Switching, the parties re-encrypt the desired ciphertext under the receiver's secret-key. The second step is the local decryption of this re-encrypted ciphertext by the receiver.
2.iii.a Collective Key-Switching
The parties perform a re-encryption of the desired ciphertext(s) from being encrypted under the ideal secret-key to being encrypted under the receiver's secret-key. There are two instantiations of the Collective Key-Switching protocol:
- Collective Key-Switching (KeySwitch), implemented as the
mhe.KeySwitchProtocol
interface: it enables the parties to switch from their ideal secret-key s to another ideal secret-key s' when s' is collectively known by the parties. In the case where s' = 0, this is equivalent to a collective decryption protocol that can be used when the receiver is one of the input-parties. - Collective Public-Key Switching (PublicKeySwitch), implemented as the
mhe.PublicKeySwitchProtocol
interface, enables parties to switch from their ideal secret-key s to an arbitrary key s' when provided with a public encryption-key for s'. Hence, this enables key-switching to a secret-key that is not known to the input parties, which enables external receivers.
While both protocol variants have slightly different local operations, their steps are the same:
- Each party generates a share (of type
mhe.KeySwitchShare
ormhe.PublicKeySwitchShare
) with themhe.(Public)KeySwitchProtocol.GenShare
method. This requires its own secret-key (arlwe.SecretKey
) as well as the destination key: its own share of the destination key (arlwe.SecretKey
) in KeySwitch or the destination public-key (arlwe.PublicKey
) in PublicKeySwitch. - Each party discloses its
mhe.KeySwitchShare
over the public channel. The shares are aggregated with the(Public)KeySwitchProtocol.AggregateShares
method. - From the aggregated
mhe.KeySwitchShare
, any party can derive the ciphertext re-encrypted under s' by using the(Public)KeySwitchProtocol.KeySwitch
method.
2.iii.b Decryption
Once the receivers have obtained the ciphertext re-encrypted under their respective keys, they can use the usual decryption algorithm of the single-party scheme to obtain the plaintext result (see rlwe.Decryptor.
References
- Multiparty Homomorphic Encryption from Ring-Learning-With-Errors (https://eprint.iacr.org/2020/304)
- An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption (https://eprint.iacr.org/2022/780)