Part 9: MPC Decryption in fhEVMs | Building Blocks of FHE

In this part of our series on TFHE (Fully Homomorphic Encryption over the Torus), we explore the concept of MPC (Multi-Party Computation) decryption within the TFHE framework. 

TFHE is a powerful encryption scheme that allows computations to be performed on encrypted data without needing to decrypt it first, thus preserving data privacy. In MPC, several parties collaborate to compute a function over their inputs while keeping those inputs private. This article will dive into how TFHE can be combined with MPC to achieve secure decryption. We will cover the Shamir Secret Sharing scheme, the steps for decryption, reconstruction, and key properties, providing an in-depth understanding through examples and theoretical explanations. 

Additionally, we will discuss the threshold protocol in fhEVM (Fully Homomorphic Encryption Enabled Ethereum Virtual Machine), which is crucial for achieving robust and secure multi-party computations in practical applications.

Shamir Secret Sharing

Shamir's Secret Sharing is a cryptographic algorithm developed by Adi Shamir in 1979. It is used to split a secret, such as a cryptographic key, into multiple parts, or shares, so that the secret can only be reconstructed when a sufficient number of shares are combined together. 

The basic idea behind Shamir's Secret Sharing is to use polynomial interpolation. A secret is encoded as the constant term of a polynomial of degree $ k-1 $, where $ k $ is the minimum number of shares needed to reconstruct the secret.

Secret Sharing Process

1. Define the Secret and Parameters: Let the secret be $ S $ (a number). Choose two parameters:

   - $ n $: the total number of shares to create.

   - $ k $: the minimum number of shares needed to reconstruct the secret.

2. Generate a Polynomial: Construct a random polynomial $ P(x) $ of degree $ k-1 $ such that:

   $$ P(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_{k-1} x^{k-1} $$

   Here, $ a_0 = S $ is the secret, and $ a_1, a_2, \ldots, a_{k-1} $ are randomly chosen coefficients.

3. Create Shares: Generate $ n $ shares. For each $ i $ (where $ 1 \leq i \leq n $), compute:

  $$  \text{Share}_i = (i, P(i)) $$

   Each share is a pair $(x_i, y_i)$.

4. Distribute Shares: Give each participant one share.

Reconstruction

1. Collect $ k $ Shares: To reconstruct the secret, collect at least $ k $ shares, $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$.

2. Lagrange Interpolation: Use Lagrange interpolation to reconstruct the polynomial $ P(x) $. The formula for Lagrange interpolation is:

   $$ P(x) = \sum_{j=1}^{k} y_j \prod_{\substack{1 \leq m \leq k
m \ne j}} \frac{x - x_m}{x_j - x_m} $$

3. Find the Secret: The secret $ S $ is the constant term $ a_0 $ of the polynomial $ P(x) $, which can be found by evaluating $ P(0) $.

Properties

Fundamental properties of the SSS are:

- Threshold Scheme: The scheme is called a $(k, n)$ threshold scheme because any $ k $ out of $ n $ shares can reconstruct the secret, but $ k-1 $ or fewer shares cannot.

- Perfect Security: If fewer than $ k $ shares are known, no information about the secret can be determined.

Example

Let's say the secret $ S $ is 1234, $ n = 5 $ shares are to be created, and $ k = 3 $ shares are needed to reconstruct the secret.

1. Polynomial Generation: Choose a random polynomial $ P(x) = 1234 + 166x + 94x^2 $.

2. Shares Creation: Compute shares:

   - $ P(1) = 1234 + 166(1) + 94(1^2) = 1494 $ → Share 1: (1, 1494)

   - $ P(2) = 1234 + 166(2) + 94(2^2) = 1912 $ → Share 2: (2, 1912)

   - $ P(3) = 1234 + 166(3) + 94(3^2) = 2488 $ → Share 3: (3, 2488)

   - $ P(4) = 1234 + 166(4) + 94(4^2) = 3222 $ → Share 4: (4, 3222)

   - $ P(5) = 1234 + 166(5) + 94(5^2) = 4114 $ → Share 5: (5, 4114)

3. Reconstruction with 3 Shares: Collect shares (1, 1494), (2, 1912), and (3, 2488). Use Lagrange interpolation to find the polynomial and evaluate $ P(0) $ to retrieve the secret $ S = 1234 $.

Shamir's Secret Sharing is widely used in cryptographic applications to secure sensitive information and ensure it can be safely reconstructed when needed.

Shamir Sharing over $ \mathbb{Z}_Q $

Key Components

1. Finite Field Elements:

   - The elements are denoted as $ \gamma_i $, where $ i $ ranges from 1 to $ n $. Each player $ P_i $ is associated with a unique $ \gamma_i $.

2. Polynomial Construction:

   - For secret $ a $ in $ \mathbb{Z}_Q $, a polynomial $ g_a(X) $ of degree at most $ t $ is generated such that $ g_a(0) = a $.

3. Share Distribution:

   - The shares are computed as $ [a]_{\langle t, Q \rangle}_i = g_a(\gamma_i) $.

Secret Sharing Scheme:

1. Sharing:

   - A polynomial $ g_a(X) $ is generated with degree at most $ t $ where $ g_a(0) = a $.

   - Shares are computed as $ [a]_{\langle t, Q \rangle}_i = g_a(\gamma_i) $.

2. Opening:

   - To reconstruct the secret, the players compute the polynomial $ g_a(X) $ using their shares.

   - The polynomial is reconstructed as:

     $$ g_a(X) = \sum_i [a]_{\langle t, Q \rangle}_i \cdot \delta_i(X) $$

     where $ \delta_i(X) $ is a Lagrange polynomial.

   - The secret is then $ g_a(0) $, assuming no inconsistencies or errors.

Linearity

The scheme is linear, meaning given secret shares $ [a]_{\langle t, Q \rangle} $ and $ [b]_{\langle t, Q \rangle} $, it is possible to compute the shares of $ \alpha a + \beta b + \gamma $ without additional interaction among the players. This is done by:

$$  [\alpha \cdot a + \beta \cdot b + \gamma]_{\langle t, Q \rangle}_i = \alpha \cdot [a]_{\langle t, Q \rangle}_i + \beta \cdot [b]_{\langle t, Q \rangle}_i + \gamma $$

Summary

- Share(a): Generate a polynomial $ g_a(X) $ such that $ g_a(0) = a $. Compute 

shares as $ [a]_{\langle t, Q \rangle}_i = g_a(\gamma_i) $.

- Open([a]_{\langle t, Q \rangle}_1, \ldots, [a]_{\langle t, Q \rangle}_n): Reconstruct the polynomial $ g_a(X) $ and obtain the secret as $ g_a(0) $.

This method ensures both the privacy of the secret when fewer than $ t+1 $ shares are available and allows efficient reconstruction and manipulation of the shares.

Threshold Protocol in fhEVMs

We use a linear secret sharing scheme (CDD$^+$93) with respect to a modulus $ Q $ and a corruption threshold $ t < n $. The notation for a value $ a \in \mathbb{Z}_Q $ as being secret shared across a set of $ n $ parties such that more than $ t $ parties are required to reconstruct the original value is:

$$ [a]^{\langle t, Q \rangle} = ([a]_1^{\langle t, Q \rangle}, \ldots, [a]_n^{\langle t, Q \rangle}) $$

where each party $ P_i $ has their corresponding share $ [a]_i^{\langle t, Q \rangle} $.

Due to the linearity of the secret sharing scheme, given two secret shares $ [a]^{\langle t, Q \rangle} $ and $ [b]^{\langle t, Q \rangle} $, producing a secret sharing value of $ \alpha a + \beta b + \delta $ for any $ \alpha, \beta, \delta \in \mathbb{Z}_Q $ can be done without interaction, i.e., each $ P_i $ computes:

$$ [\alpha a + \beta b + \delta]_i^{\langle t, Q \rangle} \leftarrow \alpha [a]_i^{\langle t, Q \rangle} + \beta [b]_i^{\langle t, Q \rangle} + \delta $$

The same rule applies for the dot product operation $ \langle \cdot, \cdot \rangle $ where one of the terms is public as it is a linear operation.

Recall that a TFHE ciphertext is of the form $ (\vec{a}, b) \in \mathbb{Z}_q^l \times \mathbb{Z}_q $ with ciphertext modulus $ q $, where

$$ b = \langle \vec{a}, \vec{s} \rangle + \Delta \cdot m + e \mod q $$

which encrypts a message $ m \in \mathbb{Z}_p $ ($ \Delta = \frac{q}{p} $).

In order to mask the noise $ e $, we apply the operation Switch-$n$-Squash(c). This operation converts $ c = (\vec{a}, b) $ to another $ c' = (\vec{a'}, b') \in \mathbb{Z}_{q'}^l \times \mathbb{Z}_{q'} $, encrypting the same plaintext $ m $:

$$ b' = \langle \vec{a'}, \vec{s'} \rangle + \Delta' \cdot m + e' \mod q' $$

with $ \vec{a'} \in \{0, 1, 2, 3\}^l $ and $ \Delta' = \frac{q'}{p} $.

In the threshold setting, the secret key $ \vec{s'} $ is secret shared modulo $ Q $ across a set of $ n $ parties with a threshold $ t < n $ as $ [\vec{s'}]^{\langle t, Q \rangle} $.

More precisely, every bit of the secret key $ s_j \in \vec{s'} $ is secret shared separately, so each party's share $ [\vec{s'}]_i^{\langle t, Q \rangle} $ is a vector of $ L $ separate shares of the bits of $ \vec{s'} $.

The individual bits' shares are computed by evaluating for each bit $ s_j' \in [L] $ a random polynomial $ F_j $ of degree $ t $ that has its zero-degree coefficient equal to $ s_j' $; i.e., $ F_j(0) = s_j' \in \mathbb{Z}_Q $ for all $ j \in \{1, \ldots, L\} $.

When a ciphertext $ c = (\vec{a}, b) \in (\mathbb{Z}_q^l \times \mathbb{Z}_q) $ is input to be decrypted, the parties first apply $ c' \leftarrow \text{Switch-n-Squash}(c) $ to get $ c' = (\vec{a'}, b') \in (\mathbb{Z}_Q^L \times \mathbb{Z}_Q) $ and then the parties jointly generate a secret shared noise term $ [E]^{\langle t, Q \rangle} $. Each party $ P_i $ computes a partial decryption

$$ \text{PDec}_i(c') = b' - \langle \vec{a'}, [\vec{s'}]^{\langle t, Q \rangle}_i \rangle + [E]^{\langle t, Q \rangle}_i = [e' + E + \Delta' \cdot m]^{\langle t, Q \rangle}_i $$

where $ e $ is the error present in the encryption.

The variable $ [E]^{\langle t, Q \rangle} $ is used to statistically mask $ e $ in order to avoid leaking information about the secret key $ s $; see [DDE$^+$23] for more details. Note that the generation of $ [E]^{\langle t, Q \rangle} $ can be deferred into an input-independent (pre-processing) phase since it does not depend on the input ciphertext $ (a, b) $.

Combining more than $ t $ valid $ \text{PDec}_i(c') $ values allows us to reconstruct the contained message $ m $ in the clear. The $\text{Switch-n-Squash}(c)$ procedure takes approximately 300 ms while the computation of $\text{PDec}_i(c')$ and the reconstruction of $ m $ can be done in approximately 2 ms in a setting with $ n = 4 $ parties and threshold $ t = 3 $ according to [DDE$^+$23].

This final part of the series explains the detailed process of secret sharing and the steps involved in MPC decryption within the TFHE framework. It emphasizes the secure computation of partial decryptions and how the collaborative effort of multiple parties ensures the decryption of encrypted data while preserving confidentiality. This intricate mechanism combines polynomial secret sharing with advanced cryptographic operations to maintain data security and integrity throughout the decryption process.

Conclusion

Throughout the series, we have covered the essentials of fully homomorphic encryption by discussing lattice-based cryptography, learning-with-error problems, Gentry’s famous work, BFV/BGV, CKKS, TFHE schemes; and finally decryption in fhEVMs.

I hope this series of articles were useful for all of you. Thanks for reading!

Subscribe to our newsletter

Top industry insights on FHE.

By clicking Sign Up you're confirming that you agree with our Terms and Conditions.
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.