Cryptography underpins many of the technologies we use every day, from secure messaging apps to online banking. In particular, Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKPs) represent some of the most exciting advancements in cryptography, enabling private computations on encrypted data and privacy-preserving verification, respectively.

In this blog post, we’ll dive into these concepts and show you how to build a simple LWE-based encryption system, perform homomorphic addition on encrypted data, and verify it using zero-knowledge proofs (ZKPs)—all in Rust using the Plonky2 library.

This is a good first step toward grasping verifiable FHE and how it works. In future posts, we'll deal with more complex ciphertext types to prove and verify.

Let’s get started.

Introduction To FHE

FHE allows computations to be performed directly on encrypted data without decryption. This is an incredibly powerful concept because it means sensitive data can remain encrypted while still being useful for operations like adding and multiplying, or more complex functions.

For example, consider a scenario where you want a cloud service to compute something on your private data. Normally, you would need to decrypt the data, perform the computation, and then re-encrypt it. With FHE, you can simply send the encrypted data to the service, and it will perform the computation without ever decrypting it. The result of this operation will also be encrypted, and only you (with the secret key) can decrypt the final result.

Some use cases of FHE include:

• Financial privacy: Banks can process encrypted transactions without ever seeing the plaintext amounts.
• Medical research: Researchers can analyze encrypted medical data without compromising patient privacy.
• Secure voting systems: Votes can be tallied while maintaining the confidentiality of individual votes.

What Is Learning-With-Errors (LWE)?

FHE is built upon hard mathematical problems, one of which is Learning With Errors (LWE), a fundamental cryptographic primitive that ensures the security of FHE schemes.

The main idea behind LWE is to add a small amount of "noise" (error) to a system of linear equations, making it computationally infeasible for an attacker to solve the system and recover the original values.

Imagine you knew the recipe for a secret sauce and didn’t want to give it away. You could give someone the recipe but with small errors deliberately introduced, making it impossible for them to reconstruct the original recipe, even though they had all the ingredients. This is a little but like how LWE works.

Here are the components of an LWE-based encryption system:

1. Secret key: A vector that represents the secret used to encrypt data.

2. Plaintext: The message we want to encrypt (in our case, simple binary values like 0 or 1).

3. Random vector: A randomly generated vector used to "hide" the secret key during encryption.

4. Error term: Noise added to make it difficult for an attacker to reverse the encryption and recover the plaintext.

The strength of LWE encryption comes from the difficulty of solving systems of equations with these added noise terms.

LWE Encryption

Given a message mmm (e.g., a bit 0 or 1), the encrypted ciphertext is computed as follows:

$$ b = a \cdot s + e + m \cdot \frac{q}{2} $$

where;

• $a \cdot s$ is the inner product between the random vector $a$ and the secret key $s$.
• $e$ is the small noise.
• $m$ is the plaintext message (either 0 or 1).
• $q$ is a large modulus, and $q/2$​ scales the message so it fits within the LWE system.

Introduction To ZKPs

ZKPs are cryptographic protocols that allow one party (the "prover") to convince another party (the "verifier") that a certain statement is true, without revealing any additional information beyond the fact that the statement is true.

For instance, with ZKPs, you could prove that you know the solution to a puzzle without showing how to solve the puzzle itself. This is extremely useful in blockchain applications, secure communications, and any system where privacy is critical.

In this blog post, we will use Plonky2, a ZKP library, to prove that our LWE-based homomorphic operations were performed correctly without ever revealing the secret key or plaintext.

Building an LWE-Based Encryption and Homomorphic Addition System in Rust

Let’s now build an LWE-based encryption system in Rust, demonstrate homomorphic addition of ciphertexts, and verify the operation using a ZKP with Plonky2. Instead of providing a ready-made code snippet, we will build this step by step.

Step 1: Setting Up Dependencies

First, we need to import the necessary libraries. We will use the Plonky2 library for the zero-knowledge circuit generation and rand for generating random numbers (for secret keys and encryption parameters).

use anyhow::Result;
use plonky2::field::types::Field;
use plonky2::iop::witness::{PartialWitness, WitnessWrite};
use plonky2::plonk::circuit_builder::CircuitBuilder;
use plonky2::plonk::circuit_data::CircuitConfig;
use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
use rand::random;

- anyhow::Result: General-purpose error handling.

- Plonky2: Provides tools to create and manage ZKP circuits.

- rand: Used to generate random numbers for our secret keys and vectors.

Step 2: Defining the Secret Key and Random Vectors

In this step, we define the secret key and two random vectors (a1 and a2) that will be used for encryption. The secret key is the core part of the encryption process.

fn main() -> Result<()> {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;

    // Generate random secret_key, a1, and a2 vectors
    let secret_key: [F; 3] = [F::from_canonical_u64(random::<u64>()), F::from_canonical_u64(random::<u64>()), F::from_canonical_u64(random::<u64>())];
    let a1: [F; 3] = [F::from_canonical_u64(random::<u64>()), F::from_canonical_u64(random::<u64>()), F::from_canonical_u64(random::<u64>())];
    let a2: [F; 3] = [F::from_canonical_u64(random::<u64>()), F::from_canonical_u64(random::<u64>()), F::from_canonical_u64(random::<u64>())];
}

- secret_key: This is a three-dimensional vector that acts as the private key for encryption.

- a1 and a2: These are random vectors that will help in creating the LWE ciphertexts. In a real-world implementation, these vectors would be much larger for enhanced security.

Step 3: Defining LWE Parameters

Now, we define some key LWE parameters, such as the plaintext messages and the noise terms.

let m1 = F::from_canonical_u64(1); // Encrypt bit 1
let m2 = F::from_canonical_u64(0); // Encrypt bit 0
let e1 = F::from_canonical_u64(38);
let e2 = F::from_canonical_u64(133);

let q = F::from_canonical_u64(18446744069414584320);
let q_half = q / F::TWO;

- m1 and m2: These are the bits we want to encrypt (in this case, 1 and 0).

- e1 and e2: The error terms (noise) added to the ciphertexts for security.

- q and q_half: A large modulus value to ensure values stay within a finite field, commonly used in cryptographic operations.

Step 4: Constructing LWE Ciphertexts

Next, we create the LWE ciphertexts by combining the secret key, random vectors, and noise terms.

let b1 = inner_product(&a1, &secret_key) + e1 + m1 * q_half;
let b2 = inner_product(&a2, &secret_key) + e2 + m2 * q_half;

- b1 and b2: These are the encrypted ciphertexts corresponding to the plaintexts `m1` and `m2`.

Here, the ciphertexts are generated by taking the inner product of the random vectors (`a1` and `a2`) and the secret key, adding the noise (`e1` and `e2`), and embedding the plaintext message (`m1` and `m2`) scaled by `q_half`.

Step 5: Performing Homomorphic Ciphertext Addition

With two ciphertexts created, we can now add them homomorphically. This operation allows us to sum encrypted values without needing to decrypt them first.

let a3: Vec<F> = a1.iter().zip(a2.iter()).map(|(&a1i, &a2i)| a1i + a2i).collect();
let b3 = b1 + b2;

- a3: This is the element-wise sum of the two random vectors `a1` and `a2`.

- b3: This is the sum of the ciphertexts `b1` and `b2`.

By adding the ciphertexts, we get a new ciphertext that, when decrypted, will reveal the sum of the original plaintexts (`m1 + m2`).

Step 6: Building a Zero-Knowledge Circuit With Plonky2

To verify that our homomorphic operation was performed correctly, we use Plonky2 to create a zero-knowledge proof circuit.

let config = CircuitConfig::standard_recursion_config();
let mut builder = CircuitBuilder::<F, D>::new(config);

In this step, we define the ZKP circuit configuration. This will allow us to verify that the homomorphic addition was done correctly without exposing the plaintexts or the secret key.

Step 7: Verifying the Homomorphic Operation in ZKP

Finally, we generate and verify the ZKP.

let data = builder.build::<C>();
let proof = data.prove(pw)?;

println!("Final LWE ciphertext sum (a3, b3) is: ({:?}, {})", a3, b3);
data.verify(proof)?;
Ok(())

- proof: We generate a proof showing that the ciphertext addition is correct.

- verify: This step checks that the proof is valid, ensuring the integrity of the homomorphic addition.

Conclusion

In this blog post, we built an LWE-based encryption system from the ground up, performed homomorphic addition on ciphertexts, and used a zero-knowledge proof to verify that the operation was correct—all while maintaining the privacy of the original plaintexts and secret key.

The combination of FHE and ZKPs opens up new possibilities for secure and private computing. Whether you're working on privacy-preserving cloud computation, financial transactions, or secure voting systems, these tools are essential for building secure and private systems in the modern digital world.

Also notice that this blog post and the code snippets in it are for educational purposes only and are not recommended for use at the product level. For the full code: https://github.com/furkanakal/Verifiable-FHE/tree/main/LWE